A092964 -id:A092964 - cp's OEIS frontend

A051168 Triangular array T(h,k) for 0 <= k <= h read by rows: T(h,k) = number of binary Lyndon words with k ones and h-k zeros.

1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 2, 3, 2, 1, 0, 0, 1, 3, 5, 5, 3, 1, 0, 0, 1, 3, 7, 8, 7, 3, 1, 0, 0, 1, 4, 9, 14, 14, 9, 4, 1, 0, 0, 1, 4, 12, 20, 25, 20, 12, 4, 1, 0, 0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 0, 0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 0, 0, 1, 6

Offset: 0

Clark Kimberling

T(h,k) is the number of classes of aperiodic binary words of k ones and h-k zeros; words u,v are in the same class if v is a cyclic permutation of u (e.g., u=111000, v=110001) and a word is aperiodic if not a juxtaposition of 2 or more identical subwords.
T(2n, n), T(2n+1, n), T(n, 3) match A022553, A000108, A001840, respectively. Row sums match A001037.
From R. J. Mathar, Jul 31 2008: (Start)
This triangle may also be regarded as the square array A(r,n), the n-th term of the r-th Witt transform of the all-1 sequence, r >= 1, n >= 0, read by antidiagonals:
This array begins as follows:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
0 1 2 3 5 7 9 12 15 18 22 26 30 35 40 45 51 57 63
0 1 2 5 8 14 20 30 40 55 70 91 112 140 168 204 240 285 330
0 1 3 7 14 25 42 66 99 143 200 273 364 476 612 775 969 1197 1463
0 1 3 9 20 42 75 132 212 333 497 728 1026 1428 1932 2583 3384 4389 5598
0 1 4 12 30 66 132 245 429 715 1144 1768 2652 3876 5537 7752 10659 14421 19228
0 1 4 15 40 99 212 429 800 1430 2424 3978 6288 9690 14520 21318 30624 43263 60060
0 1 5 18 55 143 333 715 1430 2700 4862 8398 13995 22610 35530 54477 81719 120175
0 1 5 22 70 200 497 1144 2424 4862 9225 16796 29372 49742 81686 130750 204248
0 1 6 26 91 273 728 1768 3978 8398 16796 32065 58786 104006 178296 297160 482885
0 1 6 30 112 364 1026 2652 6288 13995 29372 58786 112632 208012 371384 643842
0 1 7 35 140 476 1428 3876 9690 22610 49742 104006 208012 400023 742900 1337220
0 1 7 40 168 612 1932 5537 14520 35530 81686 178296 371384 742900 1432613 2674440
...
It is essentially symmetric: A(r,r+i) = A(r,r-i+1).
Some of the diagonals are:
A(r,r+1): A000108
A(r,r): A022553
A(r,r-1): A000108
A(r,r+2): A000150
A(r,r+3): A050181
A(r,r+4): A050182
A(r,r+5): A050183
A(r,r-2): A000150 (End)
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)} A054533(d, v) * binomial((n + k)/d, k/d) = S(k, n, v). This 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, 1) = T(n + k, k). - Petros Hadjicostas, Jul 09 2019

			Triangle begins with:
h=0: 1
h=1: 1, 1
h=2: 0, 1, 0
h=3: 0, 1, 1, 0
h=4: 0, 1, 1, 1,  0
h=5: 0, 1, 2, 2,  1,  0
h=6: 0, 1, 2, 3,  2,  1, 0
h=7: 0, 1, 3, 5,  5,  3, 1, 0
h=8: 0, 1, 3, 7,  8,  7, 3, 1, 0
h=9: 0, 1, 4, 9, 14, 14, 9, 4, 1, 0
...
T(6,3) counts classes {111000},{110100},{110010}, each of 6 aperiodic. The class {100100} contains 3 periodic words, counted by T(3,1) as {100}, consisting of 3 aperiodic words 100,010,001.

