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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047996 Triangle of circular binomial coefficients T(n,k), 0<=k<=n. 25
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

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

REFERENCES

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.

F. Ruskey, Necklaces

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

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

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

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.

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 April 20 17:21 EDT 2014. Contains 240807 sequences.