# I need a hint

Jon Awbrey jawbrey at oakland.edu
Sat Mar 22 19:50:14 CET 2003

```o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

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) ?

blushingly yours,

Wouter.

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

wouter,

it's been a while since i did one of these, and
i only had a moment to play around with it, but
these run-type problems almost always come down
to some q-analogue of integration by parts.
here is a hint of the the kinds of pictures
that i used to draw for myself:

8---o---o---o---o---o---6
| %   %   %   %   %   % |
7---o---o---o---o---5---7
| %   %   %   %   % | # |
6---o---o---o---o---5   o
| %   %   %   %   % | # |
5---o---o---o---o---5   o
| %   %   %   %   % | # |
4---o---o---o---o---5   o
| %   %   %   %   % | # |
3---o---o---3---3---3   o
| %   %   % | # | # | # |
2---o---o---3   o   o   o
| %   %   % | # | # | # |
1---1---1---1   o   o   o
| # | # | # | # | # | # |
0---1---2---3---4---5---6

u  = <1, 1, 1, 3, 3, 7>
u' = <1, 0, 0, 2, 0, 4>

v  = <3, 3, 5, 5, 5, 5, 6>
v' = <3, 0, 2, 0, 0, 0, 1>

Sum u' = Max u = |v| = m = 7
Sum v' = Max v = |u| = n = 6

Sum u = 3(1) + 2(3) + 1(7) = 16
Sum v = 2(3) + 4(5) + 1(6) = 32

n(m+1) = 6*8 = Sum u + Sum v = 48

jon awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

```