A004251 -id:A004251 - cp's OEIS frontend

A339842 Heinz numbers of non-graphical, multigraphical integer partitions of even numbers.

9, 25, 30, 49, 63, 70, 75, 84, 100, 121, 147, 154, 165, 169, 175, 189, 196, 198, 210, 220, 250, 264, 273, 280, 286, 289, 325, 343, 351, 361, 363, 364, 385, 390, 441, 442, 462, 468, 484, 490, 495, 507, 520, 525, 529, 550, 561, 588, 594, 595, 616, 624, 637, 646

Offset: 1

Gus Wiseman, Dec 27 2020

nonn

An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph, and multigraphical if it comprises the multiset of vertex-degrees of some multigraph.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The sequence of terms together with their prime indices begins:
      9: {2,2}        189: {2,2,2,4}      363: {2,5,5}
     25: {3,3}        196: {1,1,4,4}      364: {1,1,4,6}
     30: {1,2,3}      198: {1,2,2,5}      385: {3,4,5}
     49: {4,4}        210: {1,2,3,4}      390: {1,2,3,6}
     63: {2,2,4}      220: {1,1,3,5}      441: {2,2,4,4}
     70: {1,3,4}      250: {1,3,3,3}      442: {1,6,7}
     75: {2,3,3}      264: {1,1,1,2,5}    462: {1,2,4,5}
     84: {1,1,2,4}    273: {2,4,6}        468: {1,1,2,2,6}
    100: {1,1,3,3}    280: {1,1,1,3,4}    484: {1,1,5,5}
    121: {5,5}        286: {1,5,6}        490: {1,3,4,4}
    147: {2,4,4}      289: {7,7}          495: {2,2,3,5}
    154: {1,4,5}      325: {3,3,6}        507: {2,6,6}
    165: {2,3,5}      343: {4,4,4}        520: {1,1,1,3,6}
    169: {6,6}        351: {2,2,2,6}      525: {2,3,3,4}
    175: {3,3,4}      361: {8,8}          529: {9,9}
For example, a complete list of all multigraphs with degrees (4,2,2,2) is:
  {{1,2},{1,2},{1,3},{1,4},{3,4}}
  {{1,2},{1,3},{1,3},{1,4},{2,4}}
  {{1,2},{1,3},{1,4},{1,4},{2,3}}
Since none of these is strict, i.e., a graph, the Heinz number 189 is in the sequence.

Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

See link for additional cross references.
Distinct prime shadows (images under A181819) of A340017.
A000070 counts non-multigraphical partitions (A339620).
A000569 counts graphical partitions (A320922).
A027187 counts partitions of even length (A028260).
A058696 counts partitions of even numbers (A300061).
A096373 cannot be partitioned into strict pairs.
A209816 counts multigraphical partitions (A320924).
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A320893 can be partitioned into distinct pairs but not into strict pairs.
A339560 can be partitioned into distinct strict pairs.
A339617 counts non-graphical partitions of 2n (A339618).
A339659 counts graphical partitions of 2n into k parts.
Cf. A004251, A006129, A007717, A056239, A095268, A112798, A181821, A305936, A318284, A339559.