Andrew Howroyd, Table of n, a(n) for n = 0..1274
Freddy Cachazo and Nick Early, Planar Kinematics: Cyclic Fixed Points, Mirror Superpotential, k-Dimensional Catalan Numbers, and Root Polytopes, arXiv:2010.09708 [math.CO], 2020.
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.
Romeo Meštrović, Different classes of binary necklaces and a combinatorial method for their enumerations, arXiv:1804.00992 [math.CO], 2018.
Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160.
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]
P. Stanica and S. Maitra, Rotation symmetric boolean functions - count and cryptographic properties, Disc. Appl. Math. 156 (2008) 1567-1580; see h_{n,w} in eq. (3).
Index entries for sequences related to Lyndon words

Columns 1-11: A000012, A004526(n-1), A001840(n-4), A006918(n-4), A011795(n-1), A011796(n-6), A011797(n-1), A031164(n-9), A011845, A032168, A032169. See also A000150.

Cf. A047996, A052307, A052314, A092964, A185158, A123223, A124814.

A := proc(r,n) local gf,d,genf; genf := 1/(1-x) ; gf := 0 ; for d in numtheory[divisors](r) do gf := gf + numtheory[mobius](d)*(subs(x= x^d,genf))^(r/d) ; od: gf := expand(gf/r) ; coeftayl(gf,x=0,n) ; end proc:
A051168 := proc(n,k) if n<=1 then 1; elif n=0 or n=k then 0; else A(n-k,k) ; end if;
end proc:
seq(seq(A051168(n,k),k=0..n),n=0..10) ; # R. J. Mathar, Mar 29 2011

