Basic Combinatorics

Combinatorics is a branch of mathematics that is mainly concerned with counting. This branch gives us a reason to inspect the art of counting in more detail and it further proves to its readers that it's rewarding as well! 

In fact many of you might be familiar with the fundamental rule of counting. To put it more simply, you use this rule in your everyday life. 

But before jumping into what the rule is, and  the technicalities, consider the figure below,

We want to find the number of ways, in which we can travel from point $A$ to point $C$ via $B.$

In order to reach $B$ from $A$ we have $3$ options: to either travel by Ship $1,5$ and Boat $2.$ Finally, on reaching point $B$ there are again $2$ ways of moving to $C$ using either Boat $4$ or Ship $3.$

So, the total number of ways in which we can go to $C$ from $A$ via $B$ are as follows:

Ship $5$ and then Ship $3$ 

Ship $5$ and then Boat $4$ 

Ship $1$ and then Ship $3$ 

Ship $1$ and then Boat $4$ 

Boat $2$ and then Ship $3$ 

Boat $2$ and then Boat $4$

So, we see that there are total $6$ ways in which we can move from $A$ to $C$ via $B.$

But is there any way of arriving at this answer in a more efficient way? That is, a way which requires less work?

The answer to this is, yes. To see this, observe that,

To travel from $A$ to $B$ we have $3$ ways. And for each such way, we can go from $B$ to $C$ in $2$ different ways, so in total we have $3\times 2=6$ ways to go from $A$ to $C.$ 

Note that this is the same answer that we got previously. Also, what you did in the 2nd leg of the journey i.e. from $B$ to $C$ was totally independent of what you did in the 1st leg of the journey, i.e. travelling to $B$ from $A.$ Thus the choice of the ship or boat from $B$ to $C$ had nothing to do with the choice of the ship or boat from $A$ to $B.$ Hence, the $3$ choices for the first leg when paired off with each of the $2$ choices for the 2nd leg gives us $3\times 2 = 6$ possible ways for the flight from $A$ to $C.$

Before summarizing let us clarify two terminologies.  

Two options (of doing/performing an event say, moving from $A$ to $B$ as above;) are said to be mutually exclusive if choosing one option simply eliminates the other option. In other words, if we choose one option out of the two, then it automatically implies we can't choose the other option. For example, in moving from $A$ to $B$ we had three options, i.e. to either use Ship $1,5$ or Boat $2.$ We say all these $3$ options are mutually exclusive for, choosing to go by Ship $1$ automatically means that we've chosen not to go by Ship $5$ and Boat $2,$ as, we can't simultaneously travel in a ship and boat or in two different ships. Thus, choosing one option eliminates all the other options. Similarly, choosing to go by Ship $5$ automatically eliminates the choice to go by Ship $1$ and Boat $2$ and lastly, choosing to go by Boat $2$ automatically eliminates the possibility to go by Ship $1$ and Ship $5.$

Two events $P$ and $Q$ are said to be independent of each other if, the way in which we perform $P$ does not in any way influence the way in which we perform $Q.$ For example, our choice of the ship or boat in the 1st leg of  the journey from $A$ to $B$ does not influence the choice of the ship or boat in the 2nd leg of the journey from $B$ to $C$ in the example, we considered above. Similarly, the choice of the ship or boat in the 2nd leg of the journey from $B$ to $C$ does not depend upon our choice of the ship or boat in the 1st leg of  the journey from $A$ to $B.$ So, the event of moving from $A$ to $B$ and the event of moving from $B$ to $C$ are independent of each other.

Now, for the summarization,

Let $P$ and $Q$ be two events such that event $P$ can be performed in $m$ mutually exclusive ways and $Q$ can be performed in $n$ mutually exclusive ways. If $P$ and $Q$ are independent of each other then, the events $A$ and $B$ can together be performed in $m\times n$ different ways.

This is the rule of multiplication.

We prove the validity of this rule, by proving a much more general statement. The above version of the rule will then be seen as a direct corollary of the "much more general statement." 

Here's the generalized statement/ version of the above rule,

