A242819 Number T(n,k) of permutations of [n] with exactly k occurrences of the consecutive step pattern up, down, down; triangle T(n,k), n>=0, 0<=k<=max(0,floor((n-1)/3)), read by rows.

1, 1, 2, 6, 21, 3, 90, 30, 450, 270, 2619, 2322, 99, 17334, 20772, 2214, 129114, 195372, 38394, 1067661, 1958337, 591543, 11259, 9713682, 20933154, 8826246, 443718, 96393726, 238789782, 131367258, 12450834, 1036348587, 2900868876, 1989555210, 297195804, 3052323

Offset: 0

Author

Alois P. Heinz, May 23 2014

Keywords

• nonn
• tabf

Comments

T(n,k) is also the number of permutations of [n] with exactly k occurrences of the consecutive step pattern up, up, down.

From Vaclav Kotesovec, Aug 26 2014: (Start)

Column k is asymptotic to c(k) * (3*sqrt(3)/(2*Pi))^n * n! * n^k.

Conjecture: c(k) = c(0) * (c(0)-1)^k / (3^k * k!).

Verified numerically:

c(0) = 1.96650951227123825842868... = (1+exp(Pi/sqrt(3)))*sqrt(3)/(2*Pi)

c(1) = 0.63355004986067503869384...

c(2) = 0.10205535828170995196503...

c(3) = 0.01095971939528021798...

c(4) = 0.000882722753946826148...

c(5) = 0.00005687732922585807984...

c(6) = 0.000003054026651631929902...

c(7) = 0.0000001405593242634352116...

c(8) = 0.00000000566049683079281633...

c(9) = 0.0000000002026268159682390665...

c(10)= 0.00000000000652802483581788974...

c(20)= 1.172921625090753...*10^(-28)

c(30)= 1.2959323...*10^(-47)

c(40)= 5.0751...*10^(-68)

(End)

Examples

			T(4,1) = 3: (1,4,3,2), (2,4,3,1), (3,4,2,1).
Triangle T(n,k) begins:
:  0 :       1;
:  1 :       1;
:  2 :       2;
:  3 :       6;
:  4 :      21,        3;
:  5 :      90,       30;
:  6 :     450,      270;
:  7 :    2619,     2322,      99;
:  8 :   17334,    20772,    2214;
:  9 :  129114,   195372,   38394;
: 10 : 1067661,  1958337,  591543,  11259;
: 11 : 9713682, 20933154, 8826246, 443718;
		

Links

• Alois P. Heinz, Rows n = 0..120, flattened

Crossrefs

Columns k=0-10 give: A177479, A246246, A246247, A246248, A246249, A246250, A246251, A246252, A246253, A246254, A246255.

Row sums give: A000142.

Cf. A242783, A242784, A295987.

Programs

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, [1, 3, 1][t])*`if`(t=3, x, 1), j=1..u)+
      add(b(u+j-1, o-j, 2), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Expand[Sum[b[u-j, o+j-1, {1, 3, 1}[[t]]]*If[t == 3, x, 1], {j, 1, u}] + Sum[b[u+j-1, o-j, 2], {j, 1, o}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 1]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Feb 10 2015, after Alois P. Heinz *)