A000569 -id:A000569 - 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

A207864 Number of n X 2 nonnegative integer arrays with new values 0 upwards introduced in row major order and no element equal to any horizontal or vertical neighbor (colorings ignoring permutations of colors).

Original entry on oeis.org

1, 4, 34, 500, 10900, 322768, 12297768, 580849872, 33093252880, 2227152575552, 174131286983712, 15604440074084672, 1584856558077903168, 180712593036822482176, 22946861101272125055616, 3222156375409363475703040

Offset: 1

R. H. Hardin, Feb 21 2012

nonn

From Gus Wiseman, Mar 01 2019: (Start)
Also the number of stable partitions of the n-ladder graph. A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The n-ladder has 2n vertices and looks like:
  o-o-o-   -o
  | | | ... |
  o-o-o-   -o
(End)

			Some solutions for n=5:
  0 1   0 1   0 1   0 1   0 1   0 1   0 1   0 1   0 1   0 1
  1 0   1 0   1 2   1 2   1 0   1 0   1 2   1 0   1 0   1 0
  0 1   0 1   0 1   0 1   2 1   0 1   0 1   0 2   2 1   0 1
  1 2   1 0   1 0   1 3   3 0   2 0   3 2   2 1   1 0   1 2
  0 1   0 1   2 1   2 4   1 2   0 1   0 1   0 2   0 1   2 0

R. H. Hardin, Table of n, a(n) for n = 1..61

Column 2 of A207868.

Cf. A000110, A000569, A109808, A229048, A240936, A321750, A321979, A321980, A321982, A322064.

Table[Expand[x*(x-1)*(x^2-3*x+3)^(n-1)]/.x^k_.->BellB[k],{n,20}] (* Gus Wiseman, Mar 01 2019 *)

It appears that the sequence terms are given by the Dobinski-type formula a(n+1) = (1/e) * Sum_{k>=0} (1+k+k^2)^n/k!. - Peter Bala, Mar 12 2012

Apply x^n -> B(n) to the polynomial chi(n) = x (x - 1) (x^2 - 3 x + 3)^(n - 1), where B = A000110. - Gus Wiseman, Mar 01 2019

A321981 Row n gives the chromatic symmetric function of the n-girder, expanded in terms of elementary symmetric functions and ordered by Heinz number.

Original entry on oeis.org

1, 2, 0, 6, 0, 0, 16, 0, 2, 0, 0, 40, 12, 2, 0, 0, 0, 0, 96, 16, 44, 6, 0, 0, 0, 0, 0, 0, 0, 224, 136, 66, 52, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 512, 384, 208, 96, 30, 178, 0, 18, 30, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1152, 1024, 584, 522, 138, 588, 102

Offset: 1

Gus Wiseman, Nov 23 2018

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).
A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895).
The n-girder has n vertices and looks like:
  2-4-6-     -n
  |\|\|\ ... \|
  1-3-5-     n-1
Conjecture: All terms are nonnegative (verified up to n = 10). This is a special case of Stanley and Stembridge's poset-chain conjecture.

			Triangle begins:
    1
    2   0
    6   0   0
   16   0   2   0   0
   40  12   2   0   0   0   0
   96  16  44   6   0   0   0   0   0   0   0
  224 136  66  52   2   4   0   2   0   0   0   0   0   0   0
For example, row 6 gives: X_G6 = 96e(6) + 6e(33) + 16e(42) + 44e(51).

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
Richard P. Stanley and John R. Stembridge, On immanants of Jacobi-Trudi matrices and permutations with restricted position, Journal of Combinatorial Theory Series A 62-2 (1993), 261-279.
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Row sums are A025192.

Cf. A000569, A001187, A006125, A056239, A229048, A240936, A245883, A277203, A321750, A321911, A321918, A321914, A321979, A321980, A321982.

A321994 Number of different chromatic symmetric functions of hypertrees on n vertices.

Original entry on oeis.org

1, 1, 2, 4, 9, 22, 59, 165

Offset: 1

Gus Wiseman, Nov 24 2018

A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895).

Stanley conjectured that the number of distinct chromatic symmetric functions of trees with n vertices is equal to A000055, i.e., the chromatic symmetric function distinguishes between trees. It has been proven for trees with up to 25 vertices. If it is true in general, does the chromatic symmetric function also distinguish between hypertrees, meaning this sequence would be equal to A035053?

Jeremy L. Martin, The uniqueness problem for chromatic symmetric functions of trees (2015)
Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.

