Learn – Math circle – Permutations and Combinations

Fundamental principle of counting

Exercises

Problem set

  1. There are five houses on a street. There are five different elevation possibilities for each of the houses. How many different ways could the street look?
  2. There are five houses on a street. There are five different elevation possibilities for each of the houses. How many different ways could the street look if it is required that each house needs to have a different elevation?
  3. There are five houses on a street. There are twelve different elevation possibilities for each of the houses. How many different ways could the street look?
  4. There are five houses on a street. There are twelve different elevation possibilities for each of the houses. How many different ways could the street look if it is required that each house needs to have a different elevation?
  5. A dance team consisting of seven people is deciding on their outfits. They decide to color their shirts solid using one of 10 available colors.

    1. In how many different ways could the team dress up?
    2. In how many different ways could the team dress up if they decide no two people should have the same color?

Factorials

Exercises

Problem set

Evaluate the following

  1. 5!

Problem set

Evaluate the following

  1. \frac{10!}{7!}

  2. \frac{100!}{96!}

  3. \frac{2317!}{2314!}

  4. \frac{12345!}{12342!}

Permutations

Exercises

Problem set

  1. Say, we need to find the number of flags possible with three horizontal strips such that each strip uses a different color from a set of 8 available colors.

    1. Explain why the number of flags that may be formed is same as the number of permutations of 3 objects out of 8 distinct objects.
    2. Determine how many flags are possible.
  2. A theater performance requires a group of 5 dancers to stand in a row. The costume designer is determining the colors of clothes for the performers. Say, each dancer wears a single solid color that is different from the rest of the group, and there are 9 colors to choose from. The director is interested in knowing how many different ways the group could look on stage.

    1. Explain why the number of ways the group could look is same as the number of permutations of 5 objects out of 9 distinct objects.
    2. Determine how many ways the group could look on stage.
  3. Say, we need to award gold, silver and bronze medals to participants in a competition that has 10 participants. We need to determine how many ways the three medals could be awarded.

    1. Explain why the number of ways in which the medals could be awarded is same as the number of permutations of 3 objects out of 10 distinct objects.
    2. Determine how many ways I could possibly award the medals.
  4. In how many ways, can we form a swim team of four people from a total pool of 20 applicants? Explain if the number of ways is the number of permutations of four objects out of 20 distinct objects or if it is the number of combinations of four objects out of 20 distinct objects.
  5. Rayan goes to the fruit market and he notices that the market is selling mangoes, apples, oranges, pineapples, peaches and cantaloupe. His mom asks him to pick three different kinds of fruit to fill his basket. In how many ways could he fill his basket?
  6. In an elocution competition, the organizers need to award first, second and third prizes to three different participants. In addition, they need to award two consolation prizes, both of equal value. If there are twenty participants in the competition, in how many ways could the organizers possibly give the awards among the participants?

Problem set

In each of the following, assume that the letters come from the English alphabet (26 letters in all, with 5 vowels and 21 consonants) and that we do not care whether the words formed are meaningful or not.

  1. How many four-letter words can be formed?
  2. How many five-letter words can be formed if we require that all letters are distinct? Explain how this is a permutations problem.
  3. How many six-letter words that start and end with a vowel can be formed?
  4. How many eight-letter words that start and end with a vowel can be formed, if we require that all letters are distinct?
  5. How many four-letter words that have vowels and consonants alternating can be formed?
  6. How many eight-letter words that have vowels and consonants alternating can be formed if we require all letters to be distinct?

Problem set

  1. How many four-digit numbers have 0 in tens place?
  2. How many odd numbers between 30000 and 40000 have an even number in hundreds place?
  3. What is the sum of all four-digit numbers that contain each of the digits 1,2,3 and 4?
  4. What is the sum of all four-digit numbers?

Combinations

Exercises

Problem set

  1. Justify the identify: {n \choose r} = {n \choose n-r}

  2. Justify the identify: {n \choose r} = {n-1 \choose r-1} + {n-1 \choose r}

  3. Justify why Pascal’s triangle generates the binomial coefficients.

Miscellaneous

Exercises

Problem set

  1. Assume you have 100 points on a plane no three of which lie on the same straight line.

    1. How many triangles can you make using any three points to make the vertices?
    2. How may quadrilaterals can you make using any four points as its vertices?
  2. There are certain number of points marked on a plane, no three of which lie on a line. The total number of triangles that you can make by using any three
    of the points as vertices is equal to the total number of quadrilaterals that you can make by using any four of the points as vertices. How many points are marked on the plane?
  3. Consider set A = \{1,2,3,\cdots, 25\}.

    1. How many subsets of A exist such that the number of elements in each subset is 7?
    2. How many subsets of A exist such that the number of elements in each subset is 13?
    3. How many subsets of A exist such that the number of elements in each subset is 9 and each subset contains element 3 in it?
    4. How many subsets of A exist such that the number of elements in each subset is 11 and no subset contains element 7 in it?
    5. How many subsets of A exist such that the number of elements in each subset is at least 20?
  4. We have two sets A = \{1,2,3,4,5\} and B = \{1, 2,3,\cdots,100\}.

    1. How many one-to-one functions can be constructed from A to B?
    2. How many functions can be constructed from A to B?
    3. How many strictly increasing functions can be constructed from A to B?
    4. How many increasing functions can be constructed from A to B?