A005840 -id:A005840 - cp's OEIS frontend

A016031 De Bruijn's sequence: 2^(2^(n-1) - n): number of ways of arranging 2^n bits in circle so all 2^n consecutive strings of length n are distinct.

1, 1, 2, 16, 2048, 67108864, 144115188075855872, 1329227995784915872903807060280344576, 226156424291633194186662080095093570025917938800079226639565593765455331328

Offset: 1

N. J. A. Sloane, Robert G. Wilson v

Sequence corresponds also to the largest number that may be determined by asking no more than 2^(n-1) - 1 questions("Yes"-or-"No" answerable) with lying allowed at most once. - Lekraj Beedassy, Jul 15 2002
Number of Ouroborean rings for binary n-tuplets. - Lekraj Beedassy, May 06 2004
Also the number of games of Nim that are wins for the second player when the starting position is either the empty heap or heaps of sizes 1 <= t_1 < t_2 < ... < t_k < 2^(n-1) (if n is 1, the only starting position is the empty heap). E.g.: a(4) = 16: the winning positions for the second player when all the heap sizes are different and less than 2^3: (4,5,6,7), (3,5,6), (3,4,7), (2,5,7), (2,4,6), (2,3,6,7), (2,3,4,5), (1,6,7), (1,4,5), (1,3,5,7), (1,3,4,6), (1,2,5,6), (1,2,4,7), (1,2,3), (1,2,3,4,5,6,7) and the empty heap. - Kennan Shelton (kennan.shelton(AT)gmail.com), Apr 14 2006
a(n + 1) = 2^(2^n-n-1) = 2^A000295(n) is also the number of set-systems on n vertices with no singletons. The case with singletons is A058891. The unlabeled case is A317794. The spanning/covering case is A323816. The antichain case is A006126. The connected case is A323817. The uniform case is A306021(n) - 1. The graphical case is A006125. The chain case is A005840. - Gus Wiseman, Feb 01 2019
Named after the Dutch mathematician Nicolaas Govert de Bruijn (1918-2012). - Amiram Eldar, Jun 20 2021

Jonathan L. Gross and Jay Yellen, eds., Handbook of Graph Theory, CRC Press, 2004, p. 255.
Frank Harary and Edgar M. Palmer, Graphical Enumeration, 1973, p. 31.
D. J. Newman, "A variation of the Game of Twenty Question", in: Murray S. Klamkin (ed.), Problems in Applied Mathematics, Philadelphia, PA: SIAM, 1990, Problem 66-20, pp. 121-122.
Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.6.15.
Ian Stewart, Game, Set and Math, pp. 50, Penguin 1991.

Vincenzo Librandi, Table of n, a(n) for n = 1..12
CombOS - Combinatorial Object Server, Generate de Bruijn sequences.
Robert Erra, Nik Lygeros and Nigel Stewart, On Minimal Strings Containing the Elements of S(n) by Decimation, Proceedings AA (DM-CCG), 2001, Section 5.4.
Loïc Foissy, Hopf algebraic structures on hypergraphs and multi-complexes, arXiv:2304.00810 [math.CO], 2023.
Francisco J. Muñoz and Juan Carlos Nuño, Rule-based Generation of de Bruijn Sequences: Memory and Learning, arXiv:2507.09764 [cs.FL], 2025. See p. 9.
Wikipedia, De Bruijn sequence.

Cf. A000295, A003465, A006125, A058891 (set systems), A317794 (unlabeled case), A323816 (spanning case), A323817 (connected case), A331691 (alternating signs).

[2^(2^(n-1)-n): n in [1..10]]; // Vincenzo Librandi, Aug 09 2017

Table[2^(2^(n - 1) - n), {n, 20}] (* Vincenzo Librandi, Aug 09 2017 *)

a(n) = 2^A000295(n-1). - Lekraj Beedassy, Jan 17 2007

Shifting once to the left gives the binomial transform of A323816. - Gus Wiseman, Feb 01 2019

