# Thread: Divide N balls to subgroups

1. ## Divide N balls to subgroups

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!

2. 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.
Each time I get a different way of seeing it.
So I am not really sure what it is asking.

I think you can use Stirling numbers of either the first or second kind.
Stirling Number of the Second Kind -- from Wolfram MathWorld
Stirling Number of the First Kind -- from Wolfram MathWorld

Once you look into that, perhaps you could clarify your question.

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