login
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

%I #40 Dec 23 2020 20:20:23

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

%T 6,1,1,0,1,48,210,165,55,8,1,1,0,1,115,1176,1540,1035,136,13,1,1,0,1,

%U 286,6670,19600,22155,6273,430,18,1,1,0,1,719,41041,260130,692076,324008,46185,1300,30,1,1,0

%N Square array A(m,k) is the number of unicyclic graphs with m trees of k nodes; m,k >= 0, read by falling antidiagonals.

%C 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)).

%C 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].

%C Column 1 refers to Cyclic graphs, Column 2 refers to Sunlet graphs.

%H <a href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>

%H Washington Bomfim, <a href="/A338859/a338859.png">Illustraction of graphs counted by A(2,k), k=2,3 </a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SunletGraph.html">Sunlet graph</a>

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

%e A begins,

%e ---+------------------------------------------------------------------------------

%e m/k|0 1 2 3 4 5 6 7 8 9

%e ---+------------------------------------------------------------------------------

%e 0 |1 1 1 1 1 1 1 1 1 1 ...

%e 1 |0 1 1 2 4 9 20 48 115 286 ...

%e 2 |0 1 1 3 10 45 210 1176 6670 41041 ...

%e 3 |0 1 1 4 20 165 1540 19600 260130 3939936 ...

%e 4 |0 1 1 6 55 1035 22155 692076 22247785 842202361 ...

%e 5 |0 1 1 8 136 6273 324008 25535712 2012117671 191362445560 ...

%e 6 |0 1 1 13 430 46185 5376070 1020580232 192799298140 45606942211831 ...

%e 7 |0 1 1 18 1300 344925 91508580 41936107248 19000229453710 11179807512382366 ...

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

%e ---+------------------------------------------------------------------------------

%e The A(3,3) = 4 unicyclic graphs with 3 trees of 3 nodes

%e 0 0

%e | |

%e 0 0 0 0 0 0

%e | \ / | \ /

%e 0 0 0 0

%e /*\ /*\ /*\ /*\

%e /***\ /***\ /***\ /***\

%e 0-----0 0---- 0 0-----0 0-----0

%e / \ / \ / \ / \ / \ | |

%e 0 0 0 0 0 0 0 0 0 0 0 0

%e / \ | |

%e 0 0 0 0

%e The graphs above are also representations of bracelets with m = 3 beads using up to A000081(k=3) = 2 colors.

%o (PARI) \\ From Robert A. Russell formula of A321791.

%o A(m, k)={ if( m == 0, return(1),

%o (k^((m+1)>>1)+k^ceil((m+1)/2)) / 4 + sumdiv(m, d, eulerphi(d)*k^(m/d) )/(m<<1)) };

%o seq(max_m) = { my(f = vector(max_m), kk, mm, ff); f[1] = 1;

%o 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]));

%o print1(A(0,0) ", "); for(k = 1, max_m, kk = k; mm = 0; ff = f[kk];

%o until(A(mm,ff)==0, print1(A(mm,ff)", "); mm++; kk--; if(kk==0, ff=0, ff = f[kk]) );

%o print1("0, ")) };

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

%K nonn,tabl

%O 0,12

%A _Washington Bomfim_, Nov 24 2020