A053525 Expansion of e.g.f.: (1-x)/(2-exp(x)).

Original entry on oeis.org

1, 0, 1, 4, 23, 166, 1437, 14512, 167491, 2174746, 31374953, 497909380, 8619976719, 161667969646, 3265326093109, 70663046421208, 1631123626335707, 40004637435452866, 1038860856732399105, 28476428717448349996, 821656049857815980455

Offset: 0

N. J. A. Sloane, Jan 15 2000

The number of connected labeled threshold graphs on n vertices. - Sam Spiro, Sep 22 2019

Also the number of 2-interval parking functions of size n. - Sam Spiro, Sep 24 2019

			G.f. = 1 + x^2 + 4*x^3 + 23*x^4 + 166*x^5 + 1437*x^6 + 14512*x^7 + ...

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.4(a).

T. D. Noe, Table of n, a(n) for n = 0..100
Jean-Christophe Aval, Adrien Boussicault, and Philippe Nadeau, Tree-like Tableaux, Electronic Journal of Combinatorics, 20(4), 2013, #P34.
Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Math. 205 (1999), 97-117. See Th. 6.3.
Sam Spiro, Counting Threshold Graphs with Eulerian Numbers, arXiv:1909.06518 [math.CO], 2019.
Sam Spiro, Subset Parking Functions, arXiv:1909.10109 [math.CO], 2019.

Cf. A000670, A005840, A052882.

m:=25; R:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( (1-x)/(2-Exp(x)) )); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, Mar 15 2019

A053525 := proc(n) option remember;
`if`(n < 2, 1 - n, add(binomial(n, k) * A053525(k), k = 0..n-1)) end:
seq(A053525(n), n = 0..20); # Peter Luschny, Oct 24 2021

With[{nn=20},CoefficientList[Series[(1-x)/(2-Exp[x]),{x,0,nn}], x] Range[0,nn]!] (* Harvey P. Dale, May 17 2012 *)

{a(n) = if( n<0, 0, n! * polcoeff( (1 - x) / (2 - exp(x + x*O(x^n))), n))}; /* Michael Somos, Aug 01 2016 */

m = 25; T = taylor((1-x)/(2-exp(x)), x, 0, m); [factorial(n)*T.coefficient(x, n) for n in (0..m)] # G. C. Greubel, Mar 15 2019

a(n) = c(n) - n*c(n-1) where c() = A000670.
a(n) ~ n!/2 * (1-log(2))/(log(2))^(n+1). - Vaclav Kotesovec, Dec 08 2012
Binomial transform is A005840. - Michael Somos, Aug 01 2016
a(n) = Sum_{k=0..n-1} binomial(n, k) * a(k), n>1. - Michael Somos, Aug 01 2016
a(n) = A005840(n) / 2, n>1. - Michael Somos, Aug 01 2016
E.g.f. A(x) satisfies (1 - x) * A'(x) = A(x) * (x - 2 + 2*A(x)). - Michael Somos, Aug 01 2016
a(n) = Sum_{k=1..n-1} (n-k)*A008292(n-1,k-1)*2^(k-1), valid for n>=2. - Sam Spiro, Sep 22 2019

A005612 Number of Boolean functions of n variables that are variously called "unate cascades" or "1-decision list functions" or "read-once threshold functions".

Original entry on oeis.org

2, 8, 64, 736, 10624, 183936, 3715072, 85755392, 2226939904, 64255903744, 2039436820480, 70614849282048, 2648768014680064, 106998205418995712, 4630973410260287488, 213794635951073787904, 10486975675879356104704

Offset: 1

N. J. A. Sloane

Several other characterizations are given in the paper by Eitel et al.

These functions are the Boolean functions with the nice property that all of their projections are "canalizing" or "single-faced": that is, f is constant on half of the n-cube and on the other half it recursively satisfies the same constraint.

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

