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
More information about the SeqFan
mailing list