OFFSET
2,5
LINKS
T. D. Noe, Table of n, a(n) for n=2..200
D. Birmajer, J. B. Gil, and M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 93
S. Morrison, E. Peters, and N. Snyder, Categories generated by a trivalent vertex, arXiv preprint arXiv:1501.06869 [math.QA], 2015.
Len Smiley, A Nameless Number
Len Smiley, Variants of Schroeder Dissections, arXiv:math/9907057 [math.CO], 1999.
Vasiliki Velona, Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs, arXiv:1802.03719 [math.CO], 2018.
FORMULA
G.f.: A(x) = Sum_{n>0} a(n)*x^(n-1) satisfies A(x) - A(x)^2 - A(x)^3 = x*(1 - A(x)).
a(n) = A052524(n-1)/(n-1)!, for n > 0.
Let g = (1-x)/(1-x-x^2) then a(m) = coeff. of x^(m-2) in g^(m-1)/(m-1).
D-finite with recurrence: 5*(n-1)*n*(37*n-95)*a(n) = 4*(n-1)*(74*n^2 -301*n +300)*a(n-1) + 8*(2*n-5)*(74*n^2 -301*n +297)*a(n-2) - 2*(n-3)*(2*n-7)*(37*n-58)*a(n-3). - Vaclav Kotesovec, Aug 10 2013
a(n) = A143363(n-3) + Sum_{k=0..n-6} ( A143363(k+1)*a(n-k-2) ). - Muhammed Sefa Saydam, Feb 14 2025 and Aug 05 2025
EXAMPLE
a(4)=a(5)=1 because of null placement; a(6)=4 because in addition to not placing any, we might also place one between any of the 3 pairs of opposite vertices.
MAPLE
a := n->1/(n-1)*sum(binomial(n+k-2, k)*binomial(n-k-3, k-1), k=0..floor(n/2-1)); seq(a(i), i=2..30);
MATHEMATICA
(* Programs from Jean-François Alcover, Apr 14 2017: Start *)
(* First program *)
a[2]=1; a[n_] := Sum[Binomial[n+k-2, k]*Binomial[n-k-3, k-1], {k, 0, Floor[n/2]-1}]/(n-1);
(* 2nd program: *)
x*InverseSeries[Series[(y-y^2-y^3)/(1-y), {y, 0, 29}], x]
(* 3rd program: *)
a[2]=1; a[3]=0; a[n_] := HypergeometricPFQ[{2-n/2, 5/2-n/2, n}, {2, 4-n}, -4]; Table[a[n], {n, 2, 30}]
(* End *)
PROG
(PARI) a(n)=if(n<2, 0, polcoeff(serreverse((x-x^2-x^3)/(1-x)+x*O(x^n)), n-1))
(Magma)
A046736:= func< n | n eq 2 select 1 else (&+[Binomial(n+k-2, k)*Binomial(n-k-3, k-1)/(n-1): k in [0..Floor(n/2)-1]]) >;
[A046736(n): n in [2..40]]; // G. C. Greubel, Jul 31 2024
(SageMath)
def A046736(n): return 1 if n==2 else sum(binomial(n+k-2, k)*binomial(n-k-3, k-1)//(n-1) for k in range(n//2))
[A046736(n) for n in range(2, 41)] # G. C. Greubel, Jul 31 2024
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
STATUS
approved