0
$\begingroup$

Anybody here familiar with John Riordan's Introduction to Combinatorial Analysis can kindly explain to me what the author is interpreting here:

"Here, permutations $n$ at a time only are considered; that is, the term “permutation” is used in the unqualified sense. Let $x$ be the number required. Suppose the $p$ like things are replaced by $p$ new things, distinct from each other and from all other kinds of things being permuted. These may be permuted in $p!$ ways (by equation (2)); hence the number of permutations of the new set of objects is $xp!$. The same goes for every other set of like things and, since finally all things become unlike and the number of permutations of $n$ unlike things is $n!$,

$$xp!q!... = n!$$ or
(4) $$x = \frac{n!}{p!q!...},\space\space\space p+q+... = n $$"

Added from the book

"The right of (4) is a multinomial coefficient, that is, a coefficient, in the expansion of $(a + b + · · ·)^n$. It is also the number of arrangements of n unlike things into unlike cells or boxes, $p$ in the first, $q$ in the second, and so on, without regard to order in any cell, as will be shown in Chapter 5"

for reference equation(2) is as follow:
$ P(n,n) = n(n-1)... 1 = n! $

I can only interpret it as an algebra formula moving one variable from one place to another.

Kindly advise

$\endgroup$
3
  • $\begingroup$ Is Riordan discussing permutations of multisets here? $\endgroup$ May 8, 2022 at 10:00
  • $\begingroup$ @N.F.Taussig, i just added some additional text from the book. I don't think it's relate to multisets, as the wiki explanation says "Multiset coefficients should not be confused with the unrelated multinomial coefficients that occur in the multinomial theorem." And the text mentioned something about multinomial coefficient. $\endgroup$ May 8, 2022 at 10:37
  • $\begingroup$ I should have directed you to the formula for permutations of multisets. $\endgroup$ May 8, 2022 at 10:48

1 Answer 1

2
$\begingroup$

The author is talking about permutations of multisets. I will derive the formula in a different way than Riordan, then explain his derivation.

To give an example, suppose we wish to arrange four blue, three green, and two red balls in a row, where balls of the same color are indistinguishable. We have a total of $4 + 3 + 2 = 9$ positions to fill. We can fill four of those nine positions with blue balls in $\binom{9}{4}$ ways, three of the remaining five positions with green balls in $\binom{5}{3}$ ways, and both of the remaining two positions with red balls in $\binom{2}{2}$ ways. Hence, there are $$\binom{9}{4}\binom{5}{3}\binom{2}{2} = \frac{9!}{4!5!} \cdot \frac{5!}{3!2!} \cdot \frac{2!}{2!0!} = \frac{9!}{4!3!2!0!} = \frac{9!}{4!3!2!}$$ distinguishable permutations. The factors in the denominator represent the number of ways we can permute balls of the same color among themselves within a given arrangement without producing an arrangement that is distinguishable from the given arrangement.

Suppose we have $n = n_1 + n_2 + n_3 + \cdots + n_k$ objects, of which $n_i$ are of type $i$, where $1 \leq i \leq k$. The number of ways we can arrange these objects is $$\binom{n}{n_1}\binom{n - n_1}{n_2}\binom{n - n_1 - n_2}{n_3} \cdots \binom{n - n_1 - n_2 - n_3 - \cdots - n_{k - 1}}{n_k}$$ since we must choose which $n_1$ of the $n$ positions will be filled with objects of type $1$, which $n_2$ of the remaining $n - n_1$ positions will be filled with objects of type $2$, which $n_3$ of the remaining $n - n_1 - n_2$ positions will be filled with objects of type $3$, and so forth until we fill $n_k$ of the remaining $n - n_1 - n_2 - n_3 - \cdots - n_{k - 1}$ positions with objects of type $k$.

\begin{align*} & \binom{n}{n_1}\binom{n - n_1}{n_2}\binom{n - n_1 - n_2}{n_3} \cdots \binom{n - n_1 - n_2 - n_3 - \cdots - n_{k - 1}}{n_k}\\ & \qquad = \frac{n!}{n_1!(n - n_1)!} \cdot \frac{(n - n_1)!}{n_2!(n - n_1 - n_2)!} \cdot \frac{(n - n_1 - n_2)!}{n_3!(n - n_1 - n_2 - n_3!} \cdots \frac{(n - n_1 - n_2 - n_3 - \cdots - n_{k - 1})!}{n_k!(n - n_1 - n_2 - n_3 - \cdots - n_k)!}\\ & \qquad = \frac{n!}{n_1!n_2!n_3! \cdots n_k!(n - n_1 - n_2 - n_3 - \cdots - n_k)!}\\ & \qquad = \frac{n!}{n_1!n_2!n_3! \cdots n_k!0!}\\ & \qquad = \frac{n!}{n_1!n_2!n_3! \cdots n_k!} \end{align*} where $n - n_1 - n_2 - n_3 - \cdots - n_k = 0$ since $n = n_1 + n_2 + n_3 + \cdots + n_k$ and $0! = 1$ by definition.

What Riordan is doing is calling the number of permutations of a multiset formed from $n = n_1 + n_2 + n_3 + \cdots + n_k$, with $n_i$ objects of type $i$ for $1 \leq i \leq k$, $x$. We know that if all $n$ objects were distinct, then we could arrange them in a row in $n!$ ways. Within a given arrangement, there is only one distinguishable arrangement of the objects of the same type. However, if we were to replace the $n_1$ objects of type $1$ with $n_1$ distinct objects, we could arrange them in the $n_1$ positions occupied by objects of type $1$ in $n_1!$ distinct ways. More generally, if we replaced the $n_i$ objects of type $i$, $1 \leq i \leq k$, by $n_i$ distinct objects, we could arrange them in the $n_i$ positions occupied by objects of type $i$ in $n_i!$ ways. Hence, $$xn_1!n_2!n_3! \cdots n_k! = n!$$ from which we obtain the formula that the number of permutations of a multiset formed from $n = n_1 + n_2 + n_3 + \cdots + n_k$, with $n_i$ objects of type $i$ for $1 \leq i \leq k$, is $$x = \frac{n!}{n_1!n_2!n_3! \cdots n_k!}$$

$\endgroup$
3
  • $\begingroup$ thank you for the in-depth explanation. The part from "What Riordan is doing ... " is still fuzzy to me. However, I reckon a few more read and comparing content from the wiki link you've posted should straighten it. Sidetracking from the question, do you have any recommended read for subjects on combinatorics? I started with Riordan's as it was recommended from posts I found online, however, I find a lot of his examples are very technical and hard for layman like myself to understanding. $\endgroup$ May 8, 2022 at 20:39
  • 1
    $\begingroup$ I find the derivation I gave at the beginning of my answer more intuitive than the one Riordan wrote. The first book on combinatorics I read was Mathematics of Choice by Ivan Niven. It is just a basic introduction, and it's terminology is a bit dated, but I can recommend it. You can also search this site for recommended combinatorics books. $\endgroup$ May 8, 2022 at 22:36
  • 1
    $\begingroup$ your derivation is certainty more intuitive specially for somebody like me with very limited combinatorics knowledge. Thank you for the recommendation, will get try to get hold one. I've bookmarked the book recommendation posts on the site for future references. Cheers $\endgroup$ May 8, 2022 at 23:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .