login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A125306 Number of 123-segmented permutations of length n. 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; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
Permutations avoiding a nonconsecutive 321 pattern. - Ralf Stephan, May 09 2007
LINKS
Anders Claesson, Counting segmented permutations using bicolored Dyck paths, The Electronic Journal of Combinatorics 12 (2005), #R39.
FORMULA
a(n) = Sum_{k = 0..floor(n/3)} Sum_{i = 0..k} ((2*k + i + 1)/(n -k + i + 1)) * binomial(k-1, k-i) * binomial(2*n - 4*k + i, n - 3*k).
O.g.f.: 1 + (C(x) - 1)/(1 - x/(1 + x^2) * (C(x) - 1)), where C(x) is the o.g.f. for the Catalan numbers (A000108). [corrected for a(0) = 1 by Vaclav Kotesovec, Mar 21 2014]
a(n) ~ 289 * 4^n / (169 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 21 2014
Conjecture: 2*(n+2)*a(n) - 6*n*a(n-1) + 4*(-n-2)*a(n-2) + (-13*n+34)*a(n-3) + 2*(-5*n+17)*a(n-4) + (-7*n+40)*a(n-5) + 2*(-2*n+11)*a(n-6) = 0. - R. J. Mathar, May 30 2014
O.g.f.: (C(x)*x^2 - (C(x) - 1)*x + C(x))/(x^2 - (C(x) - 1)*x + 1), where C(x) is the o.g.f. for the Catalan numbers (A000108). - Petros Hadjicostas, Aug 06 2020
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);
MATHEMATICA
CoefficientList[Series[1 + ((1 - (1 - 4 x)^(1/2))/(2 x) - 1)/(1 - x/(1 + x^2) ((1 - (1 - 4 x)^(1/2))/(2 x) - 1)), {x, 0, 40}], x] (* Vaclav Kotesovec, Mar 21 2014 *)
CROSSREFS
Cf. A000108.
Sequence in context: A111961 A190861 A071721 * A352076 A209797 A064310
KEYWORD
nonn
AUTHOR
Anders Claesson (anders(AT)ru.is), Dec 09 2006
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 22 10:40 EDT 2024. Contains 374490 sequences. (Running on oeis4.)