Originally Posted by

**guyov1** Hello.

I am trying to prove that the number of options to divide N balls to at most k groups equals the number of options to divide N balls to groups in a way that each group is with at most k balls.

The balls are indistinguishable, no empty groups are allowed and the order of the groups does not matter.

Any idea?

Thanks!

Hi guyov1,

OK, let’s take a definite example. Suppose you have 20 balls and you want to divide them into no more than 5 groups. For example, one way to do the division would be to have groups of size 10, 5, 3, 1, 1. (I’m deliberately listing the groups in order of decreasing size, which is OK because the order of the groups does not matter.) We can visualize the arrangement like this:

Code:

XXXXXXXXXX
XXXXX
XXX
X
X

Now rotate the figure.

Code:

XXXXX
XXX
XXX
XX
XX
X
X
X
X
X

This figure corresponds to a division into 10 groups, of size 5, 3, 3, 2, 2, 1, 1, 1, 1, 1.

The arrangement in the first figure will have no more than 5 groups if and only if the arrangement in the rotated figure has no groups of size larger than 5.

Get the idea?