To prove $\frac{n!}{p!q!}$.

Question

The number of permutaion of n objects, where p and are of one kind,q are of second kind,are of different kind is $\frac{n!}{p!q!}$

How can we proove above theorem $\frac{n!}{p!q!}$.I tried to prove this but I failed,I checked internet for the proof but I didn't find anything useful.In my book, it only states the definition of the theorem.I used my useful time to solve the above problem and I solved it but that was lengthy.

Answer 1

Here is one way of looking at it:

First consider the case where there are $n$ objects and $p$ of these are the same:

Consider the number of permutations on a finite set $A$, that is, the bijective functions $f:A \to A$. It is easy to see that there $|A|!$ such functions.

Now pick a subset $S \subset A$, the idea being that all elements in $S$ are equivalent. In particular, we say two permutations $f,g$ are equivalent, or $f \sim g$ iff $f(k) = g(k)$ for all $k \notin S$ and $f(S) = g(S)$ (where $f(S) = \{ f(s) | s \in S\}$. It is not hard to show that this is an equivalence relation that partitions the permutations into equivalence classes $[f]$.

To determine the number of elements $|[f]|$ in an equivalence class, we note that it is the same as the number of bijections $b:S \to S$, which is, as noted above, $|S|!$.

Since each equivalence class has the same number of elements, the total number of distinct equivalence classes is ${|A|! \over |S|! }$.

Now suppose there are two subsets $S_1 \subset A, S_2 \subset A$ with $S_1 \cap S_2 = \emptyset$. Say two permutations $f,g$ are equivalent, or $f \sim g$ iff $f(k) = g(k)$ for all $k \notin S_1 \cup S_2$ and $f(S_1) = g(S_1)$ and $f(S_2) = g(S_2)$.

To determine the number of elements $|[f]|$ in an equivalence class, we note that it is the same as the number of pairs of bijections $(b_1,b_2)$ where $b_1:S_1 \to S_1$, $b_2:S_2 \to S_2$. It is easy to see that there are $|S_1|! |S_2|!$ such pairs.

Since each equivalence class has the same number of elements, the total number of distinct equivalence classes is ${|A|! \over |S_1|! |S_2|! }$.

In the example in the question $|A| = n$, the elements of $S_1$ are of the first kind and $|S_1| = p$ and the elements of $S_2$ are of the second kind and $|S_2| = q$. Hence the number of permutations is ${n! \over p! q! }$.

Answer 2

You may permute the $n$ objects in $n!$ ways. But for every permutation that you have, you may permute the $p$-same objects (of the first kind) and the $q$-same objects (of the second kind) and the result will remain unchanged in the human eye! You can do this in $p!q!$ ways. Can you see why you should divide to get the result?

Answer 3

A simple example can be used to see whats happening, lets say we have elements as 2,2,2,3,4,5 now if we denote it as $2_1, 2_2, 2_3 $ , 3,4,5, then no of permutation is 6!, suppose some combination is like $2_1, 3,4, 2_2, 5 , 2_3 $, keeping 3,4,5 constant we can permute the rest in 3! ways, but all of them are same.

Answer 4

You are effectively counting the number of equivalence classes among the $n!$ permutations of the $n$ objects, where two permutations are equivalent if they only permute the subset of $p$ objects among itself and they only permute the subset of $q$ objects among itself, leaving the remaining $n-p-q$ objects where they are.

There are $p!$ permutations of the first $p$ objects, and $q!$ permutations of the set of $q$ objects. Thus every single permutation is equivalent to exactly $p!q!$ permutations. Thus every equivalence class of the equivalence relation has $p!q!$ members.

The number of equivalence classes is the total number of permutations of $n$ elements, divided by the number of equivalent elements in each class.