COMBINATORICS – THE EASIER WAY :)

October 10, 2012 Leave a comment

What would you do with the money should you win the lottery? Hmmm, nice theme to think about. But, what are the chances to win the lottery? What is the possibility that, of all possible combinations in the lottery game, yours is the winning one? You have to guess one combination of… hmmm… many 🙂 . How many? Well, that is the problem we need to solve. This is where combinatorics comes very handy.

In high school combinatorics can be real horror. All those permutations, combinations, variations and who knows what else. Just as you thought you get it, there comes a problem you have no idea how to solve. How to understand the basic elements of combinatorics? What are combinations, permutations, variations? And, most important, how to recognize them in specific situation.

I will try to answer all those questions as simple and comprehensible as I can. Let’s meet some important markings and formulas we will use.

FACTORIAL

Factorial of a natural number is the multiplication of all natural numbers that are smaller or equal to that number. Factorial is denoted by n! an can be calculated by formula:

n!=n\cdot (n-1)\cdot (n-2)\cdot ..\cdot 2\cdot 1

So, if we need to calculate factorial of some natural number, we just multiply all natural numbers from 1 to that number. For example, factorial of 5 is

5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120

Problem 1: What is 8!

Solution: 8!=8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=40320

If you take a closer look you can notes this connection:

n!=n\cdot (n-1)\cdot (n-2)\cdot ..\cdot 2\cdot 1=n\cdot (n-1)!

For example:

5!=5\cdot 4\cdot 3\cdot 2\cdot 1=5\cdot 4!

We can continue this:

n!=n\cdot (n-1)!=n\cdot (n-1)\cdot (n-2)!=..

This means that 10! is:

10!=10\cdot 9!=10\cdot 9\cdot 8!=10\cdot 9\cdot 8\cdot 7!=10\cdot 9\cdot 8\cdot 7\cdot 6!=...

For easier calculation we take that 0!=1.

BINOMIAL COEFFICIENT

One more important term we will use is binomial coefficient. We call it “binomial” for it’s origin from binomial theorem, but we don’t need that one so we will not waste our time over it 😉 .

Binomial coefficient is denoted by \left( \begin{matrix} n \\ k \\ \end{matrix} \right)(we read it n choose k) and is calculated as

  \left( \begin{matrix} n \\ k \\ \end{matrix} \right)=\frac{n!}{k!\cdot (n-k)!}

So, to calculate binomial coefficient we need two natural numbers.

Problem 2:

Calculate  \left( \begin{matrix} 7 \\ 4 \\ \end{matrix} \right)?

Solution: \left( \begin{matrix} 7 \\ 4 \\ \end{matrix} \right)=\frac{7!}{4!\cdot (7-4)!}=\frac{7!}{4!\cdot 3!}=\frac{7\cdot 6\cdot 5\cdot 4!}{4!\cdot 3\cdot 2\cdot 1}=\frac{210}{6}=35.

Notice that while solving Problem 2 we used 7! = 7·6·5·4! just like we explained before.

Let’s get back to combinatorics. Combinatorics calculates how many ways we can choose a subset of a given set. So, we have a set of elements, we select subsets and count them. Three basics elements of combinatorics are: permutation, variation and combination. To differ them we first need to answer two questions:

  1. Do we choose all the elements from the set?
  2. Is the order of chosed elements important?

Once we answer these two questions we will know what are we dealing with: permutation, variation or combination. J

PERMUTATIONS

Imagine we need to put three books on the shelf. How many ways we can aline them?

If we mark them as book 1, 2 and 3 we will get 6 possibilites (1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2 i 3-2-1). So, three books can be alined in six ways. Well, that wasn’t very hard.

But things get much complicated if we have more books, for example 15. Let us explore this exampleas permutation. Of all 15 books from the set all 15 must be on the shelf so all 15 are chosen. Also, their order on the shelf is important.

We see that permutation gives us these two answers to our questions:

  1. All the elements from the set ARE chosen.
  2. The order of chosen elements IS important.

So, if we get answer “Yes” to both of our questions we know we are dealing with permutations. 😉

Permutations can be without repeating  or with repeating. Without repeating means that all of the elements in the set are different (in our example all of the fifteen books are different), while permutation with repeating means that some elements can be repeated (for example, in the word DADDY letter D is repeated three times).

Number of all permutations without repeating in the set of n elements (P(n))can be calculated by formula:

P(n)=n!

