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
Examples
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.
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.
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.
Programs
-
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
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
Extensions
Name edited by Petros Hadjicostas, May 29 2019
Offset corrected by Andrew Howroyd, Sep 27 2019
Comments