login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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((n-1)/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, (n-1)/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 Wilf-classes, 2011.

S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.

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((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! + ....

n-th 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(u-j, o+j-1, 0)*`if`(j<t, x, 1), j=1..u)+

      add(b(u+j-1, o-j, 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[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 *)

CROSSREFS

Columns k=0-10 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 18 18:17 EDT 2021. Contains 345120 sequences. (Running on oeis4.)