ID: 0811.3479

Counting number of factorizations of a natural number

November 21, 2008

View on ArXiv
Shamik Ghosh
Computer Science
Mathematics
Discrete Mathematics
Number Theory

In this note we describe a new method of counting the number of unordered factorizations of a natural number by means of a generating function and a recurrence relation arising from it, which improves an earlier result in this direction.

Similar papers 1

T. M. A. Fink
Number Theory
Combinatorics

The number of ordered factorizations and the number of recursive divisors are two related arithmetic functions that are recursively defined. But it is hard to construct explicit representations of these functions. Taking advantage of their recursive definition and a geometric interpretation, we derive three closed-form expressions for them both. These expressions shed light on the structure of these functions and their number-theoretic properties. Surprisingly, both functions...

Some results on ordered and unordered factorization of a positive integers

December 1, 2014

87% Match
Daniel Yaqubi, Madjid Mirzavaziri
Combinatorics

As a well-known enumerative problem, the number of solutions of the equation $m=m_1+...+m_k$ with $m_1\leqslant...\leqslant m_k$ in positive integers is $\Pi(m,k)=\sum_{i=0}^k\Pi(m-k,i)$ and $\Pi$ is called the additive partition function. In this paper, we give a recursive formula for the so-called multiplicative partition function $\mu_1(m,k):=$ the number of solutions of the equation $m=m_1... m_k$ with $m_1\leqslant...\leqslant m_k$ in positive integers. In particular, us...

Find SimilarView on arXiv

On Colored Factorizations

August 23, 2020

86% Match
Jacob Sprittulla
Combinatorics

We study the number of factorizations of a positive integer, where the parts of the factorization are of l different colors (or kinds). Recursive or explicit formulas are derived for the case of unordered and ordered, distinct and non-distinct factorizations with at most and exactly l colors.

Find SimilarView on arXiv

Unordered Factorizations with $k$ Parts

July 17, 2019

86% Match
Jacob Sprittulla
Combinatorics

We derive new formulas for the number of unordered (distinct) factorizations with $k$ parts of a positive integer $n$ as sums over the partitions of $k$ and an auxiliary function, the number of partitions of the prime exponents of $n$, where the parts have a specific number of colors. As a consequence, some new relations between partitions, Bell numbers and Stirling number of the second kind are derived. We also derive a recursive formula for the number of unordered factoriza...

Find SimilarView on arXiv

Ordered Factorizations with $k$ Factors

October 16, 2016

86% Match
Jacob Sprittulla
Combinatorics

We give an overview of combinatoric properties of the number of ordered $k$-factorizations $f_k(n,l)$ of an integer, where every factor is greater or equal to $l$. We show that for a large number $k$ of factors, the value of the cumulative sum $F_k(x,l)=\sum\nolimits_{n\leq x} f_k(n,l)$ is a polynomial in $\lfloor \log_l x \rfloor$ and give explicit expressions for the degree and the coefficients of this polynomial. An average order of the number of ordered factorizations for...

Find SimilarView on arXiv

Elementary formulas for integer partitions

April 27, 2010

85% Match
Mohamed El Bachraoui
Number Theory

In this note we will give various exact formulas for functions on integer partitions including the functions $p(n)$ and $p(n,k)$ of the number of partitions of $n$ and the number of such partitions into exactly $k$ parts respectively. For instance, we shall prove that $$ p(n) = \sum_{d|n} \sum_{k=1}^{d} \sum_{i_0 =1}^{\lfloor d/k \rfloor} \sum_{i_1 =i_0}^{\lfloor\frac{d- i_0}{k-1} \rfloor} \sum_{i_2 =i_1}^{\lfloor\frac{d- i_0 - i_1}{k-2} \rfloor} ... \sum_{i_{k-3}=i_{k-4}}^{\...

Find SimilarView on arXiv

An expansion for the number of partitions of an integer

January 21, 2019

85% Match
Stella Brassesco, Arnaud Meyroneinc
Number Theory

We obtain an asymptotic expansion for $p(n)$, the number of partitions of a natural number $n$, starting from a formula that relates its generating function $f(t), t\in (0,1)$ with the characteristic functions of a family of sums of independent random variables indexed by $t$. The expansion consists of a factor (which is the leading term) times an asymptotic series expansion in inverse powers of a quantity that grows as $\sqrt n$ as $n\to \infty$, and whose coefficients are s...

Find SimilarView on arXiv

On the number of factorizations of an integer

September 27, 2016

85% Match
R. Balasubramanian, Priyamvad Srivastav
Number Theory

Let $f(n)$ denote the number of unordered factorizations of a positive integer $n$ into factors larger than $1$. We show that the number of distinct values of $f(n)$, less than or equal to $x$, is at most $\exp \left( C \sqrt{\frac{\log x}{\log \log x}} \left( 1 + o(1) \right) \right)$, where $C=2\pi\sqrt{2/3}$ and $x$ is sufficiently large. This improves upon a previous result of the first author and F. Luca.

Find SimilarView on arXiv

On the Oppenheim's "factorisatio numerorum" function

July 7, 2008

85% Match
Florian Luca, Anirban Mukhopadhyay, Kotyada Srinivas
Number Theory

Let $f(n)$ denote the number of distinct unordered factorisations of the natural number $n$ into factors larger than 1.In this paper, we address some aspects of the function $f(n)$.

Find SimilarView on arXiv

Using GENERATINGFUNCTIONOLOGY to Enumerate Distinct-Multiplicity Partitions

January 19, 2012

84% Match
Doron Zeilberger
Combinatorics

This article, written in fond memory of Herbert Saul Wilf (June 13, 1931- Jan. 7, 2012), explores integer partitions where each part shows up a different number of times than the other parts (if it shows up at least once), thereby making a modest contribution towards the solution of one of the eight intrigiung problems posted by Herb Wilf on his website on Dec. 13, 2010

Find SimilarView on arXiv