Chapter 1 — Combinatorics
Overview
I am starting this series to share my limited knowledge on the topic of Probability Theory. Each post would cover one topic at a time. The intended audience for this series are:
- Students and professionals who are looking to get a gentle introduction to theory of probability in a non-intimidating way (hopefully :) )
- Students and professional who want to dive deep in to study of Data Science, AI and ML. Basic understanding of Probability theory is almost always needed before you start your journey for becoming an expert in Data Science, AI and ML.
This is the first post in this series and I intend to start with a very basic introduction to get started.
Definition
Referring to Wikipedia
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.
Mastering Combinatorics topic will help you understand and/or solve problems related to counting. This will help you answering questions like:
- If a bag has 5 balls (numbered 1 to 5) then in how many ways can you pick 2 balls from this bag
- What are the number of possible outcomes when two dices are rolled together
Understanding combinatorics is essential first step towards understanding theory of probability. We will see later (specially in future posts of this series) as why is this the case.
Factorials and Binomial Coefficients
Understanding mathematical definition of factorial and binomial coefficients is needed to understand the basic concepts of combinatorics.
Factorial
Factorial is a mathematical function (F) that takes a number as input(X) and produce another number as output (Y)
Y = F(X) (X≥0 and Y>0)
Here is F(X) is nothing but the multiplication of first X integers (starting 1).
X = 0 is a special case for which Y=1.
F(X) is also represented as X! (X followed by an exclamation mark).
In other words Y = F(X) = X! = X * ( X-1) * (X-2) *……. * 4 * 3 * 2 * 1
1! = 12! = 2 * 1 = 23! = 3 * 2 * 1 = 64! = 4 * 3 * 2 * 1 = 24100! = 100 * 99 * 98 …. 3 * 2 * 1 = 9.332621544× 10 ^ 157
Side Note: You might have noticed that X! can also be written in terms of (X-1)! as => X! = X * (X-1) !. This might be an obvious observation here but this trick helps a lot in simplifying complex mathematical equations. Application of this trick will be seen in future posts.
Binomial Coefficients
Before jumping on to binomial coefficients, we will have a quick look at binomial theorem and coefficients first.
As per Wikipedia:
In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial (x + y)^n into a sum involving terms of the form a* x^b * y^c, where the exponents b and c are nonnegative integers with b + c = n, and the coefficient a of each term is a specific positive integer depending on n and b. For example, for n = 4,
Binomial coefficients are nothing but coefficients that exist in algebraic expansion. Below is the note on how binomial coefficients are represented and calculated.
Permutation & Combination
Permutation is counting of number of ways a set of objects can be arranged in different ways. For example, if we have 3 students (A, B and C) in a class and 3 empty chairs (1, 2 and 3) in that class, then following are permutations that are possible for students to occupy those chairs:
- A->1, B->2, C->3
- A->1, B->3, C->2
- A->2, B->1, C->3
- A->2, B->3, C->1
- A->3, B->1, C->2
- A->3, B->2, C->1
So total 6 possible permutations ( or 6 different ways) exist for making 3 students sit on 3 different chairs. Another way to think about this problem is to think in following order:
- For A, there are 3 options to select a chair
- For B (assuming A already occupied a chair), there are 2 options remaining to select a chair
- For C (assuming A and B already occupied chairs), there is only 1 chair left.
- Combining above 3: Total number of ways A,B and C can occupy chair is 3*2*1 = 6 = 3!
To generalize it further, for N students to sit on N chairs, there are N! different ways to assign the chairs to students.
There are also variations of arrangement counting problems that exist in practice and we will look at those scenarios in following sections
Ordered Set + With Repetition
In this class of the problems, order of the results matter. A better way to understand this class of problem would be to look at couple of examples.
Rolling the dice
Lets say we roll a 6 faced dice twice. Possible number of outcomes would in this case would be 36. Reasoning behind the math is:
- On first roll there number of possible outcomes is 6
- On second roll the number of possible outcomes is 6
So total number of possible outcomes is 6*6=36
In other words, possible results would be:
11, 12, 13, 14, 15, 16
21, 22, 23, 24, 25, 26
31, 32, 33, 34, 35, 36
41, 42, 43, 44, 45, 46
51, 52, 53, 54, 55, 56
61, 62, 63, 64, 65, 66
Above the first digit represent the possible outcome of the first roll and second digit represent the possible outcome of second roll. Combining all possible outcomes result in 6 X 6 matrix shown above.
An important observation to make here is that output of the dice roll could be repeated. I mean if you get 1 on first roll then you could very well get 1 on second roll. Same goes with 2, 3, 4, 5 and 6.
Generalizing it further, if the dice had N faces instead of 6 then this matrix would of size N x N.
Taking above observation a step further, we would have N x N x N possible dice roll results if we were to roll the dice thrice. Generalizing this observation, we can say that if an N faced dice is rolled P times then would be N^P (N to the power P) possible arrangements.
Pick Coins From Box
Let’s say we have a box with 1 cent ( C ), 1 nickel( N),1 dime( D) and 1 quarter( Q) (total 4 coins). Now we pick one coin from the box, put it back and pick a coin again. If we were to note down the outcome of both the coin picks then we would get 16 different observations. Reasoning behind the math can be understood quickly by looking at all possible results that I have noted down below
CN, CD, CC, CQ
NC, ND, NN, NQ
DC, DN, DD, DQ
QC, QN, QQ, QD
As we observed in dice roll example above, first coin pick has 4 possible outcomes and so does the second pick. This results in 4x4 possible combinations, resulting in 16 possible arrangements.
Now generalizing this, if we had N coins in the box then it would result in NxN possible arrangements. Generalizing it a step further, if we were to make P picks from the box then there would be NxNxN…N (P times) arrangements (or in other words N^P arrangements).
Ordered Set + Without Repetition
Problems in this set vary slightly as compared to the scenario where repetition of selection was allowed. Intuitively this should result in reduction in possible total number of outputs. And we will see soon that this intuition is actually accurate mathematically.
To understand this class of permutation best its good to refer to an example. Given no repetition is allowed, following example fits the constraint nicely.
Let’s say we have 3 girls (A, B, C) who want to ride horses and there are exactly 3 horses (X, Y and Z) available. Now following are the possible arrangements possible in this case:
Another way to think about this is:
- A has 3 horses to choose from.
- Once A has made the choice, B will have 2 horses to choose from.
- Once A and B have selected the horses, C will have 1 horse left to go with.
Above can be represented mathematically as 3x2 as number of possible arrangement.
Now if we had N horses instead of 3 then:
- A would have N horses to choose from
- B would have N-1 horses to choose from
- C would have N-2 horses to choose from
Now if we were to generalize it even further and say that have R girls (G1, G2…Gp) and they have N horses to choose from, then:
- G1 will have N horses to choose from
- G2 will have N-1 horses to choose from
- ..Gp will have N-R+1 horses to choose from.
Mathematically total number of arrangements can be represented as Nx(N-1)x(N-2)….(N-R+1)
Or, [Nx(N-1)x(N-2)…(N-R+1)x(N-R)x(N-R-1)….x3x2x1]/[N-R)x(N-R-1)….x3x2x1]
or N!/(N-R)!
or nPr (n=N and r=R here, I changed the case for sake of presentation).
This is also called partial permutation scenario where we are looking at arrangement of subset (R out of N horses) of a given set.
Unordered Set + Without Repetition
Let’s go back to scenario we discussed earlier where we needed to find the number of arrangements for assigning horses to girls. In that example we cared about the order as well. However if we do not care about the order then AX,BY,CZ is equivalent to AX,CZ,BY. To understand this graphically, not caring about order means we have mirror image across the green line.
If we cared about order then number of arrangements in this case would be N!/(N-R)! where N was number of horses and R was number of girls. Considering that ordering is not important, the number of arrangements here would be N!/( (N-R)! * R! )
number_of_unordered_without_repeat_arrangements = number_of_ordered_without_repeat_arrangements/R!Here R is size of the subset to be choosen.N!/((N-R)! * R!) can also be represented as nCr (N choose R) binomial coefficient.
Now the intuition behind dividing by R! is that it represents the number of ways a set of R elements can be arranged in ordered (basic ordered permutation) manner. And because for unordered case we need to get rid of dupicate counts (as mirror image above demonstrated), we need to divide the ordered count by R!.
Now this approach could also be generalized for the scenario where we needed to choose horses for R girls and B boys. In this case we need to select a total of (R+B) horses. However because order withing girls and boys do not matter, total number of possible arrangements would be nP(r+b)/(r! * b!). This equates to N!/(N-R-B)!*R!*B!
Unordered Set + With Repetition
If you deep dive and try to understand two theorems mentioned on Wikipedia then it will become lot easier to tackle this class of problem.
Let’s consider an example problem to understand this class of problem better. A box has 9 beads of different colors (Red, Blue and Green). A boy is asked to make 3 picks from box (with replacement) and note down the colors each time. Whats the possible number of outcomes observed here. Please note that from an unordered perspective, RGB==BGR
Below is the handwritten note on how to handle this
Summary
We learned how to solve different categories/types of counting problems. Below is the bullet list of primary take aways from this post.
- N! = N*(N-1)*(N-2)*(N-3)…3*2*1.
- Number of ways n items can be arranged is n!
- Ordered, With Repetition: Choosing k items from n has n^k (n to the power k) possibilities.
- Ordered, No Repetition: Choosing k items from n where repetition in selection is not allowed has n!/(n-k)! or nPk possible arrangements
- Unordered, Without Repetition: Choosing k items from n where order does not matter and repetition in selection is not allowed has nCk or n!/(k! * (n-k)!) possible arrangements
- Unordered, With Repetition: Choosing k items from nwhere order does not matter and repetition is allowed has (n+k-1)C(k-1) or (n+k-1)!/((k-1)!* n!) possible arrangements.
