The permutation sending 1→3→2→1 and 4→5→4 has cycle form (1 3 2)(4 5). Rotating a cycle, such as writing (3 2 1), does not change the permutation. Reordering disjoint cycles also changes only the notation. Counting permutations by cycle lengths therefore requires accounting for both kinds of redundant descriptions. This is a useful place to test whether division by a symmetry factor really has constant-size fibers.
Predict
Predict the count of permutations of five labels with one three-cycle and one two-cycle. Choose the three labels in C(5, 3)=10 ways; arrange them in (3−1)!=2 cycles; the remaining pair has one cycle. The total is twenty. A raw ordered list of five labels gives 120 descriptions, but each permutation is described three times by rotating the triple and twice by rotating the pair, again giving 120/6.
Experiment
Build the unsigned Stirling cycle table.
n
One cycle
Two cycles
Three cycles
1
1
0
0
2
1
1
0
3
2
3
1
The row for n=3 sums to six. List the three permutations with two cycles and explain why each consists of one transposition and one fixed point. A fixed point is a one-cycle, not an omitted object when counting cycles.
Understand
If a cycle type has m_j cycles of length j and Σj m_j=n, its count is n! divided by product j^(m_j)m_j!. Begin with labels in ordered slots grouped into cycles of the stated lengths. Each j-cycle has j equivalent rotations, and the m_j cycles of equal length can be permuted in m_j! ways. These redundancies are independent and each permutation has exactly the same number of descriptions. The formula counts permutations, not conjugacy classes: one feasible cycle type specifies one class but usually many permutations.
Apply
Let c(n, k) count permutations with k cycles. Locate label n. If it is a singleton cycle, deleting it leaves c(n−1, k−1) choices. Otherwise remove it from its cycle and connect its predecessor to its successor; reinsertion immediately after any one of the n−1 labels reverses the operation. Thus c(n, k)=c(n−1, k−1)+(n−1)c(n−1, k). With c(0, 0)=1, summing against t^k gives the rising-factorial polynomial t(t+1)…(t+n−1). Compare this with second-kind Stirling numbers: they change between ordinary powers and falling factorials, while these first-kind numbers record cycle decompositions.
Continue
Uniform insertion supplies a probabilistic interpretation. At stage n there are n equally likely choices: start a singleton or insert after one of n−1 existing labels. Repeated uniform choices generate every permutation with equal probability, as the inverse deletion is unique. The expected number of cycles therefore increases by 1/n, producing the harmonic sum. This expectation is not the most likely cycle count, and it does not imply that the cycle events for different labels are independent. The later exponential formula will rederive the cycle generating series by treating cycles as labeled components.
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Count permutations of six labels consisting of three disjoint transpositions.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Find the number of permutations of four labels with two cycles.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Prove the cycle-type count n!/product (j^m_j m_j!).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove c(n, k)=c(n−1, k−1)+(n−1)c(n−1, k).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Derive Σc(n, k)t^k=t(t+1)…(t+n−1).
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove the expected number of cycles of a uniform random n-permutation isΣ1/j.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
