A016031 -id:A016031 - cp's OEIS frontend

A330124 Number of unlabeled set-systems with n vertices and no endpoints.

1, 1, 2, 22, 1776

Offset: 0

Gus Wiseman, Dec 05 2019

A set-system is a finite set of finite nonempty sets. An endpoint is a vertex appearing only once (degree 1).

			Non-isomorphic representatives of the a(3) = 22 set-systems:
  0
  {1}{2}{12}
  {12}{13}{23}
  {1}{23}{123}
  {12}{13}{123}
  {1}{2}{13}{23}
  {1}{2}{3}{123}
  {1}{12}{13}{23}
  {1}{2}{13}{123}
  {1}{12}{13}{123}
  {1}{12}{23}{123}
  {12}{13}{23}{123}
  {1}{2}{3}{12}{13}
  {1}{2}{12}{13}{23}
  {1}{2}{3}{12}{123}
  {1}{2}{12}{13}{123}
  {1}{2}{13}{23}{123}
  {1}{12}{13}{23}{123}
  {1}{2}{3}{12}{13}{23}
  {1}{2}{3}{12}{13}{123}
  {1}{2}{12}{13}{23}{123}
  {1}{2}{3}{12}{13}{23}{123}

Partial sums of the covering case A330196.
The labeled version is A330059.
The "multi" version is A302545.
Unlabeled set-systems with no endpoints counted by weight are A330054.
Unlabeled set-systems with no singletons are A317794.
Unlabeled set-systems counted by vertices are A000612.
Unlabeled set-systems counted by weight are A283877.
The case with no singletons is A320665.
Cf. A007716, A016031, A306005, A317795, A321405, A330052, A330055.

A331691 Resultant of the Shapiro polynomials P_n(x) and Q_n(x).

Original entry on oeis.org

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

Offset: 0

Kevin Ryde, Jan 24 2020

The Shapiro polynomials P_n(x) and Q_n(x) are defined by P_0(x) = Q_0(x) = 1 and then mutual recurrences P_{n+1}(x) = P_n(x) + x^(2^n)*Q_n(x) and Q_{n+1}(x) = P_n(x) - x^(2^n)*Q_n(x). The coefficients of P are the Golay-Rudin-Shapiro sequence A020985. a(n) is the polynomial resultant R(P_n(x),Q_n(x)) as considered by Brillhart and Carlitz.

John Brillhart and L. Carlitz, Note on the Shapiro Polynomials, Proceedings of the American Mathematical Society, volume 25, number 1, May 1970, pages 114-118. Also at JSTOR. See A001782 for a scanned copy.
Harold S. Shapiro, Extremal Problems for Polynomials and Power Series, Masters Thesis, Massachusetts Institute of Technology, 1951. See pages 40-41.

Cf. A016031 (absolute values), A001782 (discriminant).

a(n) = if(n==0,1, -(-2)^(2^(n+1) - n - 2));

a(n) = my(P=1,Q=1); for(i=0,n-1, [P,Q]=[P+x^(2^i)*Q, P-x^(2^i)*Q]); polresultant(P,Q);

a(n) = (-1)^(n-1) * 2^(2^(n+1) - n - 2) for n >= 1 [Brillhart and Carlitz theorem 2].
a(n) = (-1)^(n-1) * A016031(n+2) for n >= 1.
a(n) = - 2^(2^n-1) * a(n-1) for n >= 2 [Brillhart and Carlitz in proof of theorem 2].

A344018 Table read by rows: T(n,k) (n >= 1, 1 <= k <= 2^n) is the number of cycles of length k which can be produced by a general n-stage feedback shift register.

Original entry on oeis.org

2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 3, 4, 2, 2, 1, 2, 3, 6, 7, 8, 12, 14, 17, 14, 13, 12, 20, 32, 16, 2, 1, 2, 3, 6, 9, 12, 20, 32, 57, 78, 113, 154, 208, 300, 406, 538, 703, 842, 1085, 1310, 1465, 1544, 1570, 1968, 2132, 2000, 2480, 2176, 2816, 4096, 2048

Offset: 1

N. J. A. Sloane, Jun 21 2021

T(n,k) is the number of cycles of length k in the directed binary de Bruijn graph of order n.

			The first four rows of the triangle are
