A047996 - OEIS

%I #172 Apr 04 2024 10:26:27

%S 1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,2,2,1,1,1,1,3,4,3,1,1,1,1,3,5,5,3,

%T 1,1,1,1,4,7,10,7,4,1,1,1,1,4,10,14,14,10,4,1,1,1,1,5,12,22,26,22,12,

%U 5,1,1,1,1,5,15,30,42,42,30,15,5,1,1,1,1,6,19,43,66,80,66,43,19,6,1,1,1,1,6,22

%N Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n.

%C Equivalently, T(n,k) = number of necklaces with k black beads and n-k white beads (binary necklaces of weight k).

%C The same sequence arises if we take the table U(n,k) = number of necklaces with n black beads and k white beads and read it by antidiagonals (cf. A241926). - _Franklin T. Adams-Watters_, May 02 2014

%C U(n,k) is also equal to the number of ways to express 0 as a sum of k elements in Z/nZ. - _Jens Voß_, _Franklin T. Adams-Watters_, _N. J. A. Sloane_, Apr 30 2014 - May 05 2014. See link ("A Note on Modular Partitions and Necklaces") for proof.

%C The generating function for column k is given by the substitution x_j -> x^j/(1-x^j) in the cycle index of the Symmetric Group of order k. - _R. J. Mathar_, Nov 15 2018

%C From _Petros Hadjicostas_, Jul 12 2019: (Start)

%C Regarding the comments above by Voss, Adams-Watters, and Sloane, note that Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} A054535(d, v) * binomial((n + k)/d, k/d) = S(k, n, v).

%C This result was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 0) = A241926(n, k) = U(n, k) = T(n + k, k) (where T(n, k) is the current array). Also, S(n, k, 1) = A245558(n, k). See also Panyushev (2011) for more general results and for generating functions.

%C Finally, note that A054535(d, v) = c_d(v) = Sum_{s | gcd(d,v)} s*Moebius(d/s). These are the Ramanujan sums, which equal also the von Sterneck function c_d(v) = phi(d) * Moebius(d/gcd(d, v))/phi(d/gcd(d, v)). We have A054535(d, v) = A054534(v, d).

%C It would be interesting to see whether there is a proof of the results by Fredman (1975), Elashvili et al. (1999), and Panyushev (2011) for a general v using Molien series as it is done by Sloane (2014) for the case v = 0 (in which case, A054535(d, 0) = phi(d)). (Even though the columns of array A054535(d, v) start at v = 1, we may start the array at column v = 0 as well.)

%C (End)

%C U(n, k) is the number of equivalence classes of k-tuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation. - _Álvar Ibeas_, Sep 21 2021

%D N. G. de Bruijn, Polya's theory of counting, in: Applied Combinatorial Mathematics (E. F. Beckenbach, ed.), John Wiley and Sons, New York, 1964, pp. 144-184 (implies g.f. for this triangle).

%D Richard Stanley, Enumerative Combinatorics, 2nd. ed., Vol 1, Chapter I, Problem 105, pp. 122 and 168, discusses the number of subsets of Z/nZ that add to 0. - _N. J. A. Sloane_, May 06 2014

%D J. Voß, Posting to Sequence Fans Mailing List, April 30, 2014.

%D H. S. Wilf, personal communication to _N. J. A. Sloane_, Nov., 1990.

%D See A000031 for many additional references and links.

%H Seiichi Manyama, <a href="/A047996/b047996.txt">Rows n=0..139 of triangle, flattened</a> (Rows 0..50 from T. D. Noe)

%H Ethan Akin and Morton Davis, <a href="http://www.jstor.org/stable/2323643">Bulgarian solitaire</a>, Am. Math. Monthly 92 (4) (1985), 237-250.

%H J. Brandt, <a href="http://dx.doi.org/10.1090/S0002-9939-1982-0656129-5">Cycles of partitions</a>, Proc. Am. Math. Soc. 85 (3) (1982), 483-486, Theorem 5.

%H Paul Drube and Puttipong Pongtanapaisan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Drube/drube3.html">Annular Non-Crossing Matchings</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.

%H A. Elashvili and M. Jibladze, <a href="http://dx.doi.org/10.1016/S0019-3577(98)80021-9">Hermite reciprocity for the regular representations of cyclic groups</a>, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006)

%H A. Elashvili, M. Jibladze, and D. Pataraia, <a href="http://dx.doi.org/10.1023/A:1018727630642">Combinatorics of necklaces and "Hermite reciprocity"</a>, J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014

%H M. L. Fredman, <a href="https://doi.org/10.1016/0097-3165(75)90008-4">A symmetry relationship for a class of partitions</a>, J. Combinatorial Theory Ser. A 18 (1975), 199-202.

%H Harold Fredricksen, <a href="http://dx.doi.org/10.1016/0012-365X(86)90089-0">An algorithm for generating necklaces of beads in two colors</a>, Discrete Mathematics, Volume 61, Issues 2-3, September 1986, 181-188.

%H D. E. Knuth, <a href="http://www.jstor.org/stable/2318994">Computer science and its relation to mathematics</a>, Amer. Math. Monthly, 81 (1974), 323-343.

%H D. E. Knuth, H. Wilf, C. L. Mallows, and D. Klarner, <a href="/A003322/a003322.pdf">Correspondence, 1994</a>

%H Petr Lisonek, <a href="http://www3.risc.jku.at/publications/download/risc_2382/thesis.pdf">Computer-assisted Studies in Algebraic Combinatorics</a>, Thesis, University of Linz (Austria) Sep. 1994, pp. 72-73.

