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
    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$.2012-08-08
  • 0
    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$.2012-08-08
  • 0
    @ThomasAndrews, so my proof isn't correct?2012-08-08
  • 0
    @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$.2012-08-08
  • 0
    @ray I was trying to give you an easier way to handle part (1). I haven't gotten around to reading your argument.2012-08-08
  • 0
    Ok, I see it will be much easier, thanks!2012-08-08
  • 0
    Ah! So we are allowing just "$4$" as a sort of "sum of one integer"? I'd originally assumed order wouldn't matter, but only came up with $1+1+1+1$, $1+1+2$, $1+3$, and $2+2$, so I assumed (incorrectly) that you must have been taking order into account. My apologies.2012-08-08
  • 0
    @CameronBuie, I understand. No problem.2012-08-08
  • 0
    @ray From a cursory reading of your proof, it looks like your argument is a verbose proof that essentially is the same as the comment I made above. I haven't checked all the steps.2012-08-08
  • 0
    Is 'verbose' a negative attribute? I tried to write it carefully that is why i took me some space, but I wanted to be formal.2012-08-08
  • 0
    Sometimes "verbose" is better, sometimes it isn't. I think the more direct approach is clearer in this case - I think your proof obscures what is going on, rather than clarifying. But sometimes a "quick" proof is so slick that it can obscure.2012-08-08
  • 0
    Isn't (1) proven just by remarking that $n$ can be written in $p(n-1)$ ways containing a $1$, and then just interpret the subtraction?2012-08-08
  • 0
    @Arthur Yeah, that was my point. Essentially, you are counting the set of partitions of $n$ in two ways, getting $p(n)$ by definition, and $p(n-1)+q(n)$ where $q(n)$ is the number of partitions with every element greater than $1$.2012-08-08
  • 0
    By the way, have you covered generating functions? There is a nice generating function argument for both these problems...2012-08-08
  • 0
    Yes, I have, but no idea how they would help here.2012-08-08

4 Answers 4

4

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
    Note, I skipped how to do the derivative of the infinite product, which was just a generalization of the product rule for derivatives.2012-08-08
  • 0
    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.2012-08-08
  • 0
    everything is clear, thank you very much!2012-08-08
  • 0
    See my answer for a direct counting argument of the second problem.2012-08-16
2

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

  • 0
    Oops, sorry, I misspoke. Edited. Thanks!2012-08-08
  • 0
    You still have an extra "strictly greater than one." Currently, you have the expression: $X=X-Z$ when you mean $X=Y-Z$.2012-08-08
  • 0
    Haha oops. Thanks!2012-08-08
0

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

0

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