0,13

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

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 anti-diagonals (cf. A241926). - Franklin T. Adams-Watters, May 02 2014

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.

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

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

H. S. Wilf, personal communication to N. J. A. Sloane, Nov., 1990.

See A000031 for many additional references and links.

T. D. Noe, Rows n=0..50 of triangle, flattened

Ethan Akin, Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250

J. Brandt, Cycles of partitions, Proc. Am. Math. Soc. 85 (3) (1982) 483-486

A. Elashvili, M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233--238. MR1691428 (2000c:13006)

A. Elashvili, M. Jibladze, D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - N. J. A. Sloane, Aug 06 2014

Harold Fredricksen, An algorithm for generating necklaces of beads in two colors, Discrete Mathematics, Volume 61, Issues 2-3, September 1986, Pages 181-188.

D. E. Knuth, Computer science and its relation to mathematics, Amer. Math. Monthly, 81 (1974), 323-343.

Petr Lisonek, Computer-assisted Studies in Algebraic Combinatorics, pp. 72-73.

F. Ruskey, Necklaces

F. Ruskey and J. Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.

N. J. A. Sloane, A Note on Modular Partitions and Necklaces

Wikipedia, Necklaces Animation [Broken link?]

Wolfram Research, Necklaces Applet.

Index entries for sequences related to necklaces

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

T(2*n,n)=A003239(n); T(2*n+1,n)=A000108(n). - Philippe Deléham, Jul 25 2006

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

Triangle starts:

[ 0]  1,

[ 1]  1, 1,

[ 2]  1, 1, 1,

[ 3]  1, 1, 1, 1,

[ 4]  1, 1, 2, 1, 1,

[ 5]  1, 1, 2, 2, 1, 1,

[ 6]  1, 1, 3, 4, 3, 1, 1,

[ 7]  1, 1, 3, 5, 5, 3, 1, 1,

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

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

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

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

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

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:

seq(seq(A047996(n, k), k=0..n), n=0..10) ; # R. J. Mathar, Apr 14 2011

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 *)

(PARI)

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

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

/* Joerg Arndt, Sep 28 2012 */

(PARI)

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

/* print triangle: */

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

/* Joerg Arndt, Oct 21 2012 */

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

Cf. A051168, A052307, A052311-A052313.

See A037306 for an essentially identical triangle. - N. J. A. Sloane, Sep 05 2012

A241926 is also essentially identical.

See A245558, A245559 for a closely related array.

Sequence in context: A052307 A067059 A049704 * A227690 A063686 A008327

Adjacent sequences:  A047993 A047994 A047995 * A047997 A047998 A047999

nonn,tabl,easy,nice

N. J. A. Sloane

Elashvili et al. references supplied by Vladimir Popov, May 17 2014

approved