# Combinatorics in probability

My professor put forward some equations in class, for which she had no names, and definitions that I found confusing. They seem to be spin offs of Stirling numbers of one kind or another, based on reading some wikipedia articles, but with some extra caveats. I want to figure out what these rules are or are called, so that I can study them further. Below are the definitions she gave for the two rules I am having the most trouble with:

1. Let $r_1,\dots r_k \in \mathbb{Z}^+ : \sum_{i=1}^{k}r_i = n$ then the number of ways n elements can be partitioned into $k$ groups where group $i$ contains $r_i$ is:

$$\frac{n!}{r_1!r_2!\dots r_k!}$$

1. The number of distinct permutations of length k of a set of n objects where each object in the permutation is unique in type is:

$$\frac{n!}{n_1!n_2!\dots n_k!}$$

Rule 2 came with an example:

Given a set $\{teacher_1, teacher_2, student, doctor\}$ and $k=2$, then the equation fills out to be:

$$\frac{2!}{2!1!1!}$$

Help pinning down where these rules came from and what they are called will help me to find more examples for use in my studies.

• Both of your displayed formulas are examples of "multinomial coefficients", which are a kind of generalization of binomial coefficients. Are you happy with statements like "The binomial coefficient $\binom{10}{3}$ counts the number of 10-long sequences of 0s and 1s with exactly 3 0s and 7 1s"? If so, the multinomial coefficients should be within your reach, too. Commented Sep 20, 2017 at 2:32
• What exactly does $n_k$ mean? Commented Sep 20, 2017 at 2:38
• @kimchilover I am not that far along in my understanding of combinatorics, but when this test is over, I will revisit your comment and see if I can't make that connection. Thank you for giving me something to ponder. Commented Sep 20, 2017 at 18:25

Rule no 1 is generalisation of $$\binom{n}{r}$$ Let's prove it,  No of ways we can divide $n$ objects into groups of length $r_i$

Suppose we have n place and we have set markers after $r_i$ positions one after another, i.e. first marker goes after $r_1$ places then second goes after $r_2$ places after first marker and such.

Now we arrange the objects in these places,

No. of ways to do so=$n!$

Now we split them into groups as such that objects between two markers go in the same group,

Hence now we have groups with $r_1,r_2,\cdots$ no of objects

But each group has specific arrangement of objects, so a different arrangement of same objects in the same group also gets counted,

So to we need to disarrange them, to do so we divide by the number of ways objects in a group can be arranged (as that many times extra combinations you have), and we do that for every group,

Hence we get no of ways we can split $n$ objects into groups of length $r_1,r_2\cdots$ will be $=\frac{n!}{r_1!r_2!\cdots}$

You can prove the next rule similarly.

• Suppose we have 7 objects. Commented Sep 20, 2017 at 16:37
• Let them be ${1,2,3,4,5,6,7}$ Commented Sep 20, 2017 at 16:38
• Now we want to split them into 3 groups of length: 3,2,2 Commented Sep 20, 2017 at 16:38
• Now let's add our markers as$$-,-,-\color{red}{,}-,-\color{red}{,}-,-\color{red}{.}$$ Commented Sep 20, 2017 at 16:40
• Now no of ways of arranging 7 groups in those 7 places is$$7!$$ Commented Sep 20, 2017 at 16:42

For the first group, choose $r_1$ objects in $\binom{n}{r_1}$ ways. Of the remaining $n-r_1$ objects, choose $r_2$ for the second group in $\binom{n-r_1}{r_2}$ ways and so on. Thus the number of ways is \begin{align*} \binom{n}{r_1}\binom{n-r_1}{r_2}&\cdots \binom{n-r_1-r_2-\cdots-r_{k-1}}{r_k}\\ &= \frac{n!}{r_1! (n-r_1)!} \frac{(n-r_1)!}{r_2!(n-r_1-r_2)!} \cdots \frac{(n-r_1-r_2-\cdots-r_{k-1})!}{r_k! (n-r_1-r_2-\cdots-r_{k-1}-r_k)!} \\ &= \frac{n!}{r_1!r_2!\cdots r_k!} \end{align*}

• this derivation makes great sense. Can you include an example of what this means in a tangible sense? I ask because the class is a probability theory course, and I will be given a word problem requiring that I understand which rule to apply in order to solve it. Commented Sep 20, 2017 at 14:16
• A good, elementary book to learn the basics of counting is G.E.Martin, Counting: The Art of Enumerative Combinatorics, Springer Verlag, 2001.
– user348749
Commented Sep 20, 2017 at 14:45