A003122 Number of Hamiltonian rooted triangulations with n internal nodes and 3 external nodes.
1, 3, 18, 136, 1170, 10962, 109158, 1138032, 12298392, 136803060, 1558392462, 18110005704, 214056200904, 2567339253864, 31186302919290, 383088799324192, 4752646170647124, 59485067001886392, 750454803914305388, 9535654298173667520, 121954511767711578480, 1568979034333191541588, 20295073846979967634038
Offset: 0
Keywords
References
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Peter J. Taylor, Table of n, a(n) for n = 0..500 (terms 0..50 from _Remigiusz Suwalski_)
- P. N. Rathie, The enumeration of Hamiltonian polygons in rooted planar triangulations, Discrete Math., 6 (1973), 163-168.
- _Peter J. Taylor_, C# program to compute terms
Programs
-
Mathematica
functiony[l_] := If[Range[Length[l]].l > Length[l], {}, len = Length[l]; Select[Permutations[l], #.Range[len] == len &]] functionb[s_, m_] := Module[{l = 0}, If[m + s == 0, 1, If[m s == 0, 0, If[m >= s, If[m > s, 0, 1], If[m == 1, CatalanNumber[s]^2, If[s - m == 1, 4 m, l = Flatten[Map[functiony, IntegerPartitions[s + m, {s}] - 1], 1]; Map[Times @@ # &, Map[Map[r, Range[1, s]]^# &, l]].(Map[Times @@ # &, Map[Factorial, l]])^(-1)*m!] ] ] ] ] ] a[n_, s_] := Sum[Binomial[n, m] b[s, m], {m, 1, s}] b[s_, m_] := If[s + m > 0, table1[[s + 1, m + 1]], If[s + m == 0, 1, 0]] f[n_, k_] := k (2 n + 2 k - 4)! (2 n + k - 1)!/((n + k - 1)! (n + k - 2)! n! (n + k)!) - Sum[table2[[s + 1]] a[k + s, n - s], {s, 0, n - 1}] r[n_] := (Binomial[2 n, n])^2/(n^2 + 2 n + 1) answer[n_] := f[n, 3] index = 24; table1 = Table[functionb[s, m], {s, 0, index}, {m, 0, index}]; table2 = Range[index]; For[i = 2, i <= index, i++, table2[[i]] = f[i - 1, 3]]; f[index - 1, 3] (* Xesda Gonia, Dec 29 2015 *) -
PARI
P(n,k) = k*(2*n+2*k-4)!*(2*n+k-1)!/((n+k-1)!*(n+k-2)!*n!*(n+k)!); F(K, N=23) = { my(x='x + O('x^(K+1)), t='t + O('t^(N+1)), r='t*Ser(vector(N, n, sqr(binomial(2*n,n)/(n+1))),'t), p=x^3*Ser(apply(k->Ser(vector(N, n, P(n-1,k)),'t), [3..K])), s=serreverse(t*(1+r)), f=subst(subst(p, 't, s), 'x, 'x*s/'t)); Vec(polcoeff(f,K)); }; F(3) \\ Gheorghe Coserea, Aug 18 2017
Formula
r(n) = (binomial(2*n, n) / (n + 1))^2.
B(s, m) = sum((m! / m_1! ... m_s!) * r(1)^{m_1} ... r(s)^{m_s}) where the sum is over all partitions of s such that s = m_1 + 2*m_2 + ... + s*m_s and m = m_1 + m_2 + ... + m_s.
A(n, s) = Sum_{m=1..s} binomial(n, m) * B(s, m).
p(n, k) = k * (2*n + 2*k - 4)! * (2*n + k - 1)! / ((n + k - 1)! * (n + k - 2)! * n! * (n + k)!).
f(n, k) = p(n, k) - Sum_{s=0..n-1} f(s, k) * A(k+s, n-s).
a(n) = f(n, 3). - Sean A. Irvine, Feb 02 2015
Extensions
More terms and title clarified by Sean A. Irvine, Feb 02 2015
Three more terms from Xesda Gonia, Dec 29 2015