A005513 -id:A005513 - cp's OEIS frontend

A308583 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.

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

Offset: 1

Petros Hadjicostas, Jun 08 2019

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.

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.

			The triangle begins (with rows for n >= 1 and columns for k >= 1) as follows:
  0;
  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,  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, 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;
  ...
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.
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).
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.
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.

Petros Hadjicostas, Formulas for chiral bracelets, 2019.
Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207-220.
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

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

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

T(n, k) = Sum_{d|gcd(n,k)} mu(d) * A180472(n/d, k/d) for 1 <= k <= n.
T(n, k) = T(n, n - k) for 1 <= k <= n - 1.
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.
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.
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)).
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)).

A259342 Irregular triangle read by rows: T(n,k) = number of equivalence classes of binary sequences of length n containing exactly 2k ones.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 3, 3, 1, 1, 3, 4, 1, 1, 4, 8, 4, 1, 1, 4, 10, 7, 1, 1, 5, 16, 16, 5, 1, 1, 5, 20, 26, 10, 1, 1, 6, 29, 50, 29, 6, 1, 1, 6, 35, 76, 57, 14, 1, 1, 7, 47, 126, 126, 47, 7, 1, 1, 7, 56, 185, 232, 111, 19, 1, 1, 8, 72, 280, 440, 280, 72, 8, 1

Offset: 1

N. J. A. Sloane, Jun 27 2015

			Triangle begins:
  1;
  1, 1;
  1, 1;
  1, 2,  1;
  1, 2,  1;
  1, 3,  3,   1;
  1, 3,  4,   1;
  1, 4,  8,   4,   1;
  1, 4, 10,   7,   1;
  1, 5, 16,  16,   5,  1;
  1, 5, 20,  26,  10,  1;
  1, 6, 29,  50,  29,  6, 1;
  1, 6, 35,  76,  57, 14, 1;
  1, 7, 47, 126, 126, 47, 7, 1;
  ...

Alois P. Heinz, Rows n = 1..200, flattened
W. D. Hoskins and Anne Penfold Street, Twills on a given number of harnesses, J. Austral. Math. Soc. Ser. A 33 (1982), no. 1, 1-15.
W. D. Hoskins and A. P. Street, Twills on a given number of harnesses, J. Austral. Math. Soc. (Series A), 33 (1982), 1-15. (Annotated scanned copy)

Row sums are (essentially) A000011.

with(numtheory):
T:= (n, k)-> (add(`if`(irem(2*k*d, n)=0, phi(n/d)
     *binomial(d, 2*k*d/n), 0), d=divisors(n))
     +n*binomial(iquo(n, 2), k))/(2*n):
seq(seq(T(n, k), k=0..n/2), n=1..20);  # Alois P. Heinz, Jun 28 2015

