cp's OEIS Frontend

A003122 Number of Hamiltonian rooted triangulations with n internal nodes and 3 external nodes.

%I A003122 M3049 #40 Aug 21 2017 05:52:15
%S A003122 1,3,18,136,1170,10962,109158,1138032,12298392,136803060,1558392462,
%T A003122 18110005704,214056200904,2567339253864,31186302919290,
%U A003122 383088799324192,4752646170647124,59485067001886392,750454803914305388,9535654298173667520,121954511767711578480,1568979034333191541588,20295073846979967634038
%N A003122 Number of Hamiltonian rooted triangulations with n internal nodes and 3 external nodes.
%D A003122 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003122 Peter J. Taylor, <a href="/A003122/b003122.txt">Table of n, a(n) for n = 0..500</a> (terms 0..50 from _Remigiusz Suwalski_)
%H A003122 P. N. Rathie, <a href="http://dx.doi.org/10.1016/0012-365X(73)90046-0">The enumeration of Hamiltonian polygons in rooted planar triangulations</a>, Discrete Math., 6 (1973), 163-168.
%H A003122 _Peter J. Taylor_, <a href="/A003122/a003122.txt">C# program to compute terms</a>
%F A003122 r(n) = (binomial(2*n, n) / (n + 1))^2.
%F A003122 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.
%F A003122 A(n, s) = Sum_{m=1..s} binomial(n, m) * B(s, m).
%F A003122 p(n, k) = k * (2*n + 2*k - 4)! * (2*n + k - 1)! / ((n + k - 1)! * (n + k - 2)! * n! * (n + k)!).
%F A003122 f(n, k) = p(n, k) - Sum_{s=0..n-1} f(s, k) * A(k+s, n-s).
%F A003122 a(n) = f(n, 3). - _Sean A. Irvine_, Feb 02 2015
%t A003122 functiony[l_] :=
%t A003122 If[Range[Length[l]].l > Length[l], {}, len = Length[l];
%t A003122   Select[Permutations[l], #.Range[len] == len &]]
%t A003122 functionb[s_, m_] := Module[{l = 0},
%t A003122   If[m + s == 0, 1,
%t A003122    If[m s == 0, 0,
%t A003122     If[m >= s,
%t A003122      If[m > s, 0, 1],
%t A003122      If[m == 1, CatalanNumber[s]^2,
%t A003122       If[s - m == 1, 4 m,
%t A003122        l =
%t A003122         Flatten[Map[functiony, IntegerPartitions[s + m, {s}] - 1], 1];
%t A003122         Map[Times @@ # &,
%t A003122           Map[Map[r, Range[1, s]]^# &,
%t A003122            l]].(Map[Times @@ # &, Map[Factorial, l]])^(-1)*m!]
%t A003122       ]
%t A003122      ]
%t A003122     ]
%t A003122    ]
%t A003122   ]
%t A003122 a[n_, s_] := Sum[Binomial[n, m] b[s, m], {m, 1, s}]
%t A003122 b[s_, m_] :=
%t A003122 If[s + m > 0, table1[[s + 1, m + 1]], If[s + m == 0, 1, 0]]
%t A003122 f[n_, k_] :=
%t A003122 k (2 n + 2 k -
%t A003122       4)! (2 n + k - 1)!/((n + k - 1)! (n + k - 2)! n! (n + k)!) -
%t A003122   Sum[table2[[s + 1]] a[k + s, n - s], {s, 0, n - 1}]
%t A003122 r[n_] := (Binomial[2 n, n])^2/(n^2 + 2 n + 1)
%t A003122 answer[n_] := f[n, 3]
%t A003122 index = 24;
%t A003122 table1 = Table[functionb[s, m], {s, 0, index}, {m, 0, index}];
%t A003122 table2 = Range[index];
%t A003122 For[i = 2, i <= index, i++, table2[[i]] = f[i - 1, 3]];
%t A003122 f[index - 1, 3]
%t A003122 (* _Xesda Gonia_, Dec 29 2015 *)
%o A003122 (C#) See Taylor link
%o A003122 (PARI)
%o A003122 P(n,k) = k*(2*n+2*k-4)!*(2*n+k-1)!/((n+k-1)!*(n+k-2)!*n!*(n+k)!);
%o A003122 F(K, N=23) = {
%o A003122   my(x='x + O('x^(K+1)), t='t + O('t^(N+1)),
%o A003122      r='t*Ser(vector(N, n, sqr(binomial(2*n,n)/(n+1))),'t),
%o A003122      p=x^3*Ser(apply(k->Ser(vector(N, n, P(n-1,k)),'t), [3..K])),
%o A003122      s=serreverse(t*(1+r)), f=subst(subst(p, 't, s), 'x, 'x*s/'t));
%o A003122   Vec(polcoeff(f,K));
%o A003122 };
%o A003122 F(3) \\ _Gheorghe Coserea_, Aug 18 2017
%Y A003122 Cf. A003123, A005979.
%K A003122 nonn
%O A003122 0,2
%A A003122 _N. J. A. Sloane_
%E A003122 More terms and title clarified by _Sean A. Irvine_, Feb 02 2015
%E A003122 Three more terms from _Xesda Gonia_, Dec 29 2015