%H D. I. Panyushev, <a href="https://doi.org/10.1007/s10801-010-0236-6">Fredman's reciprocity, invariants of abelian groups, and the permanent of the Cayley table</a>, J. Algebraic Combin. 33 (2011), 111-125.

%H Mónica A. Reyes, Cristina Dalfó, Miguel Àngel Fiol, and Arnau Messegué, <a href="https://arxiv.org/abs/2403.20148">A general method to find the spectrum and eigenspaces of the k-token of a cycle, and 2-token through continuous fractions</a>, arXiv:2403.20148 [math.CO], 2024. See p. 5.

%H Frank Ruskey, <a href="http://combos.org/necklace">Generate Necklaces, Lyndon words, and relatives</a>, The Combinatorial Object Server.

%H Frank Ruskey and Joe Sawada, <a href="http://dx.doi.org/10.1137/S0097539798344112">An Efficient Algorithm for Generating Necklaces with Fixed Density</a>, SIAM J. Computing, 29 (1999) 671-684.

%H Frank Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]

%H N. J. A. Sloane, <a href="/A047996/a047996.pdf">A Note on Modular Partitions and Necklaces</a>, 2014.

%H Pantelimon Stănică and Subhamoy Maitra, <a href="https://doi.org/10.1016/j.dam.2007.04.029">Rotation symmetric boolean functions - count and cryptographic properties</a>, Disc. Appl. Math. 156 (2008) 1567-1580, g_{n,w} Theorem 9.

%H Wikipedia, <a href="http://commons.wikimedia.org/wiki/Image:A31.gif">Necklaces Animation</a> [Broken link?]

%H Wolfram Research, <a href="http://demonstrations.wolfram.com/MakingNecklaces/">Necklaces Applet</a>.

%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>

%F T(n, k) = (1/n) * Sum_{d | (n, k)} phi(d)*binomial(n/d, k/d).

%F T(2*n,n) = A003239(n); T(2*n+1,n) = A000108(n). - _Philippe Deléham_, Jul 25 2006

%F G.f. for row n (n>=1):  (1/n) * Sum_{i=0..n-1} ( x^(n/gcd(i,n)) + 1 )^gcd(i,n). - _Joerg Arndt_, Sep 28 2012

%F G.f.: Sum_{n, k >= 0} T(n, k)*x^n*y^k = 1 - Sum_{s>=1} (phi(s)/s)*log(1-x^s*(1+y^s)). - _Petros Hadjicostas_, Oct 26 2017

%F Product_{d >= 1} (1 - x^d - y^d) = Product_{i,j >= 0} (1 - x^i*y^j)^T(i+j, j), where not both i and j are zero. (It follows from Somos' infinite product for array A051168.) - _Petros Hadjicostas_, Jul 12 2019

%e Triangle starts:

%e [ 0]  1,

%e [ 1]  1,  1,

%e [ 2]  1,  1,  1,

%e [ 3]  1,  1,  1,  1,

%e [ 4]  1,  1,  2,  1,  1,

%e [ 5]  1,  1,  2,  2,  1,  1,

%e [ 6]  1,  1,  3,  4,  3,  1,  1,

%e [ 7]  1,  1,  3,  5,  5,  3,  1,  1,

%e [ 8]  1,  1,  4,  7, 10,  7,  4,  1,  1,

%e [ 9]  1,  1,  4, 10, 14, 14, 10,  4,  1,  1,

%e [10]  1,  1,  5, 12, 22, 26, 22, 12,  5,  1, 1,

%e [11]  1,  1,  5, 15, 30, 42, 42, 30, 15,  5, 1, 1,

%e [12]  1,  1,  6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, ...

%p A047996 := proc(n,k) local C,d; if k= 0 then return 1; end if; C := 0 ; for d in numtheory[divisors](igcd(n,k)) do C := C+numtheory[phi](d)*binomial(n/d,k/d) ; end do: C/n ; end proc:

%p seq(seq(A047996(n,k),k=0..n),n=0..10) ; # _R. J. Mathar_, Apr 14 2011

%t t[n_, k_] := Total[EulerPhi[#]*Binomial[n/#, k/#] & /@ Divisors[GCD[n, k]]]/n; t[0, 0] = 1; Flatten[Table[t[n, k], {n, 0, 13}, {k, 0, n}]] (* _Jean-François Alcover_, Jul 19 2011, after given formula *)

%o (PARI)

%o p(n) = if(n<=0, n==0, 1/n * sum(i=0,n-1, (x^(n/gcd(i,n))+1)^gcd(i,n) ));

%o for (n=0,17, print(Vec(p(n)))); /* print triangle */

%o /* _Joerg Arndt_, Sep 28 2012 */

%o (PARI)

%o T(n,k) = if(n<=0, n==0, 1/n * sumdiv(gcd(n,k), d, eulerphi(d)*binomial(n/d,k/d) ) );

%o /* print triangle: */

%o { for (n=0, 17, for (k=0, n, print1(T(n,k),", "); ); print(); ); }

%o /* _Joerg Arndt_, Oct 21 2012 */

%Y Row sums: A000031. Columns 0-12: A000012, A000012, A004526, A007997(n+5), A008610, A008646, A032191-A032197.

%Y Cf. A051168, A052307, A052311-A052313.

%Y See A037306 and A241926 for essentially identical triangles.

%Y See A245558, A245559 for a closely related array.

%K nonn,tabl,easy,nice

%O 0,13

%A _N. J. A. Sloane_

%E Name edited by _Petros Hadjicostas_, Nov 16 2017