Cf. A000055, A000569, A001187, A001349, A006125, A035053, A229048, A240936, A245883, A277203, A030019, A321750, A321895, A321911.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
density[c_]:=Total[(Length[#]-1&)/@c]-Length[Union@@c];
hyall[n_]:=Select[stableSets[Select[Subsets[Range[n]],Length[#]>1&],Or[SubsetQ[#1,#2],Length[Intersection[#1,#2]]>1]&],And[Union@@#==Range[n],Length[csm[#]]==1,density[#]==-1]&];
chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
Table[Length[Union[chromSF/@If[n==1,{{{1}}},hyall[n]]]],{n,5}]

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

A321176 Number of integer partitions of n that are the vertex-degrees of some set system with no singletons.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 5, 7, 10, 15, 21, 28

Offset: 0

Gus Wiseman, Oct 29 2018

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

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

Cf. A000070, A000569, A147878, A209816, A283877, A306005, A318361, A320922, A320923, A320924, A321177.

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]&];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[n],hyp[#]!={}&]],{n,8}]

A322136 Numbers whose number of prime factors counted with multiplicity exceeds half their sum of prime indices by at least 1.

Original entry on oeis.org

4, 8, 12, 16, 24, 32, 36, 40, 48, 64, 72, 80, 96, 108, 112, 120, 128, 144, 160, 192, 216, 224, 240, 256, 288, 320, 324, 336, 352, 360, 384, 400, 432, 448, 480, 512, 576, 640, 648, 672, 704, 720, 768, 800, 832, 864, 896, 960, 972

Offset: 1

Gus Wiseman, Nov 27 2018

nonn

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k). The sequence lists all Heinz numbers of integer partitions where the number of parts is at least 1 plus half the sum of parts.

Also Heinz numbers of integer partitions that are the vertex-degrees of some hypertree. We allow no singletons in a hypertree, so 2 is not included.

			The sequence of partitions with Heinz numbers in the sequence begins: (11), (111), (211), (1111), (2111), (11111), (2211), (3111), (21111), (111111), (22111), (31111), (211111), (22211), (41111), (32111), (1111111).

Cf. A000569, A025065, A030019, A056156, A056239, A056503, A112798, A181821, A242414, A304382, A320922, A320923, A320924, A320925.

Select[Range[1000],PrimeOmega[#]>=(Total[Cases[FactorInteger[#],{p_,k_}:>k*PrimePi[p]]]+2)/2&]

A001130 Number of graphical basis partitions of 2n.

Original entry on oeis.org

1, 1, 3, 4, 6, 11, 16, 23, 36, 52, 71, 103, 141, 197, 272, 366, 482, 657, 863, 1140, 1489, 1951, 2511, 3241, 4155, 5317, 6782, 8574, 10786, 13645, 17111, 21313, 26631, 33020, 41005, 50640, 62373, 76510, 94089, 114991, 140376, 170970, 207837, 251552, 305342, 368474, 444360, 534692, 642593, 770278

Offset: 1

Pranav Kumar Tiwari (pktiwari(AT)eos.ncsu.edu)

nonn

A partition of an even integer is graphical if it is the degree sequence of a simple graph.

Nolan, Jennifer M.; Sivaraman, Vijay; Savage, Carla D.; and Tiwari, Pranav K., Graphical basis partitions, Graphs Combin. 14 (1998), no. 3, 241-261. Math. Rev. 99j:05014. See http://www4.ncsu.edu/~savage/papers.html for postscript file.

Ray Chandler, Table of n, a(n) for n = 1..100 [from the Nolan et al. paper]
Index entries for sequences related to graphical partitions

Cf. A000041, A000569, A066447.

Seven more terms (all that are presently known, apparently) added from the Nolan et al. paper by N. J. A. Sloane, Jun 01 2012

Extended b-file from Nolan et al. paper and adjusted description to even n by Ray Chandler, Sep 17 2015

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

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

A207864 Number of n X 2 nonnegative integer arrays with new values 0 upwards introduced in row major order and no element equal to any horizontal or vertical neighbor (colorings ignoring permutations of colors).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A321981 Row n gives the chromatic symmetric function of the n-girder, expanded in terms of elementary symmetric functions and ordered by Heinz number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A321994 Number of different chromatic symmetric functions of hypertrees on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

A321176 Number of integer partitions of n that are the vertex-degrees of some set system with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A322136 Numbers whose number of prime factors counted with multiplicity exceeds half their sum of prime indices by at least 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A001130 Number of graphical basis partitions of 2n.

Views

Author