A003122 Number of Hamiltonian rooted triangulations with n internal nodes and 3 external nodes. (Formerly M3049)

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,2

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

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

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 *)

Prog

(C#) See Taylor link
(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

Crossrefs

Cf. A003123, A005979.

Sequence in context: A371416 A376224 A118970 * A275549 A357403 A039618

Adjacent sequences: A003119 A003120 A003121 * A003123 A003124 A003125

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms and title clarified by Sean A. Irvine, Feb 02 2015

Three more terms from Xesda Gonia, Dec 29 2015

Status

approved