Let $P_1,P_2,...,P_n$ be $n$ events such that event $P_i$ (, $1\leq i\leq n$ ) can be performed in $p_i$ mutually exclusive ways. If  the $P_i$'s are independent of each other then, the events $P_1,P_2,...,P_n$ can together be performed in $p_1\times p_2\times p_n$ different ways.

This statement is what we call the Fundamental principle/rule of counting (FPC). 

Let's prove this generalized statement:

Given, each event $P_i$ (, $1\leq i\leq n$ ) can be performed in $p_i$ mutually exclusive ways. In particular,  the event $P_1$ can be performed in $p_1$ mutually exclusive ways. For each such way of performing the event $P_1$ there are $p_2$ different ways in which $P_2$ can be performed as the way in which $P_1$ occurs, does not influence the occurrence of  $P_2$ in any way. This means both the events $P_1$ and $P_2$ can occur together in $p_1\times p_2$ number of ways. We denote the event of occurrence of both $P_1$ and $P_2$ by $P_1\cap P_2.$ Now, for each such way (, out of those $p_1\times p_2$ ways) in which both $P_1\cap P_2$ can occur, the event $P_3$ can occur in $p_3$ different ways as, the way in which $P_1\cap P_2$  occurs, does not influence the occurrence of  $P_3$ in any way. This means both the events $P_1\cap P_2$ and $P_3$ can occur together in $p_1\times p_2\times p_3$ number of ways. We denote the event of occurrence of both $P_1\cap P_2$ and $P_3$  by $P_1\cap P_2\cap P_3.$ Now, repeating this argument a finite number of times and continuing in a similar way, we get that all the events $P_i$ (, $1\leq i\leq n$ ) can together be performed in $p_1\times p_2\times p_n$ different ways. This proves the statement. $\blacksquare$

Before moving on to some examples, there is one more thing that may be mentioned. We are going to present a new rule(, well, not really! You have been using it till now all implicitly and never bothered to look at it in a magnified way...) But even if this rule was not stated here, it wouldn't have been any problem for you. In fact, we are stating it, just as a custom.

Say, a task $T$ can be performed either through events $A$ and $B.$ Furthermore, let's asskme that $A$ and $B$ can be performed in $m$ and $n$ mutually exclusive ways respectively. For example, say the task $T$ is going from San Francisco to New York. We can do task $T$ through two events as follows:

1. Event $A$ consists of using either an automobile or a bus,

2. Event $B$ consists of using either an airplane, a jet, or a whirlybird.

Thus, event $A$ focuses upon going by land while event $B$ focuses on going through air.

Also, we see that $A$ can be performed in $m=2$ mutually exclusive ways and $B$ can be performed in $n=3$ mutually exclusive ways. 

Note that, the event $A$ and $B$ in itself are mutually exclusive to one another. For either you travel by land or through air. You can't travel through both the mediums at the same time!

Now, the question is, in how many ways can we perform the task $T$?

Well, the answer is $m+n=3+2=5$ ways.

So,  to summarize:

Let a task $T$ can be accomplished by performing either  of the events $E_1,E_2,\cdots,E_n$ such that each $E_i$ (,$1\leq i\leq n$) can be done in $m_i$ mutually exclusive ways. Then, the total number of ways in which $T$ can be accomplished is $\sum_{i=1}^n m_i$ number of ways.

This is an "obvious" thing. Isn't this what you've been using all your life? This so-called "rule" is probably embedded in a human mind naturally. In some books, this is given as the Rule of Addition. 

Ok, now move on to some examples.

Example 1: Frank goes to a library in Auburn, as it has a good collection of mathematics and history books. Frank wants to issue a mathematics book and a history book from a set of 50 mathematics books and 60 history books. In how many ways how can he do the same?

Solution. Ok, so this is a simple problem. The solution is just an application of  FPC. Note that the choice of a mathematics book has nothing to do with the choice of the history book and vice-versa. So, if $A$ and $B$ denotes respectively the events of choosing a mathematics and a history book, then, the number of ways in which both $A$ and $B$ can be done is $50\times 60.$  $\blacksquare$

Example 2:  A millionaire goes Alaska to spend a vacation. It's freezing cold outside. But he wants to go out. He needs a coat and a hat. He checks his baggage and finds that he has 25 coats and 10 hats with him at the moment. In how many ways, can he choose a coat and a hat?

