Ordered Sums of 10

Question

In how many ways can 10 be written as an ordered sum of positive integers? (10; 1+9; 9+1; 2+3+5; … all count separately.)

Accepted Answer

Lay out 10 units in a row. A composition is exactly a choice, for each of the 9 gaps between adjacent units, of "cut here" or "don't", the cuts carve the row into ordered positive parts: 2^9 = 512. The map is a genuine bijection: every cut-pattern gives a composition, every composition comes from exactly one cut-pattern. This gap-cutting picture also gives compositions into exactly k parts for free: choose k-1 of the 9 gaps, binom9k-1. Terminology trap: compositions (ordered) vs partitions (unordered). Partitions of 10 number just 42, and there is no closed form for partition counts, if an interviewer says "ways to write 10 as a sum," ask whether order matters before computing anything. The two answers differ by an order of magnitude, and asking the clarifying question is itself being graded.

Ordered Sums of 10

Problem

Your answer

Hints