I need a hint
Dean Hickerson
dean at math.ucdavis.edu
Sat Mar 22 21:18:09 CET 2003
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
More information about the SeqFan
mailing list