A197365 - OEIS

%I #48 May 20 2023 18:38:51

%S 1,1,2,5,1,16,8,63,54,3,296,368,56,1623,2649,753,15,10176,20544,9024,

%T 576,71793,172596,104814,13572,105,562848,1569408,1228608,259968,7968,

%U 4853949,15398829,14824314,4532034,306729,945,45664896,162412416,185991936,75929856

%N 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((n-1)/2))).

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

%C From _Petros Hadjicostas_, Nov 05 2019: (Start)

%C 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, (n-1)/t).

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

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

%C (End)

%H Alois P. Heinz, <a href="/A197365/b197365.txt">Rows n = 0..100, flattened</a>

%H A. Baxter, B. Nakamura, and D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/auto.html">Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes</a>, 2011.

%H S. Elizalde and M. Noy, <a href="http://dx.doi.org/10.1016/S0196-8858(02)00527-4">Consecutive patterns in permutations</a>, Adv. Appl. Math. 30 (2003), 110-125.

%H Petros Hadjicostas, <a href="/A197365/a197365.txt">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</a>. [Here r = 0 and in the program t = r + 2 = 2.]

%F E.g.f.: 1/(1 - int_{t = 0..z} exp((u-1)*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! + ....

%F n-th row sum = n!. First column is A111004.

%e Table begins

%e .n\k.|......0......1.....2......3

%e = = = = = = = = = = = = = = = = =

%e ..0..|......1

%e ..1..|......1

%e ..2..|......2

%e ..3..|......5......1

%e ..4..|.....16......8

%e ..5..|.....63.....54.....3

%e ..6..|....296....368....56

%e ..7..|...1623...2649...753....15

%e ..8..|..10176..20544..9024...576

%e ...

%e 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).

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

%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(

%p       add(b(u-j, o+j-1, 0)*`if`(j<t, x, 1), j=1..u)+

%p       add(b(u+j-1, o-j, j), j=1..o)))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):

%p seq(T(n), n=0..14);  # _Alois P. Heinz_, Oct 30 2013

%t b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Expand[Sum[b[u-j, o+j-1, 0]*If[j<t, x, 1], {j, 1, u}] + Sum[b[u+j-1, o-j, 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 (* _Jean-François Alcover_, Mar 05 2015, after _Alois P. Heinz_ *)

%Y Columns k=0-10 give: A111004, A263885, A263886, A263887, A263888, A263889, A263890, A263891, A263892, A263893, A263894.

%Y T(2n+1,n) gives A001147.

%Y T(2n+2,n) gives 2*A076729.

%Y Cf. A162975, A264781 (pattern 12354).

%K nonn,easy,tabf

%O 0,3

%A _Peter Bala_, Oct 14 2011