# [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
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.

```