|
Search: id:A125306
|
|
|
| A125306 |
|
Number of 123-segmented permutations of length n. |
|
+0
1
|
|
| 1, 1, 2, 6, 18, 56, 182, 607, 2064, 7132, 24970, 88383, 315748, 1137014, 4122762, 15039631, 55157790, 203255438, 752190764, 2794352648, 10417047964, 38956725596, 146108755556, 549442692378, 2071236137154, 7825588757910
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
Permutations avoiding a nonconsecutive 321 pattern. - Ralf Stephan, May 09 2007
|
|
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.
D. Callan, Permutations avoiding a nonconsecutive instance of a 2- or 3-letter pattern
|
|
FORMULA
|
a(n) = sum(sum((2*k+i+1)/(n-k+i+1)*binomial(k-1,k-i)*binomial(2*n-4*k+i,n-3*k),i=0..k),k=0..floor(n/3)); generating function = (C(x)-1)/(1-x/(1+x^2)*(C(x)-1)) in which C(x) is the ogf for the Catalan numbers.
|
|
EXAMPLE
|
a(4)=18 because of the 24 permutations of {1,2,3,4} only 1234, 1243, 1324, 1423, 2134 and 2314 are not 123-segmented; i.e., they contain more occurrences of the pattern (1-2-3) than of the pattern (123).
|
|
MAPLE
|
a := n->add(add((2*k+i+1)/(n-k+i+1)*binomial(k-1, k-i)*binomial(2*n-4*k+i, n-3*k), i=0..k), k=0..floor(n/3)); seq(a(n), n=0..25);
|
|
CROSSREFS
|
Sequence in context: A091142 A111961 A071721 this_sequence A064310 A126983 A104629
Adjacent sequences: A125303 A125304 A125305 this_sequence A125307 A125308 A125309
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Anders Claesson (anders(AT)ru.is), Dec 09 2006
|
|
|
Search completed in 0.002 seconds
|
