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

%I #9 Dec 31 2020 17:02:00

%S 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,

%T 2612,0,1,12,120,880,4620,15672,25988,0,1,14,168,1540,10780,54852,

%U 181916,296564,0,1,16,224,2464,21560,146272,727664,2372512,3816548

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

%C 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.

%H Andrew Howroyd, <a href="/A335461/b335461.txt">Table of n, a(n) for n = 0..1325</a> (rows 0..50)

%F T(n,k) = A005649(k-1) * binomial(n-1,k-1) for k > 0. - _Andrew Howroyd_, Dec 31 2020

%e Triangle begins:

%e 1

%e 0 1

%e 0 1 2

%e 0 1 4 8

%e 0 1 6 24 44

%e 0 1 8 48 176 308

%e 0 1 10 80 440 1540 2612

%e 0 1 12 120 880 4620 15672 25988

%e Row n = 3 counts the following patterns:

%e (1,1,1) (1,1,2) (1,2,1)

%e (1,2,2) (1,2,3)

%e (2,1,1) (1,3,2)

%e (2,2,1) (2,1,2)

%e (2,1,3)

%e (2,3,1)

%e (3,1,2)

%e (3,2,1)

%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];

%t Table[Length[Select[Join@@Permutations/@allnorm[n],Length[Split[#]]==k&]],{n,0,5},{k,0,n}]

%o (PARI) \\ here b(n) is A005649.

%o b(n) = {sum(k=0, n, stirling(n,k,2)*(k + 1)!)}

%o T(n,k)=if(n==0, k==0, b(k-1)*binomial(n-1,k-1)) \\ _Andrew Howroyd_, Dec 31 2020

%Y Row sums are A000670.

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

%Y Central coefficients are A337564.

%Y The version for compositions is A333755.

%Y Runs of standard compositions are counted by A124767.

%Y Run-lengths of standard compositions are A333769.

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

%K nonn,tabl

%O 0,6

%A _Gus Wiseman_, Jul 03 2020