A330785 Triangle read by rows where T(n,k) is the number of chains of length k from minimum to maximum in the poset of integer partitions of n ordered by refinement.

1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 5, 8, 4, 0, 1, 9, 25, 28, 11, 0, 1, 13, 57, 111, 99, 33, 0, 1, 20, 129, 379, 561, 408, 116, 0, 1, 28, 253, 1057, 2332, 2805, 1739, 435, 0, 1, 40, 496, 2833, 8695, 15271, 15373, 8253, 1832, 0, 1, 54, 898, 6824, 28071, 67790, 98946, 85870, 40789, 8167

Offset: 1

Author

Gus Wiseman, Jan 03 2020

Keywords

• nonn
• tabl

Examples

			Triangle begins:
   1
   0   1
   0   1   1
   0   1   3   2
   0   1   5   8   4
   0   1   9  25  28  11
   0   1  13  57 111  99  33
   0   1  20 129 379 561 408 116
Row n = 5 counts the following chains (minimum and maximum not shown):
  ()  (14)    (113)->(14)    (1112)->(113)->(14)
      (23)    (113)->(23)    (1112)->(113)->(23)
      (113)   (122)->(14)    (1112)->(122)->(14)
      (122)   (122)->(23)    (1112)->(122)->(23)
      (1112)  (1112)->(14)
              (1112)->(23)
              (1112)->(113)
              (1112)->(122)
		

Crossrefs

Row sums are A213427.

Main diagonal is A002846.

Column k=3 is A007042.

Dominated by A330784.

The version for set partitions is A008826.

The version for factorizations is A330935.

Cf. A000111, A000258, A000311, A005121, A141268, A196545, A265947, A300383, A306186, A317141, A317176, A318813, A320160, A330679.

Programs

Mathematica

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
upr[q_]:=Union[Sort/@Apply[Plus,mps[q],{2}]];
paths[eds_,start_,end_]:=If[start==end,Prepend[#,{}],#]&[Join@@Table[Prepend[#,e]&/@paths[eds,Last[e],end],{e,Select[eds,First[#]==start&]}]];
Table[Length[Select[paths[Join@@Table[{y,#}&/@DeleteCases[upr[y],y],{y,Sort/@IntegerPartitions[n]}],ConstantArray[1,n],{n}],Length[#]==k-1&]],{n,8},{k,n}]

Formula

T(n,k) = A330935(2^n,k).