Combinations and their Properties. Pascal's Triangle

Combinations of k elements from n different elements are all possible arrangements, that contain k elements, taken from n given elements. Arrangements differ from each other if they contain different elements. For example, abc, acd are different arrangements, but `abc,bca` are same combinations.

Difference between combinations and permutations is that in combinations ORDER is NOT IMPORTANT!.

There are two forms of combinations:

  1. without repetitions - every element in combination can occur only once (for example, combinations without repetitions from n=4 elements a,b,c,d of k=2 elements are following: ab,ac,ad,bc,bd,cd. Note that combination like aa is not allowed here).
  2. with repetitions - every element in combination can occur more than once (for example, combinationss with repetitions from n=4 elements a,b,c,d of k=2 elements are following: aa,ab,ac,ad,bb,bc,bd,cc,cd,dd; combinations with repetitions from n=2 elements a,b of k=4 elements are aaaa,abab,abbb,bbbb).

Number of combinations without repetitions of k elements from n elements is `C_n^k=(n!)/((n-k)!k!)`, where `k<=n`, `C_n^0=1`. Sometimes number of combinations can be denoted by `([k],[n])`.

Number of combinations with repetitions of k elements from n elements is `bar(C)_n^k=C_(n+k-1)^k=((n+k-1)!)/((n-1)!k!)`.

Example 1. Suppose we have ten people. In how many ways we can form jury consisting of 4 people?

Note, that order is not important here. So, we use formula for combinations without repetitions: `C_(10)^4=(10!)/((10-4)!4!)=(10!)/(6!4!)=210`.

Example 2. Suppose in the shop we can buy meringues, eclairs and biscuits. How many different 9-cake sets can be formed?

Here order is not important, but each type of cake can occur more than once. Therefore, we use formula for combinations with repetitions: `bar(C)_3^9=C_(3+9-1)^9=C_11^9=(11!)/((11-9)!9!)=(11!)/(2!9!)=(11*10*9!)/(2!9!)=110/2=55`.

Following properties are true for the combinations without repetitions:

  1. `C_n^k=C_n^(n-k)`;
  2. `C_n^k+C_n^(k+1)=C_(n+1)^(k+1)`.

With the help of properties of combinations we can create table for finding combinations without repetitions `C_n^k` when n=2,3,4,... . First of all note, that `C_0^0=1` and `C_n^0=C_n^n=1`.

Now, using property 2 we have that

`C_2^0=1,C_2^1=C_1^0+C_1^1=1+1=2,C_2^2=1`;

`C_3^0=1,C_3^1=C_2^0+C_2^1=1+2=3`,

`C_2^2=C_2^1+C_2^2=2+1=3,C_3^3=1`.

Now, lets draw found numbers in the form of triangular table, shown to the right.pascal triangle

It is clear that next row of this table contains numbers `C_4^0,C_4^1,C_4^2,C_4^3,C_4^4`. The leftmost and rightmost elements of each row equals 1, and each of other members equals sum of two elements that are situated above it (for example, in fourth row first 3=1+2 and second 3=2+1). In a similar manner we obtain next rows. As result we have triangular table that is called Pascal's triangle.

pascal triangle

n-th row of this table contains numbers `C_n^0,C_n^1,C_n^2,...,C_n^n`.