Compilation of elementary results related to permutations and combinations: Pre RMO, RMO, IITJEE math

1. Disjunctive or Sum Rule:

If an event can occur in m ways and another event can occur in n ways and if these two events cannot occur simultaneously, then one of the two events can occur in m+n ways. More generally, if E_{i} (i=1,2,\ldots,k) are k events such that no two of them can occur at the same time, and if E_{i} can occur in n_{i} ways, then one of the k events can occur in n_{1}+n_{2}+\ldots+n_{k} ways.

2. Sequential or Product Rule:

If an event can occur in m ways and a second event can occur in n ways, and if the number of ways the second event occurs does not depend upon how the first event occurs, then the two events can occur simultaneously in mn ways. More generally, $if E_{1} can occur in n_{1}, E_{2} can occur in n_{2} ways (no matter how E_{1} occurs), E_{3} can occur in n_{3} ways (no matter how E_{1} and E_{2} occur), \ldots, E_{k} can occur in n_{k} ways (no matter how the previous k-1 events occur), then the k events can occur simultaneously in n_{1}n_{2}n_{3}\ldots n_{k} ways.

)3. Definitions and some basic relations:

Suppose X is a collection of n distinct objects and r is a nonnegative integer less than or equal to n. An r-permutation of X is a selection of r out of the n objects but the selections are ordered. 

An n-permutation of X is called a simply a permutation of X.

The number of r-permutations of a collection of n distinct objects is denoted by P(n,r); this number is evaluated as follows: A member of X can be chosen to occupy the first of the r positions in n ways. After that, an object from the remaining collections of (n-1) objects can be chosen to occupy the second position in (n-1) ways. Notice that the number of ways of placing the second object does not depend upon how the first object was placed or chosen. Thus, by the product rule, the first two positions can be filled in n(n-1) ways,….and all r positions can be filled in

P(n,r) = n(n-1)\ldots (n-r+1) = \frac{n!}{(n-r)}! ways.

In particular, P(n,n) = n!

Note: An unordered selection of r out of the n elements of X is called an r-combination of X. In other words, any subset of X with r elements is an r-combination of X. The number of r-combinations or r-subsets of a set of n distinct objects is denoted by n \choose r (read as ” n ‘choose’ r). For each r-subset of X there is a unique complementary (n-r)-subset, whence the important relation {n \choose r} = n \choose {n-r}.

To evaluate n \choose r, note that an r-permutation of an n-set X is necessarily a permutation of some r-subset of X. Moreover, distinct r-subsets generate r-permutations each. Hence, by the sum rule:

P(n,r)=P(r,r)+P(r,r)+\ldots + P(r,r)

The number of terms on the right is the number of r-subsets of X. That is, n \choose r. Thus, P(n,r)=P(r,r) \times {n \choose r}=r! \times {n \choose r}.

The following is our summary:

  1. P(n,r) = \frac{n!}{(n-r)!}
  2. {n \choose r}=\frac{P(n,r)}{r!}=\frac{n!}{r! (n-r)!}=n \choose {n-r}

4. The Pigeonhole Principle: Basic Version:

If n pigeonholes (or mailboxes) shelter n+1 or more pigeons (or letters), at least 1 pigeonhole (or mailbox) shelters at least 2 pigeons (or letters).

5. The number of ways in which m+n things can be divided into two groups containing m and n equal things respectively is given by : \frac{(m+n)!}{m!n!}

Note: If m=n, the groups are equal (and hence, indistinguishable), and in this case the number of different ways of subdivision is \frac{(2m)!}{2!m!m!}

6. The number of ways in which m+n+p things can be divided into three groups containing m, n, p things severally is given by: \frac{(m+n+p)!}{m!n!p!}

Note: If we put m=n=p, we obtain \frac{(3m)!}{m!m!m !} but this formula regards as different all the possible orders in which the three groups can occur in any one mode of subdivision. And, since there are 3! such orders corresponding to each mode of subdivision, the number of different ways in which subdivision into three equal groups can be made in \frac{(3m)!}{m!m!m!3!} ways.

