login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A125305 Number of 132-segmented permutations of length n. 2
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 (list; graph; refs; listen; history; text; internal format)
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: A126983 A104629 A000957 * A273203 A148458 A148459

Adjacent sequences:  A125302 A125303 A125304 * A125306 A125307 A125308

KEYWORD

nonn

AUTHOR

Anders Claesson, Dec 09 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 00:36 EDT 2018. Contains 316327 sequences. (Running on oeis4.)