|
| |
|
|
A338859
|
|
Square array A(m,k) is the number of unicyclic graphs with m trees of k nodes; m,k >= 0, read by falling antidiagonals.
|
|
1
|
|
|
|
1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 4, 3, 1, 1, 0, 1, 9, 10, 4, 1, 1, 0, 1, 20, 45, 20, 6, 1, 1, 0, 1, 48, 210, 165, 55, 8, 1, 1, 0, 1, 115, 1176, 1540, 1035, 136, 13, 1, 1, 0, 1, 286, 6670, 19600, 22155, 6273, 430, 18, 1, 1, 0, 1, 719, 41041, 260130, 692076, 324008, 46185, 1300, 30, 1, 1, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,12
|
|
|
COMMENTS
|
The number of unicyclic graphs with m k-trees is equal to the number of bracelets with m beads using up to A000081(k) colors, so A(m,k) = A321791(m, A000081(k)).
Because A102911(k) is the number of graphs constituted by 2 k-node rooted trees with the roots joined by an edge, A(2,k) = A102911(k). [Bomfim illustration for k=2,3].
Column 1 refers to Cyclic graphs, Column 2 refers to Sunlet graphs.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
A begins,
---+------------------------------------------------------------------------------
m/k|0 1 2 3 4 5 6 7 8 9
---+------------------------------------------------------------------------------
0 |1 1 1 1 1 1 1 1 1 1 ...
1 |0 1 1 2 4 9 20 48 115 286 ...
2 |0 1 1 3 10 45 210 1176 6670 41041 ...
3 |0 1 1 4 20 165 1540 19600 260130 3939936 ...
4 |0 1 1 6 55 1035 22155 692076 22247785 842202361 ...
5 |0 1 1 8 136 6273 324008 25535712 2012117671 191362445560 ...
6 |0 1 1 13 430 46185 5376070 1020580232 192799298140 45606942211831 ...
7 |0 1 1 18 1300 344925 91508580 41936107248 19000229453710 11179807512382366 ...
...| ... ... ... ... ...
---+------------------------------------------------------------------------------
The A(3,3) = 4 unicyclic graphs with 3 trees of 3 nodes
0 0
| |
0 0 0 0 0 0
| \ / | \ /
0 0 0 0
/*\ /*\ /*\ /*\
/***\ /***\ /***\ /***\
0-----0 0---- 0 0-----0 0-----0
/ \ / \ / \ / \ / \ | |
0 0 0 0 0 0 0 0 0 0 0 0
/ \ | |
0 0 0 0
The graphs above are also representations of bracelets with m = 3 beads using up to A000081(k=3) = 2 colors.
|
|
|
PROG
|
(PARI) \\ From Robert A. Russell formula of A321791.
A(m, k)={ if( m == 0, return(1),
(k^((m+1)>>1)+k^ceil((m+1)/2)) / 4 + sumdiv(m, d, eulerphi(d)*k^(m/d) )/(m<<1)) };
seq(max_m) = { my(f = vector(max_m), kk, mm, ff); f[1] = 1;
for(j=1, max_m - 1, f[j+1] = 1/j * sum(k=1, j, sumdiv(k, d, d * f[d]) * f[j-k+1]));
print1(A(0, 0) ", "); for(k = 1, max_m, kk = k; mm = 0; ff = f[kk];
until(A(mm, ff)==0, print1(A(mm, ff)", "); mm++; kk--; if(kk==0, ff=0, ff = f[kk]) );
print1("0, ")) };
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
