|
| |
|
|
A125305
|
|
Number of 132-segmented permutations of length n.
|
|
0
| |
|
|
1, 1, 2, 6, 18, 57, 190, 654, 2306, 8290, 30272, 111973, 418666, 1579803, 6008464, 23009240, 88645034, 343334976, 1336105472, 5221667740, 20485272152, 80645855014, 318489386884, 1261428593649, 5009356014722, 19941674099985
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
LINKS
| A. Claesson, Home page (listed in lieu of email address)
A. Claesson, Counting segmented permutations using bicolored Dyck paths, The Electronic Journal of Combinatorics 12 (2005), #R39.
|
|
|
FORMULA
| a(n) = sum(binomial(n-2*k,k)*catalan(n-2*k),k=0..floor(n/3)); generating function = C(x + x^3), where C(x) is the generating function for the Catalan numbers.
G.f. A(x)=1/(1-z/(1-z/(1-z/(...)))) where z=x+x^3 (continued fraction, a special case of the previous formula) [Joerg Arndt, Mar 18 2011]
|
|
|
EXAMPLE
| a(4)=18 because of the 24 permutations of {1,2,3,4} only 1243, 1342, 1423, 1432, 2143, 2413 are not 132-segmented; i.e., those permutations have more occurrences of the pattern (1-3-2) than of the pattern (132).
|
|
|
MAPLE
| a := n->sum(binomial(n-2*k, k)*catalan(n-2*k), k=0..floor(n/3)); seq(a(n), n=0..25);
|
|
|
CROSSREFS
| Sequence in context: A126983 A104629 A000957 * A148458 A148459 A081057
Adjacent sequences: A125302 A125303 A125304 * A125306 A125307 A125308
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Anders Claesson Dec 09 2006
|
| |
|
|
