Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the 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