COMBINATIONS

"Nature is an endless combination and repetition of a very few laws. She hums the old well-known air through innumerable variations"

~ Ralph Waldo Emerson (American Poet, Lecturer and Essayist, 1803-1882)

Every living being is a combination of various cells. Every inanimate object around us is a combination of atoms. Every machine is a combination of various individual parts. For example, your car has the gear shaft, brakes, accelerator, engine, steering wheel etc…..What matters most to you is that the car has all these essential parts rather than the internal arrangement of these parts. Or consider treating your friends on your birthday. All that is important is that which of your friends come, not the order in which they sit around the table. Thus all your friends constitute a selection where the order is completely unimportant. Such a selection is called a COMBINATION.

Consider another scenario. Suppose you are at a candy shop that has say 20 types of chocolates. You decide to buy 5 chocolates, each of a different type. Here choosing 5 different chocolates is important than the order in which you pick them. By rule of product, there are

20*19*18*17*16=$\frac{20!}{15!}$= P(20,5)

possibilities of choosing 5 chocolates from 20 in succession and without replacement. Since the order in which chocolates are chosen is not important, we remove 5!(corresponding to permutations of 5 chocolates). Therefore :

$\frac{20!}{5!15!}$= 15504 ways!!

The number of ways in which you can choose 5 chocolates out of 20 is called C(20,5), read as 20choose 5 and is equal to 15504.

More generally, the number of ways in which r objects from n distinct objects , with no reference to order is given by

C(n,r)=$\frac{P(n,r)}{ r!}$ = $\frac{n!}{ r!(n-r)!)}$ 0≤r≤n.

Further,

For all n≥0 , C(n,0)=C(n,n)=1.

For n≥1, C(n,1)=C(n,n-1)=n

When 0≤n≤r, then C(n,r)=0

COMBINATIONS WITH REPETITIONS

In the previous example of picking chocolates, we picked 5 different chocolates that is to say no two chocolates chosen were identical. Or in other words, repetition wasn’t allowed. If we were to say that you could pick more than one chocolate of a given type then it becomes a more intriguing problem. This brings us to a concept called Combinations with repetitions, meaning, the number of combinations of n objects taken r at a time, with repetition. The following example illustrates this concept.

Let us say there are five flavors of ice cream: banana, chocolate, lemon, strawberry and vanilla. You can have three scoops. How many variations could there be? Let's use letters for the flavors: {b, c, l, s, v}. Example selections would be {c, c, c} (3 scoops of chocolate) {b, l, v} (one each of banana, lemon and vanilla) {b, v, v} (one of banana, two of vanilla)

(And just to be clear: There are n=5 things to choose from, and you choose r=3 of them.
Order does not matter, and you can repeat!)

Here’s a special technique that lets you work it out.

	Think about the ice cream being in containers, you could say "skip the first, then 3 scoops, then skip the next 3 containers" and you will end up with 3 scoops of chocolate!
	So, it is like you are ordering a robot to get your ice cream, but it doesn't change anything, you still get what you want.

Now you could write this down as (arrow means skip, circle means scoop)

In fact the three examples above would be written like this:

{c, c, c} (3 scoops of chocolate):
{b, l, v} (one each of banana, lemon and vanilla):
{b, v, v} (one of banana, two of vanilla):

OK, so instead of worrying about different flavors, we have a simpler problem to solve: "how many different ways can you arrange arrows and circles"

Notice that there are always 3 circles (3 scoops of ice cream) and 4 arrows (you need to move 4 times to go from the 1st to 5th container).

So (being general here) there are r + (n-1) positions, and we want to choose r of them to have circles.

This is like saying "we have r + (n-1) pool balls and want to choose r of them". In other words it is now like the pool balls problem, but with slightly changed numbers. And you would write it like this:

