Problem: Number Partitioning

Had a go to derive a formula for the number of partitions of a number. Initially, tried to compare it with the 'pirates and gold bars' problem and see if I could derive some formula based on similar reasoning. After this failed attempt, decided to come up with a recursive formula.

Suppose you order the partitions by increasing size, and within a partition order the elements in weakly increasing order. For example, you write the partitions of 4 as:
4
1 3
2 2
1 1 2
1 1 1 1

Now, consider a way of generating all the partitions of a given size k. Suppose these partitions are to be arranged lexicographically. Then, the first partition consists of (k-1) 1s followed by the number n-(k-1). For example, the first 4-sized partition of 8 would be:
1 1 1 5

The next partition is generated by taking 1 away from the rightmost element (rightmost_elem) and adding it to the previous element. This process should be continued upto the point where the elements within the partition cannot be arranged in weakly increasing order. So, we have:
1 1 1 5
1 1 2 4
1 1 3 3
(cant go for 1 1 4 2)

For each of the partitions generated above, partitions for the (k-1) leftmost elements can be generated keeping the rightmost element constant. Hence, this can be viewed as a recursive process of generating sub-partitions for the number (n - rightmost_elem), each of size (k-1). Also, while generating these sub-partitions, the maximum value of any element should not exceed the value of the rightmost_elem.

This idea of recursive sub-partitions is captured by the following recurrence equation:
And the following equation generates all partitions of a number:
We also need to take care of the end conditions properly. If k ==1, only 1 partition is possible and when n==k, only 1 partition is possible i.e. T(n,1,max) = 1 and T(n,n,max) = 1.

Problem: Pirates and gold bars

Problem: There are 13 indivisible, identical gold bars that are to be divided among 5 pirates. In how many ways can this be done ?

[ The reason I attempted this problem was because of two things involved in it: pirates and gold.]

Solution: Suppose you have 4 knives that you can place at any position in between the gold bars and the number of gold bars pirate i gets is the number of gold bars between knife i-1 and knife i where knife 0 and knife 5 are imaginary knives.

The problem may now be visualized as permuting the 13+4 elements out of which 13 are alike and 4 are alike.

Number of ways = fact(17) / (fact(13) * fact(4)) = 17C4

Generalization: The number of ways in which n gold bars may be divided among m pirates is (n+m-1)C(m-1) = (n+m-1)Cn

Path towards the solution: The problem may be viewed as placing (m-1) dividers so as to get m parts from the array of gold bars. Each of the (m-1) dividers may be placed at any of the (n+1) positions. Therefore, the solution could be (n+1)^(m-1). However, the dividers themselves are not distinct and we are counting a particular division more than once. In other words, the divisors are all alike. Hence, now we have to consider the sequence of gold bars interspersed with divisors of length (n+m-1) out of which n are alike and (m-1) are alike.

Similar problems:

(1) The number of positive integer solutions to x1 + x2 + ... + xk = n where x1,x2,...,xk >= 0.

[Here, the total number of gold bars is n and pirate i is given the number of gold bars equal to xi.]

p->next:

(1) Number partitioning and Partition functions

(2) Young diagrams