7. The number of ways in which n things can be arranged amongst themselves, taking them all at a time, when p of the things are exactly alike of one kind, q of them are exactly alike of a another kind, r of them are exactly alike of a third kind, and the rest are all different is as follows: \frac{n!}{p!q!r!}

8. The number of permutations of n things r at a time, when such things may be repeated once, twice, thrice…up to r times in any arrangement is given by: n^{r}. Cute quiz: In how many ways, can 5 prizes be given away to 4 boys, when each boy is eligible for all the prizes? (Compare your answers with your friends’ answers :-))

9. The total number of ways in which it is possible to make a selection by taking some or all of n things is given by : 2^{n}-1

10. The total number of ways in which it is possible to make a selection by taking some or all out of p+q+r+\ldots things, whereof p are alike of one kind, q alike of a second kind, r alike of a third kind, and so on is given by : (p+1)(q+1)(r+1)\ldots-1.

Regards,

Nalin Pithwa.

Basic Enumeration once again

Prove the following identity (a):

\sum_{k=0}^{n}\left\{ \begin{array}{c} n \\ k \end{array} \right\}x(x-1)\ldots(x-k+1)=x^{n}

Prove the following identity (b):

\sum_{k=0}^{n}\left [ \begin{array}{c} n \\ k \end{array} \right] = x(x+1)\ldots(x+n-1)

Prove the following identity (c);

\sum_{k=0}^{n}(-1)^{k}\left\{ \begin{array}{c} n \\ k \end{array} \right\}\left[ \begin{array}{c} k \\ j \end{array} \right]= 1, if j=n and is 0, otherwise.

General Hint for all three problems: Please see Wikipedia for Stirling numbers!

Hint (a):

If x is an integer, both sides of the first identity  count mappings of an n element set into an x-element set.

Hint (b):

Both sides count pairs (\pi, \alpha) where \pi is a permutation of an n-element set S, and \alpha is a coloration of S with x colors invariant under \pi.

Hint (c):

Combine the identities in (a) and (b).

Solution (a):

Suppose first that x is a positive integer. Let |X|=x and |N|=n. The number of mappings of N into X is x^{n}. On the other hand, let k denote the cardinality of the range of a mapping of N into X. For k fixed, we can specify in \left\{ \begin{array}{c} n \\ k \end{array} \right\} ways which elements of N are mapped onto the same element of X. Once this partition of N is specified, we have to find an image for each class of it, distinct images for distinct classes. This can be done is x(x-1)\ldots(x-k+1) ways. Thus,

\left\{ \begin{array}{c} n \\ k \end{array}\right\}x(x-1)\ldots(x-k+1)

is the number of mappings of N  into X with range of cardinality k. This proves the identity when x is a positive integer. But this means that if we consider x as a variable the polynomials on the two sides have infinitely many values in common. Therefore, they must be identical.

Solution (b):

Again, we may assume that x is a positive integer. If a permutation \pi of a set S has exactly k cycles, then

x^{k}, then x^{k} is the number of x-colorations of S invariant under \pi. The left hand side of the identity sums these numbers for all permutations \pi of S=\{ 1 \ldots n \}. A given x-coloration of S is counted k_{1}!\ldots k_{x}! times, where k_{i} is the number of elements with color i. The number of occurrences of a given sequence k_{1},\ldots, k_{x} is

\frac{n!}{k_{1}!\ldots k_{x}!} and so, (fill this missing gap in proof) this sum is

\sum_{(k_{1},\ldots,k_{x}>0) (k_{1}+\ldots+k_{x}=n)}\frac{n!}{k_{1}!\ldots k_{x}!}k_{1}!\ldots k_{x}!

which equals

n! {{x+n-1}\choose n}=x(x+1)\ldots (x+n-1)

Solution (c):

Homework and do send comments, suggestions, questions…

More later,

Nalin Pithwa

 

 

Basic Enumeration continued

Problem (a): Find recurrence relations for the Stirling partition numbers 

\left \{ \begin{array}{c}    n \\    k \end{array} \right \} and the Stirling cycle numbers 

\left [ \begin{array}{c}    n \\    k \end{array} \right ] and tabulate them for n \leq 6.

Problem (b): Prove that 

\left \{ \begin{array}{c}    n \\    n-k \end{array} \right \} and

