This site is supported by donations to The OEIS Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A047996 Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n. 36

%I

%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

%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.

%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, 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, 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, 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 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, Pages 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, & D. Klarner, <a href="/A003322/a003322.pdf">Correspondence, 1994</a>

%H Petr Lisonek, <a href="http://www.lacim.uqam.ca/~plouffe/articles/thesis.pdf">Computer-assisted Studies in Algebraic Combinatorics</a>, Thesis, 1994, pp. 72-73.

%H F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/gen/neck.html">Necklaces</a>

%H F. Ruskey and J. 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 F. 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>

%H P. Stanica, S. 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.: 1 - Sum_{s>=1} (phi(s)/s)*log(1-x^s*(1+y^s)). - _Petros Hadjicostas_, Oct 26 2017

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 20 02:13 EST 2019. Contains 319320 sequences. (Running on oeis4.)