Anders Claesson - cp's OEIS frontend

User: Anders Claesson

Anders Claesson has authored 2 sequences.

A125305 Number of 132-segmented permutations of length n.

1, 1, 2, 6, 18, 57, 190, 654, 2306, 8290, 30272, 111973, 418666, 1579803, 6008464, 23009240, 88645034, 343334976, 1336105472, 5221667740, 20485272152, 80645855014, 318489386884, 1261428593649, 5009356014722, 19941674099985

Offset: 0

Anders Claesson, Dec 09 2006

nonn

From [Callan 2006] Theorem 3, the number of permutations on [n] that avoid a nonconsecutive 132 pattern is Sum_{k=0..n/3} binomial(n-2k, k) C_{n-2k}. - Michael Somos, Sep 07 2018

			a(4)=18 because of the 24 permutations of {1,2,3,4} only 1243, 1342, 1423, 1432, 2143, 2413 are not 132-segmented; i.e., those permutations have more occurrences of the pattern (1-3-2) than of the pattern (132).

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.
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.

a := n->sum(binomial(n-2*k,k)*catalan(n-2*k),k=0..floor(n/3)); seq(a(n),n=0..25);

Table[Sum[Binomial[n - 2 k, k] Binomial[2 n - 4 * k, n - 2 k]/(n - 2 k + 1), {k, 0, Floor[n/3]}], {n, 0, 40}] (* Vaclav Kotesovec, Mar 21 2014 *)

a(n) = sum(binomial(n-2*k,k)*catalan(n-2*k),k=0..floor(n/3)); generating function = C(x + x^3), where C(x) is the generating function for the Catalan numbers.
G.f.: A(x)=1/(1-z/(1-z/(1-z/(...)))) where z=x+x^3 (continued fraction, a special case of the previous formula). - Joerg Arndt, Mar 18 2011
Recurrence: (n+1)*a(n) = 2*(2*n-1)*a(n-1) - (n+1)*a(n-2) + 8*(n-2)*a(n-3) + 2*(2*n-7)*a(n-5). - Vaclav Kotesovec, Mar 21 2014
a(n) ~ sqrt(48 - 4*(27+3*sqrt(273))^(2/3) + 9*(27+3*sqrt(273))^(1/3)) / ((27+3*sqrt(273))^(1/6) * sqrt(3*Pi)) * (16 + (118+6*sqrt(273))^(2/3) + 4*(118+6*sqrt(273))^(1/3))^n / ((118+6*sqrt(273))^(n/3) * n^(3/2) * 3^n). - Vaclav Kotesovec, Mar 21 2014

A125306 Number of 123-segmented permutations of length n.

Original entry on oeis.org

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

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

nonn

Permutations avoiding a nonconsecutive 321 pattern. - Ralf Stephan, May 09 2007

			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).

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.

Cf. A000108.

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);

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 *)

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

cp's OEIS Frontend

User: Anders Claesson

A125305 Number of 132-segmented permutations of length n.

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

Formula