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
Keywords
Examples
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).
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.
Crossrefs
Cf. A000108.
Programs
-
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 *)
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
Comments