|
Search: id:A125305
|
|
|
| A125305 |
|
Number of 132-segmented permutations of length n. |
|
+0
1
|
|
| 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; listen)
|
|
|
OFFSET
|
0,3
|
|
|
LINKS
|
A. Claesson, Home page (listed in lieu of email address)
A. Claesson,Counting segmented permutations using bicoloured 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.
|
|
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 this_sequence A081057 A000137 A085139
Adjacent sequences: A125302 A125303 A125304 this_sequence A125306 A125307 A125308
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Anders Claesson Dec 09 2006
|
|
|
Search completed in 0.002 seconds
|
