|
| |
|
|
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.
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
|
|
|
|
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)):
|
|
|
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.
|
|
|
KEYWORD
|
nonn,easy,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
