cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A047996 Triangle read by rows: T(n,k) is the (n,k)-th circular binomial coefficient, where 0 <= k <= n.

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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
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.
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
From Petros Hadjicostas, Jul 12 2019: (Start)
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

Examples

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

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.
  • H. S. Wilf, personal communication to N. J. A. Sloane, Nov., 1990.
  • See A000031 for many additional references and links.

Links

Crossrefs

Row sums: A000031. Columns 0-12: A000012, A000012, A004526, A007997(n+5), A008610, A008646, A032191-A032197.
Cf. A051168, A052307, A052311-A052313.
See A037306 and A241926 for essentially identical triangles.
See A245558, A245559 for a closely related array.

Programs

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

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

Extensions

Name edited by Petros Hadjicostas, Nov 16 2017

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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