where n is the number of things to choose from, and you choose r of them (Repetition allowed, order doesn't matter)

Interestingly, we could have looked at the arrows instead of the circles, and we would have then been saying "we have r + (n-1) positions and want to choose (n-1) of them to have arrows", and the answer would be the same ...

This brings us to a formula derived by a celebrated mathematician Leonhard Euler(1707-1783).

So, what about our example, what is the answer?

(5+3-1)!	=	7!	=	5040	= 35
3!(5-1)!		3!×4!		6×24

Euler’s derivation of the formula for combinations with repetitions:

Suppose we have n distinct objects. We can label them with the integers from 1 to n. Now consider a k-combination, that is, an unordered selection of k integers, possibly with repetitions, from among 1....n, say i₁, i₂, ..., i_k. Even though we do not care about the order, we can certainly arrange the selected integers in order, for convenience in counting the possibilities. Suppose therefore that the sequence i₁, i₂, ..., i_k is in increasing order (but not strictly). Then the sequence

i₁, i₂+1, i₃+2, ..., i_k+(k-1)

is a strictly increasing sequence of k integers selected from the integers from 1 to n+k-1. Moreover each such sequence can occur. The number of such sequences is the number of k-combinations, without repetition, from n+k-1 distinct objects. Thus the number of k-combinations, with repetitions, from n distinct object is

Here is another way to view k-combinations: suppose we have n distinct cells (boxes) and k indistinguishable objects (think of x's) to place in the cells. How many ways can it be done? Order the cells, so we can refer to them by number. Lay out the objects (the x's) in a line. Place dividers between them to divide them into lots that go in successive cells. We will require n-1 dividers. A configuration of objects and dividers looks like

xxx|xx|xxxx|||xx|xxx

Here 3 x's go in the first cell, 2 x's in the second, 4 x's in the third, none in the fourth, and so on. Each such configuration is completely determined by the location of the dividers. Thus we must choose n-1 locations out of a total of n+k-1 locations for the dividers. This can be done in C(n+k-1,n-1)= C(n+k-1,k) ways.

Now the configuration above can also be described without the dividers simply by labelling each x according to the cell it goes in, for example by using successive letters of the alphabet. Thus the configuration above could be described by

aaabbccccffgg

We see immediately that C(n+k-1,n-1)= C(n+k-1,k) is equal to the number of possibly distinct partial derivatives of total order k for a function of n variables.

Alternatively you could adopt a whole new approach to solve such problems. If you are allergic to the use of formulae , then the following method could work wonders for you-

Suppose that you want to choose, with repetition and disregarding order, n objects of k distinct types. You can encode each selection as a binary sequence like this:

- Take k - 1 0's and n 1's; the 0's function as markers to separate the distinct kinds of objects, while the 1's represent the selected objects.

- The sequence has the form 1...101...101.....1.
To give an example, suppose that you have three objects, {a,b,c} and choose 5 of them each time; then typical selections will look like (disregarding order):

aabcc, abbbc, bbccc, aaacc, etc.

And the corresponding sequences are: 1101011, 1011101, 0110111, 1110011

Note that you need only two 0's to distinguish three kinds, and that the sequences begins, ends, or have consecutive 0's if at least one of the kinds is not selected.

But then you reduced the original problem to the one of counting a particular class of binary sequences which is typically much easier: the sequences will have length n + k - 1, and k - 1 0's; as C(m,j) counts the number of length m sequences with j 1's, then you have C(n + k - 1,n). There, that’s not so difficult isn’t it?

How many ways can I select 15 cans of soda from a cooler containing large quantities of Coke,

Pepsi, Diet Coke, Root Beer and Sprite?

• We have to model this problem using the chart:

Coke Pepsi Diet Coke Root Beer Sprite

A: 111 111 111 111 111 =15

B: 11 111111 111111 1 =15

C: 1111 1111111 1111 =15

• Here, we set an order of the categories and just count how many from each category are chosen.

• Now, each event will contain fifteen 1’s, but we need to indicate where we transition from one

Category to the next. If we use 0 to mark our transitions, then the events become:

A: 1110111011101110111

B: 1100111111011111101

C: 0011110111111101111

• Thus, associated with each event is a binary string with #1’s = #things to be chosen and #0’s =

#transitions between categories.

• From this example we see that the number of ways to select 15 sodas from a collection of 5 types of

soda is C(15 + 4,15) = C(19,15) = C(19,4).

• Note that #zeros = #transitions = #categories -1.

• Theorem: The number of ways to fill r slots from n

categories with repetition allowed is:

C(r + n-1, r) = C(r + n -1, n -1).

• In words, the counts are:

C(#slots + #transitions, #slots)

The number of combinations of three letters a,b,c arranged two at a time is:

$\frac{(3+2-1)!}{2!(3-1)!}$ =6

a,a /a,b / a,c / b,b / b,c/ c,c

Problems involving combinations with repetitions can also be solved using a table like the one that follows:

Here n= no of distinct objects and r is the no. of objects selected at a time.

The concept of combinations with repetitions can be used not only to find the number of ways a selection can be made in real life situations, but also to determine the time-efficiency of various algorithms. Thus it is an extremely useful concept in discrete mathematics.

By.

Deepthi P Hudedagaddi and

(deepthiph@gmail.com)

Pallavi Ravishankar

(pallavi23ravi@gmail.com)