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, 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

Offset: 0

Author

Washington Bomfim, Nov 24 2020

Keywords

• nonn
• tabl

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.

Examples

			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.
		

Links

• Index entries for sequences related to bracelets
• Washington Bomfim, Illustraction of graphs counted by A(2,k), k=2,3
• Eric Weisstein's World of Mathematics, Sunlet graph

Crossrefs

Cf. A000081 (row 1), A321791, A102911 (row 2), A000029 (column 3), A032275 (column 4).

Programs

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, ")) };

Formula

A(m,k) = A321791(m, A000081(k)).