strr[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strr[n/d],Min@@#>=d&]],{d,Select[Divisors[n],And[SquareFreeQ[#],PrimeOmega[#]==2]&]}]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[100],EvenQ[Length[nrmptn[#]]]&& Select[strr[Times@@Prime/@nrmptn[#]],UnsameQ@@#&]=={}&&strr[Times@@Prime/@nrmptn[#]]!={}&]

Equals A320924 /\ A339618.

Equals A320924 \ A320922.

A007721 Number of distinct degree sequences among all connected graphs with n nodes.

Original entry on oeis.org

1, 1, 2, 6, 19, 68, 236, 863, 3137, 11636, 43306, 162728, 614142, 2330454, 8875656, 33924699, 130038017, 499753560, 1924912505, 7429159770, 28723877046, 111236422377, 431403469046, 1675316533812, 6513837677642, 25354842098354, 98794053266471, 385312558567775

Offset: 1

Frank Ruskey

Sometimes called "graphical partitions", although this term is deprecated.

Wang Kai, Table of n, a(n) for n = 1..118
N. Durand, G. Granger, A traffic complexity approach through cluster analysis, in proceedings of the 5th ATM R&D Seminar, Budapest, Hungary (2003)
T. Hoppe, A. Petrone,Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
F. Ruskey, Alley CATs in search of good homes, Congress. Numerant., 102 (1994) 97-110.
Kai Wang, Efficient Counting of Degree Sequences, arXiv preprint arXiv:1604.04148 [math.CO], 2017.
Index entries for sequences related to graphical partitions

Cf. A000569, A004250, A004251, A007722, A029889; A095268 (analog for all graphs).

a(9) corrected by Gordon Royle, Aug 30 2006
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 19 2007
Prepended missing term a(1), Travis Hoppe, Aug 04 2014
a(22)-a(28) added by Wang Kai, Feb 15 2017

A029894 Number of directed (or Gale-Ryser) graphical partitions: degree-vector pairs (in-degree, out-degree) for directed graphs (loops allowed) with n vertices; or possible ordered pair (row-sum, column-sum) vectors for a 0-1 matrix.

Original entry on oeis.org

1, 2, 7, 34, 221, 1736, 15584, 153228, 1611189, 17826202, 205282376, 2441437708, 29816628471, 372314544202, 4737438631001, 61264426341926, 803488037899349, 10668478221202710, 143203795004873285, 1940953294927992976, 26536578116407809962, 365653739580163294032

Offset: 0

torsten.sillke(AT)lhsystems.com

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..30
Peter L. Erdos, I Miklós, Z Toroczkai, New classes of degree sequences with fast mixing swap Markov chain sampling, arXiv preprint arXiv:1601.08224 [math.CO], 2016.
Index entries for sequences related to graphical partitions

Main diagonal of A327913.

Cf. A000569, A004250, A004251, A029889, A318396.

\\ see A327913 for T(n,m)
for(n=0, 15, print1(T(n,n), ", ")) \\ Andrew Howroyd, Nov 01 2019

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

a(n) = F(n, n, 0, n) where F(b, c, t, w) = Sum_{i=0..b} Sum_{j=ceiling((t+i)/w)..min(t+i, c)} F(i, j, t+i-j, w-1) for w > 0, F(b, c, 0, 0) = 1 and F(b, c, t, 0) = 0 for t > 0. - Andrew Howroyd, Nov 01 2019

"Loops allowed" added to the definition by Brendan McKay, Oct 20 2015

a(0)=1 prepended and terms a(12) and beyond from Andrew Howroyd, Oct 31 2019

A005155 Number of degree sequences of n-node graphs.

Original entry on oeis.org

1, 1, 2, 8, 54, 533, 6944, 111850, 2135740, 47003045, 1168832808, 32363244260, 986532609608, 32810811179569, 1181865951824800, 45823912079507918, 1902469319507438352, 84195282530581058825, 3956365033583165905568, 196716723188140236180160

Offset: 0

N. J. A. Sloane

Given a simple graph, the degree sequence maps each vertex to the valence or degree of that vertex.

			1 + x + 2*x^2 + 8*x^3 + 54*x^4 + 533*x^5 + 6944*x^6 + 111850*x^7 + 2135740*x^8 + ...
a(3)=8 because we have: {0, 0, 0}, {0, 1, 1}, {1, 0, 1}, {1, 1, 0}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {2, 2, 2}. - _Geoffrey Critzer_, Aug 24 2016

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.16.

Alois P. Heinz, Table of n, a(n) for n = 0..386 (first 101 terms from James Spahlinger)
R. Simion, Convex Polytopes and Enumeration, Adv. in Appl. Math. 18 (1997) pp. 149-180.
R. P. Stanley, A zonotope associated with graphical degree sequences, in Applied Geometry and Discrete Combinatorics. DIMACS Series in Discrete Math., Amer. Math. Soc., Vol. 4, pp. 555-570, 1991.
Kai Wang, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016, p. 2 and p. 13.

Cf. A004251 for graphs up to isomorphism.

max = 18; w = ProductLog; f[x_] := (Sqrt[(1 - w[-x])/(1 + w[-x])] - w[-x]/x)*(Exp[-w[-x]^2/2]/ 2); CoefficientList[ Series[f[x], {x, 0, max}], x]*Range[0, max]! (* Jean-François Alcover, Dec 12 2011, after Vladeta Jovovic *)

{a(n) = local(A, B, C); if( n<0, 0, A = sum( k=1, n, k^k * x^k / k!, x * O(x^n)); B = intformal( 1 + A); C = intformal( 1 / (1 - B)); n! * polcoeff( (1 + (1 - B) * sqrt(1 + 2*A)) / 2 * exp(C), n))} /* Michael Somos, Aug 19 2005 */

There is an explicit formula and e.g.f.
E.g.f.: (sqrt((1-LambertW(-x))/(1+LambertW(-x)))-LambertW(-x)/x)*exp(-LambertW(-x)^2/2)/2. - Vladeta Jovovic, Jun 21 2007
a(n) ~ Gamma(3/4) * n^(n-1/4) / (2^(3/4) * exp(1/2) * sqrt(Pi)) * (1 - 11*Pi/(24*Gamma(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Jul 09 2013

Minor edits by Vaclav Kotesovec, Mar 31 2014

A007722 Number of graphical partitions of biconnected graphs with n nodes.

Original entry on oeis.org

1, 3, 9, 34, 125, 473, 1779, 6732, 25492, 96927, 369463, 1412700, 5415117, 20807502, 80120350, 309106496, 1194609429, 4624160156, 17925278497, 69578272204, 270401326899, 1052036082719, 4097343156323, 15973179953261, 62325892264031, 243392644741599

Offset: 3

Frank Ruskey

nonn

F. Ruskey, Alley CATs in search of good homes, Congress. Numerant., 102 (1994) 97-110.

Wang Kai, Table of n, a(n) for n = 3..101
Kai Wang, Efficient Counting of Degree Sequences, arXiv preprint arXiv:1604.04148 [math.CO], 2016-2017.
Index entries for sequences related to graphical partitions

Cf. A000569, A004250, A004251, A007721, A029889, A095268.

a(15)-a(28) added by Kai Wang, Feb 15 2017

A029890 Number of odd graphical partitions.

Original entry on oeis.org

1, 2, 7, 20, 70, 234, 832, 2956, 10759, 39394, 145892, 543564, 2038831, 7684116, 29092055, 110550260, 421495147, 1611662256

Offset: 1

TORSTEN.SILLKE(AT)LHSYSTEMS.COM

nonn

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.

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

A029891 Number of even graphical partitions.

Original entry on oeis.org

1, 3, 7, 23, 70, 242, 832, 2983, 10759, 39482, 145892, 543877, 2038831, 7685211, 29092055, 110554267, 421495147, 1611676767

Offset: 1

TORSTEN.SILLKE(AT)LHSYSTEMS.COM

nonn

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.

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

A259873 Triangle read by rows: T(n,k) (n >= 3, 3 <= k <= n) = number of possible graphical partitions for simple graphs with n non-isolated nodes and k edges.

Original entry on oeis.org

1, 0, 2, 0, 1, 4, 0, 1, 4, 7, 0, 0, 4, 9, 11, 0, 0, 2, 11, 15, 17, 0, 0, 1, 11, 22, 25, 25, 0, 0, 1, 9, 26, 38, 37, 36, 0, 0, 0, 7, 29, 49, 58, 55, 50, 0, 0, 0, 5, 29, 63, 81, 87, 77, 70

Offset: 3

N. J. A. Sloane, Jul 09 2015

			Triangle begins:
1,
0,2,
0,1,4,
0,1,4,7,
0,0,4,9,11,
0,0,2,11,15,17,
0,0,1,11,22,25,25,
0,0,1,9,26,38,37,36,
0,0,0,7,29,49,58,55,50,
0,0,0,5,29,63,81,87,77,70,
...

P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). Contains table for n <= 27.

P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]

A004250 is a diagonal. Cf. A000088, A004251.

A029893 Number of graphical partitions with up to n parts (?).

Original entry on oeis.org

1, 2, 4, 10, 24, 68, 198, 656, 2112

Offset: 1

torsten.sillke(AT)lhsystems.com

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

T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995).
Index entries for sequences related to graphical partitions

Cf. A000569, A004250, A004251, A029889.

A possible duplicate of A028506.

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

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).

cp's OEIS Frontend

A339842 Heinz numbers of non-graphical, multigraphical integer partitions of even numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A007721 Number of distinct degree sequences among all connected graphs with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A029894 Number of directed (or Gale-Ryser) graphical partitions: degree-vector pairs (in-degree, out-degree) for directed graphs (loops allowed) with n vertices; or possible ordered pair (row-sum, column-sum) vectors for a 0-1 matrix.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A005155 Number of degree sequences of n-node graphs.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A007722 Number of graphical partitions of biconnected graphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A029890 Number of odd graphical partitions.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A029891 Number of even graphical partitions.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A259873 Triangle read by rows: T(n,k) (n >= 3, 3 <= k <= n) = number of possible graphical partitions for simple graphs with n non-isolated nodes and k edges.

Views

Author

Keywords

Examples

References

Links

Crossrefs

A029893 Number of graphical partitions with up to n parts (?).

Views

Author