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