A074143 -id:A074143 - cp's OEIS frontend

A254040 Number T(n,k) of primitive (= aperiodic) n-bead necklaces with colored beads of exactly k different colors; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

1, 0, 1, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 9, 6, 0, 0, 6, 30, 48, 24, 0, 0, 9, 89, 260, 300, 120, 0, 0, 18, 258, 1200, 2400, 2160, 720, 0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040, 0, 0, 56, 2016, 20720, 92680, 211680, 258720, 161280, 40320

Offset: 0

Alois P. Heinz, Jan 23 2015

Turning over the necklaces is not allowed.

With other words: T(n,k) is the number of normal Lyndon words of length n and maximum k, where a finite sequence is normal if it spans an initial interval of positive integers. - Gus Wiseman, Dec 22 2017

			Triangle T(n,k) begins:
  1;
  0, 1;
  0, 0,  1;
  0, 0,  2,   2;
  0, 0,  3,   9,    6;
  0, 0,  6,  30,   48,    24;
  0, 0,  9,  89,  260,   300,   120;
  0, 0, 18, 258, 1200,  2400,  2160,   720;
  0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040;
  ...
The T(4,3) = 9 normal Lyndon words of length 4 with maximum 3 are: 1233, 1323, 1332, 1223, 1232, 1322, 1123, 1132, 1213. - _Gus Wiseman_, Dec 22 2017

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A063524, A001037 (for n>1), A056288, A056289, A056290, A056291, A254079, A254080, A254081, A254082.
Row sums give A060223.
Main diagonal and lower diagonal give: A000142, A074143.
T(2n,n) gives A254083.
Cf. A074650, A087854.
Cf. A000670, A000740, A008683, A019536, A059966, A185700, A296372, A296373, A296657.

with(numtheory):
b:= proc(n, k) option remember; `if`(n=0, 1,
      add(mobius(n/d)*k^d, d=divisors(n))/n)
    end:
