A016031 -id:A016031 - cp's OEIS frontend

A330297 Number of labeled simple graphs covering n vertices with exactly two automorphisms, or with exactly n!/2 graphs obtainable by permuting the vertices.

0, 0, 1, 3, 24, 540, 13320

Offset: 0

Gus Wiseman, Dec 12 2019

These are graphs with exactly one involution and no other symmetries.

			The a(4) = 24 graphs:
  {12,13,24}  {12,13,14,23}
  {12,13,34}  {12,13,14,24}
  {12,14,23}  {12,13,14,34}
  {12,14,34}  {12,13,23,24}
  {12,23,34}  {12,13,23,34}
  {12,24,34}  {12,14,23,24}
  {13,14,23}  {12,14,24,34}
  {13,14,24}  {12,23,24,34}
  {13,23,24}  {13,14,23,34}
  {13,24,34}  {13,14,24,34}
  {14,23,24}  {13,23,24,34}
  {14,23,34}  {14,23,24,34}

Gus Wiseman, All 9 distinct unlabeled representatives of the a(5) = 540 graphs.

The non-covering version is A330345.
The unlabeled version is A330346 (not A241454).
Covering simple graphs are A006129.
Covering graphs with exactly one automorphism are A330343.
Graphs with exactly two automorphisms are A330297 (labeled covering), A330344 (unlabeled), A330345 (labeled), and A330346 (unlabeled covering).
Cf. A003400, A006125, A016031, A124059, A143543, A241454, A330098, A330229, A330230, A330231, A330233.