Herman Jamke and Robert Israel, Table of n, a(n) for n = 1..350 (n = 1..22 from Herman Jamke)
E. A. Bender and J. T. Butler, Asymptotic approximations for the number of fanout-free functions, IEEE Trans. Computers, 27 (1978), 1180-1183. (Annotated scanned copy)
Aniruddha Biswas and Palash Sarkar, Counting unate and balanced monotone Boolean functions, arXiv:2304.14069 [math.CO], 2023.
J. T. Butler, Letter to N. J. A. Sloane, Dec. 1978.
Thomas Eiter, Toshihide Ibaraki and Kazuhisa Makino, Decision lists and related Boolean functions, Theoretical Computer Science 270 (2002), 493-524.
A. S. Jarraha, B. Raposab and R. Laubenbachera, Nested canalyzing, unate cascade and polynomial functions, Physica D: Nonlinear Phenomena Volume 233, Issue 2, 15 September 2007, 167-174.
T. Sasao and K. Kinoshita, On the Number of Fanout-Free Functions and Unate Cascade Functions, IEEE Transactions on Computers, Volume C-28, Issue 1 (1979), 66-72.
Index entries for sequences related to Boolean functions

See also sequence A005840, which is A005612 divided by 2^n. These are the monotone functions of the kind enumerated in the present sequence.

egf:= (2-4*x)/(2-exp(2*x))+2*x-2:
S:=series(egf,x,31):
seq(j! *coeff(S,x,j), j=1..30); # Robert Israel, Jul 07 2015

p[0] = 1; p[n_] := p[n] = Sum[Binomial[n, k]*p[n-k], {k, 1, n}]; a[n_] := a[n] = 2^(n+1)*(p[n] - n*p[n-1]); a[1] = 2; Table[a[n], {n, 1, 17}] (* Jean-François Alcover, Aug 01 2011, after formula *)

a(n)=if(n<0, 0, n!*polcoeff(subst((2-4*y)/(2-exp(2*y))+2*y-2, y, x+x*O(x^n)), n)) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008

When n > 1, the number is 2^{n+1}(P_n-nP_{n-1}), where P_n is the number of weak orders (preferential arrangements), sequence A000670. For example, when n=4 we have 736 = 32 times (75 - 4*13).
Bender and Butler give the e.g.f. 2(x+e^{-2x}-1)/(1-2e^{-2x}), which can easily be simplified to (2-4x)/(2-e^(2x))+2x-2.
a(n) ~ n! * (1 - log(2)) * 2^n / (log(2))^(n+1). - Vaclav Kotesovec, Nov 27 2017

Better description, comments, formulas and a new reference from Don Knuth, Sep 22 2007

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 23 2008

A051045 Number of distinct resistances possible for n resistors with resistances 1, 2, ..., n, each connected in series or parallel to the previous one.

Original entry on oeis.org

1, 2, 8, 44, 298, 2350, 22774, 252079, 3154451

Offset: 1

Eric W. Weisstein

For n = 4, there would be an additional 4 possible values if circuits were allowed that combine complex subcircuits in series or parallel, rather than requiring that one of them consists of a single resistor. See illustration in links. - Kival Ngaokrajang, Aug 22 2013 (rephrased by Dave R.M. Langers, Nov 13 2013)

Sean A. Irvine, Java program (github)
Kival Ngaokrajang, Illustration for n = 4
Eric Weisstein's World of Mathematics, Resistor Network.
Index to sequences related to resistances.

Cf. A005840.

Offset corrected and a(8)-a(9) from Sean A. Irvine, Aug 23 2021

A376544 a(n) is the number of singleton commuting ordered set partitions.

Original entry on oeis.org

1, 1, 2, 8, 40, 242, 1784, 15374, 151008, 1669010, 20503768, 277049126, 4083693200, 65211041690, 1121435565384, 20662801363790, 406100030507200, 8480197575505442, 187500501495191480, 4376026842424336886, 107506303414618515696, 2773174380946415844266

Offset: 0