Solution.  This is similar to the problem above. Yes, the answer is $25\times 10.$ $\blacksquare$

Example 3:  In how many ways can we arrange the $4$ letters $A,B,C,$ and $D$ to form a word of length $5?$

Solution.  Now, to solve this, think that you have $5$ blank places. And label them as Place No. $1,2,3,4$ and $5.$ Let $E_i$ (,$1\leq i\leq 5$) be the event of filling up Place No. $i$ with either of those $4$ letters. Now, each $E_i$ can be performed in $4$ mutually exclusive ways as we have $4$ letters. So, the total number of ways in which all the events $E_i$ can be accomplished or, in other words, the total number of ways in which we can arrange the $4$ letters $A,B,C,$ and $D$ to form a word of length $5$ is, $4\times 4\times 4\times 4\times 4=4^5.$ $\blacksquare$

Example 4:  In how many ways can we arrange the $4$ letters $A,B,C,$ and $D$ to form a word of length $3?$ But this time, we add an additional condition that no repetitions of letters are to be allowed, i.e., words like $AABC,DABB,BCCA$, etc are not allowed. 

Solution.  Now, to solve this, again think that you have $4$ blank places. And label them as Place No. $1,2,3,4$ and $5.$ Let $E_1,E_2$ and $E_3$ be $3$ events defined as follows:

• $E_1:$ Filling up Place No. $1$ with any one of the $4$ letters,
• $E_2:$ After filling up the 1st place, the event of filling up Place No. $2$ with any of the remaining $3$ letters,
• $E_2:$ After filling up the 1st and 2nd place, the event of filling up Place No. $3$ with any of the remaining $2$ letters.

Consider, $E_1.$ We can fill up the first place with any of those $4$ letters given, and so, we can perform $E_1$ in $4$ mutually exclusive ways. Now, for $E_2$ since no repetitions are allowed, we can only fill the 2nd place with the remaining $3$ letters. 

Ok, this might sound confusing at first. Let's get into more details.

Say, we placed the letter $A$ in the 1st position. Then, we can only place either of the letters from $B,C$ or $D$ in the 2nd place as it's mentioned that repetitions aren't allowed. So, this means that the 2nd place must contain a letter different from $A,$ (for if, we place $A$ in the 2nd position, repetitions of the letter $A$ occur in the $3$ letter word we are trying to form and by the problem's condition, this isn't allowed). Thus, we have $3$ mutually exclusive ways in which we can place a letter in the 2nd position. 

Similarly, if we had placed the letter $B$ in the 1st position. Then, we can only place either of the letters from $A,C$ or $D$ in the 2nd place as it's mentioned that repetitions aren't allowed. So, this means that the 2nd place must contain a letter different from $B,$ , i.e. it must contain either $A,C$ or $D.$ Thus, we have $3$ mutually exclusive ways in which we can place a letter in the 2nd position. 

By the same logic, 

If we had placed the letter $C$ in the 1st position. Then, we can only place either of the letters from $A,B$ or $D$ in the 2nd place, i.e. we'd have $3$ mutually exclusive ways in which we can place a letter in the 2nd position, and,

If we had placed the letter $D$ in the 1st position. Then, we can only place either of the letters from $A,B$ or $C$ in the 2nd place, i.e. we'd have $3$ mutually exclusive ways in which we can place a letter in the 2nd position.

So, in all the cases we find that, we are left with only $3$ (mutually exclusive) options of filling up the 2nd position, after, the 1st position is filled up. 

So, this is the reason why, we made the statement,

"Now, for $E_2$ since no repetitions are allowed, we can only fill the 2nd place with the remaining $3$ letters."

Hopefully, the reason behind the above statement is evident. Thus, we can perform $E_2$ in $3$ mutually exclusive ways. 

Now, by a similar reasoning we can say that we can fill the last, i.e. the 3rd place in $2$ mutually exclusive ways. (First, start with the assumption that the 2nd place has been filled in any of the $3$ ways. Then, note that, as the 1st position and 2nd position are filled, so we must have $2$ letters remaining out of which we have to place one of them in the 3rd position. Hence, we can conclude that $E_3$ can be performed in $2$ mutually exclusive ways.)

