A337506 Triangle read by rows where T(n,k) is the number of length-n sequences covering an initial interval of positive integers with k maximal anti-runs.

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

Offset: 0

Author

Gus Wiseman, Sep 06 2020

Keywords

• nonn
• tabl

Comments

An anti-run is a sequence with no adjacent equal parts. The number of maximal anti-runs is one more than the number of adjacent equal parts.

Examples

			Triangle begins:
  1
  0      1
  0      2      1
  0      8      4      1
  0     44     24      6      1
  0    308    176     48      8      1
  0   2612   1540    440     80     10      1
  0  25988  15672   4620    880    120     12      1
  0 296564 181916  54852  10780   1540    168     14      1
Row n = 3 counts the following sequences (empty column indicated by dot):
  .  (1,2,1)  (1,1,2)  (1,1,1)
     (1,2,3)  (1,2,2)
     (1,3,2)  (2,1,1)
     (2,1,2)  (2,2,1)
     (2,1,3)
     (2,3,1)
     (3,1,2)
     (3,2,1)
		

Links

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

Crossrefs

A000670 gives row sums.

A005649 gives column k = 1.

A337507 gives column k = 2.

A337505 gives the diagonal n = 2*k.

A106356 is the version for compositions.

A238130/A238279/A333755 is the version for runs in compositions.

A335461 has the reversed rows (except zeros).

A003242 counts anti-run compositions.

A124762 counts adjacent equal terms in standard compositions.

A124767 counts maximal runs in standard compositions.

A333381 counts maximal anti-runs in standard compositions.

A333382 counts adjacent unequal terms in standard compositions.

A333489 ranks anti-run compositions.

A333769 gives maximal run-lengths in standard compositions.

A337565 gives maximal anti-run lengths in standard compositions.

Cf. A019472, A052841, A060223, A106351, A269134, A325535, A337564.

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[#,UnsameQ]]==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(n-k)*binomial(n-1,k-1)) \\ Andrew Howroyd, Dec 31 2020

Formula

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

Extensions

Terms a(45) and beyond from Andrew Howroyd, Dec 31 2020