Raul Penaguiao, Sep 27 2024

nonn

a(n) is also the dimension of the span of chromatic quasi-symmetric invariants of generalized permutahedra.

			a(2) = 2 because the ordered set partitions 1|2 and 2|1 are counted only once.
a(3) = 8, all ordered set partitions with length 3 (e.g. 1|2|3) are counted only once.
a(4) = 40 counts 1|34|2 separately to 2|34|1, but treats 1|2|34 as the same as 2|1|34 since only adjacent singletons can commute.

Alois P. Heinz, Table of n, a(n) for n = 0..435
Vladimir Grujić, Counting faces of graphical zonotopes, Ars Math. Contemp., 13(1), 2017; arXiv preprint, arXiv:1604.06931 [math.CO], 2017.
Raul Penaguiao, The kernel of chromatic quasisymmetric functions on graphs and hypergraphic polytopes, Journal of Combinatorial Theory, Series A, 175, 105258, 2020.

Corresponds to a subset of elements counted in A000670.

Cf. A005840, A113059, A307389, A358623.

b:= proc(n, p) option remember; `if`(n=0, 1/p!, add(
      b(n-j, 0)*binomial(n, j)/p!, j=2..n)+b(n-1, p+1)*n)
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..21);  # Alois P. Heinz, Nov 19 2024

\\ here B(n,k) is A008299 or A358623.
B(n, k) = {sum(i=0, k, (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) ); }
a(n)={sum(k=0, n, binomial(n,k)*sum(j=0, k\2, B(k,j)*j!*(j+1)^(n-k)))} \\ Andrew Howroyd, Sep 27 2024

seq(n)=my(g=exp(x + O(x*x^n))); Vec(serlaplace(g/(1 - g*(g-x-1)))) \\ Andrew Howroyd, Sep 27 2024

Asymptotic growth: a(n) = n! * b^(-n) * c, where b is the unique positive root of exp(2*x) = 1 + e^x + x*e^x, and c is 0.722487... .
From Andrew Howroyd, Sep 27 2024: (Start)
a(n) = Sum_{k=0..n} Sum_{j=0..floor(k/2)} binomial(n,k)*A358623(k,j)*j!*(j+1)^(n-k).
E.g.f.: exp(x)/(1 - exp(x)*(exp(x)-x-1)). (End)
In the notation above, c = 1/(b*(2*exp(b) - b - 2)). - Vaclav Kotesovec, Nov 21 2024

a(10) onwards from Andrew Howroyd, Sep 27 2024

A123750 Number of distinct resistances possible with at most n arbitrary resistors connected in series or in parallel.

Original entry on oeis.org

1, 4, 17, 94, 667, 5752, 58053, 669970, 8698991, 125499820, 1991637529, 34479906886, 646671878595, 13061304372448, 282652185684845, 6524494505342842, 160018549741811479, 4155443426929596436, 113905714869793400001, 3286624199431263921838

Offset: 1

I. N. Galidakis (jgal(AT)ath.forthnet.gr), Nov 28 2006

The difference between this problem and A005840 and A051045 is the word "at most". In this problem, at most n different resistors are used to generate all possible resistances using in series and in parallel wirings, also including resistances where some of the resistors from the collection 1,2,...,n, are not used.

Cf. A005840, A051045.

a:= n-> n!* coeff(series(exp(x)*(-2*exp(x) +
            exp(x)*x + 2)/(-2 + exp(x)), x, n+1),x,n):
seq(a(n), n=1..25);

a(n) = 2 * A005840(n) + n - 2, n > 1.

E.g.f.: exp(x)*(-2*exp(x) + exp(x)*x + 2)/(-2 + exp(x)).

A232005 Number of distinct resistances that can be produced from a circuit of resistors with resistances 1, 2, ..., n using only series and parallel combinations.

Original entry on oeis.org

1, 2, 8, 48, 386, 3781, 49475, 762869, 13554897, 266817541

Offset: 1

