|
|
A372310
|
|
Number of permutations of length n avoiding the pattern 1324 and with 1 appearing before n.
|
|
0
|
|
|
1, 3, 11, 45, 198, 919, 4446, 22239, 114347, 601722, 3229614, 17632437, 97707195, 548538588, 3115293151, 17875151109, 103511938302, 604392787819, 3555410248782, 21057224371290, 125484804821226, 752020468811244, 4530163818778839, 27419805899781843, 166694596163875206
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,2
|
|
COMMENTS
|
This sequence counts the number of permutations of size n written in one-line notation that avoid the pattern 1324 and have the 1 appearing before the n.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: A(x) = (x*(B(x)-2))/(3-B(x)), where B(x) is the g.f. for A000139. (See arxiv paper by Gil, Lopez, Weiner.)
G.f. satisfies 0 = x^4*(8*x-1) + x^2*(9*x-1)*(4*x-1)*A(x) + x*(6*x-1)*(9*x-2)*A(x)^2 + (27*x^2-9*x+1)*A(x)^3.
|
|
EXAMPLE
|
For n=4, a(4)=11 is counting the permutations (in one-line notation): 1234, 1243, 1342, 1423, 1432, 2134, 2143, 2314, 3124, 3142, 3214.
|
|
MAPLE
|
f:= proc(n) f(n):= 2*(3*n)!/((2*n+1)!*(n+1)!) end:
a:= proc(n) option remember; `if`(n=1, 1,
add(a(n-i)*f(i), i=1..n))
end:
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|