Skip to main content

Combinatorics

Let n and p be two non-zero natural numbers. The number of sequences of p elements belonging to a set of n elements is np{{n}^{p}}.

Let E and F be two non-empty sets. If CardE=pCard E=p and Card F=nCard\text{ F}=n, then the number of functions defined on E with values in the set F is np{{n}^{p}}.

Factorials

0 !=10\,!=1 (by definition).

1!=1

2!=1⋅21\cdot 2=2

3!=1⋅2⋅31\cdot 2\cdot 3=6

4!=1⋅2⋅3⋅41\cdot 2\cdot 3\cdot 4=24

......

n!= 1⋅2⋅3⋅...⋅n, n≥11\cdot 2\cdot 3\cdot ...\cdot n\text{, }n\ge 1

Properties: n !=(n−1) !nn\,!=\left( n-1 \right)\,!n; n !=(n+1) !n+1n\,!=\frac{\left( n+1 \right)\,!}{n+1}

Permutations

Definition: A set together with a fixed order of its elements is an ordered set, written (a1,a2,...,an)\left( {{a}_{1}},{{a}_{2}},...,{{a}_{n}} \right).

Definition: The permutations of a set AA with nn elements are all the ordered sets that can be formed from the nn elements of nn. The number of permutations of nn elements, n∈N∗n\in {{N}^{*}}, is Pn=1⋅2⋅3⋅...⋅n=n !{{P}_{n}}=1\cdot 2\cdot 3\cdot ...\cdot n=n\,!;

Pn=n(n−1) !=nPn−1,(∀)n∈N∗{{P}_{n}}=n(n-1)\,!=n{{P}_{n-1}},(\forall )n\in {{\mathbb{N}}^{*}} the recurrence formula

Arrangements

Definition: The arrangements of n elements taken m at a time (m≤n)\left( m\le n \right) of a set AA are all the ordered subsets of mm elements that can be formed from the nn elements of the set AA, taken nn at a time. They are written AnkA_{n}^{k}.

The number of arrangements of nn elements taken k at a time is:

Ank=n(n−1)...(n−k+1)=n !(n−k) !, n≥mA_{n}^{k}=n\left( n-1 \right)...\left( n-k+1 \right)=\frac{n\,!}{\left( n-k \right)\,!},\,n\ge m; p,n∈Np,n\in \mathbb{N}.

Properties:Ann=Pn, A_{n}^{n}={{P}_{n}},\,  Ann=n !0 !\,A_{n}^{n}=\frac{n\,!}{0\,!} or Ann=n !A_{n}^{n}=n\,!;An0=1A_{n}^{0}=1

Ank=(n−k+1)Ank−1A_{n}^{k}=(n-k+1)A_{n}^{k-1} Ann=Ann−1A_{n}^{n}=A_{n}^{n-1};.

Combinations

Definition: The combinations of n elements taken k at a time (k≤n)\left( k\le n \right) of a set AA with nn elements are all the subsets of k elements that can be formed from the nn elements of the set AA. They are written CnkC_{n}^{k}.

Properties:

1) Cn1=n ; Cnn=Cn0=C00=1 ;C_{n}^{1}=n\,;\,C_{n}^{n}=C_{n}^{0}=C_{0}^{0}=1\,; Cnk=n !k !(n−k) !C_{n}^{k}=\frac{n\,!}{k\,!\left( n-k \right)\,!};

2) Cnk=AnkPpC_{n}^{k}=\frac{A_{n}^{k}}{{{P}_{p}}} n,k∈N, 0≤k≤n, Cnk∈N∗\text{n,k}\in \mathbb{N}\text{, 0}\le \text{k}\le \text{n, }C_{n}^{k}\in {{\mathbb{N}}^{*}}

3) The formula for complementary combinations: Cnk=Cnn−k ;C_{n}^{k}=C_{n}^{n-k}\,;

4) The decomposition formula for combinations:  Cnk=Cn−1k+Cn−1k−1 ;\,C_{n}^{k}=C_{n-1}^{k}+C_{n-1}^{k-1}\,;

n,k∈N, 0≤k≤n, Cnk∈N∗\text{n,k}\in \mathbb{N}\text{, 0}\le \text{k}\le \text{n, }C_{n}^{k}\in {{\mathbb{N}}^{*}}

Cnk=Cn−2k+2Cn−2k−1 +Cn−2k−2C_{n}^{k}=C_{n-2}^{k}+2C_{n-2}^{k-1}\,+C_{n-2}^{k-2}

