|
| |
|
|
A109033
|
|
Number of permutations in S_n avoiding the patterns 1342 and 2143.
|
|
4
| |
|
|
1, 1, 2, 6, 22, 88, 368, 1584, 6968, 31192, 141656, 651136, 3023840, 14166496, 66876096, 317809216, 1519163456, 7299577216, 35237444736, 170812433536, 831127053696, 4057858988416, 19873611712896, 97609555091456
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Also number of permutations in S_n avoiding the patterns 3142 and 2341. Partial sums of A109034.
Hankel transform is 2^floor(n^2/3) (see A134751). [From Paul Barry (pbarry(AT)wit.ie), Dec 15 2008]
|
|
|
REFERENCES
| Ian Le, Wilf classes of pairs of permutations of length 4, The Electronic J. of Combinatorics, 12, 2005, R25.
Kremer, Darla and Shiu, Wai Chee; Finite transition matrices for permutations avoiding pairs of length four patterns. Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
|
|
|
LINKS
| Wikipedia, Permutation classes avoiding two patterns of length 4.
|
|
|
FORMULA
| G.f.: (1-sqrt(1-8*x+16*x^2-8*x^3))/(4*x*(1-x))
Contribution from Paul Barry (pbarry(AT)wit.ie), Dec 15 2008: (Start)
G.f.: (1-x)*c(2*x*(1-x)^2), where c(x) is the g.f. of A000108;
a(n):=sum{k=0..n, (-1)^(n-k)*C(2k+1,n-k)*2^k*A000108(k)}; (End)
G.f.: 1/(1-x/(1-x/(1-2x/(1-x/(1-x/(1-2x/(1-x/(1-x/(1-2x...... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), Dec 15 2008]
a(n)= Sum_{k, 0<=k<=n} A091866(n,k)*2^(n-k). [From Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Nov 27 2009]
|
|
|
EXAMPLE
| a(4)=22 because all permutations of 1234 qualify with the exception of 1342 and 2143.
|
|
|
MAPLE
| G:=(1-sqrt(1-8*x+16*x^2-8*x^3))/4/x/(1-x): Gser:=series(G, x=0, 30): 1, seq(coeff(Gser, x^n), n=1..27);
|
|
|
MATHEMATICA
| CoefficientList[Series[(1-Sqrt[1-8x+16x^2-8x^3])/(4x(1-x)), {x, 0, 30}], x] (* From Harvey P. Dale, July 02 2011 *)
|
|
|
CROSSREFS
| Cf. A109034.
Sequence in context: A165537 A165538 A165539 * A049135 A049127 A199481
Adjacent sequences: A109030 A109031 A109032 * A109034 A109035 A109036
|
|
|
KEYWORD
| nonn,changed
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 16 2005
|
| |
|
|
