What is the formula for permutations of multiple kinds in combinatorics?

12john
Messages
12
Reaction score
1
Thread moved from the technical forums to the schoolwork forums
My combinatorics professor has a MA, PhD from Princeton University. On our test, she asked

What's the explicit formula for the number of ##p## permutations of ##t## things with ##k## kinds, where ##n_1, n_2, n_3, \cdots , n_k## = the number of each kind of thing ?

I handwrote, but transcribed in Latex, my answer below.

To deduce the formula for all the unique permutations of length ##l## of ##\{n_1,n_2,...,n_k\}##, we must find all combinations ##C=\{c_1,c_2,...,c_k\}## where ##0 \leq c_k \leq n_k##, such that
##\sum_{i=1}^k c_i=l##.

What we need, is actually the product of the factorials of the elements of that combination:
##{\prod_{i=1}^k c_i!}##

Presuppose that the number of combinations is J. Then to answer your question, the number of permutations is
$$= \sum_{j=1}^J \frac{l!}{\prod_{i=1}^k c_i!}
= \sum_{c_1+c_2+...+c_k=l} \binom{l}{c_1,c_2, \cdots ,c_n},$$
as a closed form expression with a Multinomial Coefficient. *QED.*

How can I improve this? What else should I've written? Professor awarded me merely 50%. She wrote
Your answer is correct, but your solution is too snippy. You need to elaborate.
 
Last edited by a moderator:
Physics news on Phys.org
12john said:
I handwrote, but transcribed in Latex, my answer below.
I edited your LaTeX. At this site we use MathJax, which has to be delimited by either pairs of # characters (for inline TeX) or pairs of $ characters (standalone).
I also removed all the color stuff. We prefer that you use a minimum of extra color, bolding, italics, etc.
12john said:
How can I improve this? What else should I've written?
What she wrote was "You need to elaborate." The best explanation would come from your instructor.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top