I need a hint

[Dean Hickerson]

Wouter Meeussen asked:

> can anybody help me further with this?
>
> define function 'runs' as
> runs[li : {__Integer}] := ((Length /@ Split[#])) &  [Sort at li]
>
> saying :  count the runs of equal integers in a sorted list,
> runs[ {1,1,1,3,3,7}]  gives {3,2,1},
>
> next define 'multiplicity' as the multinomial of the runs,
> multiplicity[{1,1,1,3,3,7}] gives 6!/(3!*2!*1!) = 60
>
> Given all that, can anyone make this poor soul understand why
> the sum of the multiplicities of the partitions of n equals 2^(n-1) ?

A 'composition' of n is a way of writing n as a sum of smaller positive
integers, in which the order of the parts matters.  For example, one
composition of 9 is 1+1+4+1+2.  If you sort the parts in a composition you
get a partition, and for each partition P, the number of compositions that
give rise to it is multiplicity(p).  So we need to show that the number of
compositions of n is 2^(n-1).

Think of a composition as a way of breaking a ruler of length n into
pieces with integer lengths.  There are n-1 places where you can break
the ruler: 1 unit from the left end, 2 units from the left end, ...,
n-1 units from the left end.  There are 2^(n-1) ways to choose which
places to break the ruler, and each one corresponds to a composition.

Dean Hickerson
dean at math.ucdavis.edu