T[n_, k_] := (DivisorSum[n, If[Mod[2k*#, n]==0, EulerPhi[n/#]*Binomial[#, 2k*#/n], 0]&] + n*Binomial[Quotient[n, 2], k])/(2n); Table[T[n, k], {n, 1, 20}, { k, 0, n/2}] // Flatten (* Jean-François Alcover, Feb 28 2017, after Alois P. Heinz *)

Theorem 1 of Hoskins-Street gives an explicit formula.

A294085 a(n) is the number of self-symmetric anonymous and neutral equivalence classes of preference profiles with 3 alternatives and n agents (IANC model).

Original entry on oeis.org

1, 1, 3, 4, 8, 10, 17, 20, 30, 35, 49, 56, 75, 84, 108, 120, 150, 165, 202, 220, 264, 286, 338, 364, 425, 455, 525, 560, 640, 680, 771, 816, 918, 969, 1083, 1140, 1267, 1330, 1470, 1540, 1694, 1771, 1940, 2024, 2208, 2300, 2500, 2600, 2817, 2925, 3159, 3276, 3528, 3654, 3925

Offset: 0

Alexander Karpov, Apr 12 2018

Colin Barker, Table of n, a(n) for n = 0..1000
A. Karpov, An Informational Basis for Voting Rules, NRU Higher School of Economics. Series WP BRP "Economics/EC". 2018. No. 188
Index entries for linear recurrences with constant coefficients, signature (1,2,-2,-1,1,1,-1,-2,2,1,-1).

Cf. A037240, A005513.

For odd n, it is A000292.

Vec((1 + x^3 + x^4) / ((1 - x)^4*(1 + x)^3*(1 - x + x^2)*(1 + x + x^2)) + O(x^60)) \\ Colin Barker, May 11 2018

a(n) = 2*A005513(n-6) - A037240(n).
If n is odd, a(n) = (n+5)*(n+3)*(n+1)/48;
If n is even, a(n) = ceiling((n+4)^2*(n+2)/48).
From Colin Barker, May 11 2018: (Start)
G.f.: (1 + x^3 + x^4) / ((1 - x)^4*(1 + x)^3*(1 - x + x^2)*(1 + x + x^2)).
a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3) - a(n-4) + a(n-5) + a(n-6) - a(n-7) - 2*a(n-8) + 2*a(n-9) + a(n-10) - a(n-11) for n>10.
(End)

A143654 Array T(n,k) read by rows: number of binary bracelets with n beads, k of them 0, with 00 prohibited, (n >= 2, 0 <= k <= floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 3, 3, 1, 1, 1, 4, 4, 3, 1, 1, 1, 4, 5, 4, 1, 1, 1, 5, 7, 8, 3, 1, 1, 1, 5, 8, 10, 5, 1, 1, 1, 6, 10, 16, 10, 4, 1, 1, 1, 6, 12, 20, 16, 7, 1, 1, 1, 7, 14, 29, 26, 16, 4, 1, 1, 1, 7, 16, 35, 38, 26, 8, 1, 1, 1, 8, 19, 47, 57, 50

Offset: 2

Washington Bomfim, Aug 28 2008

The initial columns give A057427, A057427, A004526, A069905, A005232, A032279, A005513, A032280, A005514, A032281, A005515, A032282, A005516. Row sums give A129526.
A binary bracelet with n beads, k of them 0, with 00 prohibited has from 0 to floor(n/2) beads 0, i.e., 0 <= k <= floor(n/2). If n is even, the bracelet 0101...01 with n/2 beads of each kind does not have 00 and we cannot change any 1 of it to a 0. If n is odd we cannot change a 1 to a 0 in the bracelet 0101...011 with (n-1)/2 beads 0.
The number of binary bracelets with n beads, 0 <= k <= floor(n/2) of them 0 with 00 prohibited, is equal to the number of binary bracelets with n-k beads, k of them 0. See below.
Let B be a binary bracelet with n-k beads, k of them 0. If we insert one 1 (circularly) after a 0 of B, we obtain a bracelet with n-k+1 beads, k of them 0.
If we do this insertion k times, each time after a distinct 0 of B, we obtain a bracelet with n = n-k+k beads, k of them 0, with 00 prohibited.
On the contrary, Let B be a binary bracelet with n beads, k of them 0, with 00 prohibited. If we remove from B one 1 that is after a 0, we obtain a bracelet of n-1 beads, k of them 0. (If not and we undo the removal, the configuration obtained cannot be a bracelet and this is absurd.) If we repeat this removal k times, after each distinct bead 0, we obtain a bracelet with n-k beads, k of them 0.

			Array begins
1 1
1 1
1 1 1
1 1 1
1 1 2 1
1 1 2 1
1 1 3 2 1
1 1 3 3 1
1 1 4 4 3 1
...
A129526(10) = A057427(10) + A057427(9) + A004526(8) + A069905(7) + A005232(6) +
A032279(5) = 1+1+4+4+3+1 = 14.

Cf. A057427, A004526, A069905, A005232, A032279, A005513, A032280, A005514, A032281, A005515, A032282, A005516. Row sums of array give A129526.

cp's OEIS Frontend

A308583 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A259342 Irregular triangle read by rows: T(n,k) = number of equivalence classes of binary sequences of length n containing exactly 2k ones.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A294085 a(n) is the number of self-symmetric anonymous and neutral equivalence classes of preference profiles with 3 alternatives and n agents (IANC model).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A143654 Array T(n,k) read by rows: number of binary bracelets with n beads, k of them 0, with 00 prohibited, (n >= 2, 0 <= k <= floor(n/2)).

Views

Author

Keywords

Comments

Examples

Crossrefs