[seqfan] path counts and hook lengths in Ferrers diagrams
wouter meeussen
wouter.meeussen at pandora.be
Sun Aug 29 22:24:23 CEST 2010
hi seqfans,
below are a number of 'counting sequences', not yet in OEIS
(except when indicated so).
They may be too artificial. Ballast?
To each partition corresponds a Ferrers diagram,
like to {5,3,2,2,1,1,1} corresponds
x
x
x x
x x x x
x x x x x x x
and in a structure like this, we can count paths between the corners as
(* each cell equals the one above + the one to the left*)
1
1
1 1
1 2 2 2
1 3 5 7 7 7 7
or equivalently on the transpose {7,4,2,1,1}
1
1
1
1 1
1 2
1 3 3
1 4 7 7 7
so the path count of {5,3,2,2,1,1,1} is 7.
The max path count over the partitions of n (n=1..24) is strictly slowly
increasing:
1, 1, 1, 2, 2, 3, 3, 5, 6, 7, 9, 10, 14, 16, 19, 23, 28, 32, 42, 47, 56, 66,
76, 90
while the sum of path counts is wilder:
1, 2, 3, 6, 9, 18, 27, 49, 77, 129, 199, 329, 497, 787, 1194, 1838, 2738,
4154,
6108, 9098, 13265, 19432, 28024, 40612
and the sum of path counts over the triangle of partitions of n with exactly
k parts:
1
1, 1
1, 1, 1
1, 3, 1, 1
1, 3, 3, 1, 1
1, 6, 6, 3, 1, 1
1, 6, 9, 6, 3, 1, 1
1, 10, 14, 13, 6, 3, 1, 1
where the reverse of the last row stabilises to
1, 1, 3, 6, 13, 23, 46, 78, 143, 240, 414, 673, 1127, 1788, 2885, 4514
which are also the central elements of the odd rows.
---------------------------------
In a similar vein, the hook lengths are 1+ the count of X's above and to the
right of
the cell under consideration, giving for {5,3,2,2,1,1,1}
1
2
4 1
7 4 2 1
11 8 6 4 2 1
It is evident that the maximal hook length will be in the lower left corner,
equal to -1+Length[par]+First[par]
1, 4, 9, 19, 33, 59, 93, 150, 226, 342, 494, 721, 1011, 1425, 1960, 2695,
3633,
4903, 6506, 8633, 11312, 14796, 19157, 24773
The total sum of hook lengths *is* in OEIS as A066183,
but the sum of hook lengths over the triangle of partitions of n with
exactly k parts isn't:
1
3, 3
6, 5, 6
10, 16, 8, 10
15, 23, 22, 12, 15
21, 47, 44, 30, 17, 21
28, 62, 74, 56, 40, 23, 28
(notice the funny dip in the next to last position)
--------------------------------
finally, some Mathematica implementations
( mostly for my own records, not realy one-liners, need more thought)
pathcount[p_?PartitionQ]:=Block[{ferr=(0*Range[#])&/@
p},Last at Fold[Rest[FoldList[Plus,0,Drop[#1,Length[#1]-Length[#2]]+#2]]&,1+Fir
st[ferr],Rest[ferr]] ]
and
hooklength[p_?PartitionQ]:=Block[{ferr=PadLeft[1+0*Range[#],Max[p]]&/@ p},
DeleteCases[
Rest[FoldList[Plus,0,#]]&/@ ferr + Reverse/@ Reverse@
Transpose[Rest[FoldList[Plus,0,#]]&/@ Reverse[Reverse/@ Transpose[ferr]]]
,0,{2}]-1 ]
and ofcourse,
partitionexact[n_,m_]:=TransposePartition/@ (Prepend[#,m]&/@
Partitions[n-m,m])
----------------------------------
potentially sequentially yours,
Wouter.
More information about the SeqFan
mailing list