Enumerative Combinatorics · Compositions, multisets, and distributing objects into boxes

For n ≥ 1, a positive composition of n is an ordered list of positive integers summing…

Problem

For $n\ge 1$, a positive composition of $n$ is an ordered list of positive integers summing to $n$. Count positive compositions with exactly $k$ parts, where $1\le k\le n$, and then count all positive compositions with any allowed number of parts. Use cuts in a row of $n$ marks, giving the inverse of the encoding. Evaluate the fixed-length count for $n=9,k=4$ and the unrestricted-length count for $n=9$. Explain why exchanging two unequal parts generally creates a different composition.

Hint

Arrange $n$ marks and inspect the internal gaps.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

Check your answer See the full solution

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Enumerative Combinatorics sample problem: Try the free sample problem.

More Enumerative Combinatorics practice problems

A group has six distinct volunteersCounting principles, bijections, and the pigeonhole principle
Among n distinct volunteers, a specified set of r volunteers is qualified to serve as…Counting principles, bijections, and the pigeonhole principle
Let a,b ≥ 0 and let k be an integerBinomial and multinomial coefficients, identities, and lattice paths
Let a,b ≥ 0 and h ≥ 1 be integers with b-a<hBinomial and multinomial coefficients, identities, and lattice paths
Among thirty labeled projects, eighteen use method A, fourteen use method B, and twelve…Inclusion-exclusion, derangements, and surjections
Let S(n,k) count partitions of [n] into k nonempty unordered blocksSet partitions, Stirling numbers, and the cycle structure of permutations
An integer partition of n is a finite weakly decreasing sequence of positive integers…Integer partitions and Ferrers diagrams
Let a₀=2, a₁=5, and aₙ=5aₙ₋₁-6aₙ₋₂ for n ≥ 2Ordinary generating functions, recurrences, and Catalan numbers
If aₙ counts structures on a specified set of n distinct labels, its exponential…Exponential generating functions and labeled structures