Композиция натурального n — это упорядоченная цепочка положительных целых слагаемых, дающих в сумме n (например, для n=4 композиции: 4; 3+1; 1+3; 2+2; 2+1+1; 1+2+1; 1+1+2; 1+1+1+1).

Доказательство: представьте n как сумму n единиц
1 + 1 + ... + 1 (n штук).
Между этими единицами есть n−1 «промежутков». В каждом таком промежутке либо ставим границу между частями композиции, либо не ставим (если не ставим, две соседние единицы объединяются в одно слагаемое). Поэтому каждой композиции соответствует уникальный набор выбранных границ, то есть подмножество из n−1 промежутков. Число всех подмножеств множества из n−1 элементов равно 2^{n−1}. Обратно, любое такое подмножество дает композицию. Получаем биекцию и число композиций равно 2^{n−1}.

Почему то же не верно для неупорядоченных разбиений (разделов, partitions)? Непорядоченное разбиение не различает порядок слагаемых, поэтому многие разные композиции дают одно и то же разбиение. Следовательно число разбиений p(n) меньше числа композиций 2^{n-1} (и для n≥3 строго меньше). Простейший контрпример: для n=4 число композиций 2^{3}=8, а число разбиений p(4)=5 (разбиения: 4; 3+1; 2+2; 2+1+1; 1+1+1+1). Более того, функция p(n) имеет совсем другую асимптотику (формула Харди—Рамануджана ~ exp(π√(2n/3))/(4n√3)), она растёт намного медленнее, чем 2^{n-1}.

Итого: для композиций есть простая биекция с подмножествами n−1 промежутков, отсюда 2^{n-1}. Для разбиений такой простой двоичный выбор отсутствует, и равенство не выполняется.