Solution
Palindromic Compositions
Show the problem again
A composition of n is an ordered sum of positive integers equal to n, such as 3 + 1 + 4 for 8. A composition is palindromic if its sequence of parts reads the same forwards and backwards (for example 2 + 5 + 5 + 2 or 3 + 14 + 3, or the one-part composition 20). How many palindromic compositions of 20 are there? Give an integer.
Worked solution
**Answer: 1024.** A palindromic composition is determined by its first half, plus a middle part if the length is odd. - Even length: the first half is any composition of 10: 2^9 = 512 choices. - Odd length: the middle part m must be even (since 20 − m splits into two equal halves). If m = 20 the halves are empty (1 way); if m = 20 − 2j with 1 ≤ j ≤ 9 the first half is a composition of j, giving 2^(j−1) choices. These total 1 + (1 + 2 + ... + 2^8) = 1 + 511 = 512. Altogether 512 + 512 = 1024 = 2^10. In general a positive integer n has 2^⌊n/2⌋ palindromic compositions.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.