|
| |
|
|
A047996
|
|
Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n.
|
|
37
|
|
|
|
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 antidiagonals (cf. A241926). - Franklin T. Adams-Watters, May 02 2014
The generating function for column k is given by the substitution x_j -> x^j/(1-x^j) in the cycle index of the Symmetric Group of order k. - R. J. Mathar, Nov 15 2018
Regarding the comments above by Voss, Adams-Watters, and Sloane, note that Fredman (1975) proved that the number S(n, k, v) of vectors (a_0, ..., a_{n-1}) of nonnegative integer components that satisfy a_0 + ... + a_{n-1} = k and Sum_{i=0..n-1} i*a_i = v (mod n) is given by S(n, k, v) = (1/(n + k)) * Sum_{d | gcd(n, k)} A054535(d, v) * binomial((n + k)/d, k/d) = S(k, n, v).
This result was also proved by Elashvili et al. (1999), who also proved that S(n, k, v) = Sum_{d | gcd(n, k, v)} S(n/d, k/d, 1). Here, S(n, k, 0) = A241926(n, k) = U(n, k) = T(n + k, k) (where T(n, k) is the current array). Also, S(n, k, 1) = A245558(n, k). See also Panyushev (2011) for more general results and for generating functions.
Finally, note that A054535(d, v) = c_d(v) = Sum_{s | gcd(d,v)} s*Moebius(d/s). These are the Ramanujan sums, which equal also the von Sterneck function c_d(v) = phi(d) * Moebius(d/gcd(d, v))/phi(d/gcd(d, v)). We have A054535(d, v) = A054534(v, d).
It would be interesting to see whether there is a proof of the results by Fredman (1975), Elashvili et al. (1999), and Panyushev (2011) for a general v using Molien series as it is done by Sloane (2014) for the case v = 0 (in which case, A054535(d, 0) = phi(d)). (Even though the columns of array A054535(d, v) start at v = 1, we may start the array at column v = 0 as well.)
(End)
U(n, k) is the number of equivalence classes of k-tuples of residues modulo n, identifying those that differ componentwise by a constant and those that differ by a permutation. - Álvar Ibeas, Sep 21 2021
|
|
|
REFERENCES
|
N. G. de Bruijn, Polya's theory of counting, in: Applied Combinatorial Mathematics (E. F. Beckenbach, ed.), John Wiley and Sons, New York, 1964, pp. 144-184 (implies g.f. for this triangle).
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.
See A000031 for many additional references and links.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n, k) = (1/n) * Sum_{d | (n, k)} phi(d)*binomial(n/d, k/d).
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
G.f.: Sum_{n, k >= 0} T(n, k)*x^n*y^k = 1 - Sum_{s>=1} (phi(s)/s)*log(1-x^s*(1+y^s)). - Petros Hadjicostas, Oct 26 2017
Product_{d >= 1} (1 - x^d - y^d) = Product_{i,j >= 0} (1 - x^i*y^j)^T(i+j, j), where not both i and j are zero. (It follows from Somos' infinite product for array A051168.) - Petros Hadjicostas, Jul 12 2019
|
|
|
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:
|
|
|
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 */
(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(); ); }
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