2, 1,
2, 1, 2, 1,
2, 1, 2, 3, 2, 3, 4, 2,
2, 1, 2, 3, 6, 7, 8, 12, 14, 17, 14, 13, 12, 20, 32, 16,
...

Pontus von Brömssen, Rows n = 1..6, flattened
Peter R. Bryant and J. Christensen, The enumeration of shift register sequences, Journal of Combinatorial Theory, Series A, Vol. 35, No. 2 (1983), 154-172.
Oscar Cabrera, Introducing loop compression for encoding de Bruijn sequences, engrXiv (2025) Art. No. 4431. See p. 13.

Cf. A000010, A001037, A016031, A346018.

Row sums: A306522.

import networkx as nx
def deBruijn(n): return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
def A344018_row(n):
  a=[0]*2**n
  for c in nx.simple_cycles(deBruijn(n)):
    a[len(c)-1]+=1
  return a # Pontus von Brömssen, Jun 28 2021

From Pontus von Brömssen, Jun 28 2021: (Start)
T(n,k) = A001037(k) for n >= k-1.
T(k-2,k) = A001037(k) - A000010(k).
T(k-3,k) = A001037(k) - 2*A346018(k,2) + 2 for k >= 5.
T(n,2^n-1) = 2*T(n,2^n) = 2*A016031(n).
(See page 157 in the paper by Bryant and Christensen.)
(End)
From Pontus von Brömssen, Jul 01 2021: (Start)
Conjectures by Bryant and Christensen (1983):
Conjecture 1: T(k-4,k) = A001037(k) - 4*A346018(k,3) - 2*gcd(k,2) + 10 for k >= 8.
Conjecture 2: T(k-5,k) = A001037(k) - 8*A346018(k,4) - gcd(k,3) + 19 for k >= 11.
Conjecture 3: T(k-6,k) = A001037(k) - 16*A346018(k,5) - 4*gcd(k,2) - 2*gcd(k,3) + 48 for k >= 15. (End)
Sum_{k=1..m} T(n, k) = A062692(m) for 1 <= m <= n + 1. - C.S. Elder, Nov 07 2023

More terms from Pontus von Brömssen, Jun 28 2021

A359998 Number of longest directed cycles in the 2-Fibonacci digraph of order n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 28, 216, 65200, 167084480

Offset: 1

Pontus von Brömssen, Jan 21 2023

See Dalfó and Fiol (2019) or A360000 for the definition of the 2-Fibonacci digraph.

The longest cycles appear to have length A080023(n).

C. Dalfó and M. A. Fiol, On d-Fibonacci digraphs, arXiv:1909.06766 [math.CO], 2019.

Cf. A016031, A080023, A359997, A360000.

a(10) from Bert Dobbelaere, Jan 24 2023

A373343 Array read by ascending antidiagonals: A(n,k) is the number of cyclic de Bruijn sequences of order k and alphabet of size n, with k > 0.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 6, 24, 2, 1, 24, 20736, 373248, 16, 1, 120, 995328000, 189321481108517289984, 12635683568857645056, 2048, 1

Offset: 1

Stefano Spezia, Jun 01 2024

The 7th antidiagonal is too large to be included in Data.

			The array begins:
  1,  1,      1,                    1, ...
  1,  1,      2,                   16, ...
  2, 24, 373248, 12635683568857645056, ...
  ...

D. Condon, Yuxin Wang, and E. Yang, De Bruijn Polyominoes, arXiv:2405.18543 [math.CO], 2024. See page 5.
T. van Aardenne-Ehrenfest and N. G. de Brujin, Circuits and Trees in Oriented Linear Graphs. In: Simon Stevin 28 (1951), pp. 203-217.

Cf. A000012 (n=1), A000142 (k=1), A003992, A016031 (n=2), A373341 (acyclic), A373344 (antidiagonal sums).

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

A(n,k) = (n!)^(n^(k-1))/n^k.

A(n,k) = A373341(n,k)/A003992(n,k).

A001320 Number of self-complementary Boolean functions of n variables, up to equivalence under the group (C_2)^n of all 2^n complementations of variables.

Original entry on oeis.org

