A335461 Triangle read by rows where T(n,k) is the number of patterns of length n with k runs.

1, 0, 1, 0, 1, 2, 0, 1, 4, 8, 0, 1, 6, 24, 44, 0, 1, 8, 48, 176, 308, 0, 1, 10, 80, 440, 1540, 2612, 0, 1, 12, 120, 880, 4620, 15672, 25988, 0, 1, 14, 168, 1540, 10780, 54852, 181916, 296564, 0, 1, 16, 224, 2464, 21560, 146272, 727664, 2372512, 3816548

Offset: 0

Author

Gus Wiseman, Jul 03 2020

Keywords

• nonn
• tabl

Comments

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217.

Examples

			Triangle begins:
     1
     0     1
     0     1     2
     0     1     4     8
     0     1     6    24    44
     0     1     8    48   176   308
     0     1    10    80   440  1540  2612
     0     1    12   120   880  4620 15672 25988
Row n = 3 counts the following patterns:
  (1,1,1)  (1,1,2)  (1,2,1)
           (1,2,2)  (1,2,3)
           (2,1,1)  (1,3,2)
           (2,2,1)  (2,1,2)
                    (2,1,3)
                    (2,3,1)
                    (3,1,2)
                    (3,2,1)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Crossrefs

Row sums are A000670.

Column n = k is A005649 (anti-run patterns).

Central coefficients are A337564.

The version for compositions is A333755.

Runs of standard compositions are counted by A124767.

Run-lengths of standard compositions are A333769.

Cf. A003242, A052841, A060223, A106351, A106356, A269134, A325535, A333489, A333627, A335838.

Programs

Mathematica

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],Length[Split[#]]==k&]],{n,0,5},{k,0,n}]

PARI

\\ here b(n) is A005649.
b(n) = {sum(k=0, n, stirling(n,k,2)*(k + 1)!)}
T(n,k)=if(n==0, k==0, b(k-1)*binomial(n-1,k-1)) \\ Andrew Howroyd, Dec 31 2020

Formula

T(n,k) = A005649(k-1) * binomial(n-1,k-1) for k > 0. - Andrew Howroyd, Dec 31 2020