So, we have the following:

• $E_1$ can be performed in $4$ mutually exclusive ways,
• $E_2$ can be performed in $3$ mutually exclusive ways,
• $E_3$ can be performed in $2$ mutually exclusive ways

Now, the question is, what are the total number of ways in which all these $3$ events can be performed together? In other words, we now come to the question of finding the total number of ways in which we can arrange the $4$ letters in $3$ positions without any repetitions.

For this, simply note that the events $E_1,E_2$ and $E_3$ are independent of one another. 

A possible question may be: "But wait, how are these events independent of each other. We had the $3$ ways for performing  event $E_2$ just because of the 1st place was filled up by a letter (or, in other words, just because $E_1$ was performed). Also, we had the $2$ ways for performing  event $E_3$ since the 1st and 2nd places were filled up by a letter (or, in other words, just because $E_1$ and $E_2$ were performed)."

 Note the definitions of the events $E_1,E_2$ and $E_3.$ Just for the sake of clarity, let us again write those definitions here:

• $E_1:$ Filling up Place No. $1$ with any one of the $4$ letters,
• $E_2:$ After filling up the 1st place, the event of filling up Place No. $2$ with any of the remaining $3$ letters,
• $E_2:$ After filling up the 1st and 2nd place, the event of filling up Place No. $3$ with any of the remaining $2$ letters.

Note that, in the definition of event $E_2,$ the words, "after filling up the 1st place" are important. Which $3$ symbols contribute to Event $E_2$ is dependent on event $E_1,$ but the event $E_2$ by definition, is the choice of the three remaining symbols (say, $B,C$ or $D$, if $A$ is placed in the 1st position) that can be placed in the 2nd position. This choice (of whether to put $B,C$ or $D$ in the 2nd place) does not in any way influenced by the event $E_1.$   

Following a similar line of reasoning, we may say that the event $E_3$ is independednt of events $1$ and $2.$ 

Hence, by FTC, we can say that, the number of ways in which $E_1,E_2$ and $E_3$ together is equal to $4\times 3\times 2.$ $\blacksquare$

We are now in a position to make an important point. This last example is a problem of rearrangement.

But first let's define the concept of rearrangement.

Well, suppose you've got $n$ distinct symbols and you want to create all words of length $r\leq n.$  So, this process is what is termed as rearrangement of $n$ symbols (taking $r$ symbols at a time). So, in the last example, $n=4$ and $r=3.$

This procedure of arranging $n$ distinct symbols or objects taking $r$ objects at a time without repetition is broadly called a permutation or more precisely, a permutation of $n$ distinct objects taking r at a time. In this case, $n=4,r=3.$

Now, we try to derive a formula for a more general version of the last example. To state this more explicitly, we desire a solution to the problem below:

Find the total number of ways in which we can arrange $n$ objects taking $r$ symbols at a time without repetition.

So, we proceed as follows.

Like the last example, we start by considering $r$ distinct blanks. The number of ways to fill the first blank is $n.$ The number of ways to fill the second blank is $n-1.$ (We reason just as we did in the last example.)  Continuing with a similar line of reasoning the number of ways to fill the rth blank is $n-r+1.$ 

Thus, the total number of ways to fill all the $r$ blanks is $n(n-1)(n-2)\cdots (n-r+1)\tag 1$ $\blacksquare$

The number of ways in which we can arrange $n$ distinct objects taking $r$ symbols at a time without repetition is denoted by the symbol $P(n,r).$ 

In fact, $P(n,r)=n(n-1)(n-2)\cdots (n-r+1).$ But, $(1)$ can be written in a much more compact form as $P(n,r)=\frac{n!}{(n-r)!r!}.$

Example 5:  Find the number of $6$ letter words that can be formed from the word, "PQRSTUVWX".

Solution.  The answer to this question is just the permutation of $9$ letters in the given word given taking $6$ at a time. This is equal to $P(9,6).$ $\blacksquare$

We define $P(n,0)=1.$

Example 6:  Find the number of $6$ letter words that can be formed from the word, "PQRSTUVWX".

