Elementary Foundations: An introduction to topics in discrete mathematics

There are \(\combinationalt{n}{i_1}\) possibilities for \(A_1\text{.}\) After choosing \(A_1\text{,}\) there are \(\combinationalt{n - i_1}{i_2}\) possibilities for \(A_2\text{.}\) After choosing \(A_2\text{,}\) there are \(\combinationalt{n - i_1 - i_2}{i_3}\) possibilities for \(A_2\text{.}\) Continue in this fashion, all the way to \(A_m\text{,}\) then multiply all the combination formula expressions together.

Going back to basic counting principles, we can approach this in the same way that we came up with the factorial formula for the choose function. Choosing a permutation of \(A\) (\(n!\) ways) gives us an instance of the desired partition of \(A\) by setting \(A_1\) to be the subset consisting of the first \(i_1\) objects in the permutation, then setting \(A_2\) to be the subset consisting of the next \(i_2\) objects in the permutation, and so on. However, the ordering of the elements inside any such subset \(A_j\) does not matter, and we would get the same partition if we took our permutation of \(A\) and again permuted the “clusters” corresponding to each subset \(A_j\text{.}\) Since there are \(i_j!\) ways to permute subset \(A_j\text{,}\) we should divide \(n!\) by each of the factorials \(i_j!\text{.}\)

If we view each letter \(x_i\) as a variable and each word made up of the letters \(x_1,\dotsc,x_m\) as a product of these variables, then each of the words we want to count gives us one way to achieve a term of \(x_1^{i_1} \dotsm x_m^{i_m}\) in the expansion of \((x_1 + \dotsb + x_m)^n\text{.}\) The number of such ways is the multinomial coefficient.