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.

Let $p_k(n)$ be a number of ways to express $n$ as a sum of $k$ positive integers. For example $p_2(3)=1$.

Problem 1. Prove that following recurrences are correct:

$p_k(n)=p_{k-1}(n-1)+p_k(n-k)$

$p_k(n)=p_k(n-k)+p_{k-1}(n-k) + ... + p_1(n-k)$

Problem 2. Find $p_2(n)$ and $p_3(n)$.

Unfortunately I was always weak in showing recurrences and I have no idea for 1. I tried to use Ferrers diagrams to see sth but I haven't seen anything. For 2 it is easy to observe that $p_2(n)=\lfloor n/2 \rfloor$ and using first recurrence, that I failed to prove, I got $\displaystyle p_3(n)=\sum_{k=0}^{\lceil n/2 \rceil-1} \left\lfloor\frac{n-3k-1}{2}\right\rfloor$ but I don't know if it's possible to simplify this sum. Maybe some combinatorial interpretation, with Ferrers diagrams for example, will lead to more explicit form for $p_3(n)$?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

For Problem 1:

a) Either you have a part that's $1$, then the remaining parts can be any partition of $n-1$ into $k-1$ parts, or you don't, then you can subtract $1$ from all $k$ parts and are left with a partition of $n-k$ into $k$ parts.

b) Subtract $1$ from every part; then you have $n-k$ left, in anything from $1$ to $k$ parts.

share|improve this answer
    
brilliant, thank you very much. that gives me some ideas for other problems I try to solve. –  ray Aug 8 '12 at 10:22
    
@ray: You're welcome! –  joriki Aug 8 '12 at 10:23
    
Actually point b) fails for $k=n$; then the only applicable partition of $n$ leaves a partition of $0$ into no parts at all. –  Marc van Leeuwen Sep 2 '12 at 10:26
    
@Marc: True -- so we should add a term $p_0(n-k)$ to the sum, which would be $0$ for $k\ne n$ and $1$ for $k=n$? –  joriki Sep 2 '12 at 14:03

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.