Compositions of n: ordered ways to write n as a sum of positive integers. 3 has 4 compositions: 3, 2+1, 1+2, 1+1+1. Count: 2^(n-1). With exactly k parts: C(n-1,k-1). Unlike partitions, order matters!
How to Use
Enter n:
- Count: 2^(n-1)
- List: All compositions
- k parts: Restricted count
Why 2^(n-1)?
Place n objects in a row. Between adjacent objects are n-1 gaps. Each gap is either a 'cut' (new part) or not. That's 2 choices per gap = 2^(n-1) total. The bijection: cuts determine parts.
vs Partitions
Partitions: unordered (2+1 = 1+2). Compositions: ordered (2+1 ≠ 1+2). Partitions of 5: 7. Compositions of 5: 16 = 2^4. Compositions are always more numerous because order creates distinctions.
Step-by-Step Instructions
- 1Enter n.
- 2Count: 2^(n-1).
- 3List all.
- 4Filter by k parts.
- 5Compare to partitions.