# Two hard number partition problems

For every positive integer $n$, let $p(n)$ denote the number of ways to express $n$ as a sum of positive integers. For instance, $p(4)=5$. Also define $p(0)=1.$

Problem 1. Prove that $p(n)-p(n-1)$ is the number of ways to express $n$ as a sum of integers each of which is strictly greater than $1$.

Problem 2. Prove that the total number of components in all partitions of $n$ is equal to $\displaystyle\sum_{k=0}^{n-1}p(k)\cdot \tau(n-k)$, where $\tau(m)=\sum_{d|m} 1$ is the number of positive divisors of $m$.

I came up with a solution for first problem, but I'm not sure if everything is OK with it, so I would be very grateful if you tell me what I should correct here:

Let $p_k(n)$ denote number of ways to express $n$ as a sum of exactly $k$ positive integers. So $p_k(n)=\left|\left\{ \langle a_1,...,a_k \rangle : \sum_{i=1}^k a_i=n \wedge 1\le a_i\le a_{i+1} \text{ for } 1\le i\le k-1 \right\}\right|$. It's quite easy to observe that $p_k(n)=p_{k-1}(n-1)+p_k(n-k)$ by dividing above set into two disjoint sets:

-set of tuples $\langle 1,...,a_k \rangle$

-set of tuples $\langle a_1,...,a_k \rangle$, where $a_1>1$

So let's count $p(n)-p(n-1)$ knowing that $p(n)=\sum_{k=1}^n p_k(n)$.

$$p(n)-p(n-1)=p_n(n)+\sum_{k=1}^{n-1}p_k(n)-p_k(n-1)=\\=1+\sum_{k=1}^{n-1}p_{k-1}(n-1)+p_k(n-k)-p_k(n-1)=\\=1+ p_0(n-1)+p_1(n-1)-p_1(n-1)+p_1(n-1)+p_2(n-2)-p_2(n-1)+\dots+p_{n-3}(n-1)+p_{n-2}(2)-p_{n-2}(n-1)+p_{n-2}(n-1)+p_{n-1}(1)-p_{n-1}(n-1)=\\=1+0-p_{n-1}(n-1)+\sum_{k=1}^{n-1}p_k(n-k)=\sum_{k=1}^{n-1}p_k(n-k)$$

On the other hand, let $r(n)$ be number of partitions that we are looking for: $r(n)=\left| \left\{ \langle a_1,...,a_k \rangle : 1\le k\le n-1, \ \sum_{i=1}^k a_i=n \wedge 2\le a_i\le a_{i+1} \text{ for } 1\le i\le k-1 \right\} \right|$

and for a given $k$:

$r_k(n)=\left| \left\{ \langle a_1,...,a_k \rangle : \sum_{i=1}^k a_i=n \wedge 2\le a_i\le a_{i+1} \text{ for } 1\le i\le k-1 \right\} \right|$ is a number of partitions that we are looking for but consisting only of $k$ integers.

Since there is a simple bijection between tuples $\langle a_1,...,a_k \rangle \leftrightarrow \langle a_1-1,...,a_k-1 \rangle$, where $2\le a_i\le a_{i+1}$ for $1\le i\le k-1$ and still $1\le a_i-1$, then $\sum_{i=1}^k(a_i-1)=n-k$ and tuple $\langle a_1-1,...,a_k-1 \rangle$ is some partition of $n-k$. So $r_k(n)=p_k(n-k)$.

Hence cases $r_k(n)$ are pairwise disjoint for $1\le k\le n-1$, it follows that: $\displaystyle r(n)=\sum_{k=1}^{n-1}r_k(n)=\sum_{k=1}^{n-1}p_k(n-k)=p(n)-p(n-1)$ as desired.

Is that correct?

I don't know how to approach second problem. Too hard it seems to be.

-
For the first part, just seperate the set of partitions that include the value $1$ and the partitions that do no. then show that the set of partitions of $n$ that include a $1$ are in $1-1$ correspondence with the partitions of $n-1$. –  Thomas Andrews Aug 8 '12 at 15:27
Not that it particularly matters to the problem, but $$4=1+1+1+1=1+1+2=1+2+1=2+1+1=3+1=1+3=2+2,$$ so $p(4)=7$. –  Cameron Buie Aug 8 '12 at 15:31
@ThomasAndrews, so my proof isn't correct? –  ray Aug 8 '12 at 15:32
@CameronBuie, order of elements in partition doesn't count. $p(4)=5$, because $4=1+1+1+1=2+2=1+3=1+1+2$. –  ray Aug 8 '12 at 15:33
@ray I was trying to give you an easier way to handle part (1). I haven't gotten around to reading your argument. –  Thomas Andrews Aug 8 '12 at 15:35

Generating function proofs

The trick is to note the generating function for $p(n)$ satisfies this nice formula:

$$P(x)=\sum_{n=0}^\infty p(n)x^n = \prod_{m=1}^\infty \frac{1}{1-x^m}$$

Proving that is a counting argument, noting that $\frac{1}{1-x^m}=\sum_{j=0}^\infty x^{jm}$

By the same reasoning, if $q(n)$ is the number of partitions of $n$ with all values greater than $1$, then:

$$\sum_{n=0}^\infty q(n)x^n = \prod_{m=2}^\infty \frac{1}{1-x^m} = (1-x)P(x)$$

