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,3

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

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.

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

Example

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

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

Crossrefs

Sequence in context: A000957 A307496 A339044 * A369621 A273203 A148458

Adjacent sequences: A125302 A125303 A125304 * A125306 A125307 A125308

Keyword

nonn

Author

Anders Claesson, Dec 09 2006

Status

approved