Compositions of n: ordered sums k₁+...+kₘ=n with kᵢ≥1. Total: 2^(n-1) (stars and bars with order). Compositions of 3: 3, 2+1, 1+2, 1+1+1 = 4 = 2². With exactly k parts: C(n-1,k-1). Compositions relate to binary strings of length n-1.
How to Use
Enter n:
- Count: 2^(n-1)
- List: All compositions
- By parts: Group by # of parts
Binary String Bijection
Each composition of n ↔ binary string of length n-1. Place 0/1 between consecutive 1's: 1 = 'cut here'. Example: 3+1+2 for n=6 ↔ 00101 (cuts after positions 3 and 4). This proves count = 2^(n-1).
Weak Compositions
If kᵢ≥0 (zeros allowed) with k parts: C(n+k-1,k-1) by stars and bars. Weak compositions of 3 into 3 parts: C(5,2)=10, including (0,0,3), (1,1,1), etc.
Step-by-Step Instructions
- 1Enter n.
- 2See count.
- 3List all.
- 4Group by parts.
- 5Try restrictions.