

A197365


T(n,k) gives the number of permutations of the set [n] that contain k occurrences of the subword (132); irregular array read by rows (n >= 0 and 0 <= k <= max(0, floor((n1)/2))).


13



1, 1, 2, 5, 1, 16, 8, 63, 54, 3, 296, 368, 56, 1623, 2649, 753, 15, 10176, 20544, 9024, 576, 71793, 172596, 104814, 13572, 105, 562848, 1569408, 1228608, 259968, 7968, 4853949, 15398829, 14824314, 4532034, 306729, 945, 45664896, 162412416, 185991936, 75929856
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

A permutation p(1)p(2)...p(n) in the symmetric group S_n contains the subword (132) if there are 3 consecutive elements p(i)p(j)p(k) that have the same order relations as (132), that is, p(i) < p(j) > p(k) and p(i) < p(k). For the enumeration of permutations containing the subword (123) see A162975.
From Petros Hadjicostas, Nov 05 2019: (Start)
The attached Maple program gives a recurrence for the o.g.f. of each row in terms of u for T(n,k), the number of permutations of [n] containing exactly k occurrences of the consecutive pattern 123...(r+1)(r+3)(r+2) for r >= 0. In the program, t = r + 2. Here, n >= 0 and 0 <= k <= max(0, (n1)/t).
Using that recurrence we may get any row or column from the irregular triangular array T(n, k) for any r >= 0. (Here r = 0, while in array A264781 we have r = 2.)
The recurrence follows from manipulation of the bivariate o.g.f/e.g.f. 1/W(u,z) = Sum_{n, k >= 0} T(n, k)*u^k*z^n/n!, whose reciprocal W(u,z) is the solution of the o.d.e. in Theorem 3.2 in Elizalde and Noy (2003) (with m = a = r + 1). The number t = r + 2 is the order of the o.d.e. in terms of the variable z.
(End)


LINKS

Alois P. Heinz, Rows n = 0..100, flattened
A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilfclasses, 2011.
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110125.
Petros Hadjicostas, General Maple program for a recurrence for the number of permutations of [n] containing exactly k times the consecutive pattern 123...(r+1)(r+3)(r+2) for r >= 0. [Here r = 0 and in the program t = r + 2 = 2.]


FORMULA

E.g.f.: 1/(1  int_{t = 0..z} exp((u1)*t^2/2!)) = sqrt(1  u)/(sqrt(1  u) sqrt(Pi/2) * erf(z/2*sqrt(1  u))) = 1 + z + 2*z^2/2! + (5 + u)*z^3/3! + (16 + 8*u)*z^4/4! + ....
nth row sum = n!. First column is A111004.


EXAMPLE

Table begins
.n\k.......0......1.....2......3
= = = = = = = = = = = = = = = = =
..0........1
..1........1
..2........2
..3........5......1
..4.......16......8
..5.......63.....54.....3
..6......296....368....56
..7.....1623...2649...753....15
..8....10176..20544..9024...576
...
T(4,0) = 16: The 16 permutations of S_4 not containing the subword (132) are (1234), (2134), (2314), (3124), (3214), (1342), (2341), (3241), (2413), (3412), (3421), (4123), (4213), (4231), (4312), (4321).
T(4,1) = 8: The 8 permutations of S_4 with 1 occurrence of the subword (132) are 1243, 1324, 1423, 1432, 2143, 2431, 3142, 4132.


MAPLE

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
add(b(uj, o+j1, 0)*`if`(j<t, x, 1), j=1..u)+
add(b(u+j1, oj, j), j=1..o)))
end:
T:= n> (p> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..14); # Alois P. Heinz, Oct 30 2013


MATHEMATICA

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Expand[Sum[b[uj, o+j1, 0]*If[j<t, x, 1], {j, 1, u}] + Sum[b[u+j1, oj, j], {j, 1, o}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* JeanFrançois Alcover, Mar 05 2015, after Alois P. Heinz *)


CROSSREFS

Columns k=010 give: A111004, A263885, A263886, A263887, A263888, A263889, A263890, A263891, A263892, A263893, A263894.
T(2n+1,n) gives A001147.
T(2n+2,n) gives 2*A076729.
Cf. A162975, A264781 (pattern 12354).
Sequence in context: A104546 A121632 A186361 * A121579 A214733 A106852
Adjacent sequences: A197362 A197363 A197364 * A197366 A197367 A197368


KEYWORD

nonn,easy,tabf


AUTHOR

Peter Bala, Oct 14 2011


STATUS

approved



