Applications of combinatorics

Algebra: Binomial Coefficient

Applications of combinatorics

In this section we will discuss several combinatorial problems which can be reformulated in terms of drawing, with and without putting back, balls (numbered or not) from a box. More generally, we're talking about objects instead of balls and a set of #n# objects instead of a box of #n# balls.

First we need the concept of #n# factorial, which is written as #n!#

Permutations The number of ways to arrange #n# is \[n! = 1\times 2\times 3\times \cdots \times n\tiny.\] Such an arrangement is called a permutation.

Suppose we want to put five people in a row. For the first place we could choose among five people. For the second place we have four candidates, because one person has already been put in the first place. In total there are \(5\times 4\times 3\times 2\times 1=5!=120\) possibilities.

If we number the persons #1# to #5#, then each arrangement consists of a row of numbers. For example, #12345#, #54321#, and #21354#.

Using the factorial #n!# and the binomial coefficient, we can solve four similar counting problems:

Taking with/without putting back and with/without order

Let #n# be a natural number and #k# a non-negative integer.

Taking \(k\) objects from a set of size \(n\), when after each draw the taken object is put back, and where the order is relevant, is called a repetition variation of #k# from #n#. This number is equal to #n^k#.
Taking \(k\) objects from a set of size \(n\), when after each draw the taken object is put aside and where the order is relevant, is called a variation of #k# from #n#. This number is equal to #n\cdot (n-1)\cdots (n-k+1)# if #k\le n# and #0# otherwise.
Taking \(k\) objects from a set of size \(n\) , when after each draw the taken object is set aside, and where the order is not important, is called a combination of #k# from #n#. This number is equal to #\binom{n}{k}#.
Taking \(k\) objects from a set of size of \(n\), when after each draw the taken object is put back, and where the order is not relevant, is called a repetition combination of #k# from #n#. This number is equal to #\binom{n+k-1}{k}#.

Examples:

Repetition Variations: a PIN consists of four digits. For each of the four digits, there are ten possibilities (the digits 0/9). The number of different PIN's is equal to \(10\times 10\times 10\times 10=10^4\) . You can also reformulate the problem as follows: You have a box of ten balls numbered 0 to 9 and the balls are mixed properly. Take a random ball from the box, note the number of the ball on a paper, put the ball back into the box and mix the balls back together. After that, take again a random ball out of the box, write the number of the ball down again, put the ball back into the box and mix the balls together. Repeat this process twice more so that you finally have four numbers on paper. The amount of possible combinations of these numbers is then equal to the number of repetition variations of four out of ten, which is \(10^4.\)

Variations: Suppose a company wants to elect a board out of the 25 members, consisting of a chairman, secretary and treasurer and they do not allow the same person having multiple positions. Assume that everyone is available for each position. The board can be constructed in \(25\times 24\times 23=13800\) ways. If we assume that the choice for the positions is made in an order, then there are 25 candidates for the chairmanship, which leaves 24 persons for the position of secretary and 23 people may finally be elected for treasurer. The election of the Board can be done not only by a voting at a general assembly, but also by a drawing. Number the members with 1 till 25 and put twenty-five balls in a box numbered with 1 till 25. One takes a random ball out of the box and the person with the number equal to the number on the drawn ball becomes president. Then you take another ball out of the box. This time the person with the number equal to the number on the ball becomes the secretary. Finally, take a third ball and the number of the ball indicates who is treasurer. It is now a drawing without putting back and with order.

Combinations: Let us return to the example of the election of a board consisting of three people of a company with twenty-five members. Assume now that the positions of the board do not matter and the only thing you have to do is to elect a board consisting of three persons from 25 members. Then it turns into a drawing without putting back and without order. In this case you have to divide the number of variations by the number of possible scenarios within the board. The number of board combinations is equal to \[\frac{25\times 24\times 23}{3!}=\frac{25!}{22!\times 3!}=\!\binom{25}{3}=2300\]

Repetition Combinations: Suppose you can order a sundae in an ice cream parlor with three scoops of our own choice. If the ice cream shop offers ten flavors of ice cream, then the number of types of sundaes equal to \(\binom{12}{3}\) . This is to be understood as follows: write for every flavor as much vertical tallies as the number of selected scoops of this paricular taste and write between the tallies associated with the various flavors horizontal hyphen as a sort of seperation sign. Then there are \(3\) vertical tallies and \(10-1=9\) horizontal hyphens in a description of a selected sundae.

The code || - | -------- can mean 2 scoops of vanilla and one scoop of chocolate, while
the code | - || --------- means 1 scoop vanilla and 2 scoops of chocolate.
The code | - | - | ------- would be a sundae with a scoop of vanilla, chocolate, and pistachio.

The number of different sundaes is equal to the number of ways to place \(3\) vertical tallies on \(12\) possible locations. This is the number of combinations of \(3\) from \(12\) in a draw without putting back and without order.

The following table provides a summary of the four types of problems.

repetition	with order (variation)	without order (combination)
with putting back	#\ n^k#	#\binom{n+k-1}{k}#
without putting back	#\ \binom{n}{k}\cdot k!#	#\binom{n}{k}#

The formula for #3!# gives #3!=3\times2=6#.

Write down all six permutations of the three numbers #1#, #2#, #3#.

#123#
#132#
#213#
#231#
#312#
#321#

New example