Solution
No Two Alike in a Row
Show the problem again
A composition of 10 is an ordered sum of positive integers equal to 10 (so 1 + 2 and 2 + 1 are different compositions of 3). How many compositions of 10 have no two adjacent parts equal? For example 3 + 1 + 2 + 4 qualifies, but 3 + 3 + 4 does not. The one-part composition 10 qualifies. Give an integer.
Worked solution
**Answer: 124.** Let c(n, k) be the number of valid compositions of n whose last part is k. Removing the last part leaves either nothing (when n = k) or a valid composition of n − k whose last part is not k: c(n, k) = [n = k] + Σ_{j ≠ k} c(n − k, j) = [n = k] + T(n − k) − c(n − k, k), where T(m) is the total for m. Filling the table row by row gives the totals T(1..10) = 1, 1, 3, 4, 7, 14, 23, 39, 71, 124. (Check small cases: for 3 the valid compositions are 3, 1 + 2, 2 + 1; for 4 they are 4, 1 + 3, 3 + 1, 1 + 2 + 1.) So there are 124. These are known as Carlitz compositions.
Source: Such compositions were studied by L. Carlitz (1976). Statement written for AxiomIQ.