1, 3, 14, 240, 63488, 4227858432, 18302628885633695744, 338953138925153547590470800371487866880, 115565932813024562229384322928592814283244066726840484812818018414147674308608

Offset: 1

N. J. A. Sloane

The next term (a(10)) has 155 digits. - Harvey P. Dale, Jul 27 2011

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

M. A. Harrison, The number of equivalence classes of Boolean functions under groups containing negation, IEEE Trans. Electron. Comput. 12 (1963), 559-561.
M. A. Harrison, The number of equivalence classes of Boolean functions under groups containing negation, IEEE Trans. Electron. Comput. 12 (1963), 559-561. [Annotated scanned copy]
Index entries for sequences related to Boolean functions

Cf. A000610.

a:=n->sum(((fermat(n)-1))/2^(j+1),j=0..n): seq(a(n), n=0..8); # Zerinvary Lajos, Oct 24 2006

Table[2^(2^(n-1))(2^n-1)/2^n,{n,10}] (* Harvey P. Dale, Jul 27 2011 *)

a(n) = 2^(2^(n-1)) * (2^n-1) / 2^n. - Zerinvary Lajos, Oct 24 2006, corrected by R. J. Mathar, Apr 14 2010

a(n) = A016031(n)*A000079(n-1). - R. J. Mathar, Apr 14 2010

More terms from Vladeta Jovovic, Feb 23 2000

Clarification to the definition by R. J. Mathar, Apr 14 2010, edited and incorporated into the name by Andrey Zabolotskiy, Apr 18 2025

A175808 n-th term is the length of a shortest common superstring of the binary representations of all natural numbers from 1 to n.

Original entry on oeis.org

1, 2, 3, 4, 6, 6, 7, 8, 11, 11, 13, 13, 14, 14, 15, 16, 20, 20, 23, 23, 25, 25, 28, 28, 28, 28, 29, 29, 30, 30, 31, 32, 37, 37, 41, 41, 44, 44, 48, 48, 50, 50, 52, 52, 55, 55, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 61, 61, 62, 62, 63, 64

Offset: 1

Vladimir Reshetnikov, Sep 08 2010

If a(n) = 2^m, then we know that the lexicographically largest superstring coincides with the lexicographically largest de Bruijn sequence, B(2,m) (A166316(m)). - Thomas Scheuerle, Oct 09 2021

			a(5)=6 because 6 is the length of 110100 or 101100, which are the 2 possible shortest common superstrings of 1,10,11,100,101.

Cf. A175809 (number of shortest common superstrings).
Cf. A056744 (least decimal values of shortest common superstrings).
Cf. A166316, A016031.

It appears that a(2^n-1) = 2^n-1 and a(2^n) = 2^n. - Thomas Scheuerle, Oct 09 2021

a(23)-a(64) from Thomas Scheuerle, Oct 09 2021

A175809 a(n) is the number of shortest common superstrings of the binary representations of all natural numbers from 1 to n.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 2, 6, 4, 6, 4, 16, 16, 16, 16, 84, 56, 120, 108, 216, 108, 1296, 972, 504, 312, 768, 448, 2048, 2048, 2048, 2048

Offset: 1

Vladimir Reshetnikov, Sep 08 2010

All shortest common superstrings share the same number of ones and the same number of substrings of the form "10". If the length of the shortest common superstrings is a power of two (A175808(n) = 2^m), then we know that the lexicographically largest superstring coincides with the lexicographically largest de Bruijn sequence, B(2,m) (A166316(m)). This tells us that in this case all shortest common superstrings contain 2^(m-1) ones in 2^(m-2) groups separated by one or more zeros. - Thomas Scheuerle, Sep 19 2021

			a(5)=2 because there are 2 shortest common superstrings of 1,10,11,100,101; they are 110100 and 101100.

Cf. A175808 (length of shortest common superstrings).
Cf. A056744 (least decimal values of shortest common superstrings).
Cf. A166316, A016031.

From Thomas Scheuerle, Sep 19 2021: (Start)
a(2^n) = A016031(n) (if conjectured A175808(2^n) = 2^n is true).
a(2^n-3) = a(2^n-2) for n > 2. In this case the set of superstrings is equal.
a(2^n-2) = a(2^n-1) = a(2^n) for n > 1. Conjectured. (End)

