OFFSET
0,3
COMMENTS
REFERENCES
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, New York, 1983.
LINKS
Alois P. Heinz, Rows n = 0..142, flattened
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-123.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 210
Yan Zhuang, Monoid networks and counting permutations by runs, arXiv preprint arXiv:1505.02308 [math.CO], 2015.
Y. Zhuang, Counting permutations by runs, J. Comb. Theory Ser. A 142 (2016), pp. 147-176.
FORMULA
E.g.f.: 1/(1 - x - Sum_{k,n} I(n,k)(y - 1)^k*x^n/n!) where I(n,k) is the coefficient of y^k*x^n in the ordinary generating function expansion of y x^3/(1 - y*x - y*x^2). See Flajolet and Sedgewick reference in Links section. - Geoffrey Critzer, Dec 12 2012
EXAMPLE
T(5,2) = 8 because we have 15432, 25431, 35421, 43215, 45321, 53214, 54213, and 54312.
Triangle starts:
1;
1;
2;
5, 1;
17, 6, 1;
70, 41, 8, 1;
349, 274, 86, 10, 1;
MAPLE
n := 7: dds := proc (p) local ct, j: ct := 0: for j from 3 to nops(p) do if p[j] < p[j-1] and p[j-1] < p[j-2] then ct := ct+1 else end if end do: ct end proc: with(combinat): P := permute(n): f[n] := sort(add(t^dds(P[i]), i = 1 .. factorial(n)));
# second Maple program:
b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
add(b(u-j, o+j-1, 1), j=1..u)+
add(b(u+j-1, o-j, 2)*`if`(t=2, x, 1), 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); # Alois P. Heinz, Oct 25 2013
MATHEMATICA
nn=10; u=y-1; a=Apply[Plus, Table[Normal[Series[y x^3/(1-y x - y x^2), {x, 0, nn}]][[n]]/(n+2)!, {n, 1, nn-2}]]/.y->u; Range[0, nn]! CoefficientList[Series[1/(1-x-a), {x, 0, nn}], {x, y}]//Grid (* Geoffrey Critzer, Dec 12 2012 *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jul 26 2009
STATUS
approved