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,6

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.

Links

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

Formula

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

Example

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)

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}]

Prog

(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

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.

Sequence in context: A329020 A351640 A173003 * A294411 A274390 A244128

Adjacent sequences: A335458 A335459 A335460 * A335462 A335463 A335464

Keyword

nonn,tabl

Author

Gus Wiseman, Jul 03 2020

Status

approved