T:= (n, k)-> add(b(n, k-j)*binomial(k,j)*(-1)^j, j=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[MoebiusMu[n/d]*k^d, {d, Divisors[n]}]/n]; T[n_, k_] := Sum[b[n, k-j]*Binomial[k, j]*(-1)^j, {j, 0, k}]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)
LyndonQ[q_]:=q==={}||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
allnorm[n_,k_]:=If[k===0,If[n===0,{{}}, {}],Join@@Permutations/@Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Select[Subsets[Range[n-1]+1],Length[#]===k-1&]];
Table[Length[Select[allnorm[n,k],LyndonQ]],{n,0,7},{k,0,n}] (* Gus Wiseman, Dec 22 2017 *)

T(n,k) = Sum_{j=0..k} (-1)^j * C(k,j) * A074650(n,k-j).

T(n,k) = Sum_{d|n} mu(d) * A087854(n/d, k) for n >= 1 and 1 <= k <= n. - Petros Hadjicostas, Aug 20 2019

A087854 Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 4, 9, 6, 1, 6, 30, 48, 24, 1, 12, 91, 260, 300, 120, 1, 18, 258, 1200, 2400, 2160, 720, 1, 34, 729, 5106, 15750, 23940, 17640, 5040, 1, 58, 2018, 20720, 92680, 211680, 258720, 161280, 40320, 1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880

Offset: 1

Philippe Deléham

Equivalently, T(n,k) is the number of sequences (words) of length n on an alphabet of k letters where each letter of the alphabet occurs at least once in the sequence. Two sequences are considered equivalent if one can be obtained from the other by a cyclic shift of the letters. Cf. A054631 where the surjective restriction is removed. - Geoffrey Critzer, Jun 18 2013

Robert A. Russell's g.f. for column k >= 1 (in the Formula section below) can be proved by integrating both sides of the formula Sum_{n>=1} S2(n, k)*x^(n-1) = x^(k-1)/((1 - x)* (1 - 2*x) * (1 - 3*x) * ... * (1 - k*x)) w.r.t. x. A variation of this identity (valid for |x| < 1/k) can be found in the Formula section of A008277. - Petros Hadjicostas, Aug 20 2019

			The triangle begins with T(1,1):
  1;
  1,   1;
  1,   2,    2;
  1,   4,    9,     6;
  1,   6,   30,    48,     24;
  1,  12,   91,   260,    300,     120;
  1,  18,  258,  1200,   2400,    2160,     720;
  1,  34,  729,  5106,  15750,   23940,   17640,    5040;
  1,  58, 2018, 20720,  92680,  211680,  258720,  161280,   40320;
  1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880;
  ...
For T(4,2) = 4, the necklaces are AAAB, AABB, ABAB, and ABBB.
For T(4,4) = 6, the necklaces are ABCD, ABDC, ACBD, ACDB, ADBC, and ADCB.

Alois P. Heinz, Rows n = 1..141, flattened

Columns 1-6: A057427, A052823, A056283, A056284, A056285, A056286.
Diagonals: A000142 and A074143.
Row sums: A019536.
Cf. A000010 (Euler totient phi function), A008277 (Stirling2 numbers), A075195 (table of Jablonski).
Cf. A254040, A273891.

with(numtheory):
T:= (n, k)-> (k!/n) *add(phi(d) *Stirling2(n/d, k), d=divisors(n)):
seq(seq(T(n,k), k=1..n), n=1..12);  # Alois P. Heinz, Jun 19 2013

Table[Table[Sum[EulerPhi[d]*StirlingS2[n/d,k]k!,{d,Divisors[n]}]/n,{k,1,n}],{n,1,10}]//Grid (* Geoffrey Critzer, Jun 18 2013 *)

T(n, k) = (k!/n) * sumdiv(n, d, eulerphi(d) * stirling(n/d, k, 2)); \\ Joerg Arndt, Sep 25 2020

T(n,k) = Sum_{i=0..k-1} (-1)^i * C(k,i) * A075195(n,k-i); A075195 = Jablonski's table.
T(n,k) = (k!/n) * Sum_{d|n} phi(d) * S2(n/d, k), where S2(n,k) = Stirling numbers of 2nd kind A008277.
G.f. for column k: -Sum_{d>0} (phi(d)/d) * Sum_{j = 1..k} (-1)^(k-j) * C(k,j) * log(1 - j * x^d). - Robert A. Russell, Sep 26 2018
T(n,k) = Sum_{d|n} A254040(d, k) for n, k >= 1. - Petros Hadjicostas, Aug 19 2019

Formula section edited by Petros Hadjicostas, Aug 20 2019

A082425 a(1)=1, a(n) = -1 + n*Sum_{j=1..n-1} a(j).

Original entry on oeis.org

1, 1, 5, 27, 169, 1217, 9939, 90871, 920069, 10222989, 123698167, 1619321459, 22805443881, 343835923129, 5525934478859, 94309281772527, 1703461402016269, 32465970250192421, 651123070017747999, 13707854105636799979, 302258183029291439537, 6966331456484621749329

Offset: 1

Benoit Cloitre, Apr 24 2003

nonn

G. C. Greubel, Table of n, a(n) for n = 1..445

Cf. A001339, A056543, A083746.

Cf. A007808, A074143, A082427, A082428, A082430, A383436, A383437.

[n le 2 select 1 else (n^2*Self(n-1) +1)/(n-1): n in [1..30]]; // G. C. Greubel, Feb 03 2024

a:= n -> n*n!*add(1/(k*(k-1)*k!), k = 2..n): seq(a(n), n = 2..20); # Peter Bala, Jul 09 2008

a[n_]:= a[n]= If[n<3, 1, -1 +n*Sum[a[j], {j,n-1}]];
Table[a[n], {n,40}] (* G. C. Greubel, Feb 03 2024 *)

@CachedFunction # a = A082425
def a(n): return 1 if (n==1) else -1 + n*sum(a(j) for j in range(1,n))
[a(n) for n in range(1,41)] # G. C. Greubel, Feb 03 2024

For n >= 2, a(n) = floor(n*(3-e)*n!).
a(n) = n*A056543(n) - 1, n > 1. - Vladeta Jovovic, Apr 26 2003
From Peter Bala, Jul 09 2008: (Start)
In the following remarks we use an offset of 1, i.e., a(1) = 1, a(2) = 1, a(3) = 5, ... .
  For n >= 2, a(n) = n*n!*Sum_{k = 2..n} 1/(k*(k-1)*k!).
  For n >= 2, a(n) = 3*n*n! - Sum_{k = 0..n} (k+1)!*binomial(n,k).
  Limit_{n -> oo} a(n)/(n*n!) = 3 - e.
  E.g.f.: 1 + t + (3*t - exp(t))/(1-t)^2.
  a(n) = A083746(n+2) - A001339(n).
Recurrence relation: a(1) = 1, a(2) = 1, a(3) = 5, a(n) = (n+2)*a(n-1) - (n-1)*a(n-2) for n >= 4.
Recurrence relation: a(1) = 1, a(2) = 1, a(n) = (n^2*a(n-1) + 1)/(n-1) for n >= 3.
The recurrence relation x(n) = (n^2*x(n-1) - 1)/(n-1), for n >= 2, has the general solution x(n) = n*n!*x(1) - a(n); particular solutions are A007808 (x(1) = 1) and A001339 (x(1) = 3). (End)

Offset corrected by G. C. Greubel, Feb 03 2024

A082430 a(1)=1; for n > 1, a(n) = n*(a(n-1) + a(n-2) + ... + a(2) + a(1)) + 4.

Original entry on oeis.org

1, 6, 25, 132, 824, 5932, 48444, 442916, 4484524, 49828044, 602919332, 7892762164, 111156400476, 1675896499484, 26934050884564, 459674468429892, 8302870086014924, 158242935756990316, 3173649989348528004, 66813683986284800084, 1473241731897579841852

Offset: 1

Benoit Cloitre, Apr 24 2003

nonn

More generally, if m is an integer and a(1)=1, a(n) = n*(a(n-1) + a(n-2) + ... + a(2) + a(1)) + m then a(n) has a closed form formula as a(n) = floor/ceiling(n*r(m)*n!) where r(m) = frac(e*m) + 0 or + 1/2 or -1/2 + integer. (See Example section.)

			r(10) = frac(10*e) + 1/2 + 2;
r(12) = frac(12*e) - 1/2 + 3;
r(15) = frac(15*e) + 3;
r(18) = frac(18*e) - 1/2 + 4.

Harvey P. Dale, Table of n, a(n) for n = 1..448

Cf. A007808, A074143, A082425, A082427, A082428, A383436, A383437.

Cf. A001339.

nxt[{n_,t_,a_}]:=Module[{c=t(n+1)+4},{n+1,t+c,c}]; NestList[nxt,{1,1,1},20][[;;,3]] (* Harvey P. Dale, Mar 28 2024 *)

For n >= 2, a(n) = ceiling(n*(19/2 - 4*e)*n!).
From Seiichi Manyama, Apr 27 2025: (Start)
E.g.f.: -4 - 3*x/2 + (-19*x/2 + 4*exp(x))/(1-x)^2.
a(n) = -19*n/2 * n! + 4 * Sum_{k=0..n} (k+1)! * binomial(n,k) for n > 1.
a(n) = (n^2 * a(n-1) - 4)/(n-1) for n > 2.
a(n) = (n+2) * a(n-1) - (n-1) * a(n-2) for n > 3. (End)

A082427 a(1)=1, a(n) = n * (Sum_{k=1..n-1} a(k)) - 2.

Original entry on oeis.org

1, 0, 1, 6, 38, 274, 2238, 20462, 207178, 2301978, 27853934, 364633318, 5135252562, 77423807858, 1244311197718, 21236244441054, 383579665216538, 7310577148832842, 146617686151591998, 3086688129507199958, 68061473255633759074, 1568654907415559018658

Offset: 1

Benoit Cloitre, Apr 24 2003

nonn

Cf. A007808, A074143, A082425, A082428, A082430, A383436, A383437.

Cf. A001339.

Join[{1},Table[Floor[n(11/2-2E)n!],{n,2,20}]] (* Harvey P. Dale, May 09 2013 *)

a(n) = floor(n*(11/2 - 2*e)*n!) for n >= 2.
a(n) = (n+2)*a(n-1) - (n-1)*a(n-2) for n>3. - Gary Detlefs, Jun 30 2024
From Seiichi Manyama, Apr 27 2025: (Start)
E.g.f.: 2 + 3*x/2 + (11*x/2 - 2*exp(x))/(1-x)^2.
a(n) = 11*n/2 * n! - 2 * Sum_{k=0..n} (k+1)! * binomial(n,k) for n > 1.
a(n) = (n^2 * a(n-1) + 2)/(n-1) for n > 2. (End)

Offset changed to 1 by Georg Fischer, May 15 2024

A082428 a(1) = 1; a(n) = 3 + n * Sum_{k=1..n-1} a(k).

Original entry on oeis.org

1, 5, 21, 111, 693, 4989, 40743, 372507, 3771633, 41907033, 507075099, 6638074023, 93486209157, 1409484384213, 22652427603423, 386601431098419, 6982988349215193, 133087542655630737, 2669144605482372003, 56192518010155200063, 1239045022123922161389, 28557037652760872672013

Offset: 1

Benoit Cloitre, Apr 24 2003

nonn

Cf. A007808, A074143, A082425, A082427, A082430, A383436, A383437.

Cf. A001339.

for n>=2 a(n) = ceiling(n*(3e-7)*n!).
From Seiichi Manyama, Apr 27 2025: (Start)
E.g.f.: -3 - x + (-7*x + 3*exp(x))/(1-x)^2.
a(n) = -7 * n * n! + 3 * Sum_{k=0..n} (k+1)! * binomial(n,k) for n > 1.
a(n) = (n^2 * a(n-1) - 3)/(n-1) for n > 2.
a(n) = (n+2) * a(n-1) - (n-1) * a(n-2) for n > 3. (End)

A383436 a(1) = 1; a(n) = 2 + n * Sum_{k=1..n-1} a(k).

Original entry on oeis.org

1, 4, 17, 90, 562, 4046, 33042, 302098, 3058742, 33986022, 411230866, 5383385882, 75816017838, 1143072268942, 18370804322282, 313528393766946, 5663106612415462, 107932149554271158, 2164639221616216002, 45571352034025600042, 1004848312350264480926, 23159361103691809941342

Offset: 1

Seiichi Manyama, Apr 27 2025

nonn

Cf. A007808, A074143, A082425, A082427, A082428, A082430, A383437.

Cf. A001339.

my(N=30, x='x+O('x^N)); Vec(serlaplace(-2-x/2+(-9*x/2+2*exp(x))/(1-x)^2))

E.g.f.: -2 - x/2 + (-9*x/2 + 2*exp(x))/(1-x)^2.
a(n) = -9*n/2 * n! + 2 * Sum_{k=0..n} (k+1)! * binomial(n,k) for n > 1.
a(n) = (n^2 * a(n-1) - 2)/(n-1) for n > 2.
a(n) = (n+2) * a(n-1) - (n-1) * a(n-2) for n > 3.

A383437 a(1) = 1; a(n) = 5 + n * Sum_{k=1..n-1} a(k).

Original entry on oeis.org

1, 7, 29, 153, 955, 6875, 56145, 513325, 5197415, 57749055, 698763565, 9147450305, 128826591795, 1942308614755, 31215674165705, 532747505761365, 9622751822814655, 183398328858349895, 3678155373214684005, 77434849962414400105, 1707438441671237522315

Offset: 1

Seiichi Manyama, Apr 27 2025

nonn

Cf. A007808, A074143, A082425, A082427, A082428, A082430, A383436.

Cf. A001339.

my(N=30, x='x+O('x^N)); Vec(serlaplace(-5-2*x+(-12*x+5*exp(x))/(1-x)^2))

E.g.f.: -5 - 2*x + (-12*x + 5*exp(x))/(1-x)^2.
a(n) = -12 * n * n! + 5 * Sum_{k=0..n} (k+1)! * binomial(n,k) for n > 1.
a(n) = (n^2 * a(n-1) - 5)/(n-1) for n > 2.
a(n) = (n+2) * a(n-1) - (n-1) * a(n-2) for n > 3.

A137268 Triangle T(n, k) = k! * (k+1)^(n-k), read by rows.

Original entry on oeis.org

1, 2, 2, 4, 6, 6, 8, 18, 24, 24, 16, 54, 96, 120, 120, 32, 162, 384, 600, 720, 720, 64, 486, 1536, 3000, 4320, 5040, 5040, 128, 1458, 6144, 15000, 25920, 35280, 40320, 40320, 256, 4374, 24576, 75000, 155520, 246960, 322560, 362880, 362880

Offset: 1

Roger L. Bagula, Mar 12 2008

Essentially the same as A104001.

			Triangle begins as:
    1;
    2,     2;
    4,     6,     6;
    8,    18,    24,     24;
   16,    54,    96,    120,    120;
   32,   162,   384,    600,    720,     720;
   64,   486,  1536,   3000,   4320,    5040,    5040;
  128,  1458,  6144,  15000,  25920,   35280,   40320,   40320;
  256,  4374, 24576,  75000, 155520,  246960,  322560,  362880,  362880;
  512, 13122, 98304, 375000, 933120, 1728720, 2580480, 3265920, 3628800, 3628800;

G. C. Greubel, Rows n = 1..50 of the triangle, flattened
Fan Chung and R. L. Graham, Primitive juggling sequences, Am. Math. Monthly 115 (3) (2008) 185-194.

Cf. A061711, A066319, A074143, A104001, A152684.

[Factorial(k)*(k+1)^(n-k): k in [1..n], n in [1..12]]; // G. C. Greubel, Nov 28 2022

T[n_, k_]:= k!*(k+1)^(n-k);
Table[T[n, k], {n, 12}, {k, n}]//Flatten

def A137268(n,k): return factorial(k)*(k+1)^(n-k)
flatten([[A137268(n,k) for k in range(1,n+1)] for n in range(14)]) # G. C. Greubel, Nov 28 2022

J(b, n) = (b+1)^(n-b)*b! if n > b, otherwise n! (notation of Chung and Graham).
From G. C. Greubel, Nov 28 2022: (Start)
T(n, k) = k! * (k+1)^(n-k).
T(n, n-2) = 2*A074143(n), n > 1.
T(2*n, n) = A152684(n).
T(2*n, n-1) = A061711(n).
T(2*n+1, n+1) = A066319(n). (End)

Edited by G. C. Greubel, Nov 28 2022

A095238 a(1) = 1, a(n) = n*(sum of all previous terms mod n).

Original entry on oeis.org

1, 2, 0, 12, 0, 18, 35, 32, 9, 90, 11, 72, 117, 98, 30, 240, 34, 162, 247, 200, 63, 462, 69, 288, 425, 338, 108, 756, 116, 450, 651, 512, 165, 1122, 175, 648, 925, 722, 234, 1560, 246, 882, 1247, 968, 315, 2070, 329, 1152, 1617, 1250, 408, 2652, 424, 1458, 2035

Offset: 1

Amarnath Murthy, Jun 15 2004

nonn

An open question is whether the sequence contains zeros except for the 3rd and the 5th number. I checked this up to a(10000), which happens to be 99990000. - Johan Claes, Jun 16 2004

			a(6) = 6*((1 + 2 + 0 + 12 + 0) mod 6) = 18.

Cf. A074143.

A095238:=proc(n) option remember; n*(add(A095238(i),i=1..n-1) mod n) end: A095238(1):=1: seq(A095238(n),n=1..100);

a[1] = 1; a[n_] := a[n] = n*Mod[Sum[a[i], {i, n - 1}], n]; Table[ a[n], {n, 55}] (* Robert G. Wilson v, Jun 16 2004 *)

a=vector(1000);a[1]=1;for(i=2,1000,a[i]=i*lift(Mod(sum(j=1,i-1,a[j]),i)))

Appears to satisfy a linear recurrence with characteristic polynomial (1+x)(1+x^3)^2(1-x^3)^3 (checked up to n = 10^4). - Ralf Stephan, Dec 04 2004

More terms from Alec Mihailovs (alec(AT)mihailovs.com), Robert G. Wilson v and Johan Claes, Jun 16 2004

cp's OEIS Frontend

A254040 Number T(n,k) of primitive (= aperiodic) n-bead necklaces with colored beads of exactly k different colors; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A087854 Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A082425 a(1)=1, a(n) = -1 + n*Sum_{j=1..n-1} a(j).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A082430 a(1)=1; for n > 1, a(n) = n*(a(n-1) + a(n-2) + ... + a(2) + a(1)) + 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A082427 a(1)=1, a(n) = n * (Sum_{k=1..n-1} a(k)) - 2.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

Extensions

A082428 a(1) = 1; a(n) = 3 + n * Sum_{k=1..n-1} a(k).

Views

Author

Keywords

Crossrefs

Formula

A383436 a(1) = 1; a(n) = 2 + n * Sum_{k=1..n-1} a(k).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A383437 a(1) = 1; a(n) = 5 + n * Sum_{k=1..n-1} a(k).

Views

Author

Keywords

Crossrefs

Programs