login
Number of simple labeled graphs on n nodes with exactly 2 connected components that are trees or cycles.
3

%I #20 Apr 22 2021 08:48:00

%S 1,3,19,135,1267,15029,218627,3783582,75956664,1734309929,44357222772,

%T 1255715827483,38971877812380,1315634598619830,47994245894462576,

%U 1881406032047006812,78870928008704884848,3520953336130828001295,166762291211479030734580

%N Number of simple labeled graphs on n nodes with exactly 2 connected components that are trees or cycles.

%H Alois P. Heinz, <a href="/A215852/b215852.txt">Table of n, a(n) for n = 2..145</a>

%F a(n) ~ c * n^(n-2), where c = 0.511564031298... . - _Vaclav Kotesovec_, Sep 07 2014

%e a(3) = 3:

%e .1 2. .1-2. .1 2.

%e .|. . . . . . / .

%e .3... .3... .3...

%p T:= proc(n, k) option remember; `if`(k<0 or k>n, 0,

%p `if`(n=0, 1, add(binomial(n-1, i)*T(n-1-i, k-1)*

%p `if`(i<2, 1, i!/2 +(i+1)^(i-1)), i=0..n-k)))

%p end:

%p a:= n-> T(n, 2):

%p seq(a(n), n=2..25);

%t T[n_, k_]:=T[n, k]=If[k<0 || k>n, 0, If[n==0, 1, Sum[Binomial[n - 1, i] T[n - 1 - i, k - 1] If[i<2, 1, i!/2 + (i + 1)^(i - 1)], {i, 0, n - k}]]]; Table[T[n, 2], {n, 2, 50}] (* _Indranil Ghosh_, Aug 07 2017, after Maple *)

%o (Python)

%o from sympy.core.cache import cacheit

%o from sympy import binomial, factorial as f

%o @cacheit

%o def T(n, k): return 0 if k<0 or k>n else 1 if n==0 else sum([binomial(n - 1, i)*T(n - 1 - i, k - 1)*(1 if i<2 else f(i)//2 + (i + 1)**(i - 1)) for i in range(n - k + 1)])

%o def a(n): return T(n , 2)

%o print([a(n) for n in range(2, 51)]) # _Indranil Ghosh_, Aug 07 2017, after maple code

%Y Column k=2 of A215861.

%Y The unlabeled version is A215982.

%K nonn

%O 2,2

%A _Alois P. Heinz_, Aug 25 2012