A261494 Number A(n,k) of necklaces with n white beads and k*n black beads; square array A(n,k), n>=0, k>=0, read by antidiagonals.
1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 4, 1, 1, 1, 4, 10, 10, 1, 1, 1, 5, 19, 43, 26, 1, 1, 1, 6, 31, 116, 201, 80, 1, 1, 1, 7, 46, 245, 776, 1038, 246, 1, 1, 1, 8, 64, 446, 2126, 5620, 5538, 810, 1, 1, 1, 9, 85, 735, 4751, 19811, 42288, 30667, 2704, 1
Offset: 0
Examples
A(2,2) = 3: 000011, 000101, 001001. A(3,2) = 10: 000000111, 000001011, 000010011, 000100011, 001000011, 010000011, 000010101, 000100101, 001000101, 001001001. Square array A(n,k) begins: 1, 1, 1, 1, 1, 1, 1, ... 1, 1, 1, 1, 1, 1, 1, ... 1, 2, 3, 4, 5, 6, 7, ... 1, 4, 10, 19, 31, 46, 64, ... 1, 10, 43, 116, 245, 446, 735, ... 1, 26, 201, 776, 2126, 4751, 9276, ... 1, 80, 1038, 5620, 19811, 54132, 124936, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
- F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
- F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
- Eric Weisstein's World of Mathematics, Necklace
- Wikipedia, Necklace (combinatorics)
- Index entries for sequences related to necklaces
Crossrefs
Programs
-
Maple
with(numtheory): A:= (n, k)-> `if`(n=0, 1, add(binomial((k+1)*n/d, n/d) *phi(d), d=divisors(n))/((k+1)*n)): seq(seq(A(n, d-n), n=0..d), d=0..14); -
Mathematica
A[n_, k_] := If[n==0, 1, DivisorSum[n, Binomial[(k+1)*n/#, n/#]*EulerPhi[#] /((k+1)*n)&]]; Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Feb 19 2017, translated from Maple *) -
PARI
a(n,k) = if(n<1, 1, sumdiv(n, d, binomial((k + 1)*n/d, n/d) * eulerphi(d)) / ((k + 1)*n)); for(d=0, 14, for(n=0, d, print1(a(n, d - n),", ");); print();) \\ Indranil Ghosh, Mar 25 2017
Formula
A(n,k) = 1/((k+1)*n) * Sum_{d|n} C((k+1)*n/d,n/d) * A000010(d) for n>0, A(0,k) = 1.
A(n,k) = 1/((k+1)*n)*Sum_{i=1..n} C((k+1)*gcd(n,i),gcd(n,i)) = 1/((k+1)*n)*Sum_{i=1..n} C((k+1)*n/gcd(n,i),n/gcd(n,i))*phi(gcd(n,i))/phi(n/gcd(n,i)) for n >= 1, where phi = A000010. - Richard L. Ollerton, May 19 2021
Comments