A125305 - OEIS

%I #22 Sep 07 2018 03:33:05

%S 1,1,2,6,18,57,190,654,2306,8290,30272,111973,418666,1579803,6008464,

%T 23009240,88645034,343334976,1336105472,5221667740,20485272152,

%U 80645855014,318489386884,1261428593649,5009356014722,19941674099985

%N Number of 132-segmented permutations of length n.

%C 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

%H Vincenzo Librandi, <a href="/A125305/b125305.txt">Table of n, a(n) for n = 0..200</a>

%H D. Callan, <a href="https://arxiv.org/abs/math/0610428">Permutations avoiding a nonconsecutive instance of a 2- or 3-letter pattern</a>, arXiv:math/0610428[math.CO], 2006.

%H A. Claesson, <a href="http://www.math.ru.is/anders">Home page (listed in lieu of email address)</a>

%H A. Claesson, <a href="http://www.combinatorics.org/Volume_12/Abstracts/v12i1r39.html">Counting segmented permutations using bicolored Dyck paths</a>, The Electronic Journal of Combinatorics 12 (2005), #R39.

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

%F 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

%F 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

%F 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

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

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

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

%K nonn

%O 0,3

%A _Anders Claesson_, Dec 09 2006