A125306 Number of 123-segmented permutations of length n.

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

Vincenzo Librandi, Table of n, a(n) for n = 0..200

D. Callan, Permutations avoiding a nonconsecutive instance of a 2- or 3-letter pattern, arXiv:math/0610428 [math.CO], 2006.

Anders Claesson, Home page (listed in lieu of email address).

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

Adjacent sequences: A125303 A125304 A125305 * A125307 A125308 A125309

Keyword

nonn

Author

Anders Claesson (anders(AT)ru.is), Dec 09 2006

Status

approved