|
|
To count the number of ways to place objects in boxes, we need to be very clear regarding our ability to distinguish among the objects and among the boxes. If two objects are indistinguishable, then interchanging them doesn't result in a new way of placing the objects in boxes. Similarly, if two boxes are indistinguishable, then moving all the objects from one box to another box doesn't result in a new way of placing the objects in boxes. So we need to consider all the cases of whether the objects and whether the boxes are distinguishable.
Sometimes boxes are called "urns"
Sometimes "distinguishable" and "indistinguishable" are called "labeled" or "unlabeled"
When we speak of permutations of a string, we're really talking about putting objects in labeled boxes. The boxes are the positions of the objects in the string. For example, there are six permutations of the string ABC, which are ABC, ACB, BAC, BCA, CAB, and CBA. The three boxes, here, are the place for the first letter, the place for the second letter, and the place for the third letter. So permutations fall into the category of putting things (which may or may not be labeled) into labeled boxes, but with the restriction that exactly one object must be put into each box.
| labeled urns | unlabeled urns | |
| labeled objects | Placing particular numbers (n1, n2, ..., nk)
of labeled balls into labeled urns: n! / (n1! n2! ... nk!)
|
Placing n labeled balls into exactly k non-empty unlabeled urns: B(n,k) = B(n-1,k-1) + k B(n-1,k) |
| unlabeled objects | MISSISSIPPI: Permutations of
sets with some indistinguishable objects Placing n unlabeled balls into k labeled boxes: C(n+k-1,k-1) |
Placing n unlabeled balls into k
unlabeled boxes: Part(n,k) is the number of k-element partitions of n. |
Consider the word MISSISSIPPI. It has 1 M, 4 I's, 2 P's, and 4 S's.
If each of the letters were distinct, say, M1I1S1S2I2S3S4I3P1P2I4, then there would be 11! ways to arrange them. But if we couldn't tell the S's apart, then we would reduce the number of possible ways to arrange the new word, M1I1SSI2SSI3P1P2I4, by a factor of 4!, which is the number of different permutations of the S's, all other things being equal. Similarly, if we couldn't tell the I's apart, we would reduce the number of permutations by another factor of 4!, and if we couldn't tell the P's apart, we would reduce the number by yet another factor of 2! this time.
So the number of distinct permutations of MISSISSIPPI is 11! / (4! 4! 2!)
There's another way to figure this out. Imagine there were 11 spaces in which to write the letters that make up the word MISSISSIPPI.
__ __ __ __ __ __ __ __ __ __ __ 1 2 3 4 5 6 7 8 9 10 11
To find the number of permutations, consider placing the letters into these 11 spaces. There are C(11,1) ways to place the M. Having placed it, there are C(10,4) ways to place the I's. Having placed them, there are C(6,2) ways to place the P's, and then C(4,4) ways to place the S's.
So the number of distinct permutations of MISSISSIPPI is
C(11,1) C(10,4) C(6,2) C(4,4)
which can be written as
11!/(10! 1!) 10!/(6! 4!) 6!/(4! 2!) 4!/(4! 0!)
after canceling common factors, this becomes
11! / (1! 4! 2! 4!)
In general, if you have n total objects and k unique objects, call n1 the number of indistinguishable objects of type 1, n2 indistinguishable objects of type 2, ... and nk the number of indistinguishable objects of type k, then the number of different permutations of these objects is
n! / (n1! n2! ... nk!)
One more example, that might look different at first glance: Consider the word FACETIOUS. How may ways can it be rearranged, leaving the vowels in order A,E,I,O,U?
The trick is to realize that this is the same as the number of ways to rearrange FACATAAAS, which is the same word except I use the letter "A" to represent every vowel. The reason this is the same is that for any arrangement of the letters FACATAAAS, you can reconstruct the letters of FACETIOUS with the vowels in order -- just change the second "A" to "E", change the third "A" to "O", etc.
So the answer is 9! / 1! 1! 1! 1! 5! = 9! / 5! = 9*8*7*6 = 3024
That is, placing n1 objects into the first box, n2 objects into the second box, etc., and nk into the kth box.
Surprisingly, the problem of counting the ways to put particular numbers of n labeled balls in k labeled urns is the same as that of counting the ways to permute sets of n objects with k types of indistinguishable objects, with a particular number of each type of object.
I say surprisingly, because at first these appear to be different problems. But if you think back to the MISSISSIPPI problem, and consider not permuting not the M's, I's, S's, and P's, but rather assigning the eleven letter positions to labeled urns, then the problem becomes "How many ways can the numbers 1 through 11 be placed in four urns such that one number be placed in urn 'M', 4 numbers be placed in urn 'I', 2 numbers be placed in urn 'P', and 4 numbers be placed in urn 'S'"? For each way of permuting the letters in MISSISSIPPI, there is a corresponding way of assigning the given quantities of the 11 letter positions to the four urns.
So the formula for the number of ways to place n distinguishable objects into k distinguishable boxes, such that n1 objects go in the first box, n2 in the second, ... and nk go in the kth box is:
n! / (n1! n2! ... nk!)
The number of different ways to distribute n indistinguishable balls into k distinguishable boxes is C(n+k-1,k-1).
For example, 5 balls into 3 boxes can be done in these C(7,2) = 21 ways:
Box 1 Box 2 Box 3 aaaaa aaaa a aaaa a aaa aa aaa a a aaa aa aa aaa aa aa a aa a aa aa aaa a aaaa a aaa a a aa aa a a aaa a aaaa aaaaa aaaa a aaa aa aa aaa a aaaa aaaaa
The easiest way to understand this formula is to consider the permutations of the string XXaaaaa -- in each permutation, the 2 X's divide the a's into one of three boxes. From the first section, on permutations of sets with some indistinguishable objects, we know that the number of distinct permutations of XXaaaaa is C(7,2). In general, the number of permutations of a string of n a's and k-1 X's is C(n+k-1,k-1), and each of these permutations corresponds to one of the ways you can place n indistinguishable objects into k labeled boxes.
If you're told that the boxes can't be empty, then this is the same as putting one ball in each of k boxes first (that part is forced, so there's one way to do it), and then it's the number of ways to distribute n-k identical balls into k labeled boxes, or C(n-1,k-1)
The number of different ways to distribute n indistinguishable balls into exactly k indistinguishable non-empty boxes is the number of k-element partitions of n.
For example, 7 can be partitioned into exactly 3 non-empty boxes these four ways:
1+1+5
1+2+4
1+3+3
2+2+3
The function, part, is defined this way. Part(n,k) is the number of k-element partitions of n. So part(7,3)=4.
A recurrence relation is
part(n,k) = part(n-1,k-1) + part(n-k,k) (proof)
I define part(n) (Sloan's A000041) to be the sum from k=1 to n of part(n,k) (Sloan's A008284).
n \ k 1 2 3 4 5 6 7 8 9 10 part(n) 0 1 1 1 1 1 2 1 1 2 3 1 1 1 3 4 1 2 1 1 5 5 1 2 2 1 1 7 6 1 3 3 2 1 1 11 7 1 3 4 3 2 1 1 15 8 1 4 5 5 3 2 1 1 22 9 1 4 7 6 5 3 2 1 1 30 10 1 5 8 9 7 5 3 2 1 1 42
Another fascinating recurrence relation is this:
Let part(0)=1
Stop the following process when the index of a term becomes less than zero.
part(n) = part(n-1) + part(n-2) (m=1) -part(n-5) - part(n-7) (m=2) +part(n-12) + part(n-15) (m=3) - ................ +- part(n-m(3m-1)/2) +- part(n-m(3m+1)/2) (m >= 1)
The last line is the general form for the pairs of terms.
When m is odd, add the two terms, and when m is even, subtract them.
For example:
part(10)= part(9) + part(8) - part(5) - part(3)
= 30 + 22 - 7 - 3 = 42
The number of different ways to distribute n labeled balls into exactly k indistinguishable non-empty boxes, which I will call B(n,k), is given by the recurrence relation,
B(n,k) = B(n-1,k-1) + k B(n-1,k)
The reason this recurrence relation works can be illustrated recursively.
B(1,1)=1 because there is just one way to put one labeled ball into one unlabeled box.
Now suppose you know the number of ways to put n-1 labeled balls into k unlabeled boxes (and you also know the number of ways to put n-1 labeled balls into k-1 unlabeled boxes), and you want to add one more ball and use k boxes. You can either start with any of the B(n-1,k-1) combinations, and put the nth ball into a new box or else you can start with any of the B(n-1,k) combinations, and put the nth ball into a non-empty box.
For each of the B(n-1,k-1) combinations, there is just one way to add the new ball to a new box.
For each of the B(n-1,k) combinations, there are k ways to add the new ball to a non-empty box.
Thus the number of combinations B(n,k) is the sum of B(n-1,k-1) and k times B(n-1,k).
B(n,k) are known as Stirling numbers of 2nd kind, sometimes S2(n,k) (Sloan's A008277)
This table shows the number of ways of putting n labeled balls in n bins that use k of the n bins.
n \ k 1 2 3 4 5 6 7 8 9 10 Sum 1 1 1 2 1 1 2 3 1 3 1 5 4 1 7 6 1 15 5 1 15 25 10 1 52 6 1 31 90 65 15 1 203 7 1 63 301 350 140 21 1 877 8 1 127 966 1701 1050 266 28 1 4140 9 1 255 3025 7770 6951 2646 462 36 1 21147 10 1 511 9330 34105 42525 22827 5880 750 45 1 115975 Table Showing Recurrence relation B(n,k) = B(n-1,k-1) + k B(n-1,k)
If you need to find the number of ways to put n labeled balls into k boxes, and the boxes can be empty, then just sum B(n,j), for j=1 to k.
By the way, the nth "Bell Number" is B(n,n), and this is Sloan's A000110.
Partitioning Integers , from Bob's Positive Integer Pages (fascinating reading!)
Sloan's A000041: the number of partitions of n.
Sloan's A000110: the nth "Bell Number".
Sloan's A008277: Stirling numbers of 2nd kind, sometimes S2(n,k)
Sloan's A008284: part(n,k), the number of partitions of n into exactly k parts, and also (by conjugate partitions) the number of partitions of n whose largest part is k.
Partition Recurrence Relation -- calculating the number of k-element partitions of n using part(n,k) = part(n-1,k-1) + part(n-k,k). Conjugate partitions.
The webmaster and author of this Math Help site is Graeme McRae.