Solution.  The answer to this question is just the permutation of $9$ letters in the given word given taking $6$ at a time. This is equal to $P(9,6).$ $\blacksquare$

Next, we want to presenta very popular type of problem, often called as the "Rank Problem."

Example 7:  Find the rank of the word "TEXAS".  By this question, we mean to find the number of permutations of the letters that come before the given word in lexicographic order. We add the condition that repetitions of letters is NOT allowed.

Solution.  This question can be solved as follows:

• We find the alphabet that comes first in the English alphabet list, from the letters T,E,X,A,S which is namely, A.
• Next, we try to find the number of $5$ letter words that can be formed  using the letters of TEXAS such that the 1st position  contains A. Now, this is precisely equal to $4!.$
• Now, the next letter that comes after $A$ in English alphabet list, from the letters of TEXAS is, $E.$ Similar to what we did above, we try to find the number of $5$ letter words that can be formed  using the letters of TEXAS such that the 1st position  contains E. Now, this is again equal to $4!.$
•  The next letter that comes after $E$ in English alphabet list, from the letters of TEXAS is, $S.$ Similar to what we did above, we try to find the number of $5$ letter words that can be formed  using the letters of TEXAS such that the 1st position  contains S. Now, this is again equal to $4!.$
• The next letter that comes after $S$ in English alphabet list, from the letters of TEXAS is, $T.$ We try to find the number of $5$ letter words that can be formed  using the letters of TEXAS such that the 1st and 2nd position  contains T and A respectively. The number of such words is $3!$
• Now, we've come very near to the word TEXAS. We now consider TEA in the 1st three positions (since E comes after A among the letters in the word given). The number of such words is $2!$
• Proceeding in the same way, the next 5 letter words with 1st three positions as TES is also $2!$
• Next, the word that we shall consider in sequence is TEXAS. 
• So, the rank of this word is: $3\times 4!+3!+2\times 2!+1=83.$ $\blacksquare$

Example 6:  Find the number of $7$ letter words that can be formed from the word, "SEATTLE".

We give two solutions to this example. More specifically, the 2nd solution is more shorter. But we advise to read both the solutions to gain a better understanding.

Solution (1).  This is a bit different from the problems that we're solving till now. You might expect that the answer is, $7!.$ But the answer is not so, however! Note that when we talked about permutations, i.e. gave its definitions, properties, etc we did mention an important word that holds much more meaning given this context.

Let us repeat again, 

"The number of ways in which we can arrange $n$ distinct objects taking $r$ symbols at a time without repetition is denoted by the symbol $P(n,r).$"

Note the word, "distinct".

In this problem, the answer would've been $7!$ if all the $7$ letters in the word were distinct. But that's not the case here, the objects namely the letters are repeating. For instance, we have $2$ T's and $2$ E's. But that's not a thing to worry!  To solve this problem, lets assume that all the letters are distinct. Then we have a total of $7!$ possible words. Note that, out of this $7!$ words, we've counted some words more than once. To see why it's so, let us first denote the 1st two T's appearing in the given word, by $T_1$ and $T_2$ respectively and the two E's appearing in the given word, by $E_1$ and $E_2$ respectively. 

Now, the word:

$SE_1AT_1T_2LE_2$ is counted in the those $7!$ possible words.

Next, the word, $SE_2AT_1T_2LE_1$ is also counted in the those $7!$ possible words.

Similarly, the words, $SE_1AT_2T_1LE_2$  and $SE_2AT_2T_1LE_2$ are also counted in those $7!$ possible words. 

But observe that, all these $4$ words are actually referring to the same word, i.e. $SEATTLE.$ When saying that the total number of such words possible to be equal to $7!$ we're treating each $T$ and $E$ distinct from the other $T$ and $E.$ That's the reason we were getting the answer as $7!.$ 

This happens precisely for each possible rearrangement of the word, SEATTLE. (For e.g., the word, SEEATTL is also counted $4$ times when we got the answer $7!.$)

Let $n$ be the 'real' number of ways, in which the letters in the SEATTLE is arranged without any overcounting ( and by considering the two E's indistinct and the 2 T's indistinct). Then we have the following: $$4n=7!\implies n=\frac{7!}{4}.$$