Cnk=Cn−3k+3Cn−3k−1 +3Cn−3k−2+Cn−3k−3C_{n}^{k}=C_{n-3}^{k}+3C_{n-3}^{k-1}\,+3C_{n-3}^{k-2}+C_{n-3}^{k-3}

5) The number of subsets of a set with nn elements is 2n{{2}^{n}};

6) Cnm=Cn−1m−1+Cn−2m−1+...+Cm+1m−1+Cmm−1+Cm−1m−1 ;C_{n}^{m}=C_{n-1}^{m-1}+C_{n-2}^{m-1}+...+C_{m+1}^{m-1}+C_{m}^{m-1}+C_{m-1}^{m-1}\,;

e.g.: C73=C62+C52+C42+C32+C22;C_{7}^{3}=C_{6}^{2}+C_{5}^{2}+C_{4}^{2}+C_{3}^{2}+C_{2}^{2};

7) n!p1!p2!...pk!=Cnp1⋅Cn−p1p2...Cn−(p1+...+pk−1)pk\frac{n!}{{{p}_{1}}!{{p}_{2}}!...{{p}_{k}}!}=C_{n}^{{{p}_{1}}}\cdot C_{n-{{p}_{1}}}^{{{p}_{2}}}...C_{n-({{p}_{1}}+...+{{p}_{k-1}})}^{{{p}_{k}}} where p1+...+pk−1<n{{p}_{1}}+...+{{p}_{k-1}}<n.

The binomial theorem

(x+a)n=Cn0xn+Cn1xn−1a+...+Cnkxn−kak+...+Cnnan=∑k=0nCnkxn−kak\displaystyle {{\left( x+a \right)}^{n}}=C_{n}^{0}{{x}^{n}}+C_{n}^{1}{{x}^{n-1}}a+...+C_{n}^{k}{{x}^{n-k}}{{a}^{k}}+...+C_{n}^{n}{{a}^{n}}=\sum\limits_{k=0}^{n}{C_{n}^{k}{{x}^{n-k}}{{a}^{k}}},

(x−a)n=Cn0xn−Cn1xn−1a+...+(−1)kCnkxn−kak+...+(−1)nCnnan{{\left( x-a \right)}^{n}}=C_{n}^{0}{{x}^{n}}-C_{n}^{1}{{x}^{n-1}}a+...+{{\left( -1 \right)}^{k}}C_{n}^{k}{{x}^{n-k}}{{a}^{k}}+...+{{\left( -1 \right)}^{n}}C_{n}^{n}{{a}^{n}} where n∈Nn\in N.

Properties:

1) The term of rank k+1k+1 is Tk+1=(−1)kCnkxn−kak{{T}_{k+1}}={{\left( -1 \right)}^{k}}C_{n}^{k}{{x}^{n-k}}{{a}^{k}}

2) Cnk+1=n−kk+1Cn+1k+1 ; Cn+1k+1=n−kk+1CnkC_{n}^{k+1}=\frac{n-k}{k+1}C_{n+1}^{k+1}\,;\,C_{n+1}^{k+1}=\frac{n-k}{k+1}C_{n}^{k}

3) Tk+2=n−kk+1axTk+1{{T}_{k+2}}=\frac{n-k}{k+1}\frac{a}{x}{{T}_{k+1}} or Tk+2=−n−kk+1akTk+1{{T}_{k+2}}=-\frac{n-k}{k+1}\frac{a}{k}{{T}_{k+1}}

4) The number of terms in the expansion (x±a)n{{\left( x\pm a \right)}^{n}} is n+1n+1

5) The coefficients of terms equally distant from the ends are equal.

6) Cn0,Cn1,...,Cnn C_{n}^{0}, C_{n}^{1} ,..., C_{n}^{n}\, are called binomial coefficients.

Important relations:

Cn0+Cn1+...+Cnn=2n ; C_{n}^{0}+C_{n}^{1}+...+C_{n}^{n}={{2}^{n}}\,;\, Cn0−Cn1+...+(−1)nCnn=0 ;C_{n}^{0}-C_{n}^{1}+...+{{\left( -1 \right)}^{n}}C_{n}^{n}=0\,;

Cn0+Cn2+Cn4+...=2n−1; C_{n}^{0}+C_{n}^{2}+C_{n}^{4}+...={{2}^{n-1}};\,  Cn1+Cn3+Cn5+...=2n−1;\,C_{n}^{1}+C_{n}^{3}+C_{n}^{5}+...={{2}^{n-1}};

