OFFSET
0,40
COMMENTS
Let Z_n = {0,1,...,n-1} denote the integers mod n.
Let S be a k-subset of Z_n.
Then S has multiplier -1 iff there is a z in Z_n for which S = -S + z. Otherwise, S doesn't have multiplier -1.
For example in Z_7 the set S = {0,1,2} has multiplier -1 since -S = {0,-1,-2} = {0,5,6} and then {0,1,2} = {0,5,6} + 2, so S = -S + 2. But S={0,1,3} doesn't have multiplier -1.
Let S and S' be two k-subsets of Z_n.
Define an equivalence relation on the set of k-subsets as follows: S is congruent to S' iff S=S'+z or S = -S' + z for some z in Z_n.
Then define OC(n, k) to be the number of such congruence classes.
And define OC(n, k; not -1) to be the number of such congruence classes in which the representative doesn't have -1 as a multiplier.
Then this sequence is the 'OC(n,k; not -1)' triangle read by rows.
For convenience we start the triangle at n = 0, and we have 0 <= k <= n.
See the McSorley and Schoen (2013) reference below for equivalent definitions of this sequence in terms of (n,k)-Ovals and k-compositions of n.
From Petros Hadjicostas, May 29 2019: (Start)
Here, T(n, k) is the number of bracelets (turnover necklaces) of length n that have no reflection symmetry and consist of k white beads and n - k black beads. (Bracelets that have no reflection symmetry are also known as chiral bracelets.)
It is also the number of dihedral compositions of n into k parts with no reflection symmetry. It is also the number of dihedral compositions of n into n - k parts with no reflection symmetry. (For a definition of a dihedral composition, see Knopfmacher and Robbins (2013) in the references.)
For MacMahon's method for transforming a cyclic composition into a necklace and vice versa, see the comments for sequence A308401. See also p. 273 in Sommerville (1909).
(End)
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1274
Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
Petros Hadjicostas, The aperiodic version of Herbert Kociemba's formula for bracelets with no reflection symmetry, 2019.
Arnold Knopfmacher and Neville Robbins, Some properties of dihedral compositions, Util. Math. 92 (2013), 207-220.
John P. McSorley and Alan H. Schoen, Rhombic tilings of (n,k)-Ovals, (n, k, lambda)-cyclic difference sets, and related topics, Discrete Math. 313 (2013), 129-154. (See Table 1 on p. 137.) - From N. J. A. Sloane, Nov 26 2012
Frank Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Vladimir S. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Vladimir S. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
Duncan M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.
FORMULA
From Petros Hadjicostas, May 29 2019: (Start)
T(n,k) = -binomial(floor(n/2) - (k mod 2) * (1 - (n mod 2)), floor(k/2)) / 2 + Sum_{d|n, d|k} (phi(d)*binomial(n/d, k/d)) / (2*n) for n >= 1 and 0 <= k <= n. (This is a modification of formulas due to Gupta (1979), Shevelev (2004), and W. Bomfim in sequence A052307.)
T(n, k) = A052307(n, k) - A119963(n,k) for 0 <= k <= n. (See the comments in CROSSREFS by J. P. McSorley.)
T(n, k) = T(n, n - k) for 0 <= k <= n.
G.f. for column k >= 1: (x^k/2) * (-(1 + x)/(1 - x^2)^floor((k/2) + 1) + (1/k) * Sum_{m|k} phi(m)/(1 - x^m)^(k/m)). (This formula is due to Herbert Kociemba.)
(End)
Bivariate g.f.: Sum_{n,k >= 0} T(n, k)*x^n*y^k = (1/2) * (1 - (1 + x) * (1 + x*y) / (1 - x^2 * (1 + y^2)) - Sum_{d >= 1} (phi(d) / d) * log(1 - x^d * (1 + y^d))). - Petros Hadjicostas, Jun 15 2019
EXAMPLE
The triangle begins (with rows for n >= 0 and columns for k >= 0) as follows:
0
0 0
0 0 0
0 0 0 0
0 0 0 0 0
0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 2 2 2 0 0 0
0 0 0 3 4 4 3 0 0 0
0 0 0 4 6 10 6 4 0 0 0
0 0 0 5 10 16 16 10 5 0 0 0
0 0 0 7 14 28 30 28 14 7 0 0 0
0 0 0 8 20 42 56 56 42 20 8 0 0 0
0 0 0 10 26 64 91 113 91 64 26 10 0 0 0 0
...
For example the row which corresponds to Z_7 is: 0 0 0 1 1 0 0 0.
The first '1' here corresponds to the 3-subsets of Z_7.
There are 4 congruence classes of the 3-subsets of Z_7, their representatives are {0,1,2}, {0,2,4}, {0,1,4} and {0,1,3}. The first 3 representatives have multiplier -1, but the last doesn't. Hence there is just one 3-subset of Z_7 without multiplier -1, up to congruency.
PROG
(PARI) T(n, k) = if ((n==0) && (k==0), 0, -binomial(floor(n/2) - (k % 2) * (1 - n % 2), floor(k/2)) / 2 + sumdiv(gcd(n, k), d, (eulerphi(d)*binomial(n/d, k/d))) / (2*n)); tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, May 30 2019
CROSSREFS
This sequence is A052307-A119963. The sequence A052307 is formed from the triangle whose (n, k)-term is the number of k-subsets of Z_n up to congruence, and the sequence A119963 is formed from the triangle whose (n, k)-term is the number of k-subsets of Z_n with multiplier -1 up to congruence.
The row sums of the 'OC(n, k, not -1)' triangle above give sequence A059076.
KEYWORD
nonn,tabl
AUTHOR
John P. McSorley, Sep 06 2010
EXTENSIONS
Name edited by Petros Hadjicostas, May 29 2019
Offset corrected by Andrew Howroyd, Sep 27 2019
STATUS
approved