A composition of the positive integer n is obtained by writing
n = n1 + n2 + … + nk,
where n1, n2,…, nk are positive integers, and the order in which n1, n2,…, nk matters. The number of compositions of n equals 2n–1. For example the compositions of 4 are
4 = 3 + 1 = 1 + 3 = 2 + 2 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 1 + 1 + 1 + 1.
See partition.