graprms[m_]:=Union[Table[Sort[Sort/@(m/.Rule@@@Table[{p[[i]],i},{i,Length[p]}])],{p,Permutations[Union@@m]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[graprms[#]]==n!/2&]],{n,0,5}]

a(n) = n!/2 * A330346(n).

A340263 T(n, k) = [x^k] ((1-x)^(2^n) + 2^(-n)((2^n-1)(x-1)^(2^n) + (x+1)^(2^n)))/2. Irregular triangle read by rows, for n >= 0 and 0 <= k <= 2^n.

Original entry on oeis.org

1, 1, -1, 1, 1, -3, 6, -3, 1, 1, -7, 28, -49, 70, -49, 28, -7, 1, 1, -15, 120, -525, 1820, -4095, 8008, -10725, 12870, -10725, 8008, -4095, 1820, -525, 120, -15, 1

Offset: 0

Peter Luschny, Jan 06 2021

Conjecture: for n >= 1 the polynomials are irreducible.

			Polynomials begin:
[0] 1;
[1] x^2 - x + 1;
[2] x^4 - 3*x^3 + 6*x^2 - 3*x + 1;
[3] x^8 - 7*x^7 + 28*x^6 - 49*x^5 + 70*x^4 - 49*x^3 + 28*x^2 - 7*x + 1;
Triangle begins:
[0] [1]
[1] [1, -1, 1]
[2] [1, -3, 6, -3, 1]
[3] [1, -7, 28, -49, 70, -49, 28, -7, 1]
[4] [1, -15, 120, -525, 1820, -4095, 8008, -10725, 12870, -10725, 8008, -4095, 1820, -525, 120, -15, 1]

Peter Luschny, Table of n, a(n) for n = 0..1031

Row sums are 2^(2^n - n - 1) = A016031(n-1).
Central terms of the rows are A037293(n) for n >= 2.
Cf. A340312.

A340263_row := proc(n) local a, b;
if n = 0 then return [1] fi;
b := n -> add(binomial(2^n, 2*k)*x^(2*k), k = 0..2^n);
a := n -> x*mul(b(k), k = 0..n);
expand(b(n) - (2^n-1)*a(n-1));
[seq(coeff(%, x, j), j = 0..2^n)] end:
for n from 0 to 5 do A340263_row(n) od;
# Alternatively:
CoeffList := p -> [op(PolynomialTools:-CoefficientList(p, x))]:
Tpoly := n -> ((1-x)^(2^n) + 2^(-n)*((2^n-1)*(x-1)^(2^n) + (x + 1)^(2^n)))/2:
seq(print(CoeffList(Tpoly(n))), n=0..5); # Peter Luschny, Feb 03 2021

def A340263():
    a, b, c = 1, 1, 1
    yield [1]
    while True:
        c *= 2
        a *= b
        b = sum(binomial(c, 2 * k) * x ^ (2 * k) for k in range(c + 1))
        yield ((b - (c - 1) * x * a)).list()
A340263_row = A340263()
for _ in range(6):
    print(next(A340263_row))

Let p_n(x) = b(n) - (2^n-1)*a(n-1), b(n) = Sum_{k=0..2^n} binomial(2^n, 2*k)* x^(2*k), and a(n) = x*Product_{k=0..n} b(k). Then T(n, k) = [x^k] p_n(x).

Shorter name by Peter Luschny, Feb 03 2021

A368731 Number of non-isomorphic n-element sets of nonempty subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 10, 97, 2160, 126862, 21485262, 11105374322, 18109358131513, 95465831661532570, 1660400673336788987026, 96929369602251313489896310, 19268528295096123543660356281600, 13203875101002459910158494602665950757, 31517691852305548841992346407978317698725021

Offset: 0

Gus Wiseman, Jan 07 2024

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..50

The case of graphs is A001434, labeled A116508.
Labeled version is A136556, covering A054780, binomial transform of A367916.
The case of labeled covering graphs is A367863, binomial transform A367862.
These include the set-systems ranked by A367917.
The covering case is A368186, for graphs A006649, connected A057500.
Requiring all edges to be singletons or pairs gives A368598.
A003465 counts covers with any number of edges, unlabeled A055621.
A046165 counts minimal covers, ranks A309326.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
Cf. A000088, A007716, A283877, A367901, A367902, A367903, A368599.

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]},{i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Subsets[Subsets[Range[n],{1,n}],{n}]]],{n,0,4}]

a(n) = polcoef(G(n, n), n) \\ G defined in A368186. - Andrew Howroyd, Jan 11 2024

Terms a(6) and beyond from Andrew Howroyd, Jan 11 2024

A330057 Number of set-systems covering n vertices with no singletons or endpoints.

Original entry on oeis.org

1, 0, 0, 5, 1703, 66954642, 144115175199102143, 1329227995784915808340204290157341181, 226156424291633194186662080095093568664788471116325389572604136316742486364

Offset: 0

Gus Wiseman, Nov 30 2019

nonn

A set-system is a finite set of finite nonempty set of positive integers. A singleton is an edge of size 1. An endpoint is a vertex appearing only once (degree 1).

			The a(3) = 5 set-systems:
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}
  {{1,2},{2,3},{1,2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..11
Wikipedia, Degree (graph theory)

The version for non-isomorphic set-systems is A330055 (by weight).
The non-covering version is A330056.
Set-systems with no singletons are A016031.
Set-systems with no endpoints are A330059.
Non-isomorphic set-systems with no singletons are A306005 (by weight).
Non-isomorphic set-systems with no endpoints are A330054 (by weight).
Non-isomorphic set-systems counted by vertices are A000612.
Non-isomorphic set-systems counted by weight are A283877.
Cf. A007716, A055621, A302545, A317533, A317794, A319559, A320665, A321405, A330052, A330058.

Table[Length[Select[Subsets[Subsets[Range[n],{2,n}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]>1&]],{n,0,4}]

\\ here b(n) is A330056(n).
AS2(n, k) = {sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) )}
b(n) = {sum(k=0, n, (-1)^k*binomial(n,k)*2^(2^(n-k)-(n-k)-1) * sum(j=0, k\2, sum(i=0, k-2*j, binomial(k,i) * AS2(k-i, j) * (2^(n-k)-1)^i * 2^(j*(n-k)) )))}
a(n) = {sum(k=0, n, (-1)^k*binomial(n,k)*b(n-k))} \\ Andrew Howroyd, Jan 16 2023

Binomial transform is A330056.

Terms a(5) and beyond from Andrew Howroyd, Jan 16 2023

A368928 Triangle read by rows where T(n,k) is the number of labeled loop-graphs with n vertices and n edges, k of which are loops.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 1, 9, 9, 1, 15, 80, 90, 24, 1, 252, 1050, 1200, 450, 50, 1, 5005, 18018, 20475, 9100, 1575, 90, 1, 116280, 379848, 427329, 209475, 46550, 4410, 147, 1, 3108105, 9472320, 10548720, 5503680, 1433250, 183456, 10584, 224, 1

Offset: 0

Gus Wiseman, Jan 11 2024

			Triangle begins:
     1
     0     1
     0     2     1
     1     9     9     1
    15    80    90    24     1
   252  1050  1200   450    50     1
  5005 18018 20475  9100  1575    90     1
The loop-graphs counted in row n = 3 (loops shown as singletons):
  {12}{13}{23}  {1}{12}{13}  {1}{2}{12}  {1}{2}{3}
                {1}{12}{23}  {1}{2}{13}
                {1}{13}{23}  {1}{2}{23}
                {2}{12}{13}  {1}{3}{12}
                {2}{12}{23}  {1}{3}{13}
                {2}{13}{23}  {1}{3}{23}
                {3}{12}{13}  {2}{3}{12}
                {3}{12}{23}  {2}{3}{13}
                {3}{13}{23}  {2}{3}{23}

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Row sums are A014068, unlabeled version A000666.
Column k = 0 is A116508, covering version A367863.
The covering case is A368597.
The unlabeled version is A368836.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A322661 counts labeled covering loop-graphs, connected A062740.
Cf. A057500, A079491, A339065, A368596, A368927.

Table[Length[Select[Subsets[Subsets[Range[n], {1,2}],{n}],Count[#,{_}]==k&]],{n,0,5},{k,0,n}]
T[n_,k_]:= Binomial[n,k]*Binomial[Binomial[n,2],n-k]; Table[T[n,k],{n,0,8},{k,0,n}]// Flatten (* Stefano Spezia, Jan 14 2024 *)

T(n,k) = binomial(n,k)*binomial(binomial(n,2),n-k) \\ Andrew Howroyd, Jan 14 2024

T(n,k) = binomial(n,k)*binomial(binomial(n,2),n-k).

A306522 Number of simple directed cycles in the binary de Bruijn graphs of order n.

Original entry on oeis.org

3, 6, 19, 179, 30176, 1202267287

Offset: 1

Guillaume Marçais, Feb 21 2019

The numbers are computed empirically by the C++ program below. For n=7, the value is > 144*10^15 (the number of Hamiltonian cycles, A016031).

			For n=1, the cycles are (0), (1) and (0, 1).
For n=2, they are (00), (00, 01, 10), (00, 01, 11, 10), (01, 10), (01, 11, 10), (11).

Cf. A016031.

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 A306522(n): return sum(1 for c in nx.simple_cycles(deBruijn(n))) # Pontus von Brömssen, Jun 28 2021

A317586 Number of circular binary words of length n having the maximum possible number of distinct blocks of length floor(log_2 n) and floor(log_2 n)+1.

Original entry on oeis.org

2, 1, 2, 1, 2, 3, 4, 2, 4, 3, 6, 13, 12, 20, 32, 16, 32, 36, 68, 141, 242, 407, 600, 898, 1440, 1812, 2000, 2480, 2176, 2816, 4096, 2048, 4096, 3840, 7040, 13744, 28272, 54196, 88608, 160082, 295624, 553395, 940878, 1457197, 2234864, 3302752, 4975168, 7459376

Offset: 1

Jeffrey Shallit, Aug 01 2018

nonn

A circular binary word (a.k.a. "necklace") can be viewed as a representative of the equivalence class under cyclic shift.
The words counted by this sequence have 2^i distinct blocks of length i = floor(log_2 n) and n distinct blocks of length i+1.
This sequence counts a certain natural generalization of de Bruijn words, which are cyclic words of length 2^n containing all n-bit blocks as subwords.

			For n = 6 the 3 possibilities are {000111, 001011, 001101}.  Each contains all 4 blocks of length 2, and 6 distinct blocks of length 3 (when considered circularly).

D. Gabric, S. Holub, and J. Shallit, Generalized de Bruijn words and the state complexity of conjugate sets, arXiv:1903.05442 [cs.FL], March 13 2019.

Cf. A016031, which gives the value of this sequence evaluated at powers of 2.

Cf. A318687.

Terms a(33)-a(48) provided by Štěpán Holub

A330343 Number of labeled fully chiral simple graphs (also called identity or asymmetric graphs) covering n vertices.

Original entry on oeis.org

1, 0, 0, 0, 0, 5760, 766080, 149022720, 48990251520, 28928242022400, 32147584690636800, 69035206021583155200

Offset: 1

Gus Wiseman, Dec 12 2019

In a fully chiral graph, every permutation of the vertices gives a different representative, so the only automorphism is the identity.

The unlabeled version is A003400.
Identity trees are A004111.
Covering simple graphs are A006129.
Full chiral integer partitions are A330228.
Fully chiral factorizations are A330235.
Fully chiral set-systems are A330229 (labeled covering), A330282 (labeled), A330294 (unlabeled), A330295 (unlabeled covering).
Graphs with exactly two automorphisms are A330297 (labeled covering), A330344 (unlabeled), A330345 (labeled), A330346 (unlabeled covering), A241454 (unlabeled connected).
Cf. A006125, A016031, A124059, A143543, A330098, A330224, A330226, A330227, A330230, A330231, A330236.

graprms[m_]:=Union[Table[Sort[Sort/@(m/.Rule@@@Table[{p[[i]],i},{i,Length[p]}])],{p,Permutations[Union@@m]}]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[graprms[#]]==n!&]],{n,5}] (* brute force, not for computation *)

a(n) = n! * A003400(n).

A058342 De Bruijn sequence of order 6: every window of size 6, [a(j),a(j+1),...,a(j+5)], shows a different 6-tuple, for 0 <= j <= 63.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1

Offset: 0

Leon J. Tate (leonjtate(AT)earthlink.net), Dec 14 2000

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.6.12.

Index entries for linear recurrences with constant coefficients, signature (1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1).

Cf. A016031. A169671 gives the earliest such sequence.

A173009 Expansion of o.g.f. x(1 - x + x^2)/(1 -3x +x^2 +3x^3 -2x^4).

Original entry on oeis.org

0, 1, 2, 6, 13, 29, 60, 124, 251, 507, 1018, 2042, 4089, 8185, 16376, 32760, 65527, 131063, 262134, 524278, 1048565, 2097141, 4194292, 8388596, 16777203, 33554419, 67108850, 134217714, 268435441, 536870897

Offset: 1

Thomas Wieder, Feb 07 2010

The mean value m(n) = Sum_{k=0..(2^n -n-1)} k*p(n,k) of the distribution function p(n,k) = binomial(2^n-n-1, k)/2^(2^n-n-1) is 0., 0.5, 2., 5.5, 13., 28.5, 60., 123.5, 251., 506.5, 1018., 2041.5, 4089., 8184.5... We set a(n) = round(m(n)).

The half-integer sequence h(n) = 0, 1/2, 2, 11/2, 13, 57/2, 60, 247/2, 251, 1013/2, 1018, 4083/2, 4089, 16369/2, 16376, 65519/2, 65527, ... is the binomial transform of 0, 1/2, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,2).

Cf. A000295, A016031, A173010.

[Round((2^n -n-1)/2): n in [1..40]]; // G. C. Greubel, Feb 20 2021

A173009:= n-> round((2^n -n-1)/2); seq(A173009(n), n=1..40); # G. C. Greubel, Feb 20 2021

Table[Ceiling[(2^n-n-1)/2],{n,30}] (* or *) LinearRecurrence[{3,-1,-3,2},{0,1,2,6},30] (* Harvey P. Dale, Nov 16 2011 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 2,-3,-1,3]^(n-1)*[0;1;2;6])[1,1] \\ Charles R Greathouse IV, Apr 18 2020

[round((2^n -n-1)/2) for n in (1..40)] # G. C. Greubel, Feb 20 2021

G.f.: x*(1 - x + x^2)/(1 -3*x +x^2 +3*x^3 -2*x^4).
m(n) = (1/4)*2^n - 1/2 + m*(n-1) with m(1)=0 and a(n) = round(m(n)).
a(1)=0, a(2)=1, a(3)=2, a(4)=6, a(n) = 3*a(n-1) -a(n-2) -3*a(n-3) +2*a(n-4). - Harvey P. Dale, Nov 16 2011
a(n) = round(A000295(n)/2). - G. C. Greubel, Feb 20 2021

cp's OEIS Frontend

A330297 Number of labeled simple graphs covering n vertices with exactly two automorphisms, or with exactly n!/2 graphs obtainable by permuting the vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A340263 T(n, k) = [x^k] ((1-x)^(2^n) + 2^(-n)*((2^n-1)*(x-1)^(2^n) + (x+1)^(2^n)))/2. Irregular triangle read by rows, for n >= 0 and 0 <= k <= 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

SageMath

Formula

Extensions

A368731 Number of non-isomorphic n-element sets of nonempty subsets of {1..n}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A330057 Number of set-systems covering n vertices with no singletons or endpoints.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A368928 Triangle read by rows where T(n,k) is the number of labeled loop-graphs with n vertices and n edges, k of which are loops.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A306522 Number of simple directed cycles in the binary de Bruijn graphs of order n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A317586 Number of circular binary words of length n having the maximum possible number of distinct blocks of length floor(log_2 n) and floor(log_2 n)+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A330343 Number of labeled fully chiral simple graphs (also called identity or asymmetric graphs) covering n vertices.

Views

A340263 T(n, k) = [x^k] ((1-x)^(2^n) + 2^(-n)((2^n-1)(x-1)^(2^n) + (x+1)^(2^n)))/2. Irregular triangle read by rows, for n >= 0 and 0 <= k <= 2^n.

A173009 Expansion of o.g.f. x(1 - x + x^2)/(1 -3x +x^2 +3x^3 -2x^4).