login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003122 Number of Hamiltonian rooted triangulations with n internal nodes and 3 external nodes.
(Formerly M3049)
4
1, 3, 18, 136, 1170, 10962, 109158, 1138032, 12298392, 136803060, 1558392462, 18110005704, 214056200904, 2567339253864, 31186302919290, 383088799324192, 4752646170647124, 59485067001886392, 750454803914305388, 9535654298173667520, 121954511767711578480, 1568979034333191541588, 20295073846979967634038 (list; graph; refs; listen; history; text; internal format)
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: A289430 A247452 A118970 * A275549 A039618 A183363

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 01:16 EST 2018. Contains 317279 sequences. (Running on oeis4.)