So, the answer that we desired is simply, $n=\frac{7!}{4}.$ $\blacksquare$

Solution (2). Consider a possible rearrangement of the word, SEATTLE and name it $W.$ Assume that all the letters are distinct. Now, $W$ has the 4 letters $T$ and $E$ (two each), in some positions say, $t_1,t_2,e_1,e_3.$ What we mean is,  the first $T$ in $W$ is at the position number $t_1,$ the 2nd $T$ in $W$ is at the position number $t_2,$ the first $E$ in $W$ is at the position number $e_1$ and the second $R$ in $W$ is at the position number $e_2.$ (We are counting the positions from the left, say $W$ is the word, $SEATTEL$ then, the values of $t_1,t_2,e_1,e_2$ are respectively, $4,5,2,6$ respectively. Can you see why?)

We assumed the each letter in SEATTLE distinct (,i.e. the two $E$ 's in the word are considered to be different. For convenience, you may label them as $E_1,E_2$ respectively, and so on), and hence, keeping the letters in all the positions except, the positions $t_1$ and $t_2$ fixed, the word W can be arranged in $2!$ different ways and we call this event, $A_1.$ Again,  keeping the letters in all the positions except, the positions $e_1$ and $e_2$ fixed, the word W can be arranged in $2!$ different way and we call this event $A_2.$

So, in total, we can say that, the event $A_1$ and $A_2$ (, or more formally, the event $A_1\cap A_2$) can be performed in $2!\times 2!$ number of ways. (Note that, the events $A_1$ and $A_2$ are independent of each other and thus, we applied FTC.)

So, in conclusion, we found that the single word $W$ (, which is an arbitrary rearrangement of the word SEATTLE ) shall correspond to $2!2!$ different words, if we consider all the letters in the word SEATTLE to be distinct. 

Now, the total number of ways the letters of the word SEATTLE can be arranged amongst themselves considering all letters to be distinct, is $7!.$

Also, say, the total number of ways the letters of the word SEATTLE can be arranged amongst themselves (but this time, not considering all the letters to be distinct, i.e. this time we consider the two T's and E's to be the same (or same type of ) letter/object or better say, indistinct), be $n.$

Then each such word, counted in $n$ corresponds to $2!2!$ different words, if we consider all the letters in the word SEATTLE to be distinct. 

So we may write, $n2!2!=7!.$ This means, $n=\frac{7!}{2!2!}.$ $\blacksquare$

Now, we proceed to generalize the above example.

Example 7: Suppose we've $n$ objects(/letters/symbols or whatever...) and out of them, $k_1$ objects are of Type $1$, $k_2$ objects are of Type $2$,...,$k_r$ objects of Type $r.$ Find the total number of ways in which these $n$ objects can be arranged in a line.

Solution. First, we assume that all the $n$ objects are distinct. Then, the total number of ways then can be arranged in a line, is $n!.$ 

Next, for each possible rearrangement of the $n$ objects in a line, we see that, it's counted, $k_1!k_2!\cdots k_r!$ times in the $7!$ ways.

Let the total number of true rearrangements (i.e. considering the the objects of same type indistinct), be $p.$ Then, similar to the above example, we must have, $p\times k_1!k_2!\cdots k_r!=n!\implies p=\frac{n!}{k_1!k_2!\cdots k_r!}.$

This means, the total number of ways in which the $n$ objects can be arranged is $p=\frac{n!}{k_1!k_2!\cdots k_r!}.$ $\blacksquare$

The above example can be summarized as an important result as follows:

Suppose we've $n$ objects(/letters/symbols or whatever...) and out of them, $k_1$ objects are of Type $1$, $k_2$ objects are of Type $2$,...,$k_r$ objects of Type $r.$ Then, the total number of ways in which these $n$ objects can be arranged in a line is $\frac{n!}{k_1!k_2!\cdots k_r!}.$

Next, we move on to combinations.

Let's start with an example.

David goes to a Vinyl Record Store. He just got his bonus from his work and (he) wants to buy some good old records.  There were many but he finally makes up his mind and wants puts 5 records on his wishlist: Frank Sinatra's Best Hits, Nat King Cole: The Essentials, Dean Martin: Those Good Old Days, Louis Armstrong: The Best Jazz Hits and The Ultimate Oldies Collection and let's denote them by the letters, F,N,D,L,O respectively. He notices his budget's limited and he can only buy $3$ of them. Now, the question is: In how many ways, can he select 3 records out of those 5 records from his wishlist?

Let us make the questions very clear. We DON'T WANT the number of ways of arranging $5$ objects taken $3$ at a time in a line. We are interested in the number of ways in which we can just choose those 3 records not the order in which we choose. So as to say, the choice F,N,D is no different than the choice F,D,N or N,D,F or D,N,F, etc. The order in which we choose the records does not matter at all (e.g. we may choose F first, N second and D last or in some another order), but what matters only, is the records that we choose. This is the motivation of the problem. We repeat this point again, to make it clearer:

We can choose any 3 records in any possible orders but all what matters is, what did we choose and not in how we chose them. Thus, F,D,N or D,N,F or F,N,D or N,D,F ,etc all correspond to one and only one choice namely, the choice of choosing the records Frank Sinatra's Best Hits, Nat King Cole: The Essentials and Dean Martin: Those Good Old Days. We are thus, interested in counting the number of such choices possible.

Ok, so first of all, we try to find the number of ways in which we can arrange those 5 records in a line taken 3 at a time. The answer is then, $P(5,3)=60$ ways. But note that, for a particular choice of $3$ records, say, $F,N,D$ we may arrange them in $3!=6$ ways along a line.

So, any choice of $3$ records out of those $5,$ corresponds to $6$ different arrangements.

The question we want to answer, is exactly, how many such choices of 3 records can be made out of those 5 records and thus, let us denote this number by $c.$

Each such choice corresponds to $6$ different arrangements which are included/ counted/ taken into account, among the total $60$ ways.

Hence, we must have, $6c=60\implies c=10.$ 

This means, the total number of ways in which we can choose $3$ of those $5$ records is equal to $c=10.$

(We hope that you see why this is equation $6c=60$ is valid. You may want to go through this problem again. Don't hesitate, read again for a better clarity. A suggestion that I may give, is, to do the problem by yourself after having gone through the whole solution. But while solving this yourself, forget what you read in the solution and see if you can proceed. If you get stuck in some part, look in the above solution about how did I handle it in there, and then take that as a hint and proceed again with the remaining part. You may want to repeat this many times, or many days (I'm not joking!) until you can feel what's happening. Consider that you mastered this fundamental notion, only, if you are succesfull in explaining this whole thing to an imaginary student whom you should consider to know nothing about combinations. You may consider an imaginary student. Believe me, this often helps! All in all, try to visualize the things. Often coming back to this after a few days, or hours may help unexpectedly.)

So what we did above, constitutes the concept of combinations.

In combinations, the basic problem is to find, the number of ways in which we can choose $r(\leq n)$ of $n$ distinct objects. 

We now try to find this number explicitly.

We do the same thing that we did above. The number of ways of arranging $n$ objects in a line, taking $r$ at a time, is $P(n,r).$ Now, for each "choice" of $r$ objects, there are $r!$ arrangements corresponding to it which are included in those $P(n,r)$ number of ways. Hence, if the total number of choices be $c$ then, we have, $r!c=P(n,r).$ 

Thus, $c=\frac{P(n,r)}{r!}$ is our desired answer.

To summarize,

The number of ways in which we can choose $r$ of $n$ distinct objects is $\frac{P(n,r)}{r!}.$ We denote this number by the symbol, $\binom nr.$

We have thus, gave the notion of combinations.

Next, a few examples will make it clearer.

Example 7:  Find the number of ways to choose $5$ players from a group of $10$ players for a baseball team.

Solution. The answer is simply $\binom{10}{5}.$ (Why?) $\blacksquare$

Example 7:  Find the number of ways to choose $5$ players from a group of $10$ players for a baseball team.

Solution. The answer is simply $\binom{10}{5}.$ (Why?) $\blacksquare$

Example 8:  Find the number of diagonals in a hexagon (A hexagon is a polygon having $6$ sides).

$

Solution. Each diagonal has two endpoints. The number of ways in which we can choose $2$ points in a hexagon is $\binom 62.$ But we must consider the fact if the two points chosen are consecutive to each other, then the line segment obtained by joining those two points, is not a diagonal instead, it's just a side of the hexagon. So, each such choice of consecutive points corresponds to one and only one side of the hexagon. So, we must subtract the number of sides from the total number of ways of choosing $2$ points out of $6$ points to get the total number of diagonals. Hence, the desired answer is $\binom 62-2.$  $\blacksquare$

Example 9:  Find the number of nonnegative solutions of the equation, $x_1+x_2+x_3=3.$

 

Solution. Let's start with an easier problem to understand the concept. Consider the equation \(x + y = 5\).

We can list the solutions for this equation like this:

$\begin{array}{|c|c|c|}\hline x & y & \text{Binary Sequence} \\\hline 5 & 0 & 111110 \\4 & 1 & 111101 \\3 & 2 & 111011 \\2 & 3 & 110111 \\1 & 4 & 101111 \\0 & 5 & 011111 \\\hline\end{array}$

In the last column, the binary sequence shows 5 ones (1’s) and one zero (0) for each solution. The zero represents the \(+\) sign, which separates the values of \(x\) and \(y\). The number of 1’s before the zero shows the value of \(x\), and the number of 1’s after the zero shows the value of \(y\).

There are no other solutions, as you can see from the list. Each solution corresponds to a different way to arrange five 1’s and one 0 in a sequence. The number of such arrangements is:

$\frac{6!}{5!1!} = 6$

So, there are exactly 6 solutions to the equation \(x + y = 5\) in nonnegative integers.

Let's continue solving the original problem, \(x_1 + x_2 + x_3 = 3\), using the method introduced in the simplified example.

To find the number of nonnegative solutions for \(x_1 + x_2 + x_3 = 3\), we can use a similar approach with binary sequences.

Imagine a sequence of 1's representing the total sum, and place 0's to separate the values of \(x_1\), \(x_2\), and \(x_3\). Each arrangement of 1's and 0's corresponds to a unique solution.

To visualize, here are all the sequences and their corresponding solutions:

$\begin{array}{|c|c|c|c|}\hline\text{Sequence} & x_1 & x_2 & x_3 \\\hline 11100 & 3 & 0 & 0 \\11010 & 2 & 1 & 0 \\11001 & 2 & 0 & 1 \\10110 & 1 & 2 & 0 \\10101 & 1 & 1 & 1 \\10011 & 1 & 0 & 2 \\01110 & 0 & 3 & 0 \\01101 & 0 & 2 & 1 \\01011 & 0 & 1 & 2 \\00111 & 0 & 0 & 3 \\\hline\end{array}$

Each sequence above corresponds to a solution for \(x_1 + x_2 + x_3 = 3\).

For this problem, we have:

- 2 zeros (0's), representing the separation between \(x_1\), \(x_2\), and \(x_3\).

- 3 ones (1's), representing the total value of 3, where the number of 1's between two zeros represents the value of the integer variable $x_2$ (if no 1's exist then $x_2=0$ naturally), the number of $1$'s at the beginning before the first $0$ represents the value of the integer variable $x_1$ (if no 1's exist then $x_1=0$ naturally) and the number of $1$'s at the end after the last $0$ represents the value of the integer variable $x_3$ (if no 1's exist then $x_3=0$ naturally).

Each unique sequence of these ones and zeros represents a solution to the equation. We need to count how many different sequences we can create.

To solve this, we can find the number of permutations of a sequence with 3 ones and 2 zeros. This is given by:

$\frac{5!}{3!2!}$

Breaking it down:

- \(5!\) is the factorial of 5, which counts all possible arrangements of five elements.

- \(3!\) accounts for the repeated arrangements of 1's.

- \(2!\) accounts for the repeated arrangements of 0's.

So, we have:

$\frac{5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (2 \times 1)} = \frac{120}{6 \times 2} = \frac{120}{12} = 10$

Thus, there are 10 nonnegative solutions to the equation \(x_1 + x_2 + x_3 = 3\). $\blacksquare$