login
This site is supported by donations to The OEIS 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). 12
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.

LINKS

Alois P. Heinz, Rows n = 0..100, flattened

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

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

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 07:06 EST 2018. Contains 317162 sequences. (Running on oeis4.)