login
A131312
Number of labeled 3-arch graphs on n nodes.
1
0, 0, 1, 1, 10, 380, 34405, 5919536, 1709074584, 764754595200, 501266271119625, 461131039993333600, 575567346874153958896, 948234014731772610333856, 2015213091846867369590804125, 5418520468131267088808607104000, 18128426763624683428523183481856000
OFFSET
1,5
LINKS
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
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