C2nn=(Cn0)2+(Cn1)2+...+(Cnn)2C_{2n}^{n}={{\left( C_{n}^{0} \right)}^{2}}+{{\left( C_{n}^{1} \right)}^{2}}+...+{{\left( C_{n}^{n} \right)}^{2}}

We arrange numbers in the table below, placing CnkC_{n}^{k} at the intersection of row nn with column kk. Since k≤nk\le n, the table is filled in only below the main diagonal, so its shape is triangular. This array is called "Pascal's triangle" or the "arithmetic triangle".

Each number at the intersection of row nn with column kk is obtained by adding the number directly above it, at the intersection of row n−1n-1 with column kk, to the one to its left at the intersection of row n−1n-1 with column k−1k-1.

Pascal's triangle (1665):
figure

|

n

Common particular expansions:

1)(a±b)2=a2±2ab+b2;{{\left( a\pm b \right)}^{2}}={{a}^{2}}\pm 2ab+{{b}^{2}};

2)(a+b+c)2=a2+b2+c2+2(ab+bc+ac) ;{{\left( a+b+c \right)}^{2}}={{a}^{2}}+{{b}^{2}}+{{c}^{2}}+2\left( ab+bc+ac \right)\,;

3)(a+b)3=a3+3a2b+3ab2+b3;{{\left( a+b \right)}^{3}}={{a}^{3}}+3{{a}^{2}}b+3a{{b}^{2}}+{{b}^{3}};

4)(a−b)3=a3−3a2b+3ab2−b3{{\left( a-b \right)}^{3}}={{a}^{3}}-3{{a}^{2}}b+3a{{b}^{2}}-{{b}^{3}}

5)(a+b+c)3=a3+b3+c3+3(a2b+a2c+b2a+b2c+c2a+c2b)+6abc{{\left( a+b+c \right)}^{3}}={{a}^{3}}+{{b}^{3}}+{{c}^{3}}+3\left( {{a}^{2}}b+{{a}^{2}}c+{{b}^{2}}a+{{b}^{2}}c+{{c}^{2}}a+{{c}^{2}}b \right)+6abc

6)(a+b)4=a4+4a3b+6a2b2+4ab3+b4{{\left( a+b \right)}^{4}}={{a}^{4}}+4{{a}^{3}}b+6{{a}^{2}}{{b}^{2}}+4a{{b}^{3}}+{{b}^{4}}

The sum of like powers of the first n natural numbers

If Sk=1k+2k+...+nk,k∈N{{S}_{k}}={{1}^{k}}+{{2}^{k}}+...+{{n}^{k}},k\in N, then we have:

S1=n(n+1)2;S2=n(n+1)(2n+1)6;S3=[n(n+1)2]2;{{S}_{1}}=\frac{n\left( n+1 \right)}{2};{{S}_{2}}=\frac{n\left( n+1 \right)\left( 2n+1 \right)}{6};{{S}_{3}}={{\left[ \frac{n\left( n+1 \right)}{2} \right]}^{2}};

S4=n(n+1)(6n3+9n2+n−1)30;S5=n2(n+1)2(2n2+2n−1)12{{S}_{4}}=\frac{n\left( n+1 \right)\left( 6{{n}^{3}}+9{{n}^{2}}+n-1 \right)}{30};{{S}_{5}}=\frac{{{n}^{2}}{{\left( n+1 \right)}^{2}}\left( 2{{n}^{2}}+2n-1 \right)}{12}.

∑k=1n2k=n(n+1),n∈N\displaystyle \sum\limits_{k=1}^{n}{2k}=n(n+1),n\in \mathbb{N} ∑k=1n(2k−1)=n2,n∈N\displaystyle \sum\limits_{k=1}^{n}{(2k-1)}={{n}^{2}},n\in \mathbb{N}

A relation that allows Sk{{S}_{k}} to be computed once Sk−1,Sk−2,...,S1{{S}_{k-1}},{{S}_{k-2}},...,{{S}_{1}} are known is Pascal's formula:

(n+1)p+1=1+Cp+11Sp+Cp+12Sp−1+...+Cp+1pS1+n{{\left( n+1 \right)}^{p+1}}=1+C_{p+1}^{1}{{S}_{p}}+C_{p+1}^{2}{{S}_{p-1}}+...+C_{p+1}^{p}{{S}_{1}}+n