A131312 Number of labeled 3-arch graphs on n nodes.

0, 0, 1, 1, 10, 380, 34405, 5919536, 1709074584, 764754595200, 501266271119625, 461131039993333600, 575567346874153958896, 948234014731772610333856, 2015213091846867369590804125, 5418520468131267088808607104000, 18128426763624683428523183481856000

Offset

1,5

Links

Table of n, a(n) for n=1..17.

Allan Bickle,  A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.

Saverio Caminiti and Emanuele G. Fusco, On the Number of Labeled k-arch Graphs, Journal of Integer Sequences, Vol 10 (2007), Article 07.7.5

Formula

The number of labeled 3-arch graphs with n>4 nodes is given by f(n,3,n-3-1,0,3) where f is the recursive function described by the PARI/GP code below.

Prog

(PARI) f(n, k, i, u, j)={ local(s=0); if (i==1, binomial(n-u, j)*binomial(u, k-j), for (c=0, min(k, n-(i-1)-(u+j)), s+=f(n, k, i-1, u+j, c) ); binomial(n-u, j)*binomial(u, k-j)*s ) }

Crossrefs

Cf. A098721-A098724, A131311-A131315.

Sequence in context: A200804 A277663 A000591 * A055733 A349480 A203774

Adjacent sequences: A131309 A131310 A131311 * A131313 A131314 A131315

Keyword

nonn

Author

Saverio Caminiti and Emanuele G. Fusco (fusco(AT)di.uniroma1.it), Sep 18 2007

Extensions

Edited by N. J. A. Sloane, Oct 02 2007

Terms a(11) and beyond from Andrew Howroyd, Nov 07 2019

Status

approved