A007837 -id:A007837 - cp's OEIS frontend

A261531 Number of necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.

1, 1, 1, 2, 2, 4, 15, 25, 69, 254, 1799, 4039, 16828, 61751, 349831, 3485031, 10391139, 49433136, 240065255, 1282012987, 9167583734, 131550812011, 459677216341, 2707382738559, 14318807603110, 94084166753927, 601900541251447, 5894253303715375

Offset: 0

Alois P. Heinz, Aug 23 2015

nonn

			a(4) = 2: 0000, 0001.
a(5) = 4: 00000, 00001, 00011, 00101.
a(6) = 15: 000000, 000001, 000011, 000101, 000112, 000121, 000122, 001001, 001012, 001021, 001022, 001102, 001201, 001202, 010102.

Alois P. Heinz, Table of n, a(n) for n = 0..260
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]
Eric Weisstein's World of Mathematics, Necklace
Wikipedia, Necklace (combinatorics)
Index entries for sequences related to necklaces

Cf. A072605, A261599, A261600.

with(numtheory): with(combinat):
g:= l-> (n-> `if`(n=0, 1, add(phi(j)*multinomial(n/j,
        (l/j)[]), j=divisors(igcd(l[])))/n))(add(i, i=l)):
b:= proc(n, i, l) `if`(i*(i+1)/2n, 0, b(n-i, i-1, [l[], i]))))
    end:
a:= n-> b(n$2, []):
seq(a(n), n=0..35);

multinomial[n_, k_] := n!/Times @@ (k!);
g[l_] := Function[n, If[n==0, 1, Sum[EulerPhi[j]*multinomial[n/j, l/j], {j, Divisors[GCD @@ l]}]/n]][Total[l]];
b[n_, i_, l_] := If[i*(i+1)/2n, 0, b[n-i, i-1, Append[l, i]]]]];
a[n_] := b[n, n, {}];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Mar 21 2017, translated from Maple *)

a(n)={if(n==0, 1, my(p=prod(k=1, n, (1+x^k/k!) + O(x*x^n))); sumdiv(n, d, eulerphi(n/d)*d!*polcoeff(p, d))/n)} \\ Andrew Howroyd, Dec 21 2017

a(n) = (1/n) * Sum_{d | n} phi(n/d) * A007837(d) for n>0. - Andrew Howroyd, Apr 02 2017

A261599 Number of primitive (aperiodic, or Lyndon) necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.

Original entry on oeis.org

1, 1, 0, 1, 1, 3, 13, 24, 67, 252, 1795, 4038, 16812, 61750, 349806, 3485026, 10391070, 49433135, 240064988, 1282012986, 9167581934, 131550811985, 459677212302, 2707382738558, 14318807586215, 94084166753923, 601900541189696, 5894253303715121

Offset: 0

Alois P. Heinz, Aug 25 2015

nonn

			a(4) = 1: 0001.
a(5) = 3: 00001, 00011, 00101.
a(6) = 13: 000001, 000011, 000101, 000112, 000121, 000122, 001012, 001021, 001022, 001102, 001201, 001202, 010102.
a(7) = 24: 0000001, 0000011, 0000101, 0000111, 0000112, 0000121, 0000122, 0001001, 0001011, 0001012, 0001021, 0001022, 0001101, 0001102, 0001201, 0001202, 0010011, 0010012, 0010021, 0010022, 0010101, 0010102, 0010201, 0010202.

Alois P. Heinz, Table of n, a(n) for n = 0..300
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]
Eric Weisstein's World of Mathematics, Necklace
Wikipedia, Lyndon word
Wikipedia, Necklace (combinatorics)
Index entries for sequences related to necklaces

Cf. A007837, A261531, A261600.

with(numtheory):
b:= proc(n, i, g, d, j) option remember; `if`(i*(i+1)/20
       and gn, 0, binomial(n/j, i/j)*b(n-i, i-1, igcd(i, g), d, j))))
    end:
a:= n-> `if`(n=0, 1, add(add((f-> `if`(f=0, 0, f*b(n$2, 0, d, j)))(
                     mobius(j)), j=divisors(d)), d=divisors(n))/n):
