Combinatorial analysis

Combinatorial Analysis

Definition

The combinatorial analysis is the science that studies the formation of sets in all their forms, whether they are ordered or unordered.

Fundamental Counting Principle

Suppose that two events occur in order. If the first can occur in m ways and the second in n ways (after the first has occurred), then the two events can occur in order in m×n ways.

Definition of factorial notation

Definition

The product of the first n natural numbers is denoted by n! and is called n factorial:

\begin{equation*} n!=n\times \left( n-1\right) \times \cdots \times 3\times 2\times 1 \end{equation*}

Note

Zero factorial is defined as follows: 0!=1

An alternative is to define n! recursively on the non-negative integers

\begin{equation*} n!=\left\{ \begin{array}{l} 1\quad \text{if }n=0 \\ n(n-1)!\quad \text{if }n\geq 1% \end{array}% \right. \end{equation*}

As n increases, n! increases very rapidly.

For any fixed number a, n!>a^{n} for all n sufficiently large, on the other hand n!>n^{n} for all n.

Example

Calculate the following:

2!=2\times 1=2.\\ 3!=3\times 2\times 1=6.\\ 5!=5\times 4\times 3\times 2\times 1=120.\\ 10!=10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1=3628800.\\

Note

\begin{eqnarray*} 1/a!+b! &\neq &(a+b)!\quad 2/(a!)^{k}\neq (a^{k})! \\ 3/\frac{a!}{b!} &\neq &\frac{a}{b}\quad 4/a!\times b!\neq (a\times b)!. \end{eqnarray*}

Permutations

A permutation[1] is: an ordering of a number of distinct items in a line is denoted by (P[2]). Sometimes even though we have a large number of distinct items, we want to single out a smaller number and arrange those into a line; this is also a sort of permutation.

Definition

A permutation of n distinct objects is an arrangement of those objects into an ordered line. If 1≤k≤n (and k is a natural number) then an k-permutation of n objects is an arrangement of k of the n objects into an ordered line .

Example

There are 7 horses in a race

1/ In how many different orders can the horses finish?

We choose 7 horses from 7, so we use the definition of permutation as follow:

P_{n}^{n}=n!\\ P_{7}^{7}=7!=5040.

2/ In how many ways we choose the first,second, and third?

Here 3-permutations of 7 horses, there are 7 ways to choose the 6 ways to choose the second and 5 ways to choose the third.

A_{7}^{3}=7\times 6\times 5.

We can use the same reasoning to determine a general formula for the number of k-permutations of n objects:

Theorem

The number of k-permutations ( of n objects is n×(n-1)×⋯×(n-k+1) which is denoted by (A[3]). Thus, the number of k-permutations of n objects can be re-written as:

A_{n}^{k}=\dfrac{n!}{(n-k)!}

When n=k this gives

\dfrac{n!}{0!}=n!,

making sense of our definition that 0!=1.

Example

How many arrangements of the letters of the word REMAND are possible?

P_{6}^{6}=720.
  • How many arrangements of the letters of the word PARRAMATTA are possible?

In this word there is some repeated letter, so we are going to use the following rule:

P_{n}^{n_{1},n_{2},\cdots ,n_{k}}=\dfrac{n!}{n_{1}!\times n_{2}!\times \cdots \times n_{k}!}.\\ P_{10}^{2,2,4}=\dfrac{10!}{2!\times 2!\times 4!}=37800.
  • A person wanted to create a password for his email. What is the number of words that can be created that consist of

a/ 3 numbers with repetition

We note that we are faced with the following conditions

1/ The part of the whole

2/ Order is important

3/ Repetition is allowed

So we use k-permutations (arrangement) with repitition

A_{n}^{k}=n^{k}=A_{10}^{3}=10^{3}=1000.

b/ 5 numbers without repetition

We note that we are faced with the following conditions

1/ The part of the whole

2/ Order is important

3/ Repetition is not allowed

So we use k-permutations (arrangement) without repitition

A_{n}^{k}=% \dfrac{n!}{(n-k)!}\\ A_{10}^{3}=\dfrac{10!}{(10-3)!}=10\times 9\times8=720.

Properties

A_{1}^{1}=1\quad A_{1}^{0}=1\\ A_{n}^{0}=1\quad A_{n}^{n-1}=n!

Example

Calculate the following:

1/ A_{3}^{2}=\dfrac{3!}{(3-2)!}=\dfrac{3!}{1!}=3!=3\times 2\times 1=6.\\ 2/ A_{5}^{0}=\dfrac{5!}{(5-0)!}=\dfrac{5!}{5!}=1.\\ 3/ A_{4}^{4}=\dfrac{4!}{(4-4)!}=\dfrac{4!}{0!}=4!=4\times 3\times2\times 1=24.

Combinations

Sometimes the order in which individuals are chosen doesn't matter; all that matters is whether or not they were chosen.

Definition

Let n be a positive natural number, and 0≤k≤n. Assume that we have n distinct objects. An k-combination[5] of the n objects is a subset consisting of k of the objects. So a combination involves choosing items from a finite population in which every item is uniquely identified, but the order in which the choices are made is unimportant, this one is denoted by (C[4]).

We can use the same reasoning to determine a general formula for the number of k-combinations of n objects:

Theorem

The number of k-combinations of n objects is

C_{n}^{k}=\frac{n!}{k!(n-k)!}

Notation

We use \left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) to denote the number of k-combinations of n objects, so:

\left( \begin{array}{c} n \\ k% \end{array}% \right) =C_{n}^{k}=\frac{n!}{k!(n-k)!}

Note

We read \left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right)as " n choose k" so n choose k is \dfrac{n!}{k!(n-k)!},Notice that when k=n, we have

