ount all the ways that 15 objects can be put into four piles so that each pile has a different number of objects in it.

April 20, 2010 12:33 AM

"Count all the ways that 15 objects can be put into four piles so that each pile has a different number of objects in it." Is there a smart general method for solving problems like this? Feel free to assume uniqueness/non-emptiness of the piles if it helps. (Not homework)
posted by onalark to science & nature (18 answers total)

Are the objects the same or different?
posted by delmoi at 12:42 AM on April 20, 2010

delmoi: feel free to assume they are the same or different if it helps you solve the problem. The thing that is killing all of my approaches is that the number in each pile must be different.

My current best approach is:

Start with piles of:
1
2
3
4

Now you have 5 objects remaining, and you can only add to the last pile if you want a unique solution for 11:
1
2
3
5

Now with 4 objects remaining, you may add one to pile #3 or #4...

You could easily enumerate this, but I'm hoping there's something cleaner that I'm not spotting.
posted by onalark at 12:49 AM on April 20, 2010

I think delmoi is asking if the objects are uniquely identifiable.

Here's a simpler example where that would matter:

Lets say I give you 4 indistinguishable objects and ask you to divvy them into two non-empty piles. You could do 3,1, or 2,2 or 1,3 ... so, 3 different ways.

But let's say they are distinguishable objects, labeled A, B, C and D.
You could do ABC,D ABD,C ACD,B BCD,A AB,CD AC,BD CD,AB BD,AC etc.
So, there are a lot more 'ways' to put them into two piles.
posted by blenderfish at 1:09 AM on April 20, 2010

The answer to your example is 432, from brute force enumeration. The question gets a bit tricky, as the numbers in each pile are not independent: The numbers depend on those that came before, both for overlap and the sum to 15. I'm sure there is an easy formula, but unless you know it off the top of your head it is likely easier to just brute force it.
posted by scodger at 1:19 AM on April 20, 2010

blenderfish, I understand delmoi's question. If you would like to assume ABCD or AAAA, I am interested in either solution. I think it is simpler to assume the objects are indistinguishable. Remember that the number in each pile must be different, however.
posted by onalark at 1:19 AM on April 20, 2010

(Including 0 as a number, otherwise it is 144)
posted by scodger at 1:20 AM on April 20, 2010

Crap, 6 and 18 (for zeroes) if you want eg (1,2,3,4) being the same as (4,3,2,1).

