login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047996 Triangle read by rows: T(n,k) = number of circular binomial coefficients for 0<=k<=n. 27
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, 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, 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,13

COMMENTS

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.

REFERENCES

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

Elashvili, A.; Jibladze, M.; Pataraia, D. 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.

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.

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

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

FORMULA

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]

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

PROG

(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 */

CROSSREFS

Row sums: A000031. Columns 0-12: A000012, A000012, A004526, A007997(n-3), 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

KEYWORD

nonn,tabl,easy,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

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

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 1 16:17 EDT 2014. Contains 247515 sequences.