\left( \begin{array}{c} n \\ n% \end{array}% \right) =\frac{n!}{n!(n-n)!}=\frac{n!}{n!\times 0!}=1

coinciding with our earlier observation that there is only one way in which all of the n objects can be chosen. Similarly,

\left( \begin{array}{c} n \\ 0% \end{array}% \right) =\frac{n!}{0!(n-0)!}=\frac{n!}{0!\times n!}=1

there is exactly one way of choosing none of the n objects.

Properties

1/

C_{n}^{n}=1,\quad C_{n}^{1}=n,\quad C_{n}^{0}=1.

2/ For n,p∈ℕ and 0≤p≤n we have:

C_{n}^{p}=C_{n}^{n-p}

3/ For n,p∈ℕ and 1≤p≤n we have:

C_{n}^{p}=C_{n-1}^{p}+C_{n-1}^{p-1}

Example

We want to form a student committee of 5 students out of 10 students at the first year level and 15 students at the second year level.

a/ to find how many ways we can form this committee, we note that we are faced with the following conditions

  • The part of the whole

  • ∙Order is not important

  • Repetition is not allowed

So we use k-combinations without repitition:

C_{n}^{k}=\dfrac{n!}{k!(n-k)!}% =C_{25}^{5}=\dfrac{25!}{5!(25-5)!}=\dfrac{25\times 24\times 23\times 22\times 21}{5!}=53130

b/ Calculating the number of appropriate cases so that the committee includes two students from the first year level and three students from the second year level

we note that we are faced with the following conditions

  • The part of the whole

  • Order is not important

  • Repetition is not allowed

So we use k-combinations without repitition

C_{10}^{2}\times C_{15}^{3}=% \dfrac{10!}{2!(10-2)!}\times \dfrac{15!}{3!(15-3)!}=45\times 455=20475

Example

Calculate the following:

1/ C_{2}^{1}=\dfrac{2!}{1!(2-1)!}=\dfrac{2!}{1!\times 1!}=\dfrac{2\times 1}{1}=2.\\ 2/ C_{4}^{4}=\dfrac{4!}{4!(4-4)!}=\dfrac{4!}{4!\times 0!}=\dfrac{1}{0!}% =1.\\ 3/ C_{5}^{0}=\dfrac{5!}{0!(5-0)!}=\dfrac{5!}{0!\times 5!}=1.

Binomial Theorem

Theorem

For any a and b, and any natural number n, we have

\begin{equation*} (a+b)^{n}=\sum_{r=0}^{n}C_{n}^{r}a^{r}b^{n-r} \end{equation*}

One special case of this is that

\begin{equation*} (1+x)^{n}=\sum_{r=0}^{n}C_{n}^{r}x^{r} \end{equation*}

Example

Use the Binomial Theorem to evaluate the following:

1/ (x+4)^{2}=\sum% \limits_{i=0}^{2}C_{2}^{i}x^{i}4^{2-i}=C_{2}^{0}x^{0}4^{2}+C_{2}^{1}x^{1}4^{1}+C_{2}^{2}x^{2}4^{0}=16+8x+x^{2}.\\ 2/ (1-x)^{3}=\sum% \limits_{i=0}^{3}C_{3}^{i}1^{i}x^{3-i}=C_{3}^{0}1^{0}(-x)^{3}+C_{3}^{1}1(-x)^{2}+C_{3}^{2}1^{2}(-x)^{1}+C_{3}^{3}1^{3}(-x)^{0}=-x^{3}+3x^{2}-3x+1.
  1. Permutation

    Rerrangement.

  2. P: Permutations

  3. A: Arrangement

  4. C: Combinations

  5. Combination

    A union of separate parts.

PreviousPreviousNextNext
HomepageHomepagePrintPrint Public Domain licenceCreated with Scenari (new window)