Number of groupings possible from a set

[jenocean74]

I need to calculate the number of grouping combinations possible from a set. For example, starting with a set of three elements I can create:

One group of one: XXX
One group of two: XX X or X XX (the same; order does not matter)
One group of three: X X X

= A total of 3 possibilities

For a set of four elements:

One group of one: XXXX
Two groups of twos: XX XX and X XXX (again, order does not matter; X XXX is the equivalent to XXX X)
One group of three: XX X X
One group of four: X X X X

= A total of 5 possibilities.

Is there a general solution to this problem such that I can calculate a value for larger data sets (i.e. n=100)?

Many, many thanks!

Jennifer

 

[galactus]

Re: Number of groups

For the 4 elements, I think you missed two of them.

XXXX,
XX XX,
X XX X
XX X X
XX XX,
X X X X,
X XXX

There are 7.

Did you try the formula \(\displaystyle 2^{n-1}-1\)?.

Try the 5 element and see if you get 15 of them.

 

[jenocean74]

Thanks for the reply!

If I were counting the permutations, then I believe that the equation you suggested would be correct. However, I was not counting permutations, so for example XX X X is equivalent to X XX X is equivalent to X X XX. After collapsing the “equivalents” I still arrive at a count of five for a set of 4. For the set of 5, I come up with a total of seven:

XXXXX

X XXXX
XX XXX

X X XXX
X XX XX

X X X XX

X X X X X

Jennifer

 

[pka]

You are quite right about this. This is well known problem. It is usually called partitions of an integer.
The solution is not trivial, it takes a chapter in Niven’s book, MATHEMATICS OF CHOICE.

I will give you the recursive function that leads to the solution.
This can be programmed.
\(\displaystyle P(n,k) = \left\{ {\begin{array}{ll} 1 & {k = 1} \\ {P(n,k - 1) + P(n,k - 1)} & {1 < k < n} \\ {1 + P(n,n - 1)} & {k = n} \\ \end{array} } \right.\)

The answer to your question is the value \(\displaystyle P(n,n)\).
For example: \(\displaystyle P(50,50)=204226\).
That is the number of partitions of a 50 into “groups” such as you listed for four: \(\displaystyle P(4,4)=5\).

 

[galactus]

Thanks for that as well, pka. I have never seen that before. Interesting. I apparently misunderstood the question.

 

[jenocean74]

Thanks so much for the assist! I got my hands on Niven’s book; it’s a good one!

If I could take it up one more level…now that I have the total number of combinations for any value, could you suggest an approach to look at the frequency of the integers that are used?

For the example of p(5) = 7 the breakout of solutions are:

5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1

The frequencies of the integers are:

f(5) = 1
f(4) = 1
f(3) = 2
f(2) = 4
f(1) = 12

From what I can uncover, is Ewen’s sampling formula seems appropriate to make this calculation? See http://en.wikipedia.org/wiki/Ewens's_sampling_formula. If so, is anyone aware of a straight-forward way to program this?

Kind regards,
Jennifer