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

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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)

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

Seiichi Manyama, Rows n=0..139 of triangle, flattened (Rows 0..50 from T. D. Noe)

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

Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.

A. Elashvili, M. Jibladze, Hermite reciprocity for the regular representations of cyclic groups, Indag. Math. (N.S.) 9 (1998), no. 2, 233-238. MR1691428 (2000c:13006)

A. Elashvili, M. Jibladze, D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - N. J. A. Sloane, Aug 06 2014

M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.

Harold Fredricksen, An algorithm for generating necklaces of beads in two colors, Discrete Mathematics, Volume 61, Issues 2-3, September 1986, 181-188.

D. E. Knuth, Computer science and its relation to mathematics, Amer. Math. Monthly, 81 (1974), 323-343.

D. E. Knuth, H. Wilf, C. L. Mallows, & D. Klarner, Correspondence, 1994

Petr Lisonek, Computer-assisted Studies in Algebraic Combinatorics, Thesis, 1994, pp. 72-73.

D. I. Panyushev, Fredman's reciprocity, invariants of abelian groups, and the permanent of the Cayley table, J. Algebraic Combin. 33 (2011), 111-125.

F. Ruskey, Generate Necklaces, Lyndon words, and relatives, The Combinatorial Object Server.

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

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]

N. J. A. Sloane, A Note on Modular Partitions and Necklaces, 2014.

P. Stanica, S. Maitra, Rotation symmetric boolean functions - count and cryptographic properties, Disc. Appl. Math. 156 (2008) 1567-1580, g_{n,w} Theorem 9.

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

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:

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

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

EXTENSIONS

Name edited by Petros Hadjicostas, Nov 16 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 18:12 EST 2019. Contains 329847 sequences. (Running on oeis4.)