A131311 Number of labeled 2-arch graphs on n nodes.

0, 1, 1, 6, 100, 3285, 177471, 14188888, 1569185136, 229087571625, 42657089362525, 9865968972312816, 2775121127493066144, 933088633696985015341, 369664023805893580624875, 170462028446539785915840000, 90535875809937268263059201536, 54880459059177867635557856462097

Offset

1,4

Links

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

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 2-arch graphs with n>3 nodes is given by f(n,2,n-2-1,0,2) where f is the recursive function described by the PARI/GP code attached 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 ) }
(PARI) \\ faster version with memoization.
a(n, k=2)={ my(Cache=Map());
  my(f(n, k, i, u, j)=my(hk=Vecsmall([n, k, i, u, j]), z);
    if(!mapisdefined(Cache, hk, &z),
       z = binomial(n-u, j)*binomial(u, k-j)*if(i==1, 1, sum(c=0, min(k, n-(i-1)-(u+j)), self()(n, k, i-1, u+j, c) ));
       mapput(Cache, hk, z)); z);
  if(n>k+1, f(n, k, n-k-1, 0, k), n>=k)
} \\ Andrew Howroyd, Nov 07 2019

Crossrefs

Cf. A098721-A098724, A131312-A131315.

Sequence in context: A226344 A278430 A374889 * A098721 A291837 A214381

Adjacent sequences: A131308 A131309 A131310 * A131312 A131313 A131314

Keyword

nonn

Author

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

Extensions

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

Status

approved