|
| |
|
|
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.
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}]] (* From 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 * A063686 A008327 A133687
Adjacent sequences: A047993 A047994 A047995 * A047997 A047998 A047999
|
|
|
KEYWORD
|
nonn,tabl,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