Mathematica code:
Select[IntegerPartitions[15, {4}], #[[1]] != #[[2]] != #[[3]] != #[[4]] &
posted by scodger at 1:45 AM on April 20, 2010

This is similar to the old pirates/gold coins problem, where you have pirates trying to distribute 15 coins. Instead of trying to split up the coins, you think of where to place your dividers:

$$$$$$$$$$$$$$$

You can place three dividers to split it into four groups, and there are 15 spots (one before each coin). There are 15 choose 3 = 455 ways to do this. So for example:

|$$$|$$$$$$$|$$$$$

This would be 0 + 3 + 7 + 5.

However, it gets more complicated since your piles are all precious snowflakes. We need to remove the duplicate numbers one by one... I'm not sure how you'd go about it.
posted by yaymukund at 2:09 AM on April 20, 2010

What scodger said. The general solution is ugly and not easy to compute.

If you assume that size-0 piles are not allowed, then you get this recurrence relation:

Let N(OBJ, P, F-SET) be the number of ways to arrange OBJ objects into P differently-sized piles, where F-SET is a set of "forbidden" pile sizes--no pile may have a size that is a member of F. So your puzzle is to find N(15, 4, {}).

Base cases:
N(0, P, F-SET) = 0 (no empty piles allowed)
N(OBJ, 0, F-SET) = 0 (we must use all objects)
N(OBJ, 1, F-SET) = 1 if OBJ is not in F-SET, 0 if it is (if there's only one pile left, all the remaining objects must go there, so there's exactly one way to arrange them; if that size is forbidden, there is no solution)

Recursive case:
N(OBJ, P, F-SET) = 1/P * sum{i = 1 to OBJ, i not in F-SET} N(OBJ - i, P - 1, F-SET union i)
(the 1/P is there to count combinations instead of permutations)

It's that "not in F-SET" condition that makes everything nasty. You can't really simplify that sum with that condition there; any equivalence you might want to establish would have to be true for all possible F-SETs.
posted by equalpants at 2:26 AM on April 20, 2010

To do it without explicit enumeration you can use a recurrence relation:

p[n_, k_] /; n > 0 && k > 0 := p[n - 1, k - 1] + p[n - k, k]
p[1, k_] := KroneckerDelta[k, 1]
p[_, _] := 0
UnevenPartitionsQ[n_, k_] := p[n - Binomial[k, 2], k]

The answer to your question is then UnevenPartitionsQ[15, 4]:

In[49]:= UnevenPartitionsQ[15, 4]

Out[49]= 6

The function p[n, k] is equivalent to Length[IntegerPartitions[n, {k}]].

Useful references:

http://mathworld.wolfram.com/PartitionFunctionQ.html where the relation between UnevenPartitionsQ[n, k] and p[n, k] is described (equation 18).

http://mathworld.wolfram.com/PartitionFunctionP.html where the recurrence relation for p[n, k] is given (equation 55).
posted by hAndrew at 3:02 AM on April 20, 2010

It feels like a greedy recursive problem to me. To solve this I would start with the max I could put in one pile and then enough for all the rest. For for 15 things and 4, I would have:
12 + 3
so ignoring the 12, I have a problem to solve 3 objects, 3 piles. Solve it as everything I can put in 1 and still have enough for all the rest:
(12 +) 1 + 2
so ignoring the 1, I have two objects and two piles. Solve it as everything I can put in 1 and all the rest:
(12 + 1 +) 1 + 1
This is solution number 1. Unfortunately, it doesn't meet your extra constraint, so we will ignore it. *sigh* Move on.
Next:
11 + 4. I solve it as before:
11 + 2 + 2
11 + 2 + 1 + 1 - oh so close. I have to ignore it and move on.
10 + 3 + 1 + 1 - oh so close.
10 + 2 + 2 + 1 - oh so close.
9 + 4 + 1 + 1 - oh so close.
9 + 3 + 2 + 1 - KACHING - write this down - anything else starting with 9 will fail
8 + 5 + 1 + 1 - no
8 + 4 + 2 + 1 - YES
...
In this way, it's not unlike towers of Hanoi in my mind.
posted by plinth at 3:30 AM on April 20, 2010 [1 favorite]

Since each of the four piles has a different number of objects it will be convenient to calculate the number of ordered piles and then multiply by the number of permutations of four objects: 4! = 24.

Start with piles of 4, 3, 2, 1. This makes a total of ten objects, leaving five objects over. To avoid duplicates these five extra objects must be allocated among the four piles so that the addition to the first pile is greater than or equal to the addition to the second pile, which is greater than or equal to the addition to the second pile, and so forth.

The possible divisions are therefore:
5,0,0,0
4,1,0,0
3,2,0,0
3,1,1,0
2,1,1,1

There are five ways to allocate the five extra objects, which means that there are five distinct ordered sets of piles:
9,3,2,1
8,4,2,1
8,5,2,1
8,4,3,1
6,4,3,2

We can permute each of these 5 sets 24 ways, which gives us a total of 120 different arrangements of piles.
posted by Joe in Australia at 4:02 AM on April 20, 2010

Oh yes - if you allow empty piles then start with an ordered set of 3,2,1,0 leaving 9 over, and enumerate the additions as follows:
9,0,0,0
8,1,0,0
7,2,0,0
7,1,1,0
6,3,0,0
6,2,1,0
6,1,1,1
5,4,0,0
5,3,1,0
5,2,1,1
4,4,1,0
4,3,1,1
4,2,2,1
3,3,3,0
3,3,2,1
3,2,2,2

This is sixteen ordered sets of additions, which we multiply by 4! as before to give 384.
posted by Joe in Australia at 4:07 AM on April 20, 2010

Joe, I think you missed 2,2,1,0 giving the sixth solution 6 + 5 + 3 + 1 = 15.
posted by hAndrew at 4:11 AM on April 20, 2010

In the unique-elements case, the values you want are called Stirling numbers of the second kind. There's no nice closed-form for them, but the linked page gives you some recursive definitions.
posted by PMdixon at 4:39 AM on April 20, 2010

Yes, greedy and recursive is the way to go if this is supposed to be an algorithm and N remains small. But I don't know if that meets your "smart" criterion.
posted by DU at 5:39 AM on April 20, 2010

Here's an approach (which might be isomorphic to some of the ways already suggested) which I think reduces it to a simpler problem, but even then I'm not sure how to give a general solution to that one. Perhaps someone else can pick up where I leave off.

Let's count the solutions with non-unique piles, i.e., 1,3,5,6 is considered the same solution as 5,1,6,3. As others have noted above, the number with unique piles is 4! times the number of solutions with non-unique piles. I'm also considering only the problem with identical items.

I'll look at both [zero allowed], and {zero not allowed}. Equations without either brackets or braces apply to both cases.

Consider the numbers A, B, C, D in increasing order as a solution:

[A<B<C<D] {0<A<B<C<D}
A+B+C+D=15

Now, choose a, b, c, and d such that:
A=a
B=a+b
C=a+b+c
D=a+b+c+d

So now we have integers a, b, c, and d such that:
{a>0}
b>0
c>0
d>0

But any of a, b, c, and d may be identical. With our original equation, this gives us:

4a+3b+2c+d=15.

Now, substitute {a'=a-1}, b'=b-1, c'=c-1, and d'=d-1, which gives us

[4a+3b'+2c'+d'=9] {4a'+3b'+2c'+d'=5}

With the only other restriction now being that [a] {a'}, b', c', and d' are non-negative integers. (Any of them may be equal, and zero is allowed for all of them.)

Note that as long as [a] {a'}, b', and c' are such that they do not exceed the given total on their own, it is always possible to choose d' to satisfy the equation. Thus, the number of solutions of the equations above are equal to the number of solutions of:

[4a+3b'+2c'≤9] {4a'+3b'+2c'≤5}

Or, to put it another way, equal to the number of lattice points falling on or within the tetrahedron
[a≥0] {a'≥0}, b'≥0, c'≥0, [4a+3b'+2c'≤9] {4a'+3b'+2c'≤5}

Which are easy enough to enumerate by brute force in the case at hand ([18] or {6} as already noted), but I don't know if there's a general solution to that question that's any easier than the recursive solutions that have already been suggested.
posted by DevilsAdvocate at 11:42 AM on April 20, 2010

Also worth noting, "N items among P piles, different number in each pile, zero items in a pile allowed" is equivalent to "N+P items among P piles, different number in each pile, zero items in a pile not allowed," as there is a one-to-one correspondence between solutions to the first and solutions to the second; adding one item to each pile for any solution to the first problem gives a solution to the second problem.
posted by DevilsAdvocate at 11:52 AM on April 20, 2010