Skip to content

DA3. Combinatorics

Part 1: Scholarship Awards

1. Statement

  • You are organizing a swimming competition with ‘n’ participants. The school has announced scholarships for the top three swimmers.
  • The details of the scholarship is as follows:
    • First place - 100% scholarship to study abroad
    • Second-place - 100% scholarship to study in any school all over the country
    • Third-place – 50% scholarship to study in any school all over the country
  • Take ‘n’ as any two-digit number representing the total number of participants in the competition. Find how many possible ways are there to award these scholarships if there are no ties during the competition.
  • Explain in detail.

1. Solution

  • The total number of participants is n, where we are selecting k=3 participants for the scholarships.
  • Since there are no ties, the elements in the competition results are distinct.
  • Because we select the first, second, and third place, the order of the elements in the selection matters.
  • When elements are distinct and the order matters, we use the permutation formula.
  • The permutation formula states that P(n, k) = n! / (n - k)!.
  • Let’s substitute the values in the formula, and expand the factorial terms.
\[ \begin{aligned} P(n, k) &= n! / ( n - k )! \\ &= n! / ( n - 3 )! \\ &= n * ( n - 1 ) * ( n - 2 ) * ( n - 3 )! / ( n - 3 )! \\ &= n * ( n - 1 ) * ( n - 2 ) \\ \end{aligned} \]
  • The ( n - 3 )! in the numerator and denominator cancel out, so we left with n * ( n - 1 ) * ( n - 2 ).
  • So, for 10 participants, the number of ways to award the scholarships is 10 * ( 10 - 1 ) * ( 10 - 2 ) = 10 * 9 * 8 = 720.
  • For 99 participants, the number of ways to award the scholarships is 99 * ( 99 - 1 ) * ( 99 - 2 ) = 99 * 98 * 97 = 941,094.
  • So the values ranges from 720 to 941,094.

Part 2: School Funds

2. Statement

  • A group of n -school principals are trained for implementing innovative education in their schools. (Choose a two-digit number for n).
  • As a part of the innovative education scheme, 9 schools are to be offered equal funds from the government.
    1. In how many ways can 9 schools be selected from the trained group?
    2. If your school is one among the 9 selected schools, how many ways will be left to choose the other schools?
  • In both parts 1 and 2, which concepts are you using? Explain the reason to choose the concept. Also, discuss how combinatorics helps to solve real-world counting problems.

2. Solution

2.1. Part 1

  • The total number of schools is n, where we are selecting k=9 schools for the funds.
  • Assuming each school can get only one fund, the elements in the selection are distinct.
  • Assuming the order of the elements in the selection does not matter, we use the combination formula C(n, k) = n! / ( k! * ( n - k )! ) (Mathispower4u, 2022).
  • The reasoning is similar to the one used in the first question.
\[ \begin{aligned} C(n, 9) &= n! / ( 9! * ( n - 9 )! ) \\ &= n! / ( 9! * ( n - 9 )! ) \\ &= n * ( n - 1 ) * ( n - 2 ) * ( n - 3 ) * ( n - 4 ) * ( n - 5 ) * ( n - 6 ) * ( n - 7 ) * ( n - 8 ) * ( n - 9 )! / ( 9! * ( n - 9 )! ) \\ &= n * ( n - 1 ) * ( n - 2 ) * ( n - 3 ) * ( n - 4 ) * ( n - 5 ) * ( n - 6 ) * ( n - 7 ) * ( n - 8 ) / 9! \\ \end{aligned} \]
  • The formula is not simple and can not be simplified further, so I’ll just use the C(n, k) notation.
  • For 10 schools, the number of ways that a 9 schools can be selected is C(10,9) = 10.
  • For, 99 schools, the number of ways that a 9 schools can be selected is C(100,9) = 1,731,030,945,644.
  • So the values ranges from 10 to 1,731,030,945,644.

2.2. Part 2

  • The total number of schools is n, where we are selecting k=9 schools for the funds.
  • Taking our assumptions in question 2.1, into considerations we can use the combination formula C(n, k) = n! / ( k! * ( n - k )! ) (Mathispower4u, 2022).
  • Assuming our school has been selected, there are now n-1 schools left to choose k-1=8 schools from.
  • We are not simplifying the formula, and just use the C(n, k) notation.
  • For 10 schools, the number of ways that a 8 schools can be selected is C(9,8) = 9.
  • For, 99 schools, the number of ways that a 8 schools can be selected is C(98,8) = 171,200,862,756.
  • So the values ranges from 9 to 171,200,862,756 which is much smaller than the values in question 2.1.

2.3. Combinatorics in real-world

  • Combinatorics helps in imagining the size of a problem and the number of possible solutions which helps in planning and decision making.
  • Before actually implementing a solution, using combinatorics we can estimate the cost of such a solution, and based on that we can decide whether to implement it or not.

References