Dave R.M. Langers, Nov 16 2013

Found by exhaustive search: all configurations of resistors were enumerated, resistances calculated, sorted, and distinct values counted.
This sequence allows any circuits to be combined in series or in parallel (akin A000084); A051045 requires circuits to be combined with a single resistor at a time.
This sequence regards circuits as distinct only if their resistance is different; A006351 regards circuits distinct if their configuration is different, although some may have the same resistance.
This sequence considers resistors with contiguous resistances 1, 2, ..., n; A005840 considers arbitrarily different resistors, while A048211 considers n equal resistances.

			a(2) = 2 since given a 1-ohm and a 2-ohm resistor, a series circuit yields 3 ohms, while a parallel circuit yields 2/3 ohms, which thus yields two distinct resistances.

Cf. A005840, A006352, A048211, A051045.

A348436 Triangle read by rows. T(n,k) is the number of labeled threshold graphs on n vertices with k components, for 1 <= k <= n.

Original entry on oeis.org

1, 1, 1, 4, 3, 1, 23, 16, 6, 1, 166, 115, 40, 10, 1, 1437, 996, 345, 80, 15, 1, 14512, 10059, 3486, 805, 140, 21, 1, 167491, 116096, 40236, 9296, 1610, 224, 28, 1, 2174746, 1507419, 522432, 120708, 20916, 2898, 336, 36, 1, 31374953, 21747460, 7537095, 1741440, 301770, 41832, 4830, 480, 45, 1

Offset: 1

David Galvin, Oct 18 2021

The class of threshold graphs is the smallest class of graphs that includes K1 and is closed under adding isolated vertices and dominating vertices.

			Triangle begins:
         1;
         1,        1;
         4,        3,       1;
        23,       16,       6,       1;
       166,      115,      40,      10,      1;
      1437,      996,     345,      80,     15,     1;
     14512,    10059,    3486,     805,    140,    21,    1;
    167491,   116096,   40236,    9296,   1610,   224,   28,   1;
   2174746,  1507419,  522432,  120708,  20916,  2898,  336,  36,  1;
  31374953, 21747460, 7537095, 1741440, 301770, 41832, 4830, 480, 45, 1;
...

D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.
Sam Spiro, Counting Threshold Graphs with Eulerian Numbers, arXiv:1909.06518 [math.CO], 2019.

Cf. A005840 (row sums), A317057 (column k=1), A053525.

T := (n, k) -> `if`(n = k, 1, binomial(n, k-1)*A053525(n-k+1)):
for n from 1 to 10 do seq(T(n, k), k=1..n) od; # Peter Luschny, Oct 24 2021

eulerian[0, 0] := 1; eulerian[n_, m_] := eulerian[n, m] =
Sum[((-1)^k)*Binomial[n + 1, k]*((m + 1 - k)^n), {k, 0, m + 1}];
(* t[n] counts the labeled threshold graphs on n vertices *)
t[0] = 1; t[1] = 1;
t[n_] := t[n] = Sum[(n - k)*eulerian[n - 1, k - 1]*(2^k), {k, 1, n - 1}];
T[1, 1] := 1; T[n_, 1] := T[n, 1] = (1/2)*t[n]; T[n_, n_] := T[n, n] = 1;
T[n_, k_] := T[n, k] = Binomial[n, k - 1]*T[n - k + 1, 1];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten

T(1,1) = 1; for n >= 2, T(n,1) = A005840(n)/2; for n >= 3 and 2 <= k <= n-1, T(n,k) = binomial(n,k-1)*T(n-k+1,1); and for n >= 2, T(n,n)=1.

T(n, k) = binomial(n, k-1)*A053525(n - k + 1) if k != n, otherwise 1. - Peter Luschny, Oct 24 2021

A350060 Triangle read by rows: T(n,k) is the number of labeled threshold graphs on vertex set [n] in which k dominating vertices are added in standard iterative construction, n >= 1 and 0 <= k <= n-1.