a(21)-a(32) from Thomas Scheuerle, Sep 19 2021

A290952 Multi de Bruijn Sequences: Number of ways to arrange 2^(n+1) binary digits in a circle so that every length n binary string occurs exactly twice.

Original entry on oeis.org

2, 5, 82, 52496, 44079843328, 62177039921456290463744, 247422994777239366039696433386055989663945981952, 7835921708100840781377057397856335571660942358870727003819788990112934851947892015462438777389056

Offset: 1

Glenn Tesler, Aug 14 2017

Let m,q,n be positive integers. A cyclic multi de Bruijn sequence is a cyclic sequence over a q-ary alphabet in which every q-ary word of length n occurs exactly m times. Each such sequence has length m*q^n. Tesler (2017) shows the number of cyclic multi de Bruijn sequences is 1/(m*q^n) Sum_{r|m} phi(m/r) * ((r*q)! / (r!^q))^(q^(n-1)), where phi() is the Euler totient function A000010. Case m=1 is de Bruijn sequences; see A016031 for binary de Bruijn sequences (m=1, q=2, n>=1). Case m=2, q=2, n>=1 is a(n).

			For n=1, the a(1)=2 solutions are (0011) and (0101); each has two 0's and two 1's. Cyclic sequences have multiple representations via circular shifts: (0011)=(1001)=(1100)=(0110) all count as the same cyclic sequence, as do (0101)=(1010).
For n=2, the a(2)=5 solutions are (00010111), (00011011), (00011101), (00100111), and (00110011); each has two occurrences of each of 00, 01, 10, and 11. Note that in a cyclic sequence, occurrences may wrap around: in (00010111), there is one 10 in the middle, and another 10 that wraps around from the end to the start. Or, use a different rotation of the sequence: (00010111)=(10001011) shows both occurrences of 10 without wrapping.
For n=3 and 4, see the links section.

Glenn Tesler, Table of n, a(n) for n = 1..11
Glenn Tesler, Multi de Bruijn sequences, Journal of Combinatorics, Vol. 8, No. 3 (2017), 439-474 Preprint.
Glenn Tesler, List of the cyclic sequences for cases n=3 and n=4

Cf. A016031.

Table[(6^(2^(n - 1)) + 2^(2^(n - 1)))/2^(n + 1), {n, 8}] (* Michael De Vlieger, Aug 15 2017 *)

a(n) = (6^(2^(n-1)) + 2^(2^(n-1))) / 2^(n+1) \\ Felix Fröhlich, Aug 15 2017

a(n) = (6^(2^(n-1)) + 2^(2^(n-1))) / 2^(n+1).

A323820 Number of non-isomorphic connected set-systems covering n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 6, 171, 611846, 200253853704319, 263735716028826427334553304608242, 5609038300883759793482640992086670066496449147691597380632107520565546

Offset: 0

Gus Wiseman, Jan 30 2019

nonn

The labeled case is A323817.

			Non-isomorphic representatives of the a(3) = 6 set-systems:
  {{1,2,3}}
  {{1,3},{2,3}}
  {{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Cf. A000295, A003465, A016031, A048143, A055621, A293510, A305001, A317795 (not necessarily connected), A323817 (unlabeled case), A323819 (with singletons).

Inverse Euler transform of A317795.

cp's OEIS Frontend

A330124 Number of unlabeled set-systems with n vertices and no endpoints.

Views

Author

Keywords

Comments

Examples

Crossrefs

A331691 Resultant of the Shapiro polynomials P_n(x) and Q_n(x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

A344018 Table read by rows: T(n,k) (n >= 1, 1 <= k <= 2^n) is the number of cycles of length k which can be produced by a general n-stage feedback shift register.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A359998 Number of longest directed cycles in the 2-Fibonacci digraph of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A373343 Array read by ascending antidiagonals: A(n,k) is the number of cyclic de Bruijn sequences of order k and alphabet of size n, with k > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A001320 Number of self-complementary Boolean functions of n variables, up to equivalence under the group (C_2)^n of all 2^n complementations of variables.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A175808 n-th term is the length of a shortest common superstring of the binary representations of all natural numbers from 1 to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A175809 a(n) is the number of shortest common superstrings of the binary representations of all natural numbers from 1 to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula