A245558 -id:A245558 - cp's OEIS frontend

A245559 Triangle read by rows: entries on or below the main diagonal in A245558.

1, 1, 1, 1, 2, 3, 1, 2, 5, 8, 1, 3, 7, 14, 25, 1, 3, 9, 20, 42, 75, 1, 4, 12, 30, 66, 132, 245, 1, 4, 15, 40, 99, 212, 429, 800, 1, 5, 18, 55, 143, 333, 715, 1430, 2700, 1, 5, 22, 70, 200, 497, 1144, 2424, 4862, 9225, 1, 6, 26, 91, 273, 728, 1768, 3978, 8398, 16796, 32065, 1, 6, 30, 112, 364, 1026, 2652, 6288, 13995, 29372, 58786, 112632

Offset: 1

N. J. A. Sloane, Aug 07 2014

See A245558 for identification of other sequences occurring in this triangle.

			Triangle begins:
  1,
  1, 1,
  1, 2, 3,
  1, 2, 5, 8,
  1, 3, 7, 14, 25,
  1, 3, 9, 20, 42, 75,
  1, 4, 12, 30, 66, 132, 245,
  1, 4, 15, 40, 99, 212, 429, 800,
  1, 5, 18, 55, 143, 333, 715, 1430, 2700,
  1, 5, 22, 70, 200, 497, 1144, 2424, 4862, 9225,
  1, 6, 26, 91, 273, 728, 1768, 3978, 8398, 16796, 32065,
  1, 6, 30, 112, 364, 1026, 2652, 6288, 13995, 29372, 58786, 112632
  ...

A. Elashvili and 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, and D. Pataraia, Combinatorics of necklaces and "Hermite reciprocity", J. Algebraic Combin. 10 (1999), no. 2, 173-188; MR1719140 (2000j:05009). See p. 174.
J. E. Iglesias, Enumeration of closest-packings by the space group: a simple approach, Z. Krist. 221 (2006) 237-245, eq. (5).

Cf. A245558.

A245559 := proc(p,q)
    local d;
    a := 0 ;
    for d from 1 to max(p,q) do
        if modp(p,d)=0 and modp(q,d)=0 then
            a := a+numtheory[mobius](d)*(binomial((p+q)/d,p/d)) ;
        end if ;
    end do:
    a/(p+q) ;
end proc:
seq(seq( A245559(p,q),q=1..p),p=1..12) ; # R. J. Mathar, Apr 15 2024

A245559[p_, q_] := Module[{d, a = 0}, For[d = 1, d <= Max[p, q], d++, If[Mod[p, d] == 0 && Mod[q, d] == 0, a = a + MoebiusMu[d]*Binomial[ (p+q)/d, p/d]]]; a/(p+q)];
Table[Table[A245559[p, q], {q, 1, p}], {p, 1, 12}] // Flatten (* Jean-François Alcover, May 17 2024, after R. J. Mathar *)

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

N. J. A. Sloane

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

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

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.

Seiichi Manyama, Rows n=0..139 of triangle, flattened (Rows 0..50 from T. D. Noe)
Ethan Akin and 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 and 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, and 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, and D. Klarner, Correspondence, 1994
Petr Lisonek, Computer-assisted Studies in Algebraic Combinatorics, Thesis, University of Linz (Austria) Sep. 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.
Mónica A. Reyes, Cristina Dalfó, Miguel Àngel Fiol, and Arnau Messegué, A general method to find the spectrum and eigenspaces of the k-token of a cycle, and 2-token through continuous fractions, arXiv:2403.20148 [math.CO], 2024. See p. 5.
Frank Ruskey, Generate Necklaces, Lyndon words, and relatives, The Combinatorial Object Server.
Frank Ruskey and Joe Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM J. Computing, 29 (1999) 671-684.
Frank 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.
Pantelimon Stănică and Subhamoy 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

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.

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

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

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

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

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

Name edited by Petros Hadjicostas, Nov 16 2017

A185700 The number of periods in a reshuffling operation for compositions of n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 5, 5, 3, 1, 0, 1, 3, 7, 8, 7, 3, 1, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1

Offset: 1

Paul Weisenhorn, Feb 10 2011

