

A180472


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


6



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,40


COMMENTS

Let Z_n = {0,1,...,n1} denote the integers mod n.
Let S be a ksubset 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 ksubsets of Z_n.
Define an equivalence relation on the set of ksubsets 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 kcompositions 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 kgons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964999.
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), 207220.
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), 129154. (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 kgons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629638.
Vladimir S. Shevelev, Necklaces and convex kgons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629638.
Duncan M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S27(1) (1909), 263313.


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_{dn, dk} (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_{mk} 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 3subsets of Z_7.
There are 4 congruence classes of the 3subsets 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 3subset 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 A052307A119963. The sequence A052307 is formed from the triangle whose (n, k)term is the number of ksubsets of Z_n up to congruence, and the sequence A119963 is formed from the triangle whose (n, k)term is the number of ksubsets 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: A049801 A049337 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



