More Permutations and Combinations

Selection with Repetition

Combinations with Repetition

Permutations with Identical Objects

More Counting Examples

  1. Your mother-in-law buys 1000 small gifts to give to relatives for Christmas, for reasons you don't understand. Each of the 1000 things is different, because she spends too much time shopping. There are 25 relatives to give gifts to. How many ways are there to distribute the gifts?
    • Note: the question allows the possibility of one person getting 1000 things, and everyone else getting nothing. There's no fairness in this family
  2. In the above scenario, how many ways can the gifts be distributed so each person gets 40 items?
  3. The next year, you are sent to the basement to arrange the 1000 gifts into 25 piles, with one for each person. You don't know who will be getting each pile, so the order of the piles doesn't matter. How many arrangements are there for you to choose from?
  4. The next year, your mother-in-law buys 1000 identical pens to give to the family. You start to wonder what is going on. How many ways can they be distributed to 25 family members?
  5. How many ways if each person must get at least 3 pens?
  6. How many ways if each person gets 40 pens?


  1. This is a permutation with repetition. For each gift, it can be given to one of 25 family members. First gift in 25 ways, second gift in 25 ways, …. In total, \(25^{1000}\approx 8.7\times10^{1397}\) ways.
  2. Think of giving each family member 40 tokens with their name on it. Line the 1000 different gifts up in a row and have each family member drop their 40 tokens on gifts.

    A final arrangement in this case is a permutation of the 1000 tokens, with 25×40 identical ones. It is a permutation of identical objects as above and the number of permutations is \[\frac{1000!}{(40!)^{25}}\approx 5.3\times 10^{1369}\,.\]

  3. This one is surprisingly difficult. See the textbook's discussion of “distinguishable objects and indistinguishable boxes” on p. 337, or look up Stirling Numbers of the second kind.
  4. To distribute the gifts, we must select people to get each one. Order doesn't matter here, since the pens are identical. This is a combination with repetition problem: combinations of 1000 the 25 family members with repetition. So there are \(C(1024,25)\) ways to distribute.
  5. Attempt #1: Count all \(C(1024,25)\) ways to distribute the pens, then subtract the number where somebody gets 2 or fewer pens. How many of those are there? Ummmm…

    Attempt #2: First give everybody three pens, using 75 of them. Then distribute the remaining 925 in \(C(949,25)\) ways.

  6. One way: give each person 40 pens.

Generating Permutations and Combinations