I need to partition a set {1,2,3,…36} into exactly three partitions. Moreover, every of such three partitions cannot have less than 5 elements – any partition may have exactly 5 or more elements. How many variants do I have and how can I get all those partitions (I would like to have all of them listed) – maybe there is some generation algorithm.
Total number of partitions of an n-element set is the Bell number B.
The number of partitions of an n-element set into exactly k nonempty parts is the Stirling number of the second kind S(n, k).
The number of noncrossing partitions of an n-element set is the Catalan number.
- I have an additional restriction on what Stirling number does
- How to find (algorithm or practical method) all those partitions?
P.S. Stirling number formula gives 10^16 variants, but I am interested only in sizes of partitions (number of elements in each subset) – not exact elements out of [1,2..36] to fit into every subset/partition. So that 6+10+16 is one variant, 6+20+10 – another variant – all such variants (possible partition sizes) – without order, so 6+10+16 or 6+16+10 or 10+16+6 is one and the same variant for my needs.
P.S. Here I found c++ code for generating partitions, but it seemed to me buggy at first sight.
Guava partition method (java) is somewhat close, but is not exactly that – you should already specify the size of partition.
List<Integer> lst = new ArrayList<> (Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15));
Iterable<List<Integer>> it;
it = Iterables.partition(lst, 3);
for (List<Integer> list : it) {
System.out.println(list);
}
Output:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
[10, 11, 12]
[13, 14, 15]
Other partitioning API (java)
Best Answer
You're looking for triples of three numbers (which I'm going to list in nondecreasing order) that sum to 36, and where each one is at least 5.
Instead you can look for triples of three numbers $p \le q \le r$ that sum to $36 - 15 = 21$, where each is nonnegative, and then the numbers you originally sought were $p+5, q+5, r+5$. (i.e., there's a 1-1 correspondence between the collection of partition-sizes that you seek and the collection of $(p, q, r)$ with $0 \le p \le q \le r$ and $p+q+r = 21$.)
These latter triples can be divided into those with $p = 0$, where the remaining numbers sum to 21; those where $p = 1$, and the remaining numbers sum to $20$...but both are at least $1$, those where $p = 2$, and the remaining numbers sum to $19$, but both are at least $2$, etc.
But the same trick applies to those: pairs of numbers, in nondecreasing order, summing to to $19$, but both being at least $2$ have the same count as pairs of (nondecreasing) numbers, summing to $15$, but both being at least $0$.
Let's write $$ C(n, k) $$ for the number of $n$-element sets of nonnegative numbers, in increasing order, that sum to exactly $k$. Then what I've said above shows that the number you're looking for is $C(3, 21)$, and that
$$ C(3, 21) = C(2, 21) + C(2, 21-3\cdot 1) + C(2, 21-3\cdot 2) + \ldots + C(2, 21-3\cdot 7) $$
Now how large is $C(2, k)$? It, too, satisfies a recurrence: the first number is either $0$ (in which case the remaining number must sum to 21), or it's 1, in which case the remaining number must be at least 1 and sum to 20, i.e., the count of which is the same as numbers that are at least 0 and sum to 19, etc. $$ C(2, k) = C(1, k) + C(1, k-2 \cdot 1) + C(1, k-2 \cdot 2) + \ldots + C(1, k-2 \cdot (k/2)) $$ where the $k/2$ in the last term should be rounded down [i.e., if $k$ is odd, then we end with $C(1, 1)$ rather than $C(1, -1)$. ]
Now how large is $C(1, s)$ for any nonnegative $s$? It's exactly $1$.
That means that $C(2, k)$ is exactly $\lfloor \frac{k+1}{2} \rfloor$.
So $$ C(3, 21) = \lfloor \frac{22}{2} \rfloor + \lfloor \frac{19}{2} \rfloor + \lfloor \frac{16}{2} \rfloor + \lfloor \frac{13}{2} \rfloor + \lfloor \frac{10}{2} \rfloor + \lfloor \frac{7}{2} \rfloor + \lfloor \frac{4}{2} \rfloor + \lfloor \frac{1}{2} \rfloor \\ = 11+9 + 8 + 7 + 5 + 3 + 2 = 45. $$
This seems surprisingly low to me, but I don't see any obvious error (except that my "round down $(k+1)/2$" answer for $C(1, k)$ could be off by one), so I'm going to go ahead and submit it as an answer, and if not an answer, at least a suggested path for you to follow in getting to the correct answer.
Let me just sanity check by writing them down...there aren't that many.
Hunh. I seem to get 38. So I probably DID have an off-by-one error in my formula for $C(2, k)$. Anyhow, the answer is 38, and you can work out my off-by-one error by back-tracing, if it pleases you do to so.