login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
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 A378426 A209797
KEYWORD
nonn
AUTHOR
Anders Claesson (anders(AT)ru.is), Dec 09 2006
STATUS
approved