A180472 Triangle T(n, k) = OC(n, k; not -1), read by rows, where OC(n, k; not -1) is the number of k-subsets of Z_n without -1 as a multiplier, up to congruency.

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, 0, 0, 12, 35, 90, 150, 197, 197, 150, 90, 35, 12, 0, 0, 0, 0, 0, 0, 14, 44, 126, 224, 340, 370, 340, 224, 126, 44, 14, 0, 0, 0, 0, 0, 0, 16, 56, 168, 336, 544, 680, 680, 544, 336, 168, 56, 16, 0, 0, 0

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.

Cf. A001399 (column k = 3 with different offset), A008804 (column k = 4 with different offset), A032246 (column k = 5), A308401 (column k = 6), A032248 (column k = 7).

Sequence in context: A049337 A049801 A076953 * A308583 A093315 A204267

Adjacent sequences: A180469 A180470 A180471 * A180473 A180474 A180475

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