A000569 -id:A000569 - cp's OEIS frontend

A322555 Number of labeled simple graphs on n vertices where all non-isolated vertices have the same degree.

1, 1, 2, 5, 18, 69, 390, 2703, 59474, 1548349, 168926258, 12165065351, 7074423247562, 2294426405580191, 4218009215702391954, 3810376434461484994317, 35102248193591661086921250, 156873334244228518638713087133, 4144940994226400702145709978234154

Offset: 0

Gus Wiseman, Dec 15 2018

nonn

Such graphs may be said to have regular support.

			The a(4) = 18 edge sets:
  {}
  {{1,2}}
  {{1,3}}
  {{1,4}}
  {{2,3}}
  {{2,4}}
  {{3,4}}
  {{1,2},{3,4}}
  {{1,3},{2,4}}
  {{1,4},{2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,4},{2,4}}
  {{1,3},{1,4},{3,4}}
  {{2,3},{2,4},{3,4}}
  {{1,2},{1,3},{2,4},{3,4}}
  {{1,2},{1,4},{2,3},{3,4}}
  {{1,3},{1,4},{2,3},{2,4}}
  {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

Cf. A000569, A005176, A038041, A059441, A295193, A306017, A306019, A319169, A320458.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],SameQ@@Length/@Split[Sort[Join@@#]]&]],{n,6}]

a(n) = 1 + Sum_{k=1..n} binomial(n, k)*(A295193(k) - 1). - Andrew Howroyd, Dec 17 2018

a(8)-a(15) from Andrew Howroyd, Dec 17 2018

a(16)-a(18) from Andrew Howroyd, May 21 2020

A338512 a(n) is the number of Chvátal-satisfying graphical n-sequences.

Original entry on oeis.org

6, 24, 67, 263, 823, 3276, 10839, 43287, 147943

Offset: 5

Stefano Spezia, Nov 01 2020

Douglas Bauer, Linda Lesniak, Aori Nevo, and Edward Schmeichel, On the necessity of Chvátal’s Hamiltonian degree condition, AKCE International Journal of Graphs and Combinatorics. See p. 2.
Vacláv Chvátal, On Hamilton’s ideals, J. Combin. Theory Ser. B 12(2): 163-168 (1972).

Cf. A000302, A000578.

Cf. A000569, A004251, A338513 (spurious version).

a(n) = O(4^n/n^3) where O indicates the big O notation (see Ref. 2 in Bauer).

A338513 a(n) is the number of Chvátal-satisfying spurious graphical n-sequences.

Original entry on oeis.org

2, 3, 14, 31, 117, 278, 956, 2578, 8106

Offset: 5

Stefano Spezia, Nov 09 2020

Douglas Bauer, Linda Lesniak, Aori Nevo, and Edward Schmeichel, On the necessity of Chvátal’s Hamiltonian degree condition, AKCE International Journal of Graphs and Combinatorics. See p. 2.
Vacláv Chvátal, On Hamilton’s ideals, J. Combin. Theory Ser. B 12(2): 163-168 (1972).

Cf. A000569, A004251, A338512 (non-spurious version).

Conjectures from Bauer et al.: (Start)
Lim_{n->infinity} a(n)/a(n-1) = 3.
Lim_{n->infinity} a(n)/A338512(n) = 0. (End)

A342208 Number of Frobenius partitions of 2*n that satisfy the condition that the sum of the entries on the top row plus the number of columns is less than or equal to the sum of the entries on the bottom row.

Original entry on oeis.org

1, 2, 5, 9, 18, 32, 57, 95, 162, 261, 418, 659, 1016, 1555, 2347, 3499, 5152, 7558, 10914, 15704, 22363, 31684, 44460, 62161, 86191, 119026, 163282, 223015, 302854, 409809, 551477, 739370, 987091, 1312752, 1739064, 2295880, 3020066, 3959580, 5175156, 6742034

Offset: 1

Michel Marcus, Mar 05 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Kelsey Blum, Bounds on the Number of Graphical Partitions, arXiv:2103.03196 [math.CO], 2021. See Table on p. 7. [Given a(10) is incorrect.]

Cf. A000569, A058696.

\\ by partitions
a(n)={my(total=0); forpart(q=2*n, my(p=Vecrev(q), m=0, s=0); while(m<#p && p[m+1]>m, m++; s+=p[m]-m); if(s + m <= n, total++) ); total} \\ Andrew Howroyd, Jan 03 2024

\\ faster version using g.f.'s
a(n)=sum(m=1, sqrtint(2*n), my(r=2*n-m^2); my(g=1/prod(k=1, m, 1 - x^k + O(x*x^r))); sum(i=0, n-binomial(m+1,2), polcoef(g,i)*polcoef(g,r-i)) ) \\ Andrew Howroyd, Jan 03 2024

A000569(n) <= a(n) <= A058696(n). - Kelsey A. Blum, Mar 15 2021

Corrected and extended by Andrew Howroyd, Jan 03 2024

A385919 Number of non-isomorphic round-robin tournament schedules for 2*n players, where the order of rounds does not matter.

Original entry on oeis.org

1, 1, 6, 6930, 12257280, 526915620, 1132835421602062347

Offset: 1

Peter Boonstra and Hilko Koning, Jul 25 2025

A round-robin tournament schedule with 2*n players consists of 2*n-1 rounds, where in each round the players are divided into n disjoint pairs, and every player plays against every other player exactly once.
Also the number of non-isomorphic 1-factorizations of the complete graph K_{2n}. We count 1-factorizations of the complete graph K_{2n} up to isomorphism, where 'isomorphism' means that two factorizations are considered the same if one can be transformed into the other by:
(1) relabeling the vertices (i.e., permuting the players), and
(2) reordering the rounds (i.e., permuting the 1-factors).
This is equivalent to counting round-robin tournament schedules where players are unlabeled and the order of the rounds is irrelevant.
Number of ways to partition the edge set of K_{2n} into 2n-1 perfect matchings (1-factors), up to isomorphism. Also the number of non-isomorphic 1-factorizations of the complete graph K_{2n}.

			a(1) = 1: one match between two players.
a(2) = 1: three matches (A-B, C-D, etc) organized into three rounds. All factorizations are isomorphic.
a(3) = 6: The 15 edges of K_6 can be partitioned into 5 rounds of 3 matches in 6 non-isomorphic ways.

Colbourn and Dinitz, CRC Handbook of Combinatorial Designs, 2nd ed. (2006), entry on 1 factorizations of complete graphs.

Petteri Kaski and Patric R. J. Östergård, There are 1132835421602062347 nonisomorphic one-factorizations of K_14, arXiv:0801.0202 [math.CO], 2007.
Hilko Koning, Non-isomorphic 1-factorizations of K_6 (6 labeled players, 5 rounds each).
Brendan D. McKay and Ian M. Wanless, There are 526915620 nonisomorphic one-factorizations of K_12.
Wikipedia, 1-factorization.
R. M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Congressus Numerantium 15 (1976), pp. 647-659.

Cf. A000085 (number of involutive permutations), A000569 (number of 1-factorizations of K_{2n}, not up to isomorphism).

(* n=4 is extremely memory- and CPU-intensive. The Mathematica approach is theoretically correct but utterly infeasible for n >= 4 *)
ClearAll[nonIsomorphic1Factorizations];
nonIsomorphic1Factorizations[n_Integer?Positive] :=
  Module[{vertices = Range[2 n], edges, matchings, factorizations,
    perms, canonical, relabel, isIsomorphicQ, nonIsomorphicList = {}},
    edges = Subsets[vertices, {2}];
   matchings =
    Select[Subsets[edges, {n}], DuplicateFreeQ[Flatten[#]] &];
   factorizations =
    Select[Subsets[matchings, {2 n - 1}], DuplicateFreeQ[Join @@ #] &];
   canonical[fact_] := Sort[Sort /@ fact];
   perms = Permutations[vertices];
   relabel[fact_, perm_] :=
    Sort[Sort /@ (Sort /@
          Replace[#, {a_, b_} :>
            Sort[{perm[[a]], perm[[b]]}], {2}] & /@ fact)];
   isIsomorphicQ[f1_, f2_] :=
    MemberQ[relabel[f1, #] & /@ perms, canonical[f2]];
   Do[If[NoneTrue[nonIsomorphicList, isIsomorphicQ[fact, #] &],
     AppendTo[nonIsomorphicList, fact]], {fact, factorizations}];
   nonIsomorphicList];
(*Display the number of non-isomorphic 1-factorizations for K_{2n} for n=1 to 5*)
Table[With[{list = nonIsomorphic1Factorizations[n]},
  Print["n = ", n, " \[RightArrow] ", Length[list],
   " non-isomorphic 1-factorizations of K_", 2 n];
  Length[list]], {n, 1, 5}]

A029892 Number of even graphical partitions of order 2n - number of odd graphical partitions of order 2n.

Original entry on oeis.org

1, 3, 8, 27, 88, 313, 1095, 4007, 14511

Offset: 1

TORSTEN.SILLKE(AT)LHSYSTEMS.COM

The graphical partitions considered here are for graphs with 2n vertices and with half-loops allowed. Half-loops are loops which count as 1 towards the degree of the vertex. See A029889 for additional information. - Andrew Howroyd, Jan 11 2024

R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.

Index entries for sequences related to graphical partitions

Cf. A000569, A004250, A004251, A029889, A029890, A029891.

Calculated using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.

a(n) = A029891(2*n) - A029890(2*n). - Andrew Howroyd, Jan 10 2024

A321185 Number of integer partitions of n that are the vertex-degrees of some strict antichain of sets with no singletons.

Original entry on oeis.org

1, 0, 1, 1, 2, 2, 5, 5, 9, 11, 17, 20

Offset: 0

Gus Wiseman, Oct 29 2018

A strict antichain is a finite set of finite nonempty sets, none of which is a subset of any other.

			The a(2) = 1 through a(9) = 11 partitions:
  (11)  (111)  (211)   (2111)   (222)     (2221)     (2222)      (3222)
               (1111)  (11111)  (2211)    (22111)    (3221)      (22221)
                                (3111)    (31111)    (22211)     (32211)
                                (21111)   (211111)   (32111)     (33111)
                                (111111)  (1111111)  (41111)     (222111)
                                                     (221111)    (321111)
                                                     (311111)    (411111)
                                                     (2111111)   (2211111)
                                                     (11111111)  (3111111)
                                                                 (21111111)
                                                                 (111111111)
The a(8) = 9 integer partitions together with a realizing strict antichain for each (the parts of the partition count the appearances of each vertex in the antichain):
     (41111): {{1,2},{1,3},{1,4},{1,5}}
      (3221): {{1,2},{1,3},{1,4},{2,3}}
     (32111): {{1,3},{1,2,4},{1,2,5}}
    (311111): {{1,2},{1,3},{1,4,5,6}}
      (2222): {{1,2},{1,3,4},{2,3,4}}
     (22211): {{1,2,3,4},{1,2,3,5}}
    (221111): {{1,2,3},{1,2,4,5,6}}
   (2111111): {{1,2},{1,3,4,5,6,7}}
  (11111111): {{1,2,3,4,5,6,7,8}}

Cf. A000070, A000569, A006126, A096827, A209816, A283877, A293606, A293993, A306005, A318361, A319721, A321176, A321184.

submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{_,x_,W___}}/;submultisetQ[{Z},{W}]]];
stableQ[u_]:=Apply[And,Outer[#1==#2||!submultisetQ[#1,#2]&&!submultisetQ[#2,#1]&,u,u,1],{0,1}];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
anti[m_]:=Select[mps[m],And[And@@UnsameQ@@@#,UnsameQ@@#,Min@@Length/@#>1,stableQ[#]]&];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[n],anti[#]!={}&]],{n,8}]

A321188 Number of set systems with no singletons whose multiset union is row n of A305936 (a multiset whose multiplicities are the prime indices of n).

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 4, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 1, 0, 0, 0, 0, 11, 0, 0, 0, 4, 0, 0, 0, 1

Offset: 1

Gus Wiseman, Oct 29 2018

A set system is a finite set of finite nonempty sets.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(36) = 4 set systems with no singletons whose multiset union is {1,1,2,2,3,4}:
  {{1,2},{1,2,3,4}}
  {{1,2,3},{1,2,4}}
  {{1,2},{1,3},{2,4}}
  {{1,2},{1,4},{2,3}}

Cf. A000070, A000296, A000569, A050326, A056239, A112798, A283877, A292444, A305936, A306005, A318285, A318361, A320922, A320923, A320924.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
hyp[m_]:=Select[mps[m],And[And@@UnsameQ@@@#,UnsameQ@@#,Min@@Length/@#>1]&];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Table[Length[hyp[nrmptn[n]]],{n,30}]

A363936 Number of Frobenius partitions of 2n wherein the number of columns plus the weight on the top row is strictly less than the weight on the bottom row.

Original entry on oeis.org

0, 1, 2, 6, 11, 22, 40, 72, 120, 203, 331, 526, 828, 1277, 1947, 2931, 4372

Offset: 1

Kelsey A. Blum, Jul 09 2023

Cf. A000569.

K:=1
product((1+z*q*q^j)^k*(1+z^-1*x^j)^k, j=0..40):
series(%,q,35):
convert(%,polynom):
expand(%):
A:=coeff(%,z,0):
for m from 2 by 2 to 40 do
for i to m do f(m):=add(coeff(coeff(A,x,i),q,m-i),i=m/2..m);
end do;
for n from 2 by 2 to 40 do
a(n):=f(n)-coeff(coeff(A,q,n/2),x,n/2); end do

a(n) <= A000569(n).

cp's OEIS Frontend

A322555 Number of labeled simple graphs on n vertices where all non-isolated vertices have the same degree.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A338512 a(n) is the number of Chvátal-satisfying graphical n-sequences.

Views

Author

Keywords

Links

Crossrefs

Formula

A338513 a(n) is the number of Chvátal-satisfying spurious graphical n-sequences.

Views

Author

Keywords

Links

Crossrefs

Formula

A342208 Number of Frobenius partitions of 2*n that satisfy the condition that the sum of the entries on the top row plus the number of columns is less than or equal to the sum of the entries on the bottom row.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A385919 Number of non-isomorphic round-robin tournament schedules for 2*n players, where the order of rounds does not matter.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A029892 Number of even graphical partitions of order 2n - number of odd graphical partitions of order 2n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A321185 Number of integer partitions of n that are the vertex-degrees of some strict antichain of sets with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A321188 Number of set systems with no singletons whose multiset union is row n of A305936 (a multiset whose multiplicities are the prime indices of n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A363936 Number of Frobenius partitions of 2n wherein the number of columns plus the weight on the top row is strictly less than the weight on the bottom row.

Views

Author

Keywords

Crossrefs