n has 2^(n-1) compositions. For each composition remove the largest part and redistribute it by adding 1 to subsequently smaller parts (creating 1's if needed) to get a new composition of n. (This is reversing the operation in A188160.) Repeat. Eventually this sequence of compositions will cycle. We are interested in the length of the period.
Let the indices k and j be uniquely associated with n using the triangular numbers T=A000217: T(k-1) < n <= T(k) and n = T(k-1) + j with 0 < j <= k.
a(n) with T(k-1) < n <= T(k) is the number of periods with length k for 1 < k.
If k is prime then all periods of the numbers T(k-1) < n < T(k) have length k.
If k is not prime, then the length of the periods is k or a divisor of k.
n = T(k-1) + j has binomial(k,j) partitions in its periods with 0 < j < k.
n = T(k-1) + j has c(n) = Sum_{d|gcd(k,j)} (phi(d)*binomial(k/d,j/d))/k periods of length k or a divisor of k as tabulated in A047996; phi is Euler's totient function. If k is prime then a(n)=c(n) gives the number of periods with length k. If k is not prime, subtract all periods of length < k from c(n).
Obtained from A092964 by adding an initial column of 1's and appending a 1 and 0 to each row. Obtained from A051168 by reading the array downwards along antidiagonals. - R. J. Mathar, Apr 14 2011
As a regular triangle, T(n,k) is the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n and length k. Row sums are A059966. - Gus Wiseman, Dec 19 2017

			For k=5: T(4)=10 < n < T(5)=15 and all periods are of length 5:
a(11)=1 period: [(4+3+2+1+1), (4+3+2+2), (4+3+3+1), (4+4+2+1), (5+3+2+1)];
a(12)=2 periods: [(4+3+2+2+1), (4+3+3+2), (4+4+3+1), (5+4+2+1), (5+3+2+1+1)]; and [(4+4+2+2), (5+3+3+1), (4+4+2+1+1), (5+3+2+2), (4+3+3+1+1)];
a(13)=2 periods: [(4+4+2+2+1), (5+3+3+2), (4+4+3+1+1), (5+4+2+2), (5+3+3+1+1)]; and [(5+4+3+1), (5+4+2+1+1), (5+3+2+2+1), (4+3+3+2+1), (4+4+3+2)];
a(14)=1 period: [(5+4+3+2), (5+4+3+1+1), (5+4+2+2+1), (5+3+3+2+1), (4+4+3+2+1)].
For k=16; j=8; n=T(k-1)+j=128; 1<q|(16,8) --> {2,4,8} a(128) = c(128) - a(T(7)+4) - a(T(3)+2) - a(T(1)+1) =  810 - 8 - 1 - 1 = 800.
  (binomial(16,8)-8*a(T(7)+4)-4*a(T(3)+2)-2*a(T(1)+1))/16 = (12870-64-4-2)/16 = 800 = a(128).
Triangular view, with a(n) distributed in rows k=1,2,3.. according to T(k-1)< n <= T(k):
1;     k=1, n=1
1, 0;    k=2, n=2..3
1, 1,  0;    k=3, n=4..6
1, 1,  1,  0;    k=4, n=7..10
1, 2,  2,  1,   0;    k=5, n=11..15
1, 2,  3,  2,   1,   0;    k=6, n=16..21
1, 3,  5,  5,   3,   1,   0;
1, 3,  7,  8,   7,   3,   1,   0;
1, 4,  9, 14,  14,   9,   4,   1,   0;
1, 4, 12, 20,  25,  20,  12,   4,   1,  0;
1, 5, 15, 30,  42,  42,  30,  15,   5,  1,  0;
1, 5, 18, 40,  66,  75,  66,  40,  18,  5,  1, 0;
1, 6, 22, 55,  99, 132, 132,  99,  55, 22,  6, 1, 0;
1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1, 0;

R. Baumann, Computer-Knobelei, LOGIN (1987), 483-486 (in German).

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

Cf. A000740, A001037, A008965, A051168, A059966, A060223, A245558, A294859, A296302, A296373, A092964, A245559, A245558.

A000217 := proc(n) n*(n+1)/2 ; end proc:
A185700 := proc(n) local k,j,a,q; k := ceil( (-1+sqrt(1+8*n))/2 ) ; j := n-A000217(k-1) ; if n = 1 then return 1; elif j = k then return 0 ; end if; a := binomial(k,j) ; if not isprime(k) then for q in numtheory[divisors]( igcd(k,j)) minus {1} do a := a- procname(j/q+A000217(k/q-1))*k/q ; end do: end if; a/k ; end proc:
seq(A185700(n),n=1..80) ; # R. J. Mathar, Jun 11 2011

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length@Select[Join@@Permutations/@Select[IntegerPartitions[n],Length[#]===k&],LyndonQ],{n,10},{k,n}] (* Gus Wiseman, Dec 19 2017 *)

a(T(k))=0 with k > 1. a(1)=1.
If k is a prime number and n = T(k-1) + j with 0 < j < k, then a(n) = binomial(k,j)/k.
If k is not prime, subtract the sum of partitions in all periods of n with length < k from the term binomial(k,j). The difference divided by k gives the number of periods for n=T(k-1)+j: a(n)=( binomial(k,j) -sum {a(T(k/q-1)+j/q) *k/q })/k summed over all 1 < q|gcd(k,j).
If k is not prime, subtract the sum of all periods of n with length < k from the term c(n) = sum{ phi(d)*binomial(k/d,j/d) }/k summed over d|gcd(k,j), namely
  a(n) = c(n)-sum{a(T(k/q-1)+j))} summed over all 1 < q|gcd(k,j).

I have added a comment and deleted a Jun 11 2011 question from R. J. Mathar. - Paul Weisenhorn, Jan 08 2017

A037306 Triangle T(n,k) read by rows: the number of compositions of n into k parts, modulo cyclic shifts.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 3, 4, 3, 1, 1, 1, 3, 5, 5, 3, 1, 1, 1, 4, 7, 10, 7, 4, 1, 1, 1, 4, 10, 14, 14, 10, 4, 1, 1, 1, 5, 12, 22, 26, 22, 12, 5, 1, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 1, 6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1

Offset: 1

Jens Voß, Jun 30 2001

Triangle obtained from A047996 by dropping the first column (k=0), and row (n=0).
T(n, k) = number of different ways the number n can be expressed as ordered sums of k positive integers, counting only once those ordered sums that can be transformed into each other by a cyclic permutation.
These might be described as cyclic compositions, or more loosely as cyclic partitions. - N. J. A. Sloane, Sep 05 2012

			Triangle begins
  1;
  1,  1;
  1,  1,  1;
  1,  2,  1,  1;
  1,  2,  2,  1,  1;
  1,  3,  4,  3,  1,  1;
  1,  3,  5,  5,  3,  1,  1;
  1,  4,  7, 10,  7,  4,  1,  1;
  1,  4, 10, 14, 14, 10,  4,  1,  1;
  1,  5, 12, 22, 26, 22, 12,  5,  1,  1;
  1,  5, 15, 30, 42, 42, 30, 15,  5,  1,  1;
T(6,3) = 4, since there are 4 essentially different ways 1+1+4, 1+2+3, 1+3+2 and 2+2+2 of expressing 6 as a sum of 3 summands (all others can be obtained by cyclically permuting the summands in one of the above sums).

N. Zagaglia Salvi, Ordered partitions and colourings of cycles and necklaces, Bull. Inst. Combin. Appl., 27 (1999), 37-40.

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
Ethan Akin and Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250.
R. Baumann, Computer-Knobelei, , LOGIN, 163/164 (2010), 141-142 (in German).
R. Bekes, J. Pedersen and B. Shao, Mad tea party cyclic partitions, College Math. J., 43 (2012), 24-36.
A. Elashvili and 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, and 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
Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), Article 16.8.2.
Arnold Knopfmacher and Neville Robbins, Some Properties of Cyclic Compositions, Fibonacci Quart. 48 (2010), no. 3, 249-255.
D. M. Y. Sommerville, On Certain Periodic Properties of Cyclic Compositions of Numbers, Proc. London Math. Soc., s2-7, No. 1 (1909), 263-313.
R. Razen, J. Seberry, and K. Wehrhahn, Ordered partitions and codes generated by circulant matrices, J. Combin. Theory Ser. A, 27 (1979), 333-341.
D. Wasserman, Proof of the symmetry [Broken link]
D. Wasserman, Proof of the symmetry [Cached copy]

A047996 and A241926 are essentially identical to this entry.
Cf. A008965 (row sums), A000010, A007318, A027750, A215251, A004526 (column 2), A007997 (column 3), A008610 (column 4), A008646 (column 5), A032191 (column 6).
See A245558, A245559 for a closely related array.
See A052307 for compositions modulo cyclic shifts and reversal.

a037306 n k = div (sum $ map f $ a027750_row $ gcd n k) n where
   f d = a000010 d * a007318' (div n d) (div k d)
a037306_row n = map (a037306 n) [1..n]
a037306_tabl = map a037306_row [1..]
-- Reinhard Zumkeller, Feb 06 2014

A037306 := proc(n,k) local a,d; a := 0; for d in numtheory[divisors]( igcd(n,k)) do a := a+numtheory[phi](d)*binomial(n/d,k/d); end do: a/n; end proc:
seq(seq(A037306(n,k), k=1..n), n=1..20); # R. J. Mathar, Jun 11 2011

t[n_, k_] := Total[EulerPhi[#]*Binomial[n/#, k/#] & /@ Divisors[GCD[n, k]]]/n; Flatten[Table[t[n, k], {n, 13}, {k, n}]] (* Jean-François Alcover, Sep 08 2011, after formula *)
nn=15;f[list_]:=Select[list,#>0&];Map[f,Transpose[Table[Drop[CoefficientList[Series[CycleIndex[CyclicGroup[n],s]/.Table[s[i]->x^i/(1-x^i),{i,1,n}],{x,0,nn}],x],1],{n,1,nn}]]]//Grid  (* Geoffrey Critzer, Oct 30 2012 *)

T(n, k) = sumdiv(gcd(n,k), d, eulerphi(d)*binomial(n/d, k/d))/n; \\ Michel Marcus, Feb 10 2016

T(n,k) = (Sum_{d|gcd(n,k)} phi(d)*binomial(n/d,k/d))/n, where phi = A000010 = Euler's totient function. Also T(n,k) = A047996(n,k). - Paul Weisenhorn, Apr 06 2011

More terms from David Wasserman, Mar 11 2002

Comments, reference, example from Paul Weisenhorn, Dec 18 2010

A050186 Triangular array T read by rows: T(h,k) = number of binary words of k 1's and h-k 0's which are not a juxtaposition of 2 or more identical subwords.

Original entry on oeis.org

1, 1, 1, 0, 2, 0, 0, 3, 3, 0, 0, 4, 4, 4, 0, 0, 5, 10, 10, 5, 0, 0, 6, 12, 18, 12, 6, 0, 0, 7, 21, 35, 35, 21, 7, 0, 0, 8, 24, 56, 64, 56, 24, 8, 0, 0, 9, 36, 81, 126, 126, 81, 36, 9, 0, 0, 10, 40, 120, 200, 250, 200, 120, 40, 10, 0, 0, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11

Offset: 0

Clark Kimberling

			For example, T(4,2) counts 1100,1001,0011,0110; T(2,1) counts 10, 01 (hence also counts 1010, 0101).
Rows:
  1;
  1,  1;
  0,  2,  0;
  0,  3,  3,  0;
  0,  4,  4,  4,  0;
  0,  5, 10, 10,  5,  0;

M. F. Hasler, A050186, rows 0..50, Sep 27 2018
M. F. Hasler, A050186, rows 0..100, Sep 27 2018
M. F. Hasler, A050186, rows 0..200, Sep 27 2018
N. J. A. Sloane, Transforms
Index entries for triangles and arrays related to Pascal's triangle

Same triangle as A053727 except this one includes column 0.

T(2n, n), T(2n+1, n) match A007727, A001700, respectively. Row sums match A027375.

T[n_, k_] := If[n == 0, 1, DivisorSum[GCD[k, n], MoebiusMu[#] Binomial[n/#, k/#]&]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 16 2022 *)

A050186(n,k)=sumdiv(gcd(n+!n,k),d,moebius(d)*binomial(n/d,k/d)) \\ M. F. Hasler, Sep 27 2018

MOEBIUS transform of A007318 Pascal's Triangle.

If rows n > 1 are divided by n, this yields the triangle A051168, which equals A245558 surrounded by 0's (except for initial terms). This differs from A011847 from row n = 9 on. - M. F. Hasler, Sep 29 2018

A011847 Triangle of numbers read by rows: T(n,k) = floor( C(n,k)/(k+1) ), where k=0..n-1 and n >= 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 5, 5, 3, 1, 1, 3, 7, 8, 7, 3, 1, 1, 4, 9, 14, 14, 9, 4, 1, 1, 4, 12, 21, 25, 21, 12, 4, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 5, 18, 41, 66, 77, 66, 41, 18, 5, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1, 1, 6, 26, 71, 143, 214, 245, 214, 143, 71, 26, 6, 1

Offset: 1

N. J. A. Sloane

When k+1 is a prime >= 2, then T(n,k) = floor(C(n,k)/(k+1)) is the number of aperiodic necklaces of n+1 beads of 2 colors such that k+1 of them are black and n-k of them are white. This is not true when k+1 is a composite >= 4. For more details, see the comments for sequences A032168 and A032169. - Petros Hadjicostas, Aug 27 2018

Differs from A245558 from row n = 9, k = 4 on. - M. F. Hasler, Sep 29 2018

			Triangle begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  2,   1;
  1, 2,  3,   2,   1;
  1, 3,  5,   5,   3,   1;
  1, 3,  7,   8,   7,   3,    1;
  1, 4,  9,  14,  14,   9,    4,    1;
  1, 4, 12,  21,  25,  21,   12,    4,    1;
  1, 5, 15,  30,  42,  42,   30,   15,    5,    1;
  1, 5, 18,  41,  66,  77,   66,   41,   18,    5,   1;
  1, 6, 22,  55,  99, 132,  132,   99,   55,   22,   6,   1;
  1, 6, 26,  71, 143, 214,  245,  214,  143,   71,  26,   6,   1;
  1, 7, 30,  91, 200, 333,  429,  429,  333,  200,  91,  30,   7,  1;
  1, 7, 35, 113, 273, 500,  715,  804,  715,  500, 273, 113,  35,  7, 1;
  1, 8, 40, 140, 364, 728, 1144, 1430, 1430, 1144, 728, 364, 140, 40, 8, 1;
...
More than the usual number of rows are shown in order to distinguish this triangle from A245558, from which it differs in rows 9, 11, 13, ....
From _Petros Hadjicostas_, Aug 27 2018: (Start)
For k+1 = 2 and n >= k+1 = 2, the n-th element of column k=1 above, [0, 1, 1, 2, 2, 3, 3, 4, 4, ...] (i.e., the number A008619(n-2) = floor(n/2)), gives the number of aperiodic necklaces of n+1 beads of 2 colors such that 2 of them are black and n-1 of them are white. (The offset of sequence A008619 is 0.)
For k+1 = 3 and n >= k+1 = 3, the n-th element of column k=2 above, [0, 0, 1, 2, 3, 5, 7, 9, 12, ...] (i.e., the number A001840(n-2) = floor(C(n,2)/3)), gives the number of aperiodic necklaces of n+1 beads of 2 colors such that 3 of them are black and n-2 of them are white. (The offset of sequence A001840 is 0.)
For k+1 = 5 and n >= k+1 = 5, the n-th element of column k=4 above, [0, 0, 0, 0, 1, 3, 7, 14, 25, 42, ... ] (i.e., the number A011795(n) = floor(C(n,4)/5)), gives the number of aperiodic necklaces of n+1 beads of 2 colors such that 5 of them are black and n-4 of them are white. (The offset of sequence A011795 is 0.)
Counterexample for k+1 = 4: It can be proved that, for n >= k+1 = 4, the number of aperiodic necklaces of n+1 beads of 2 colors such that 4 of them are black and n-3 of them are white is (1/4)*Sum_{d|4} mu(d)*I(d|n+1)*C(floor((n+1)/d) - 1, 4/d - 1) = (1/4)*(C(n, 3) - I(2|n+1)*floor((n-1)/2)), where I(a|b) = 1 if integer a divides integer b, and 0 otherwise. For n odd >= 9, the number (1/4)*(C(n, 3) - I(2|n+1)*floor((n-1)/2)) = A006918(n-3) is not equal to floor(C(n,3)/4) = A011842(n).
(End)

G. C. Greubel, Rows n = 1..100 of the triangle, flattened

Columns include A008619, A001840, A011842, A011795, A011843, A011797, A011844, A011845, A011846, A032169.
Sums: A095718 (row), A095719 (diagonal).
Cf. A006918, A245558.

A011847:= func< n,k | Floor(Binomial(n+1,k+1)/(n+1)) >;
[A011847(n,k): k in [0..n-1], n in [1..20]]; // G. C. Greubel, Oct 20 2024

Table[Floor[Binomial[n,k]/(k+1)],{n,20},{k,0,n-1}]//Flatten (* Harvey P. Dale, Jan 09 2019 *)

A011847(n,k)=binomial(n,k)\(k+1) \\ M. F. Hasler, Sep 30 2018

def A011847(n,k): return binomial(n+1,k+1)//(n+1)
flatten([[A011847(n,k) for k in range(n)] for n in range(1,21)]) # G. C. Greubel, Oct 20 2024

The rows are palindromic: T(n, k) = T(n, n-k-1) for n >= 1 and 0 <= k <= n-1.

Sum_{k=0..floor((n-1)/2)} T(n-k, k) = A095719(n). - G. C. Greubel, Oct 20 2024

A241926 Table read by antidiagonals: T(n,k) (n >= 1, k >= 1) is the number of necklaces with n black beads and k white beads.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 3, 4, 3, 1, 1, 3, 5, 5, 3, 1, 1, 4, 7, 10, 7, 4, 1, 1, 4, 10, 14, 14, 10, 4, 1, 1, 5, 12, 22, 26, 22, 12, 5, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 6, 19, 43, 66, 80, 66, 43, 19, 6, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1

Offset: 1

Franklin T. Adams-Watters, May 02 2014

Turning over the necklace is not allowed (the group is cyclic not dihedral). T(n,k) = T(k,n) follows immediately from the formula. - N. J. A. Sloane, May 03 2014

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

			The table starts:
  1, 1,  1,  1,  1,  1,   1,   1,   1,   1,   1,    1, ...
  1, 2,  2,  3,  3,  4,   4,   5,   5,   6,   6,    7, ...
  1, 2,  4,  5,  7, 10,  12,  15,  19,  22,  26,   31, ...
  1, 3,  5, 10, 14, 22,  30,  43,  55,  73,  91,  116, ...
  1, 3,  7, 14, 26, 42,  66,  99, 143, 201, 273,  364, ...
  1, 4, 10, 22, 42, 80, 132, 217, 335, 504, 728, 1038, ...
  ...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Elashvili and 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 and 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
N. J. A. Sloane, A Note on Modular Partitions and Necklaces

Same as A047996 with first row and main diagonal removed.
A037306 is yet another version.
Cf. A003239 (main diagonal).
See A245558, A245559 for a closely related array.

# Maple program for the table - N. J. A. Sloane, May 03 2014:
with(numtheory);
T:=proc(n,k) local d, s, g, t0;
t0:=0; s:=n+k; g:=gcd(n,k);
for d from 1 to s do
   if (g mod d) = 0 then t0:=t0+phi(d)*binomial(s/d,k/d); fi;
od: t0/s; end;
r:=n->[seq(T(n,k),k=1..12)];
[seq(r(n),n=1..12)];

T[n_, k_] := DivisorSum[GCD[n, k], EulerPhi[#] Binomial[(n+k)/#, n/#]& ]/ (n+k); Table[T[n-k+1, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Dec 02 2015 *)

T(n,k) = sumdiv(gcd(n,k),d,eulerphi(d)*binomial((n+k)\d,n\d))/(n+k)

T(n,k) = (Sum_{d | gcd(n,k)} phi(d)*binomial((n+k)/d, n/d))/(n+k). [Corrected by N. J. A. Sloane, May 03 2014]

Edited by N. J. A. Sloane, May 03 2014

Elashvili et al. references supplied by Vladimir Popov, May 17 2014

A007148 Number of self-complementary 2-colored bracelets (turnover necklaces) with 2n beads.

Original entry on oeis.org

1, 2, 3, 6, 10, 20, 37, 74, 143, 284, 559, 1114, 2206, 4394, 8740, 17418, 34696, 69194, 137971, 275280, 549258, 1096286, 2188333, 4369162, 8724154, 17422652, 34797199, 69505908, 138845926, 277383872, 554189329, 1107297290, 2212558942

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
E. M. Palmer and R. W. Robinson, Enumeration of self-dual configurations Pacific J. Math., 110 (1984), 203-221.
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]
Index entries for sequences related to bracelets

Cf. A000013, A000079, A007147.

Different from, but easily confused with, A045690 and A093371.

# see A245558
L := proc(n,k)
    local a,j ;
    a := 0 ;
    for j in numtheory[divisors](igcd(n,k)) do
        a := a+numtheory[mobius](j)*binomial(n/j,k/j) ;
    end do:
    a/n ;
end proc:
A007148 := proc(n)
    local a,k,l;
    a := 0 ;
    for k from 1 to n do
        for l in numtheory[divisors](igcd(n,k)) do
            a := a+L(n/l,k/l)*ceil(k/2/l) ;
        end do:
    end do:
    a;
end proc:
seq(A007148(n),n=1..20) ; # R. J. Mathar, Jul 23 2017

a[n_] := (1/2)*(2^(n-1) + Total[ EulerPhi[2*#]*2^(n/#) &  /@ Divisors[n]]/(2*n)); Table[ a[n], {n, 1, 33}] (* Jean-François Alcover, Oct 25 2011 *)

a(n)= (1/2) *(2^(n-1)+sumdiv(n,k,eulerphi(2*k)*2^(n/k))/(2*n))

from sympy import divisors, totient
def a(n):
    if n==1: return 1
    return 2**(n - 2) + sum(totient(2*d)*2**(n//d) for d in divisors(n))//(4*n)
print([a(n) for n in range(1, 31)]) # Indranil Ghosh, Jul 24 2017

a(n) = 2^(n-2) + (1/(4n)) * Sum_{d|n} phi(2d)*2^(n/d). - N. J. A. Sloane, Sep 25 2012

a(n) = (1/2)*(A000079(n-1) + A000013(n)).

Description corrected by Christian G. Bower

A031164 Irreducible Euler sums of weight 8 and depth 10+2n.

Original entry on oeis.org

1, 4, 15, 40, 99, 212, 429, 800, 1430, 2424, 3978, 6288, 9690, 14520, 21318, 30624, 43263, 60060, 82225, 110968, 148005, 195052, 254475, 328640, 420732, 533936, 672452, 840480, 1043460, 1286832, 1577532, 1922496, 2330445

Offset: 0

David Broadhurst

a(n-9)=number of aperiodic necklaces (Lyndon words) with 8 black beads and n-8 white beads.

David J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
David Broadhurst and Xavier Roulleau, Number of partitions of modular integers, arXiv:2502.19523 [math.NT], 2025. See p. 19.
Index entries for sequences related to Lyndon words
Index entries for linear recurrences with constant coefficients, signature (4,-2,-12,17,8,-28,8,17,-12,-2,4,-1).

Cf. A000031, A001037, A051168. Row 8 in A245558.

Cf. A032094. - M. F. Hasler, May 02 2009

Table[(Binomial[n+8,7]-If[OddQ[n],1,0]Binomial[(n+7)/2,3])/8,{n,0,40}] (* or *) CoefficientList[Series[(1+x^2)/((1-x)^8 (1+x)^4),{x,0,40}],x] (* Harvey P. Dale, Jun 20 2011 *)

A031164(n)=(binomial(n+8,7)-if(n%2,binomial(n\2+4,3)))>>3 \\ M. F. Hasler, May 02 2009

G.f.: (1+x^2)/((1-x)*(1-x^2))^4
a(n) = [C(n+8,7)-(n%2)*C((n+7)/2,3)]/8, where C = binomial, n%2 = parity of n (=1 if odd, 0 else). - M. F. Hasler, May 02 2009
a(0)=1, a(1)=4, a(2)=15, a(3)=40, a(4)=99, a(5)=212, a(6)=429, a(7)=800, a(8)=1430, a(9)=2424, a(10)=3978, a(11)=6288, a(n) = 4*a(n-1)-2*a(n-2)-12*a(n-3)+17*a(n-4)+8*a(n-5)-28*a(n-6)+8*a(n-7)+17*a(n-8)-12*a(n-9)- 2*a(n-10)+4*a(n-11)-a(n-12). - Harvey P. Dale, Jun 20 2011
G.f.: ((-1+x)^-8-(-1+x^2)^-4)/(8*x). - Herbert Kociemba, Oct 16 2016

cp's OEIS Frontend

A245559 Triangle read by rows: entries on or below the main diagonal in A245558.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A185700 The number of periods in a reshuffling operation for compositions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A037306 Triangle T(n,k) read by rows: the number of compositions of n into k parts, modulo cyclic shifts.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A050186 Triangular array T read by rows: T(h,k) = number of binary words of k 1's and h-k 0's which are not a juxtaposition of 2 or more identical subwords.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A011847 Triangle of numbers read by rows: T(n,k) = floor( C(n,k)/(k+1) ), where k=0..n-1 and n >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica