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

Author

Anders Claesson, Dec 09 2006

Keywords

• nonn

Comments

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

Examples

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

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

Programs

Maple

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

Mathematica

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

Formula

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