Learn – Math circle – Permutations and Combinations

Counting

Exercises

Problem set

  1. Say, we need to form flags consisting of three horizontal strips with each strip using a different color from a collection of 8 available colors. Give the number of flags that may be formed. Explain your answer.
  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 each house needs to have a different elevation? Explain your answer.
  3. 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. How many different ways could the group look on the stage? Explain your answer.
  4. Say, we need to award gold, silver and bronze medals to participants in a competition that has 10 participants. How many different ways could the three medals be awarded? Explain your answer.
  5. In how many ways can we form a swim team of four people from a total pool of 20 applicants?
  6. 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?
  7. 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?
  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. There are five houses on a street. There are 12 different elevation possibilities for each of the houses.
    1. How many different ways could the street look?
    2. How many different ways could the street look if it is required that each house needs to have a different elevation?
  2. 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?

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?

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. Six friends went to a restaurant. In how many ways could they be seated around a circular table, if arrangements with each person having the same neighbors count as one?

  5. Three men and three women went to a restaurant. With men and women sitting alternately, in how many ways can they be seated

    1. along a straight table?
    2. along a circular table?

  6. 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?

Formulas and calculations

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!}

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.