Compare number of partitions.

40 Views Asked by At

What is more, partitions of the number $N$ into at most $k$ terms, or partitions of the number $N + k$ into exactly $k$ terms?

We consider partitions that differ only in order to be the same.

Looks like pretty easy combinatorial problem, but I have no idea that should work here.

I tried draw Young tableau, and build some bijections. As I know, there no any formula for finding number of partitions, so I need some more ideas/hints for this problem

1

There are 1 best solutions below

0
On BEST ANSWER

A partition of $N$ into at most $k$ terms is the same as a partition of $N$ into exactly $k$ terms where terms are allowed to be $0$.

Start with one of those partitions, and add $1$ to each term. You now have a partition of $N+k$ into exactly $k$ (strictly positive) terms. This process is easily reversible by subtracting $1$ from each term.

So there is a bijection between the partitions you ask about, and there is therefore an equal number of partitions of either type.