A331563
Number of labeled cyclic graphs with n edges and 2n vertices.
Original entry on oeis.org
0, 0, 20, 1610, 129654, 11688369, 1194822915, 137766789810, 17758192128830, 2535895233070628, 397875362655895761, 68087081506276861665, 12626853606957534296975, 2523446241515288646389325
Offset: 1
a(4) = 1610 since we have 3 non-isomorphic cyclic graphs with 4 edges and 8 nodes. (See illustration below.)
To compute a(4) we can consult A057500, which provides the number of labeled connected unicycles. Because A057500(4)=15, and knowing that there are 3 labeled squares, we have 15-3 = 12 Paw Graphs [see Weisstein link]. So graph 1 is labeled in 12 * C(8,4) = 840 ways. Graph 2 is labeled in 3* C(8,4) = 210 ways. A105599 gives 10 as the number of labeled forests with 5 nodes and 4 components, so graph 3 is labeled in 10 * C(8,3) = 560 ways. We have 840 + 210 + 560 = 1610.
.
graph 1 graph 2 graph 3 (triangle + forest with
5 nodes and 4 components)
*--* *--* *--* *
| /| | | | / |
|/ | | | |/ |
* * *--* * *
* * * * * * * * * * *
- Eric Weisstein's World of Mathematics, Paw Graph
A332957
Number of labeled forests with n trees and 2*n nodes without trees of order exceeding n - floor(n/4).
Original entry on oeis.org
0, 3, 195, 5145, 504945, 47896695, 4900634739, 432180333585, 57753467156385, 8322385282168815, 1297830988347128235, 195029484510994774641, 36350420770495795788825, 7233322663694914389377775, 1534057832485607065840824075
Offset: 1
E.g., a(4) = 5145. The partitions of 2*n = 8 with four parts, no parts exceeding n - floor(n/4) = 3 are [1*2 + 3*2], [1*1 + 2*2 + 3*1], and [2*4].
The first partition corresponds to f(1)^2*f(3)^2 / ((2!*1!^2)*(2!*3!^2)) = 1^2*3^2 / (2*2*36) = 1/16, the second corresponds to f(1)^1 * f(2)^2 * f(3)^1 / ((1!*1!^1)*(2!*2!^2)*(1!*3!^1)) = 1/16, and the last corresponds to f(2)^4 / (4!*2!^4) = 1/384. Finally 8! * (1/16 + 1/16 + 1/384)= 5145. (See formula).
- D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions, Addison-Wesley, 2005, pp. 39, 47.
-
a(n) = { my(S=0); forpart(aa=2*n, my(D = Set(aa)); S += prod(j= 1, #D, my(p=D[j], c=#select(x-> x==p, Vec(aa))); (p^(p-2))^c / (c!* p!^c)), [1, n-n\4], [n, n]); (2*n)! * S};
-
a(n)={my(p=sum(k=1, n-n\4, k^(k-2)*x^k/k!)); (2*n)!*polcoef( polcoef( exp(y*p + O(x*x^(2*n))), 2*n, x), n, y)} \\ Andrew Howroyd, Apr 10 2020
A332961
Triangle read by rows: T(n,k) is the number of labeled forests with n trees and 2n nodes and with the largest tree having at most k nodes, (n>=1, 2<=k<=n+1).
Original entry on oeis.org
1, 3, 15, 15, 195, 435, 105, 5145, 11865, 18865, 945, 152145, 504945, 819945, 1092105, 10395, 6039495, 27106695, 47896695, 65859255, 79170399, 135135, 276351075, 1663737075, 3429501075, 4900634739, 6111948843, 6899167275, 2027025, 14985795825, 120931635825, 286156695825, 432180333585
Offset: 1
Triangle T(n,k) begins:
1;
3, 15;
15, 195, 435;
105, 5145, 11865, 18865;
945, 152145, 504945, 819945, 1092105;
10395, 6039495, 27106695, 47896695, 65859255, 79170399;
...
The graphs for T(2,2) and T(2,3) are illustrated below:
o---o : o---o o o
: |
o---o : o---o o---o
T(2,2) = 3 since the first graph on the left has 3 labelings.
T(2,3) = 15 since the first graph has 3 labelings, and the second has 12 labelings.
- V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999, pp 30-31.
-
T(n,k) = { my(S = 0, D, p, c);
forpart(a = 2*n, D = Set(a);
S += prod(j=1,#D, p=D[j]; c=#select(x-> x==p,Vec(a)); (p^(p-2)/p!)^c /c!)
, [1, k], [n, n]); (2*n)! * S };
Comments