seq(a(n), n=0..30);

a[0] = 1; a[n_] := With[{P = Product[1 + x^k/k!, {k, 1, n}] + O[x]^(n+1) // Normal}, DivisorSum[n, MoebiusMu[n/#]*#!*Coefficient[P, x, #]&]/n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 28 2018, after Andrew Howroyd *)

a(n)={if(n==0, 1, my(p=prod(k=1, n, (1+x^k/k!) + O(x*x^n))); sumdiv(n, d, moebius(n/d)*d!*polcoeff(p, d))/n)} \\ Andrew Howroyd, Dec 21 2017

a(n) = (1/n) * Sum_{d | n} moebius(n/d) * A007837(d) for n>0. - Andrew Howroyd, Dec 21 2017

A262078 Number T(n,k) of partitions of an n-set with distinct block sizes and maximal block size equal to k; triangle T(n,k), k>=0, k<=n<=k*(k+1)/2, read by columns.

Original entry on oeis.org

1, 1, 1, 3, 1, 4, 10, 60, 1, 5, 15, 140, 280, 1260, 12600, 1, 6, 21, 224, 630, 3780, 34650, 110880, 360360, 2522520, 37837800, 1, 7, 28, 336, 1050, 7392, 74844, 276276, 1513512, 9459450, 131171040, 428828400, 2058376320, 9777287520, 97772875200, 2053230379200

Offset: 0

Alois P. Heinz, Sep 10 2015

			Triangle T(n,k) begins:
: 1;
:    1;
:       1;
:       3,  1;
:           4,     1;
:          10,     5,    1;
:          60,    15,    6,    1;
:                140,   21,    7,   1;
:                280,  224,   28,   8,  1;
:               1260,  630,  336,  36,  9,  1;
:              12600, 3780, 1050, 480, 45, 10, 1;

Alois P. Heinz, Columns k = 0..36, flattened

Row sums give A007837.
Column sums give A262073.
Cf. A000217, A002024, A262071, A262072 (same read by rows).

b:= proc(n, i) option remember; `if`(i*(i+1)/2n, 0, binomial(n, i)*b(n-i, i-1))))
    end:
T:= (n, k)-> b(n, k) -`if`(k=0, 0, b(n, k-1)):
seq(seq(T(n, k), n=k..k*(k+1)/2), k=0..7);

b[n_, i_] := b[n, i] = If[i*(i+1)/2n, 0, Binomial[n, i]*b[n-i, i-1]]]]; T[n_, k_] :=  b[n, k] - If[k==0, 0, b[n, k-1]]; Table[T[n, k], {k, 0, 7}, {n, k, k*(k+1)/2}] // Flatten (* Jean-François Alcover, Dec 18 2016, after Alois P. Heinz *)

A326569 Number of covering antichains of subsets of {1..n} with no singletons and different edge-sizes.

Original entry on oeis.org

1, 0, 1, 1, 13, 121, 2566, 121199, 13254529

Offset: 0

Gus Wiseman, Jul 18 2019

An antichain is a finite set of finite sets, none of which is a subset of any other. It is covering if its union is {1..n}. The edge-sizes are the numbers of vertices in each edge, so for example the edge sizes of {{1,3},{2,5},{3,4,5}} are {2,2,3}.

			The a(2) = 1 through a(4) = 13 antichains:
  {{1,2}}  {{1,2,3}}  {{1,2,3,4}}
                      {{1,2},{1,3,4}}
                      {{1,2},{2,3,4}}
                      {{1,3},{1,2,4}}
                      {{1,3},{2,3,4}}
                      {{1,4},{1,2,3}}
                      {{1,4},{2,3,4}}
                      {{2,3},{1,2,4}}
                      {{2,3},{1,3,4}}
                      {{2,4},{1,2,3}}
                      {{2,4},{1,3,4}}
                      {{3,4},{1,2,3}}
                      {{3,4},{1,2,4}}

Antichain covers are A006126.
Set partitions with different block sizes are A007837.
The case with singletons is A326570.
Cf. A000372, A003182, A306021, A307249, A326565, A326571, A326572, A326573.

stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
cleq[n_]:=Select[stableSets[Subsets[Range[n],{2,n}],SubsetQ[#1,#2]||Length[#1]==Length[#2]&],Union@@#==Range[n]&];
Table[Length[cleq[n]],{n,0,6}]

a(n) = A326570(n) - n*a(n-1) for n > 0. - Andrew Howroyd, Aug 13 2019

a(8) from Andrew Howroyd, Aug 13 2019

A326570 Number of covering antichains of subsets of {1..n} with different edge-sizes.

Original entry on oeis.org

2, 1, 1, 4, 17, 186, 3292, 139161, 14224121

Offset: 0

Gus Wiseman, Jul 18 2019

An antichain is a finite set of finite sets, none of which is a subset of any other. It is covering if its union is {1..n}. The edge-sizes are the numbers of vertices in each edge, so for example the edge-sizes of {{1,3},{2,5},{3,4,5}} are {2,2,3}.

			The a(0) = 2 through a(4) = 17 antichains:
  {}    {{1}}  {{1,2}}  {{1,2,3}}    {{1,2,3,4}}
  {{}}                  {{1},{2,3}}  {{1},{2,3,4}}
                        {{2},{1,3}}  {{2},{1,3,4}}
                        {{3},{1,2}}  {{3},{1,2,4}}
                                     {{4},{1,2,3}}
                                     {{1,2},{1,3,4}}
                                     {{1,2},{2,3,4}}
                                     {{1,3},{1,2,4}}
                                     {{1,3},{2,3,4}}
                                     {{1,4},{1,2,3}}
                                     {{1,4},{2,3,4}}
                                     {{2,3},{1,2,4}}
                                     {{2,3},{1,3,4}}
                                     {{2,4},{1,2,3}}
                                     {{2,4},{1,3,4}}
                                     {{3,4},{1,2,3}}
                                     {{3,4},{1,2,4}}

Antichain covers are A006126.
Set partitions with different block sizes are A007837.
The case without singletons is A326569.
(Antichain) covers with equal edge-sizes are A306021.
Cf. A000372, A003182, A307249, A326026, A326514, A326566, A326572.

stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
cleq[n_]:=Select[stableSets[Subsets[Range[n]],SubsetQ[#1,#2]||Length[#1]==Length[#2]&],Union@@#==Range[n]&];
Table[Length[cleq[n]],{n,0,6}]

a(8) from Andrew Howroyd, Aug 13 2019

A347006 E.g.f.: Product_{k>=1} (1 + exp(x) * x^k / k!).

Original entry on oeis.org

1, 1, 3, 10, 43, 206, 1044, 5909, 38371, 272314, 1995208, 14869889, 115433344, 965259881, 8773348601, 84608514095, 837220780691, 8334354200226, 83498917650084, 855936118936073, 9180736840445788, 104439240481045949, 1253608634906635901

Offset: 0

Ilya Gutkovskiy, Aug 10 2021

a(n) is the number of words of length n over an infinite alphabet such that for any letter k appearing within a word, exactly k occurrences of that letter are marked. - John Tyler Rascoe, Jul 16 2025

			a(3) = 10 counts: (1#,1,1), (1,1#,1), (1,1,1#), (1#,2#,2#), (2#,1#,2#), (2#,2#,1#), (2#,2#,2), (2#,2,2#), (2,2#,2#), (3#,3#,3#). - _John Tyler Rascoe_, Jul 16 2025

Alois P. Heinz, Table of n, a(n) for n = 0..612 (first 101 terms from John Tyler Rascoe)

Cf. A007837, A265952, A305547, A347005.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1)+add(b(n-j, min(n-j, i-1))/i!/(j-i)!, j=i..n)))
    end:
a:= n-> n!*b(n$2):
seq(a(n), n=0..22);  # Alois P. Heinz, Jul 17 2025

nmax = 22; CoefficientList[Series[Product[(1 + Exp[x] x^k/k!), {k, 1, nmax}], {x, 0, nmax}], x] Range[0, nmax]!

C_x(N) = {my(x='x+O('x^(N+1))); Vec(serlaplace(prod(k=1,N, 1 + exp(x)*x^k/k!)))} \\ John Tyler Rascoe, Jul 16 2025

E.g.f.: exp( Sum_{k>=1} ( Sum_{d|k} (-1)^(d+1) * exp(d*x) / (d * ((k/d)!)^d) ) * x^k ).

E.g.f.: Product_{k>=1} (1 + Sum_{j>=k} binomial(j,k) * x^j / j!).

A364207 Number of partitions of [n] such that the minimal element of each block is also its size.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 3, 1, 0, 0, 60, 45, 53, 24, 7, 12601, 15120, 33390, 55710, 66522, 86037, 37907754, 63130067, 202203684, 511378789, 1421634137, 2566309603, 5855352202, 2064277450957, 4418631559288, 18485494082571, 61020702809287, 232959438927000, 783244248553960

Offset: 0

Alois P. Heinz, Jul 13 2023

nonn

The block sizes are distinct as a consequence of the definition.

There are A188431(n) different block size configurations for a given n. - John Tyler Rascoe, Jul 19 2023

			a(0) = 1: () the empty partition.
a(1) = 1: 1.
a(3) = 1: 1|23.
a(6) = 3: 1|24|356, 1|25|346, 1|26|345.
a(7) = 1: 1|23|4567.
a(10) = 60: 1|25|367|489(10), 1|25|368|479(10), 1|25|369|478(10), ..., 1|28|39(10)|4567, 1|29|38(10)|4567, 1|2(10)|389|4567.
a(14) = 7: 1|23|4568|79(10)(11)(12)(13)(14), 1|23|4569|78(10)(11)(12)(13)(14), 1|23|456(10)|789(11)(12)(13)(14), 1|23|456(11)|789(10)(12)(13)(14), 1|23|456(12)|789(10)(11)(13)(14), 1|23|456(13)|789(10)(11)(12)(14), 1|23|456(14)|789(10)(11)(12)(13).

Alois P. Heinz, Table of n, a(n) for n = 0..735
Wikipedia, Partition of a set

Cf. A000110, A007837, A188431, A326493, A327711, A364406.

b:= proc(n, i) option remember; `if`(i*(i+1)/2n or i>n-i+1, 0, b(n-i, i-1)*binomial(n-i, i-1))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..33);  # Alois P. Heinz, Jul 22 2023

b[n_, i_] := b[n, i] = If[i(i+1)/2 < n, 0, If[n == 0, 1, b[n, i-1] + If[i > n || i > n-i+1, 0, b[n-i, i-1]*Binomial[n-i, i-1]]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 33}] (* Jean-François Alcover, Oct 20 2023, after Alois P. Heinz *)

A386576 Number of anti-runs of length n covering an initial interval of positive integers with strictly decreasing multiplicities.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 10, 4, 14, 84, 1136, 967, 3342, 12823, 101762, 1769580

Offset: 0

Gus Wiseman, Aug 03 2025

An anti-run is a sequence with no adjacent equal terms.

			The a(7) = 4 anti-runs are:
  (1,2,1,2,1,2,1)
  (1,2,1,2,1,3,1)
  (1,2,1,3,1,2,1)
  (1,3,1,2,1,2,1)

For any multiplicities we have A005649.
For weakly instead of strictly decreasing multiplicities we have A321688.
A003242 and A335452 count anti-runs, ranks A333489.
A005651 counts ordered set partitions with weakly decreasing sizes, strict A007837.
A032020 counts strict anti-run compositions.
A325534 counts separable multisets, ranks A335433.
A325535 counts inseparable multisets, ranks A335448.
A336103 counts normal separable multisets, inseparable A336102.
A386583 counts separable partitions by length, inseparable A386584.
A386585 counts partitions of separable type by length, sums A336106, ranks A335127.
A386586 counts partitions of inseparable type by length, sums A025065, ranks A335126.
A386633 counts separable set partitions, row sums of A386635.
A386634 counts inseparable set partitions, row sums of A386636.
Cf. A000670, A019472, A106351, A238130, A335125, A335516, A386580, A386581.

seps[ptn_,fir_]:=If[Total[ptn]==1,{{fir}},Join@@Table[Prepend[#,fir]&/@seps[MapAt[#-1&,ptn,fir],nex],{nex,Select[DeleteCases[Range[Length[ptn]],fir],ptn[[#]]>0&]}]];
seps[ptn_]:=If[Total[ptn]==0,{{}},Join@@(seps[ptn,#]&/@Range[Length[ptn]])];
Table[Sum[Length[seps[y]],{y,Select[IntegerPartitions[n],UnsameQ@@#&]}],{n,0,10}]

A127007 a(n) = number of n-digit terms in A108571.

Original entry on oeis.org

1, 1, 4, 5, 16, 82, 169, 541, 2272, 17965, 44407, 201751, 801515, 4890886, 52218595, 165519640, 835947970, 4290442728, 24096524166, 179566203960, 2739764737710, 9938147178960, 60997160143920, 331360222255920, 2154105076695000

Offset: 1

Zak Seidov, Jan 02 2007

First 9 terms coincide with terms in A007837. Sum of all 45 terms gives the total number of terms in A108571: 66712890763701234740813164553708284.

Zak Seidov, Table of n, a(n) for n = 1..45.

Cf. A007837, A108571.

a[n_, w_:{0}] := If[n == 0, Total[w]!/Times @@ (w!), Sum[a[n-k, Append[w, k]], {k, 1 + Last@w, Min[9, n]}]]; Array[a, 45] (* Giovanni Resta, May 19 2013 *)

A182928 Triangular array read by rows: [T(n,k),k=1..tau(n)] = [-n!/(d*(-(n/d)!)^d), d|n].

Original entry on oeis.org

1, 1, -1, 1, 2, 1, -3, -6, 1, 24, 1, -10, 30, -120, 1, 720, 1, -35, -630, -5040, 1, 560, 40320, 1, -126, 22680, -362880, 1, 3628800, 1, -462, 11550, -92400, -1247400, -39916800, 1, 479001600, 1, -1716, 97297200, -6227020800

Offset: 1

Peter Luschny, Apr 13 2011

The number of terms in the n-th row is the number of divisors of n. The n-th row is (apart from sign) a subsequence of the column labeled "M_1" for n-1 in Abramowitz and Stegun, Handbook, p. 831.
Let s(n) be the sum of row n. The number of partitions of an n-set with distinct block sizes can be computed recursively as A007837(0) = 1 and A007837(n) = - Sum_{1<=k<=n} binomial(n-1,k-1)*s(k)*A007837(n-k).
Let t(n) be the sum of the absolute values of row n. The sum of multinomial coefficients can be computed recursively as A005651(0) = 1 and A005651(n) = Sum_{1<=k<=n} binomial(n-1,k-1)*t(k)*A005651(n-k).

			The array starts with
[1] 1,
[2] 1,  -1,
[3] 1,   2,
[4] 1,  -3,   -6,
[5] 1,  24,
[6] 1, -10,   30,  -120,
[7] 1, 720,
[8] 1, -35,  -630, -5040,
[9] 1, 560, 40320,

Cf. A076901, A132958, A132959, A132960, A132962.

A182928_row := proc(n) local d;
seq(-n!/(d*(-(n/d)!)^d), d = numtheory[divisors](n)) end:

row[n_] := Table[ -n!/(d*(-(n/d)!)^d), {d, Divisors[n]}]; Table[row[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Jul 29 2013 *)

cp's OEIS Frontend

A261531 Number of necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A261599 Number of primitive (aperiodic, or Lyndon) necklaces with n beads of unlabeled colors such that the numbers of beads per color are distinct.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A262078 Number T(n,k) of partitions of an n-set with distinct block sizes and maximal block size equal to k; triangle T(n,k), k>=0, k<=n<=k*(k+1)/2, read by columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A326569 Number of covering antichains of subsets of {1..n} with no singletons and different edge-sizes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A326570 Number of covering antichains of subsets of {1..n} with different edge-sizes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A347006 E.g.f.: Product_{k>=1} (1 + exp(x) * x^k / k!).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A364207 Number of partitions of [n] such that the minimal element of each block is also its size.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica