|
| |
|
|
A125306
|
|
Number of 123-segmented permutations of length n.
|
|
0
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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: A111961 A190861 A071721 * A064310 A126983 A104629
Adjacent sequences: A125303 A125304 A125305 * A125307 A125308 A125309
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Anders Claesson (anders(AT)ru.is), Dec 09 2006
|
| |
|
|