Original entry on oeis.org

1, 1, 1, 1, 6, 1, 1, 22, 22, 1, 1, 65, 200, 65, 1, 1, 171, 1265, 1265, 171, 1, 1, 420, 6566, 15050, 6566, 420, 1, 1, 988, 30156, 136346, 136346, 30156, 988, 1, 1, 2259, 127632, 1039878, 2009952, 1039878, 127632, 2259, 1

Offset: 1

David Galvin, Dec 11 2021

Threshold graphs are constructed from a single vertex by iteratively adding isolated vertices (adjacent to nothing previously added) and dominating vertices (adjacent to everything previously added). The initial vertex is not considered to be a dominating vertex.

			Triangle begins:
  1;
  1,     1;
  1,     6,      1;
  1,    22,     22,       1;
  1,    65,    200,      65,       1;
  1,   171,   1265,    1265,     171,       1;
  1,   420,   6566,   15050,    6566,     420,      1;
  1,   988,  30156,  136346,  136346,   30156,    988,    1;
  1,  2259, 127632, 1039878, 2009952, 1039878, 127632,  2259,  1;
  ...

D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.

Row sums are A005840.

Cf. A348576.

eulerian[n_,m_] := eulerian[n,m] =
  Sum[((-1)^k)*Binomial[n+1,k]*((m+1-k)^n), {k,0,m+1}] (* eulerian[n, m] is an Eulerian number, counting the permutations of [n] with m descents *);
op2[n_,k_] := op2[n,k] =
   Sum[(n-j)*eulerian[n-1,j-1]*Binomial[j-1,n-k-1], {j,1,n-1}] (* op2[n,k] counts ordered partitions of [n] with k parts, with first part having size at least 2 *);
T[n_, 0] := T[n, 0] = 1; T[2, 1] = 1; T[2, k_] := T[2, k] = 0;
T[n_, k_] :=
T[n, k] =
  Sum[Binomial[n, k + 1]*
     op2[k + 1,
      l]*(Factorial[l - 1]*StirlingS2[n - k - 1, l - 1] +
       Factorial[l]*StirlingS2[n - k - 1, l]) +
    Binomial[n, k]*Factorial[l]*
     StirlingS2[k, l]*(op2[n - k, l + 1] + op2[n - k, l]), {l, 1,
    n}] (* T[n, k] is number of threshold graphs on n vertices with k dominating vertices added in construction*);
Table[T[n, k],{n,1,12},{k,0,n-1}]

T(n,0) = 1 for n >= 1; T(2,1) = 1; T(n,k) = (Sum_{j=1..k} binomial(n, k+1)*A348576(k+1, j)*((j-1)!*A008277(n-k-1, j-1) + j!*A008277(n-k-1, j))) + (Sum_{j=1..n-k-1} binomial(n, k)*j!*A008277(k, j)*(A348576(n-k, j+1) + A348576(n-k, j))) for n >= 3, k >= 1. (See also equation (7) of paper by Galvin, Wesley and Zacovic.)

cp's OEIS Frontend

A016031 De Bruijn's sequence: 2^(2^(n-1) - n): number of ways of arranging 2^n bits in circle so all 2^n consecutive strings of length n are distinct.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A053525 Expansion of e.g.f.: (1-x)/(2-exp(x)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A005612 Number of Boolean functions of n variables that are variously called "unate cascades" or "1-decision list functions" or "read-once threshold functions".

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A051045 Number of distinct resistances possible for n resistors with resistances 1, 2, ..., n, each connected in series or parallel to the previous one.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A376544 a(n) is the number of singleton commuting ordered set partitions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

PARI

Formula

Extensions

A123750 Number of distinct resistances possible with at most n arbitrary resistors connected in series or in parallel.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Formula

A232005 Number of distinct resistances that can be produced from a circuit of resistors with resistances 1, 2, ..., n using only series and parallel combinations.

Views

Author

Keywords

Comments

Examples