A308583 - OEIS

%I #41 Jun 25 2019 17:43:35

%S 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,2,2,2,0,0,

%T 0,0,0,3,4,4,3,0,0,0,0,0,4,6,10,6,4,0,0,0,0,0,5,10,16,16,10,5,0,0,0,0,

%U 0,7,14,28,29,28,14,7,0,0,0,0,0,8,20,42,56,56,42,20,8,0,0,0,0,0,10,26,64,90,113,90,64,26,10,0,0,0,0,0,12,35,90,150,197,197,150,90,35,12,0,0,0,0,0,14,44,126,222,340,368,340,222,126,44,14,0,0,0

%N Triangle read by rows: T(n,k) = number of aperiodic chiral bracelets (turnover necklaces with no reflection symmetry and period n) with n beads, k of which are white and n - k are black, for n >= 1 and 1 <= k <= n.

%C For k = 1, 4, or a prime, the columns of this triangular array are exactly the same as the corresponding columns for the triangular array A180472. In other words, all chiral bracelets with n beads, k of which are white and n - k are black, are aperiodic if k = 1, 4, or a prime.

%C Note that, T(n, k) is also the number of aperiodic dihedral compositions of n with k parts and no reflection symmetry. Since T(n, k) = T(n, n - k), T(n, k) is also the number of aperiodic dihedral compositions of n with n - k parts and no reflection symmetry.

%H Petros Hadjicostas, <a href="/A308583/a308583.pdf">Formulas for chiral bracelets</a>, 2019.

%H Arnold Knopfmacher and Neville Robbins, <a href="https://www.researchgate.net/publication/260006088_Some_Properties_of_Dihedral_Compositions">Some properties of dihedral compositions</a>, Util. Math. 92 (2013), 207-220.

%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>

%F T(n, k) = Sum_{d|gcd(n,k)} mu(d) * A180472(n/d, k/d) for 1 <= k <= n.

%F T(n, k) = T(n, n - k) for 1 <= k <= n - 1.

%F T(n, k) = (1/(2*k)) * Sum_{d|gcd(n, k)} mu(d) * (binomial(n/d - 1, k/d - 1) - k * binomial(floor(b(n, k, d)/2), floor(k/(2*d)))) for 1 <= k <= n, where b(n, k, d) = (n/d) + ((-1)^(k/d) - 1)/2.

%F T(n, k) = (1/(2*n)) * Sum_{d|gcd(n, k)} mu(d) * (binomial(n/d, k/d) - n * binomial(floor(b(n, k, d)/2), floor(k/(2*d)))) for 1 <= k <= n, where b(n, k, d) = (n/d) + ((-1)^(k/d) - 1)/2.

%F G.f. for column k >= 1: (x^k/(2*k)) * Sum_{d|k} mu(d) * (1/(1 - x^d)^(k/d) - k * (1 + x^d)/(1 - x^(2*d))^floor((k/(2*d)) + 1)).

%F Bivariate g.f.: Sum_{n,k >= 1} T(n, k)*x^n*y^k = (1/2) * Sum_{d >= 1} mu(d) * (1 - (1 + x^d) * (1 + x^d*y^d) / (1 - x^(2*d) * (1 + y^(2*d))) - (1/2) * Sum_{d >= 1} (mu(d)/d) * log(1 - x^d * (1 + y^d)).

%e The triangle begins (with rows for n >= 1 and columns for k >= 1) as follows:

%e 0;

%e 0, 0;

%e 0, 0,  0;

%e 0, 0,  0,  0;

%e 0, 0,  0,  0,  0;

%e 0, 0,  1,  0,  0,  0;

%e 0, 0,  1,  1,  0,  0,   0;

%e 0, 0,  2,  2,  2,  0,   0,  0;

%e 0, 0,  3,  4,  4,  3,   0,  0,  0;

%e 0, 0,  4,  6, 10,  6,   4,  0,  0,  0;

%e 0, 0,  5, 10, 16, 16,  10,  5,  0,  0,  0;

%e 0, 0,  7, 14, 28, 29,  28, 14,  7,  0,  0, 0;

%e 0, 0,  8, 20, 42, 56,  56, 42, 20,  8,  0, 0, 0;

%e 0, 0, 10, 26, 64, 90, 113, 90, 64, 26, 10, 0, 0, 0;

%e ...

%e Notice, for example, that T(14, 6) = 90 <> 91 = A180472(14, 6). Out of the 91 chiral bracelets with 6 W and 8 B beads, only WWBWBBBWWBWBBB is periodic.

%e Using Frank Ruskey's website (listed above) to generate bracelets of fixed content (6, 3) with string length n = 9 and alphabet size 2, we get the following A005513(n = 9) = 7 bracelets: (1) WWWWWWBBB, (2) WWWWWBWBB, (3) WWWWBWWBB, (4) WWWWBWBWB, (5) WWWBWWWBB, (6) WWWBWWBWB, and (7) WWBWWBWWB. From these, bracelets 1, 4, 5, and 7 have reflection symmetry, while bracelets 2, 3 and 6 have no reflection symmetry. Because chiral bracelets 2, 3, and 6 are aperiodic as well, we have T(9, 3) = 3 = T(9, 6).

%e Starting with a black bead, we count that bead and how many white beads follow (in one direction), and continue this process until we count all beads around the circle. We thus use MacMahon's correspondence to get the following dihedral compositions of n = 9 into 3 parts: (1) 1 + 7 + 1, (2) 1 + 2 + 6, (3) 1 + 3 + 5, (4) 2 + 5 + 2, (5) 4 + 1 + 4, (6) 2 + 3 + 4, and (7) 3 + 3 + 3. Again, dihedral compositions 1, 4, 5, and 7 are symmetric (have reflection symmetry), while dihedral compositions 2, 3, and 6 are not symmetric. In addition, chiral dihedral compositions 2, 3, and 6 are aperiodic as well, and so (again) T(9, 3) = 3.

%e We may also start with a white bead and count that bead and how many black beads follow (in one direction), and continue this process until we count all beads around the circle. We thus use MacMahon's correspondence again to get the following (conjugate) dihedral compositions of n = 9 into 6 parts: (1) 1 + 1 + 1 + 1 + 1 + 4, (2) 1 + 1 + 1 + 1 + 2 + 3, (3) 1 + 1 + 1 + 2 + 1 + 3, (4) 1 + 1 + 1 + 2 + 2 + 2, (5) 1 + 1 + 2 + 1 + 1 + 3, (6) 1 + 1 + 2 + 1 + 2 + 2, and (7) 1 + 2 + 1 + 2 + 1 + 2. Again, dihedral compositions 1, 4, 5, and 7 have reflection symmetries, while dihedral compositions 2, 3, and 6 do not have reflection symmetries. Chiral dihedral compositions 2, 3, and 6 are aperiodic as well, and hence T(9, 6) = 3.

%Y Cf. A032239 (row sums for n >= 3), A180472.

%Y Cf. A001399 (column k = 3 with a different offset), A008804 (column k = 4 with a different offset), A032246 (column k = 5), A032247 (column k = 6), A032248 (column k = 7), A032249 (column k = 8).

%K nonn,tabl

%O 1,30

%A _Petros Hadjicostas_, Jun 08 2019