Distributing Objects into Boxes

Case1: {\color{Green} }DISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES

EXAMPLE

How many ways are there to distribute hands of 5 cards to each of four players from the standard deck of 52 cards?

sol:

The first player can be choose 5 cards in C(52, 5) ways. The second player can be choose 5 cards in C(47, 5) ways, because only 47 cards are left. The third player can be choose 5 cards in C(42, 5) ways. Finally, the fourth player can be choose 5 cards in C(37, 5) ways. Hence, the total number of ways to deal four players 5 cards each is

here we use product rule,

C(52, 5)C(47, 5)C(42, 5)C(37, 5) = 52! /47! 5! · 47!/ 42! 5! · 42! /37! 5! · 37! /32! 5!

= 52!/ 5! 5! 5! 5! 32!

 

THEOREM  The number of ways to distribute n distinguishable objects into k distinguishable boxes so that ni objects are placed into box i, i = 1, 2,... , k, equals n! /n1! n2!··· nk!

 

Case2: INDISTINGUISHABLE OBJECTS AND DISTINGUISHABLE BOXES

Counting the number of ways of placing n indistinguishable objects into k distinguishable boxes turns out to be the same as counting the number of n-combinations for a set with k elements when repetitions are allowed.

 

EXAMPLE

 How many ways are there to place 10 indistinguishable balls into eight distinguishable bins?

 

Solution: The number of ways to place 10 indistinguishable balls into eight bins equals the number of 10-combinations from a set with eight elements when repetition is allowed.

 C(8 + 10 − 1, 10) = C(17, 10) = 17! /10!7!

= 19,448.

 

 This means that there are C(n + r − 1, n − 1) ways to place r indistinguishable objects into n distinguishable boxes

 

Case3: DISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES

 

EXAMPLE

How many ways are there to put four different employees into three indistinguishable offices, when each office can contain any number of employees?

Solution:

First, we note that we can distribute employees so that all four are put into one office, three are put into one office and a fourth is put into a second office, two employees are put into one office and two put into a second office, and finally, two are put into one office, and one each put into the other two offices. Each way to distribute these employees to these offices can be represented by a way to partition the elements A, B, C, and D into disjoint subsets.

we find that there are 14 ways to put four different employees into three indistinguishable offices.

 

Case4: INDISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES

EXAMPLE

How many ways are there to pack six copies of the same book into four identical boxes, where a box can contain as many as six books?

Solution:

here we will write all the ways we can pack books in the boxes

we will list the number of books in the box with the largest number of books, followed by the numbers of books in each box containing at least one book, in order of decreasing number of books in a box.

6

5, 1

4, 2

4, 1, 1

3, 3

3, 2, 1

3, 1, 1, 1

2, 2, 2

2, 2, 1, 1.

0Comment