\left [ \begin{array}{c}    n \\    n-k \end{array} \right ] are polynomials in n for each fixed k.

Problem (c): Show that there is a unique way to extend the definition of

\left \{ \begin{array}{c}    n \\    k \end{array} \right \} and

\left [ \begin{array}{c}    n \\    k \end{array} \right ] over all integers n and k so that the recurrence relations in (a) are preserved and the “boundary conditions” 

\left \{ \begin{array}{c}    0 \\    0 \end{array} \right \} which equals

\left [ \begin{array}{c}    0 \\    0 \end{array} \right ]=1

and \left \{ \begin{array}{c}    0 \\    m \end{array} \right \} which equals

\left [ \begin{array}{c}    m \\    0 \end{array} \right ]=0 (m \neq 0) are fulfilled. 

Problem (d):

Prove the duality relation:

\left \{ \begin{array}{c}    n \\    k \end{array} \right \} is equal to

\left [ \begin{array}{c}    -k \\    -n \end{array} \right ].

Hints:

Hint (a):

Possible recurrence relations are

\left \{ \begin{array}{c}    n + 1 \\    k \end{array} \right \} which is equal to the sum of

\left \{ \begin{array}{c}    n \\    k -1 \end{array} \right \} and

k \left \{ \begin{array}{c}    n \\    k \end{array} \right \}.

Hint (b):

Observe that in a partition of n elements into n-k classes, at least n-2k classes must be singletons.

Hint (c):

For the Stirling partition numbers, write the recurrence relations in (a) as

\left \{ \begin{array}{c}    n\\    k-1\end{array} \right \} is equal to the sum of

\left \{ \begin{array}{c}    n+1\\    k \end{array} \right \} and

-k \left \{ \begin{array}{c}    n \\    k \end{array} \right \} to get a recurrence for negative values of k.

Hint (d):

\left \{ \begin{array}{c}    n\\    k\end{array} \right \} and

\left [ \begin{array}{c}    -k\\    -n\end{array} \right ] satisfy the same recurrence and boundary conditions.

More later,

Nalin Pithwa.

 

 

 

Basic enumeration

Question.

We have k distinct postcards and want to send them all to our friends ( a friend can get any number of postcards, including 0). How many ways can this be done? What happens if we want to send at least one card to each friend?

Hint:

Decide now about the postcards. The answer to this question is n! {k \choose n}.

Solution:

I. We have to decide about the postcards independently. Any postcard can be sent to any of the n friends. Hence, the result if n^{k}.

II. Let C_{1},C_{2}\ldots C_{k} be the cards. The set S=\{ C_{1},C_{2},\ldots C_{k}\} must be split into n disjoint non-empty sets S_{1},\ldots, S_{n}. Thus, \{ S_{1},S_{2}\ldots S_{n}\} is a partition of S. From any partition of S into n (non-empty) classes we get n! possibilities to send out the postcards. Hence, the answer is n! {k \choose n}.

More later,

Nalin Pithwa

Permutations and combinations — an application to Statistical Mechanics

In Statistical Mechanics, one  encounters the situation of putting k particles into r distinct energy levels. The particles can thus be considered as discrete objects and the different energy levels as distinct boxes or cells. Three different situations are obtained by making  three different assumptions. These are:

a) Maxwell-Boltzmann: Here the particles are all distinct and any number of particles can be put into any of the r boxes. The number of possibilities are r^{k} as given by the following theorem:

Let M be a multi set consisting of r distinct objects, each with infinite multiplicity. Then, the total number of d-permutations of M is r^{d}.

b) Bose-Einstein: Here the particles are all identical and any number of particles can be put in any one of the r boxes. The number of possibilities is k+r-1 \choose k as given by the following theorem:

The following sets are in bijective correspondence:

i) The set of all increasing sequences of  length  k on an ordered set with r elements.

ii) The set of all the ways of putting k identical objects into  r distinct boxes.

iii) The set of all the k-combinations of a multi-set with r distinct elements. 

c) Fermi-Dirac: Here the particles are all identical  but no  box can hold more than one particle. The number of possibilities is r \choose k.

More later…

Nalin Pithwa