Then you get, by equating coefficients, that $q(n)=p(n)-p(n-1)$.

The second problem is a bit harder. Let $p(k,n)$ be the number of partitions of $n$ into exactly $k$ positive numbers.

The number you are looking for is:

$$\sum_{k=1}^n kp(k,n)$$

We can write a new generating function for $p(k,n)$ as:

$$F(x,y) = \sum_{n=0}^\infty \sum_{k=0}^\infty p(k,n)x^ny^k$$

By the same counting argument as before, we get the result:

$$F(x,y) = \prod_{m=1}^\infty \frac{1}{1-x^my}$$

Now, differentiate both sides with respect to $y$, we get:

$$\sum_{n=0}^\infty\sum_{k=0}^\infty kp(k,n)x^ny^{k-1} = \frac{dF}{dy} = F(x,y) \sum_{m=1}^\infty \frac{x^m}{1-x^my}$$

Now we are going to evaluate both sides at $y=1$. The left side at $(x,1)$ evaluates to:

$$\sum_{n=0}^\infty x^n \sum_{k=1}^n kp(k,n)$$

So the coefficient of $x^n$ is the sum that we wanted above.

On the other hand, on the right hand side, $\frac{x^m}{1-x^m}$ contributes a coefficient of $1$ for $x^n$ if $m|n$ and zero otherwise, so $$\sum_{m=1}^\infty \frac{x^m}{1-x^m} = \sum_{n=1}^\infty \tau(n)x^n$$

Notice also that $F(x,1)=P(x)=\sum p(n)x^n$.

So $$F(x,1)\sum_m \frac{x^m}{1-x^m} = P(x)\sum_m \tau(m) x^m$$

But the coefficient of $x^n$ in that multiplication is exactly what we want:

$$\sum_{k=0}^n p(k)\tau(n-k)$$

We can eliminate $k=n$ since $\tau(0)=0$, so we get the result.

There is almost certainly a direct counting argument in here, I'm just not sure what it is...

-
Note, I skipped how to do the derivative of the infinite product, which was just a generalization of the product rule for derivatives. –  Thomas Andrews Aug 8 '12 at 17:19
I've also skipped the counting arguments that use the product formula. The trick is to realize that a partition is determined by the number of $1$s, $2$s, $3$s, etc. –  Thomas Andrews Aug 8 '12 at 17:22
everything is clear, thank you very much! –  ray Aug 8 '12 at 17:52
See my answer for a direct counting argument of the second problem. –  Marc van Leeuwen Aug 16 '12 at 12:31

I think your solution to the first problem is unnecessarily complicated.

The number of ways to express $n$ as a sum of integers, each of which is strictly greater than 1, is equal to the (the number of ways to express $n$ as a sum of integers, each of which is at least 1) minus (the number of ways to express $n$ as a sum of integers, at least one of which is equal to 1). By definition, the first number is $p(n)$. To find the second number, note that we can restrict one of the numbers to be 1, and we must then find the number of ways express $n-1$ as a sum of positive integers, which is by definition $p(n-1)$. Thus the number of ways to express $n$ as a sum of integers, each of which is strictly greater than 1, is equal to $p(n) - p(n-1)$.

-
Oops, sorry, I misspoke. Edited. Thanks! –  K. Hu Aug 8 '12 at 17:21
You still have an extra "strictly greater than one." Currently, you have the expression: $X=X-Z$ when you mean $X=Y-Z$. –  Thomas Andrews Aug 8 '12 at 17:24
Haha oops. Thanks! –  K. Hu Aug 8 '12 at 17:37

A very simple solution to the first part is to realize there is a simple bijection between the sums of integers equal to $(n-1)$, and the sums of integers (with at least a one) equal to $n$. Just add a one, or remove one.

$$\begin{array}{ll} 5=1+1+1+1+1 & 4=1+1+1+1\\ 5=1+1+1+2 & 4=1+1+2\\ 5=1+1+3 & 4=1+3\\ 5=1+2+2 & 4=2+2\\ 5=1+4& 4=4\\ 5=3+2\\ 5=5\\ \end{array}$$

-

Since a simple counting argument for the first problem was already given in various answers, I'll focus on a counting for the second problem:

Prove that the total number of components in all partitions of $n$ is equal to $\sum_{k=0}^{n-1}p(k)\cdot \tau(n-k)$, where $\tau(m)=\sum_{d|m} 1$ is the number of positive divisors of $m$.

Writing each partition with its parts sorted by size (for a unique reresentation), the total number of components in all partitions of $n$ is equal to the number of such sequences with one of the parts marked (say by underlining it). The given summation counts the number of pairs $(\mu,d)$ where $\mu$ is (a sorted list of parts representing) a parition of some number $k<n$, and $d$ is some divisor of $n-k$. Now from $(\mu,d)$ one can construct a parition $\lambda$ of $n$ with one of its parts marked by starting with $\mu$ and adding $\frac{n-k}d$ copies of $d$ after any existing parts $d$ in $\mu$, marking the first of the copies of $d$ that were added. The reverse operation consists of taking $\lambda$, recording the marked part as $d$, and removing it along with any further occurrences of $d$ in $\lambda$ after the marked one. It is easily checked that the maps $(\mu,d)\leftrightarrow(\lambda,\textit{marking})$ are inverses of one another.

-