Suppuse we have 3 books to put on the shelf and two of the books are the same (we hawe twoo books labeled 1, and one book labeled 2). Now there are only three ways we can aline them on the shelf (1-1-2, 1-2-1 i 2-1-1). So, if we allow repeating of the elements in the set, the number of permutations gets lower.

If we have n elements in our set and m1, m2, m3,.. i mk are the numbers of same elements amongs them (so that m1+m2+m3+.. +mk=n), number of all permutations can be calculated by formula

P(n,{{m}_{1}},{{m}_{2}},{{m}_{3}},..{{m}_{k}})=\frac{n!}{{{m}_{1}}!\cdot {{m}_{2}}!\cdot {{m}_{3}}!\cdot \cdot \cdot {{m}_{k}}!}

So, if we have 15 books we can aline them in

P(15)=15!=1307674368000 ways.

To be honest, now that I see size of this number I’m glad I didn’t have to write all possible permutations.  🙂

Problem 3: On the shelf there are 3 same books on math, 2 same books on physics and 1 comic book. How many different ways we can aline them on the shelf?

Solution: First, let us answer to our two important questins. We can see that all books go on the shelf so all the elements from our set ARE chosen. We also notice that the their order on the shelf IS importat. As both answers to our two questions are positive, we conclude that we are dealing with permutations. Also, since some of the books are the same we have permutations with repeating.

Of n=3+2+1=6bookswe have 3 same math books so the first book repeats 3 times (m1=3). By same reasoning we get that m2=2 and m3=1. By using the formula mentioned before we get:

P(n)=\frac{n!}{{{m}_{1}}!\cdot {{m}_{2}}!\cdot {{m}_{3}}!}=\frac{6!}{3!\cdot 2!\cdot 1!}=\frac{6\cdot 5\cdot 4\cdot 3!}{3!\cdot 2\cdot 1}=\frac{120}{2}=60

VARIATIONS

Suppose there are 25 people in a local organisation and we need to choose a president, a secretary and a treasurer of the organisation. So, of 25 members we need to choose 3 while minding who is the president, who is the secretary and who is the treasurer. How many ways can we make this choice?

What we have here are called variations. Of 25 members we choose only 3 so not all elements of the set are chosen. Also, since it is important who is the president, who is the secretary and who is the treasurer, the order of chosen elements is important. Here we can conclude that the answers to our two questions are:

  1. NOT ALL elements from the set are chosen.
  2. The order of chosen elements IS important.

Variations can also be with or without repeating. If the set has n elements and we chose k of them , we get variations of k from the set of n elements and we can denote it by V_{n}^{k} if they are without repeating, and \overline{V_{n}^{k}} if they allow repeating. To avoid confusion, some references use this notation V(n,k) and \overline{V}(n,k).

We calculate the number of variations of k from the set of n elements using formula:

V_{n}^{k}=\frac{n!}{(n-k)!}

In the case of allowed repeating we can use:

\overline{V_{n}^{k}}={{n}^{k}}

In our example let’s suppose that members can’t have more than one function at the time (no one can be, for example, president and treasurer at the same time). So, of 25 members we choose 3 without repetition. These are variations of 3 from the set of 25 elements, therefore we haven=25 and k=3:

V_{25}^{3}=\frac{25!}{(25-3)!}=\frac{25!}{22!}=\frac{25\cdot 24\cdot 23\cdot 22!}{22!}=13800

Problem 4: How many three digit natural numbers can be written with digits 1, 2, 3, 4, 5 i 6 if the digits:

a)      can’t be repeated;

b)      can be repeated;

Solution:

a) Of 6 offered digits we choose 3 keeping in mind that the digits can’t be repeated. So, NOT ALL digits are chosen, and their order IS important, therefore we have variations of 3 from the set of 6 elements without repeating (n=6 and k=3):

V_{6}^{3}=\frac{6!}{(6-3)!}=\frac{6!}{3!}=\frac{6\cdot 5\cdot 4\cdot 3!}{3!}=120

We can write 3-digit 120 numbers.

b) Here we have the same case the only difference being that this time digits can be repeated, so we have:

\overline{V_{6}^{3}}={{6}^{3}}=216

COMBINATIONS

Suppose that in our group of 25 members we need to choose 2 to represent the group in a convention. In this case we chose 2 of 25 so, again, not all members are chosen. Difference from the variations is that this time the oreder of chosen members is not important (since both representatives have the same function). This are called combinations and the answers to our two questions are:

  1. NOT ALL elements from the set are chosen.
  2. The order of chosen elements IS NOT important.

