A032275 -id:A032275 - cp's OEIS frontend

A032295 Number of aperiodic bracelets (turn over necklaces) with n beads of 4 colors.

4, 6, 16, 45, 132, 404, 1296, 4380, 15064, 53622, 192696, 703895, 2589300, 9606744, 35824088, 134297280, 505421340, 1909194056, 7234153416, 27489073899, 104717489748, 399827555604, 1529763696816

Offset: 1

Christian G. Bower

nonn

C. G. Bower, Transforms (2)
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
N. J. A. Sloane, Transforms
Index entries for sequences related to bracelets

Column 4 of A276550.

mx=40;gf[x_,k_]:=Sum[ MoebiusMu[n]*(-Log[1-k*x^n]/n+Sum[Binomial[k,i]x^(n i),{i,0,2}]/( 1-k x^(2n)))/2,{n,mx}]; CoefficientList[Series[gf[x,4],{x,0,mx}],x] (* Herbert Kociemba, Nov 28 2016 *)

MOEBIUS transform of A032275.
From Herbert Kociemba, Nov 28 2016: (Start)
More generally, gf(k) is the g.f. for the number of bracelets with primitive period n and beads of k colors.
gf(k): Sum_{n>=1} mu(n)*( -log(1-k*x^n)/n + Sum_{i=0..2} binomial(k,i)x^(n*i)/(1-k*x^(2*n)) )/2. (End)

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.

Original entry on oeis.org

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

Washington Bomfim, Nov 24 2020

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.

			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.

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

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

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

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

cp's OEIS Frontend

A032295 Number of aperiodic bracelets (turn over necklaces) with n beads of 4 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula