A125306 - OEIS

%I #29 Aug 07 2020 02:06:52

%S 1,1,2,6,18,56,182,607,2064,7132,24970,88383,315748,1137014,4122762,

%T 15039631,55157790,203255438,752190764,2794352648,10417047964,

%U 38956725596,146108755556,549442692378,2071236137154,7825588757910

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

%C Permutations avoiding a nonconsecutive 321 pattern. - _Ralf Stephan_, May 09 2007

%H Vincenzo Librandi, <a href="/A125306/b125306.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 Anders Claesson, <a href="https://web.archive.org/web/20090102181113/http://www.math.ru.is/anders">Home page (listed in lieu of email address)</a>.

%H Anders 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_{k = 0..floor(n/3)} Sum_{i = 0..k} ((2*k + i + 1)/(n -k + i + 1)) * binomial(k-1, k-i) * binomial(2*n - 4*k + i, n - 3*k).

%F O.g.f.: 1 + (C(x) - 1)/(1 - x/(1 + x^2) * (C(x) - 1)), where C(x) is the o.g.f. for the Catalan numbers (A000108). [corrected for a(0) = 1 by _Vaclav Kotesovec_, Mar 21 2014]

%F a(n) ~ 289 * 4^n / (169 * sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Mar 21 2014

%F Conjecture: 2*(n+2)*a(n) - 6*n*a(n-1) + 4*(-n-2)*a(n-2) + (-13*n+34)*a(n-3) + 2*(-5*n+17)*a(n-4) + (-7*n+40)*a(n-5) + 2*(-2*n+11)*a(n-6) = 0. - _R. J. Mathar_, May 30 2014

%F O.g.f.: (C(x)*x^2 - (C(x) - 1)*x + C(x))/(x^2 - (C(x) - 1)*x + 1), where C(x) is the o.g.f. for the Catalan numbers (A000108). - _Petros Hadjicostas_, Aug 06 2020

%e a(4) = 18 because of the 24 permutations of {1, 2, 3, 4} only 1234, 1243, 1324, 1423, 2134 and 2314 are not 123-segmented; i.e., they contain more occurrences of the pattern (1-2-3) than of the pattern (123).

%p a := n->add(add((2*k+i+1)/(n-k+i+1)*binomial(k-1,k-i)*binomial(2*n-4*k+i,n-3*k),i=0..k),k=0..floor(n/3)); seq(a(n),n=0..25);

%t CoefficientList[Series[1 + ((1 - (1 - 4 x)^(1/2))/(2 x) - 1)/(1 - x/(1 + x^2) ((1 - (1 - 4 x)^(1/2))/(2 x) - 1)), {x, 0, 40}], x] (* _Vaclav Kotesovec_, Mar 21 2014 *)

%Y Cf. A000108.

%K nonn

%O 0,3

%A Anders Claesson (anders(AT)ru.is), Dec 09 2006