Combinations can also be with and without repeating. Combinations of k from the set of n elements without repeating C_{n}^{k} is calculated using formula:

C_{n}^{k}=\left( \begin{matrix} n \\ k \\ \end{matrix} \right)

Combinations of k from the set of n elements with allowed repeating (\overline{C_{n}^{k}}) is calculated using formula:

\overline{C_{n}^{k}}=\left( \begin{matrix} n+k-1 \\ k \\ \end{matrix} \right)

In our case we have 25 members of the group and we choose 2 of them (without choosing the same member twice) so we have combinations of 2 from the set of 25 elements:

C_{25}^{2}=\left( \begin{matrix} 25 \\ 2 \\ \end{matrix} \right)=\frac{25!}{2!\cdot (25-2)!}=\frac{25!}{2!\cdot 23!}=\frac{25\cdot 24\cdot 23!}{2\cdot 1\cdot 23!}=\frac{600}{2}=300

Problem 5: How many different ways can 4 cards be chosen from the deck of 32 cards?

Solution: From the deck of 32 cards we choose 4. Since not all cards are chosen and the order is not important, we conclude we have number of combinations to calculate. We have 32 elements (n=32) and we choose 4 of them (k=4), so we have:

\begin{matrix} C_{32}^{4}=\left( \begin{matrix} 32 \\ 4\\ \end{matrix} \right)=\frac{32!}{4!\cdot (32-4)!}=\frac{32!}{4!\cdot 28!}=\frac{32\cdot 31\cdot 30\cdot 29\cdot 28!}{4\cdot 3\cdot 2\cdot 1\cdot 28!}= \\ =\frac{32\cdot 31\cdot 30\cdot 29}{4\cdot 3\cdot 2\cdot 1}=\frac{863040}{24}=35960 \\ \end{matrix}

CONCLUSION

All of the above can be put in one table:

Do we choose all the elements from the set? Is the order of chosed elements important? Calculating formulas
YES YES PERMUTATIONS No repeatingP(n)=n!
With repeatingP(n,{{m}_{1}},{{m}_{2}},{{m}_{3}},..{{m}_{k}})=\frac{n!}{{{m}_{1}}!\cdot {{m}_{2}}!\cdot {{m}_{3}}!\cdot \cdot \cdot {{m}_{k}}!}
NO YES VARIATIONS No repeatingV_{n}^{k}=\frac{n!}{(n-k)!}
With repeating\overline{V_{n}^{k}}={{n}^{k}}
NO NO COMBINATIONS No repeatingC_{n}^{k}=\left( \begin{matrix} n \\ k \\ \end{matrix} \right)
With repeating\overline{C_{n}^{k}}=\left( \begin{matrix} n+k-1 \\ k \\ \end{matrix} \right)

Let us return now to the problem from the beginning of the article: what is the number of all possible combinations in the lottery game? Well, lets suppose that the game has 39 numbers of which 7 are chosen (the order is not important). First, we need to answer to our two questions. Since of 39 numbers we choose only 7, we conclude that NOT ALL elements are chosen. Also, we have already mentioned that the order of the chosen numbers IS NOT important. So, the answers are NO and NO and, by looking at the table, we conclude we are dealing with combinations of 7 from the set of 39 without repetition. By using table abvoe we get the formula:

C_{n}^{k}=\left( \begin{matrix} n \\ k \\ \end{matrix} \right)

In our case we have:

So, chances of having a winning lottery ticket are 1 in 15380937, or 1 in over 15 billions. Hmmm, can combinatorics and probability theory improve our chances? Another interesting thing to think about, isn’t it? 😉

Categories: High school math

Who am I?

October 9, 2012 Leave a comment

Hello everyone!

My name is Bojan Bogdanovich and I teach math at the Elementary school in Brestovac and at the High school in Bojnik in southern Serbia.

This blog is my attempt to make math more understandable and easier to learn. The main idea is to moderate between the complex and beautiful language of mathematics and everyday language so that highschool students can use what they learned with ease and more understanding.

All the articles are english translation of the ones written in serbian langugage that I wrote for my other blog Matematikon (notice ther’s no “h”). All translating to english is made by me so I apologize in advance for all the translation errors.

If you find any errors, please contact me so that I can correct them as soon as posible. I’m open for any creative suggestion.

Let’s help others to learn what we already know.

I wish you all happy “mathemathinking”. 😉

Bojan

Categories: About me