Answer to Question #272682 in Discrete Mathematics for Asif

Question

2.      Describe at least one way to generate all the partitions of a positive integer n. (You can get idea from Exercise 49 in Section 5.3.)

Answer 1

Partition of an integer is the representation of the positive integer n as a collection of positive integers.

Denote w(n) to be the number of ways of representing a positive integer n without considering the order of the integer. For a given integer n the number of partitions w(n) can be determined in a number of ways. Consider the given expression:

 $w(n)=\frac{1}{n} \sum_{k=1}^{n} a(k) m(n-k)$

which includes the addition of divisors of integer n and taking w(0)=1.0

a(k) denotes the addition of divisors of $k \cdot$ Suppose $\left(w 1^{r 1}\right)\left(w 2^{r 2}\right) \ldots\left(w t^{r}\right)$ are the prime factorization of k, the addition of divisors of k is given by the expression:

 $\mathrm{a}(k)=\prod_{j=1}^{t} \frac{w j^{i j+1}-1}{w j-1}$

The sequence w(n) can be computed by using the given formula recursively:

 $\mathrm{w}(n)=\sum(-1)^{(k-1)} \mathrm{w}\left(n-k \frac{(3 k \pm 1)}{2}\right)$

where, addition is calculated over all k in a way that $\frac{k(3 k \pm 1)}{2}$ lies between the values 1 ton.

Euler's generating function given by:

$\frac{1}{(1-x)\left(1-x^{2}\right)\left(1-x^{3}\right) \ldots}=1+w(1) x+w(2) x^{2}+w(3) x^{3}+\ldots$  

can be induced to cover the disjoint sets into any (and all possible) sets of integers. For each preferable summand $\mathrm{s}$ , in denominator arrange a multiple of $\left(1-x^{s}\right)$ . For example, the generating function for the partitions of n into primes is

 $\frac{1}{\left(1-x^{2}\right)\left(1-x^{3}\right)\left(1-x^{5}\right)\left(1-x^{7}\right)\left(1-x^{11}\right) \ldots}=1+0 x+1 x^{2}+1 x^{3}+1 x^{4}+2 x^{5}+2 x^{6}+3 x^{7}+\ldots$