3
$\begingroup$

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.

  • 0
    Yes, I have, but no idea how they would help here.2012-08-08

4 Answers 4

6

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...

  • 0
    See my answer for a direct counting argument of the second problem.2012-08-16
3

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 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 to 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)$.

  • 0
    Haha oops. Thanks!2012-08-08
1

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} $

1

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 partition of some number $k, and $d$ is some divisor of $n-k$. Now from $(\mu,d)$ one can construct a partition $\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.