Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
show 10 more comments

4 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.