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

Click For Summary
SUMMARY

The explicit formula for the number of permutations of multiple kinds in combinatorics is derived from the product of the factorials of the counts of each kind of item. Specifically, for a set of items characterized by counts \(n_1, n_2, \ldots, n_k\), the number of unique permutations of length \(l\) is given by the expression \(\sum_{c_1+c_2+\ldots+c_k=l} \frac{l!}{\prod_{i=1}^k c_i!}\), utilizing the Multinomial Coefficient. This formula accounts for all combinations \(C=\{c_1,c_2,\ldots,c_k\}\) where the sum of the counts equals \(l\). The discussion emphasizes the importance of elaboration in mathematical explanations to achieve full credit in academic settings.

PREREQUISITES
  • Understanding of combinatorial principles, specifically permutations and combinations.
  • Familiarity with factorial notation and operations.
  • Knowledge of Multinomial Coefficients and their applications.
  • Proficiency in LaTeX for mathematical typesetting.
NEXT STEPS
  • Study the derivation and applications of the Multinomial Theorem.
  • Explore advanced combinatorial techniques, such as generating functions.
  • Learn about the use of MathJax for rendering mathematical expressions in web environments.
  • Practice writing detailed mathematical proofs to enhance clarity and depth in explanations.
USEFUL FOR

Students in combinatorics, mathematicians seeking to refine their proof-writing skills, and educators looking to improve their mathematical communication strategies.

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.
 

Similar threads

  • · Replies 0 ·
Replies
0
Views
1K
  • · Replies 16 ·
Replies
16
Views
4K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
2K
Replies
6
Views
2K
Replies
8
Views
3K