|
Search: id:A109033
|
|
|
| A109033 |
|
Number of permutations in S_n avoiding the patterns 1342 and 2143. |
|
+0
5
|
|
| 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; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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.
|
|
FORMULA
|
G.f.=[1-sqrt(1-8x+16x^2-8x^3)]/[4x(1-x)]
Contribution from Paul Barry (pbarry(AT)wit.ie), Dec 15 2008: (Start)
G.f.: (1-x)c(2x(1-x)^2), c(x) 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);
|
|
CROSSREFS
|
Cf. A109034.
Sequence in context: A165537 A165538 A165539 this_sequence A049135 A049127 A049137
Adjacent sequences: A109030 A109031 A109032 this_sequence A109034 A109035 A109036
|
|
KEYWORD
|
nonn,new
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Jun 16 2005
|
|
|
Search completed in 0.002 seconds
|