Table[If[n===0,1,1/n Plus@@(MoebiusMu[ # ]Binomial[n/#,k/# ]&/@ Divisors[GCD[n,k]])],{n,0,12},{k,0,n}] (* Wouter Meeussen, Jul 20 2008 *)

{T(n, k) = local(A, ps, c); if( k<0 || k>n, 0, if( n==0 && k==0, 1, A = x * O(x^n) + y * O(y^n); ps = 1 - x - y + A; for( m=1, n, for( i=0, m, c = polcoeff( polcoeff(ps, i, x), m-i, y); if( m==n && i==k, break(2), ps *= (1 -y^(m-i) * x^i + A)^c))); -c))} /* Michael Somos, Jul 03 2004 */

T(n,k) = if (n==0, 1, (1/n) * sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d,k/d)));
tabl(nn) = for (n=0, nn, for (k=0, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, May 16 2018

T(h, k) = 1 for (h, k) in {(0, 0), (1, 0), (1, 1)}; T(h, k) = 0 if h >= 2 and k = 0 or k = h. Otherwise, T(h, k) = (1/h)*(C(h, k)-S(h, k)), where S(h, k) = Sum_{d <= 2, d|h, d|k} (h/d)*T(h/d, k/d).
1 - x - y = Product_{i,j} (1 - x^i * y^j)^T(i+j, j) where i >= 0, j >= 0 are not both zero. - Michael Somos, Jul 03 2004
The prime rows are given by (1+x)^p/p with noninteger coefficients rounded to zero. E.g., for h = 2 below, (1 + x)^2/2 = (1 + 2*x + x^2)/2 = 0.5 + x + 0.5*x^2 gives (0,1,0). - Tom Copeland, Oct 21 2014
T(n,k) = (1/n) * Sum_{d | gcd(n,k)} mu(d) * binomial(n/d, k/d), for n > 0. - Andrew Howroyd, Mar 26 2017
From Petros Hadjicostas, Jun 16 2019: (Start)
O.g.f. for column k >= 1: (x^k/k) * Sum_{d|k} mu(d)/(1 - x^d)^(k/d).
Bivariate o.g.f.: Sum_{n,k >= 0} T(n, k)*x^n*y^k = 1 - Sum_{d >= 1} (mu(d)/d) *log(1 - x^d * (1 + y^d)).
(End)

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

A245558 Square array read by antidiagonals: T(n,k) = number of n-tuples of nonnegative integers (u_0,...,u_{n-1}) satisfying Sum_{j=0..n-1} j*u_j == 1 mod n and Sum_{j=0..n-1} u_j = m.

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, 20, 25, 20, 12, 4, 1, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1

Offset: 1

N. J. A. Sloane, Aug 07 2014

The array is symmetric; for the entries on or below the diagonal see A245559.
If the congruence in the definition is changed from Sum_{j=0..n-1} j*u_j == 1 mod n  to Sum_{j=0..n-1} j*u_j == 0 mod n we get the array shown in A241926, A047996, and A037306.
Differs from A011847 from row n = 9, k = 4 on; if the rows are surrounded by 0's, this yields A051168 without its rows 0 and 1, i.e., a(1) is A051168(2,1). - M. F. Hasler, Sep 29 2018
This array was first studied by Fredman (1975). - Petros Hadjicostas, Jul 10 2019

			Square array begins:
  1, 1,  1,  1,   1,   1,    1,    1,    1,    1, ...
  1, 1,  2,  2,   3,   3,    4,    4,    5,    5, ...
  1, 2,  3,  5,   7,   9,   12,   15,   18,   22, ...
  1, 2,  5,  8,  14,  20,   30,   40,   55,   70, ...
  1, 3,  7, 14,  25,  42,   66,   99,  143,  200, ...
  1, 3,  9, 20,  42,  75,  132,  212,  333,  497, ...
  1, 4, 12, 30,  66, 132,  245,  429,  715, 1144, ...
  1, 4, 15, 40,  99, 212,  429,  800, 1430, 2424, ...
  1, 5, 18, 55, 143, 333,  715, 1430, 2700, 4862, ...
  1, 5, 22, 70, 200, 497, 1144, 2424, 4862, 9225, ...
  ...
Reading by antidiagonals, we get:
  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, 20, 25,  20,  12,  4,  1;
  1, 5, 15, 30, 42,  42,  30, 15,  5,  1;
  1, 5, 18, 40, 66,  75,  66, 40, 18,  5, 1;
  1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1;
  ...

Taylor Brysiewicz, Necklaces count polynomial parametric osculants, arXiv:1807.03408 [math.AG], 2018.
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.
M. L. Fredman, A symmetry relationship for a class of partitions, J. Combinatorial Theory Ser. A 18 (1975), 199-202.
I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory, Ser. A, 64, 1993, 189-215, Theorem 9.4.
J. E. Iglesias, Enumeration of closest-packings by the space group: a simple approach, Z. Krist. 221 (2006) 237-245, eq. (5).

This array is very similar to but different from A011847.
Cf. A051168, A092964, A241926, A047996, A037306, A245559.
Rows include A001840, A006918, A051170, A011796, A011797, A031164. Main diagonal is A022553.

# To produce the first 10 rows and columns (as on page 174 of the Elashvili et al. 1999 reference):
with(numtheory):
cnk:=(n,k) -> add(mobius(n/d)*d, d in divisors(gcd(n,k)));
anmk:=(n,m,k)->(1/(n+m))*add( cnk(d,k)*binomial((n+m)/d,n/d), d in divisors(gcd(n,m))); # anmk(n,m,k) is the value of a_k(n,m) as in Theorem 1, Equation (4), of the Elashvili et al. 1999 reference.
r2:=(n,k)->[seq(anmk(n,m,k),m=1..10)];
for n from 1 to 10 do lprint(r2(n,1)); od:

rows = 12;
cnk[n_, k_] := Sum[MoebiusMu[n/d] d, {d , Divisors[GCD[n, k]]}];
anmk[n_, m_, k_] := (1/(n+m)) Sum[cnk[d, k] Binomial[(n+m)/d, n/d], {d, Divisors[GCD[n, m]]}];
r2[n_, k_] := Table[anmk[n, m, k], {m, 1, rows}];
T = Table[r2[n, 1], {n, 1, rows}];
Table[T[[n-k+1, k]], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 05 2018, from Maple *)

A185158 Triangular array read by rows: T(n,k) (n>=1, 0<=k<=n-1, except 0<=k<=1 when n=1) = coefficient of x^k in expansion of (1/n)Sum_{d|n} (mobius(d)(1+x^d)^(n/d)).

Original entry on oeis.org

1, 1, 0, 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

N. J. A. Sloane, Jan 23 2012

T(n,k) is the number of binary Lyndon words of length n containing k ones. - Joerg Arndt, Oct 21 2012

			The first few polynomials are:
1+x
x
x+x^2
x+x^2+x^3
x+2*x^2+2*x^3+x^4
x+2*x^2+3*x^3+2*x^4+x^5
x+3*x^2+5*x^3+5*x^4+3*x^5+x^6
...
The triangle begins:
[ 1]  1, 1,
[ 2]  0, 1,
[ 3]  0, 1, 1,
[ 4]  0, 1, 1, 1,
[ 5]  0, 1, 2, 2, 1,
[ 6]  0, 1, 2, 3, 2, 1,
[ 7]  0, 1, 3, 5, 5, 3, 1,
[ 8]  0, 1, 3, 7, 8, 7, 3, 1,
[ 9]  0, 1, 4, 9, 14, 14, 9, 4, 1,
[10]  0, 1, 4, 12, 20, 25, 20, 12, 4, 1,
[11]  0, 1, 5, 15, 30, 42, 42, 30, 15, 5, 1,
[12]  0, 1, 5, 18, 40, 66, 75, 66, 40, 18, 5, 1,
[13]  0, 1, 6, 22, 55, 99, 132, 132, 99, 55, 22, 6, 1,
[14]  0, 1, 6, 26, 70, 143, 212, 245, 212, 143, 70, 26, 6, 1
...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Joerg Arndt, Matters Computational (The Fxtbook), section 18.3.1 "Binary necklaces with fixed density", p. 382.
Romeo Meštrović, Different classes of binary necklaces and a combinatorial method for their enumerations, arXiv:1804.00992 [math.CO], 2018.
Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160. See Example 1.

Two other versions of this triangle are in A051168 and A092964.

with(numtheory);
W:=r->expand((1/r)*add(mobius(d)*(1+x^d)^(r/d), d in divisors(r)));
for n from 1 to 14 do
lprint(W(n));
od:
for n from 1 to 14 do
lprint(seriestolist(series(W(n),x,50)));
od:

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

p(n) = if(n<=0, n==0, 'a0 + 1/n * sumdiv(n, d, moebius(d)*(1+x^d)^(n/d) ));
/* print triangle: */
for (n=1,17, v=Vec( polrecip(Pol(p(n),x)) ); v[1]-='a0; print(v) );
/* Joerg Arndt, Oct 21 2012 */

T(n,k) = 1/n * sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d,k/d) );
/* print triangle: */
{ for (n=1, 17, for (k=0, max(1,n-1), print1(T(n,k),", "); ); print(); ); }
/* Joerg Arndt, Oct 21 2012 */

T(n,k) = 1/n * sum( d divides gcd(n,k), mu(d) * C(n/d,k/d) ). - Joerg Arndt, Oct 21 2012

The prime rows are given by (1+x)^p/p, rounding non-integer coefficients to 0, e.g., (1+x)^2/2 = .5 + x + .5 x^2 gives (0,1,0), row 2 below. - Tom Copeland, Oct 21 2014

A178574 a(n) = 2n(9*n-1).

Original entry on oeis.org

16, 68, 156, 280, 440, 636, 868, 1136, 1440, 1780, 2156, 2568, 3016, 3500, 4020, 4576, 5168, 5796, 6460, 7160, 7896, 8668, 9476, 10320, 11200, 12116, 13068, 14056, 15080, 16140, 17236, 18368, 19536, 20740, 21980, 23256, 24568, 25916, 27300, 28720, 30176, 31668, 33196, 34760, 36360

Offset: 1

Paul Weisenhorn, Dec 24 2010

Numbers with ordered partitions that have periods of length 6.

From each ordered partition of the numbers (15+j) with 0

The a(n) sequence begins with 16 and each member has 1 period; the b(n) sequence begins with 17 and each member has 2 periods; the c(n) sequence begins with 18 and each member has 3 periods; the d(n) sequence begins with 19 and each member has 2 periods; the e(n) sequence begins with 20 and each member has 1 period of length 6

			a(5) = 5*(18*5-2) = 440; b(5) = a(5) + 5 = 445; c(5) = a(5)*2*5 = 450; d(5) = a(5) + 3*5 = 455; e(5) = a(5) + 4*5 = 460.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A037306, A092964.

[2*n*(9*n-1): n in [1..50]]; // Vincenzo Librandi, Jul 10 2012

Table[2n(9n-1), {n,1,50}] (* Vincenzo Librandi, Jul 10 2012 *)
LinearRecurrence[{3,-3,1},{16,68,156},50] (* Harvey P. Dale, Feb 15 2016 *)

a(n)=2*n*(9*n-1) \\ Charles R Greathouse IV, Jun 17 2017

[2*n*(9*n-1) for n in (1..50)] # G. C. Greubel, Jan 30 2019

G.f. for a(n): (16 + 20*x)/(1-x)^3.
     for b(n): (17 + 19*x)/(1-x)^3.
     for c(n): (18 + 18*x)/(1-x)^3.
     for d(n): (19 + 17*x)/(1-x)^3.
     for e(n): (20 + 16*x)/(1-x)^3.
all sequences have the same recurrence:
  s(n+3) = 3*s(n+2) - 3*s(n+1) + s(n);
  with s(0) = 0, s(1) = 15 + j, s(2) = 66 + 2*j and 0a(n) = n*(18*n-2) = 4*A022266(n).
b(n) = n*(18*n-1) = a(n) + n.
c(n) = 18*n^2 = a(n) + 2*n.
d(n) = n*(18*n+1) = a(n) + 3*n.
e(n) = n*(18*n+2) = a(n) + 4*n.
The general formula for numbers with periods of length k: a(k,j,n) = n*(k^2*n - k + 2*j)/2 and 0  For j=1 and j=(k-1) the numbers have 1 period.
  For 1A092964(k-4,j-1) periods.
  G.f. (binomial(k,2)*(1+x) + j + (k-j)*x)/(1-x)^3.
E.g.f.: 2*exp(x)*x*(8 + 9*x). - Elmo R. Oliveira, Jan 28 2025

A183110 Period-length of the ultimate periodic behavior of the orbit of a list [1,1,1,...,1] of n 1's under the mapping defined in the comments.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 4, 4, 1, 5, 5, 5, 5, 1, 6, 6, 6, 6, 6, 1, 7, 7, 7, 7, 7, 7, 1, 8, 8, 8, 8, 8, 8, 8, 1, 9, 9, 9, 9, 9, 9, 9, 9, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 1, 13, 13

Offset: 1

John W. Layman, Feb 01 2011

We use the list mapping introduced in A092964, whereby one removes the first term of the list, z(1), and adds 1 to each of the next z(1) terms (appending 1's if necessary) to get a new list.

This is also conjectured to be the length of the longest cycle of pebble-moves among the partitions of n (cf. A201144). - Andrew V. Sutherland

			Under the indicated mapping the list [1,1,1,1,1,1,1] of seven 1's results in the orbit [1,1,1,1,1,1,1], [2,1,1,1,1,1], [2,2,1,1,1], [3,2,1,1], [3,2,2], [3,3,1], [4,2,1], [3,2,1,1], ... which is clearly periodic with period-length 4, so a(7) = 4.

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A037306, A092964, A178572, A178574.

f[p_] := Module[{pp, x, lpp, m, i}, pp = p; x = pp[[1]]; pp = Delete[pp,1]; lpp = Length[pp]; m = Min[x, lpp]; For[i = 1, i ≤ m, i++, pp[[i]]++]; For[i = 1, i ≤ x - lpp, i++, AppendTo[pp, 1]]; pp]; orb[p_] := Module[{s, v}, v = p; s = {v}; While[! MemberQ[s, v = f[v]], AppendTo[s, v]]; s]; attractor[p_] := Module[{orbp, pos, len, per}, orbp = orb[p]; pos = Flatten[Position[orbp, f[orbp[[-1]]]]][[1]] - 1; (*pos = steps to enter period*) len = Length[orbp] - pos; per = Take[orbp, -len]; Sort[per]]; a = {}; For[n = 1, n ≤ 80, n++, {rn = Table[1, {k, 1, n}]; orbn = orb[rn]; lenorb = Length[orbn]; lenattr = Length[attractor[rn]]; AppendTo[a, lenattr]}]; Print[a];

It appears, but has not yet been proved, that a(n)=1 if n=t(k) and a(n)=k if t(k-1) < n < t(k) where t(k) is the k-th triangular number t(k) = k*(k+1)/2.

A178572 Numbers with ordered partitions that have periods of length 5.

Original entry on oeis.org

11, 47, 108, 194, 305, 441, 602, 788, 999, 1235, 1496, 1782, 2093, 2429, 2790, 3176, 3587, 4023, 4484, 4970, 5481, 6017, 6578, 7164, 7775, 8411, 9072, 9758, 10469, 11205, 11966, 12752, 13563, 14399, 15260, 16146, 17057, 17993, 18954, 19940, 20951

Offset: 1

Paul Weisenhorn, Dec 24 2010

From each ordered partition of the numbers (10+j) with 0

The a(n) sequence begins with 11 and each member has 1 period; the b(n) = A022282(n) sequence begins with 12 and each member has 2 periods; the c(n) = A022283(n) sequence begins with 13 and each member has 2 periods; the d(n) = n*(25*n + 3)/2 sequence begins with 14 and each member has 1 period of length 5.

			For n=11 the period is [(4,3,2,1,1), (4,3,2,2), (4,3,3,1), (4,4,2,1), (5,3,2,1)].
For n=47 the period is [(9,8,7,6,6,4,3,2,1,1), (9,8,7,7,5,4,3,2,2), (9,8,8,6,5,4,3,3,1), (9,9,7,6,5,4,4,2,1), (10,8,7,6,5,5,3,2,1)].
For n=12 the 2 periods are [(4,3,2,2,1), (4,3,3,2), (4,4,3,1), (5,4,2,1), (5,3,2,1,1)] and [(4,3,3,1,1), (4,4,2,2), (5,3,3,1), (4,4,2,1,1), (5,3,2,2)].
For n=49 the 2 periods are [(9,8,7,7,6,4,3,2,2,1), (9,8,8,7,5,4,3,3,2), (9,9,8,6,5,4,4,3,1), (10,9,7,6,5,5,4,2,1), (10,8,7,6,6,5,3,2,1,1)] and [(9,8,8,6,6,4,3,3,1,1), (9,9,7,7,5,4,4,2,2),(10,8,8,6,5,5,3,3,1), (9,9,7,6,6,4,4,2,1,1), (10,8,7,7,5,5,3,2,2)].

G. C. Greubel, Table of n, a(n) for n = 1..1000
Amelia Carolina Sparavigna, The groupoid of the Triangular Numbers and the generation of related integer sequences, Politecnico di Torino, Italy (2019).
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A092964, A037306.

List([1..50], n -> n*(25*n-3)/2); # G. C. Greubel, Jan 30 2019

[n*(25*n-3)/2: n in [1..50]]; // G. C. Greubel, Jan 30 2019

LinearRecurrence[{3,-3,1},{11,47,108},50] (* Harvey P. Dale, Jan 14 2019 *)
Table[n*(25*n-3)/2, {n,1,50}] (* G. C. Greubel, Jan 30 2019 *)

a(n)=n*(25*n-3)/2 \\ Charles R Greathouse IV, Jun 18 2017

[n*(25*n-3)/2 for n in (1..50)] # G. C. Greubel, Jan 30 2019

G.f. for a(n): (11 + 14*x)/(1-x)^3.
     for b(n): (12 + 13*x)/(1-x)^3.
     for c(n): (13 + 12*x)/(1-x)^3.
     for d(n): (14 + 11*x)/(1-x)^3.
All sequences have the same recurrence
  s(n+3) = 3*s(n+2) - 3*s(n+1) + s(n)
  with s(0)=0, s(1) = 10 + j, s(2) = 45 + 2*j and 0s(n) = n*(25*n - 5 + 2*j)/2  and 0The general formula for numbers with periods of length k:  a(k,j,n) = n*(k^2*n - k + 2*j)/2 with 0  For j=1 and j=(k-1) the numbers have 1 period.
  For 1A092964(k-4,j-1) periods.
  G.f.: (binomial(k,2)*(1+x) + j + (k-j)*x)/(1-x)^3.

A184996 For each ordered partition of n with k numbers, remove 1 from each part and add the number k to get a new partition, until a partition is repeated. Among all ordered partitions of n, a(n) gives the maximum number of steps needed to reach a period.

Original entry on oeis.org

0, 1, 3, 5, 7, 8, 9, 11, 13, 15, 15, 16, 17, 22, 24, 24, 22, 23, 26, 33, 35, 35, 29, 30, 31, 38, 46, 48, 48, 41, 38, 39, 43, 52, 61, 63, 63, 55, 47, 48, 49, 58, 68, 78, 80, 80, 71, 62, 58, 59, 64, 75, 86, 97, 99, 99, 89, 79, 69, 70, 71, 82, 94, 106, 118, 120, 120, 109, 98, 87

Offset: 1

Paul Weisenhorn, Mar 28 2011

nonn

If one plays with p(n,n) unordered partitions, one gets the same number and length of periods.

If one removes the first part z(1) of each partition and adds 1 to the next z(1) parts to get a new partition, until a partition is repeated, one gets the same length and number of periods, playing with 2^(n-1) ordered or p(n,n) unordered partitions (A185700, A092964, A037306)

			For k=6: a(19)=26; a(20)=3; a(21)=35; a(22)=35; a(23)=29; a(24)=30; a(25)=31.
For n=4: (1+1+1+1)->(4)->(3+1)->(2+2)->(1+1+2)->(1+3)--> a(4)=5 steps.
For n=5: (1+1+1+1+1)->(5)->(4+1)->(3+2)->(2+1+2)->(1+1+3)->(2+3)->(1+2+2)--> a(5)=7 steps.

R. Baumann, Computer-Knobelei, LOGIN, 4 (1987), pages ?.
H. R. Halder and W. Heise, Einführung in Kombinatorik, Hanser Verlag, Munich, 1976, pp. 75ff.

Cf. A185700, A092964, A037306.

a((k^2+k-2)/2-j)=k^2-3-(k+1)*j with 0<=j<=(k-4) div 2 and 4<=k.
a((k^2+k+2)/2+j)=k^2-1-k*j with 0<=j<=(k-5) div 2 and 5<=k.
a((k^2+2*k-2+k mod 2)/2+j)=(k^2+4*k-2+k mod 2)/2+j with 0<=j<=2-k mod 2 and 4<=k.
a(T(k))=k^2-1 with 1<= k  for all triangular numbers T(k).

Partially edited by N. J. A. Sloane, Apr 08 2011

Showing 1-9 of 9 results.

cp's OEIS Frontend

A093210 Row sums of A092964.

Views

Author

Keywords

Formula

A051168 Triangular array T(h,k) for 0 <= k <= h read by rows: T(h,k) = number of binary Lyndon words with k ones and h-k zeros.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

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

A245558 Square array read by antidiagonals: T(n,k) = number of n-tuples of nonnegative integers (u_0,...,u_{n-1}) satisfying Sum_{j=0..n-1} j*u_j == 1 mod n and Sum_{j=0..n-1} u_j = m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A185158 Triangular array read by rows: T(n,k) (n>=1, 0<=k<=n-1, except 0<=k<=1 when n=1) = coefficient of x^k in expansion of (1/n)*Sum_{d|n} (mobius(d)*(1+x^d)^(n/d)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A178574 a(n) = 2*n*(9*n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A183110 Period-length of the ultimate periodic behavior of the orbit of a list [1,1,1,...,1] of n 1's under the mapping defined in the comments.

Views

Author

Keywords

Comments

Examples

Links

A185158 Triangular array read by rows: T(n,k) (n>=1, 0<=k<=n-1, except 0<=k<=1 when n=1) = coefficient of x^k in expansion of (1/n)Sum_{d|n} (mobius(d)(1+x^d)^(n/d)).

A178574 a(n) = 2n(9*n-1).