A339659 -id:A339659 - cp's OEIS frontend

A004250 Number of partitions of n into 3 or more parts.

0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, 127, 168, 222, 288, 375, 480, 616, 781, 990, 1243, 1562, 1945, 2422, 2996, 3703, 4550, 5588, 6826, 8332, 10126, 12292, 14865, 17958, 21618, 25995, 31165, 37317, 44562

Offset: 1

N. J. A. Sloane

Number of (n+1)-vertex spider graphs: trees with n+1 vertices and exactly 1 vertex of degree at least 3 (i.e. branching vertex). There is a trivial bijection with the objects described in the definition. - Emeric Deutsch, Feb 22 2014

Also the number of graphical partitions of 2n into n parts. - Gus Wiseman, Jan 08 2021

			a(6)=7 because there are three partitions of n=6 with i=3 parts: [4, 1, 1], [3, 2, 1], [2, 2, 2] and two partitions with i=4 parts: [3, 1, 1, 1], [2, 2, 1, 1] and one partition with i=5 parts: [2, 1, 1, 1, 1] and one partition with i=6 parts: [1, 1, 1, 1, 1, 1].
From _Gus Wiseman_, Jan 18 2021: (Start)
The a(3) = 1 through a(7) = 11 graphical partitions of 2n into n parts:
  (222)  (2222)  (22222)  (222222)  (2222222)
         (3221)  (32221)  (322221)  (3222221)
                 (33211)  (332211)  (3322211)
                 (42211)  (333111)  (3332111)
                          (422211)  (4222211)
                          (432111)  (4322111)
                          (522111)  (4331111)
                                    (4421111)
                                    (5222111)
                                    (5321111)
                                    (6221111)
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
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).

T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995).
N. Metropolis and P. R. Stein, The enumeration of graphical partitions, Europ. J. Combin., 1 (1980), 139-1532.
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]
Eric Weisstein's World of Mathematics. Spider Graph
Wikipedia, Starlike tree
Index entries for sequences related to graphical partitions

Cf. A004251, A029889, A035300, A095268, A058984.
Rightmost column of A259873.
Central column of A339659.
A000041 counts partitions of 2n into n parts, ranked by A340387.
A000569 counts graphical partitions, ranked by A320922.
A008284 counts partitions by sum and length.
A027187 counts partitions of even length.
A309356 ranks simple covering graphs.
The following count vertex-degree partitions and give their Heinz numbers:
- A209816 counts multigraphical partitions (A320924).
- A320921 counts connected graphical partitions (A320923).
- A339617 counts non-graphical partitions of 2n (A339618).
- A339656 counts loop-graphical partitions (A339658).
Cf. A000070, A000219, A339560, A339561, A339661.
Partial sums of A117995.

with(combinat);
for i from 1 to 15 do pik(i,3) od;
pik:= proc(n::integer, k::integer)
# Thomas Wieder, Jan 30 2007
local i, Liste, Result;
if k > n or n < 0 or k < 1 then
return fail
end if;
Result := 0;
for i from k to n do
Liste:= PartitionList(n,i);
#print(Liste);
Result := Result + nops(Liste);
end do;
return Result;
end proc;
PartitionList := proc (n, k)
# Authors: Herbert S. Wilf and Joanna Nordlicht. Source: Lecture Notes
# "East Side West Side,..." University of Pennsylvania, USA, 2002.
# Available at: http://www.cis.upenn.edu/~wilf/lecnotes.html
# Calculates the partition of n into k parts.
# E.g. PartitionList(5,2) --> [[4, 1], [3, 2]].
local East, West;
if n < 1 or k < 1 or n < k then
RETURN([])
elif n = 1 then
RETURN([[1]])
else if n < 2 or k < 2 or n < k then
West := []
else
West := map(proc (x) options operator, arrow;
[op(x), 1] end proc,PartitionList(n-1,k-1)) end if;
if k <= n-k then
East := map(proc (y) options operator, arrow;
map(proc (x) options operator, arrow; x+1 end proc,y) end proc,PartitionList(n-k,k))
else East := [] end if;
RETURN([op(West), op(East)])
end if;
end proc;
#  Thomas Wieder, Feb 01 2007
ZL :=[S, {S = Set(Cycle(Z),3 <= card)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=1..41); # Zerinvary Lajos, Mar 25 2008
B:=[S,{S = Set(Sequence(Z,1 <= card),card >=3)},unlabelled]: seq(combstruct[count](B, size=n), n=1..41); # Zerinvary Lajos, Mar 21 2009

Length /@ Table[Select[Partitions[n], Length[#] > 2 &], {n, 20}] (* Eric W. Weisstein, May 16 2007 *)
Table[Count[Length /@ Partitions[n], ?(# > 2 &)], {n, 20}] (* _Eric W. Weisstein, May 16 2017 *)
Table[PartitionsP[n] - Floor[n/2] - 1, {n, 20}] (* Eric W. Weisstein, May 16 2017 *)
Length /@ Table[IntegerPartitions[n, {3, n}], {n, 20}] (* Eric W. Weisstein, May 16 2017 *)

a(n) = numbpart(n) - (n+2)\2; /* Joerg Arndt, Apr 03 2013 */

G.f.: Sum_{n>=0} (q^n / Product_{k=1..n+3} (1 - q^k)). -  N. J. A. Sloane
a(n) = A000041(n) - floor((n+2)/2) = A000041(n)-A004526(n+2) = A058984(n)-1. - Vladeta Jovovic, Jun 18 2003
Let P(n,i) denote the number of partitions of n into i parts. Then a(n) = Sum_{i=3..n} P(n,i). - Thomas Wieder, Feb 01 2007
a(n) = A259873(n,n). - Gus Wiseman, Jan 08 2021

Definition corrected by Thomas Wieder, Feb 01 2007 and by Eric W. Weisstein, May 16 2007

A004251 Number of graphical partitions (degree-vectors for simple graphs with n vertices, or possible ordered row-sum vectors for a symmetric 0-1 matrix with diagonal values 0).

Original entry on oeis.org

1, 1, 2, 4, 11, 31, 102, 342, 1213, 4361, 16016, 59348, 222117, 836315, 3166852, 12042620, 45967479, 176005709, 675759564, 2600672458, 10029832754, 38753710486, 149990133774, 581393603996, 2256710139346, 8770547818956, 34125389919850, 132919443189544, 518232001761434, 2022337118015338, 7898574056034636, 30873421455729728

Offset: 0

N. J. A. Sloane

In other words, a(n) is the number of graphic sequences of length n, where a graphic sequence is a sequence of numbers which can be the degree sequence of some graph.

In the article by A. Iványi, G. Gombos, L. Lucz, and T. Matuszka, "Parallel enumeration of degree sequences of simple graphs II", in Table 4 on page 260 the values a(30) = 7898574056034638 and a(31) = 30873429530206738 are incorrect due to the incorrect Gz(30) = 5876236938019300 and Gz(31) = 22974847474172100. - Wang Kai, Jun 05 2016

			For n = 3, there are 4 different graphic sequences possible: 0 0 0; 1 1 0; 2 1 1; 2 2 2. - Daan van Berkel (daan.v.berkel.1980(AT)gmail.com), Jun 25 2010
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(4) = 11 sorted degree sequences:
  ()  (0)  (0,0)  (0,0,0)  (0,0,0,0)
           (1,1)  (0,1,1)  (0,0,1,1)
                  (1,1,2)  (0,1,1,2)
                  (2,2,2)  (0,2,2,2)
                           (1,1,1,1)
                           (1,1,1,3)
                           (1,1,2,2)
                           (1,2,2,3)
                           (2,2,2,2)
                           (2,2,3,3)
                           (3,3,3,3)
For example, the graph {{2,3},{2,4}} has degrees (0,2,1,1), so (0,1,1,2) is counted under a(4).
(End)

R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
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).

Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Table of n, a(n) for n = 0..1651 (Terms 1 through 31 were computed by various authors; terms 32 through 34 by Axel Kohnert and Wang Kai; terms 35 to 79 by Wang Kai)
Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Counting graphic sequences via integrated random walks, arXiv:2301.07022 [math.CO], 2023.
T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995), #R11.
B. A. Chat, S. Pirzada, and A. Iványi, Recognition of split-graphic sequences, Acta Universitatis Sapientiae, Informatica, 6, 2 (2014) 252-286.
D. Dimitrov, Efficient computation of trees with minimal atom-bond connectivity index, arXiv:1305.1155 [cs.DM], 2013.
A. Iványi, L. Lucz, T. F. Móri and P. Sótér, On Erdős-Gallai and Havel-Hakimi algorithms, Acta Univ. Sapientiae, Inform. 3(2) (2011), 230-268.
A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapientiae, Informatica, 4, 2 (2012), 260-288. - From _N. J. A. Sloane_, Feb 15 2013
A. Ivanyi and J. E. Schoenfield, Deciding football sequences, Acta Univ. Sapientiae, Informatica, 4, 1 (2012), 130-183. - From _N. J. A. Sloane_, Dec 22 2012 [Disclaimer: I am not one of the authors of this paper; I was unpleasantly surprised to find my name on it, as explained here. - _Jon E. Schoenfield_, Nov 26 2016]
Wang Kai, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms.
P. W. Mills, R. P. Rundle, V. M. Dwyer, T. Tilma, and S. J. Devitt, A proposal for an efficient quantum algorithm solving the graph isomorphism problem, arXiv 1711.09842, 2017.
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]
Eric Weisstein's World of Mathematics, Degree Sequence.
Eric Weisstein's World of Mathematics, Graphic Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.
Index entries for sequences related to graphical partitions

Counting the positive partitions by sum gives A000569, ranked by A320922.
The version with half-loops is A029889, with covering case A339843.
The covering case (no zeros) is A095268.
Covering simple graphs are ranked by A309356 and A320458.
Non-graphical partitions are counted by A339617 and ranked by A339618.
The version with loops is A339844, with covering case A339845.
A006125 counts simple graphs, with covering case A006129.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A320921 counts connected graphical partitions.
A322353 counts factorizations into distinct semiprimes.
A339659 counts graphical partitions of 2n into k parts.
A339661 counts factorizations into distinct squarefree semiprimes.
Cf. A004250, A007717, A181819, A320894, A320923, A339560, A339561, A339842.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Subsets[Subsets[Range[n],{2}]]]],{n,0,5}] (* Gus Wiseman, Dec 31 2020 *)

G.f. = 1 + x + 2*x^2 + 4*x^3 + 11*x^4 + 31*x^5 + 102*x^6 + 342*x^7 + 1213*x^8 + ...

a(n) ~ c * 4^n / n^(3/4) for some constant c > 0. Computational estimates suggest c ≈ 0.099094. - Tom Johnston, Jan 18 2023

More terms from Torsten Sillke, torsten.sillke(AT)lhsystems.com, using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.
a(19) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 19 2007
a(20)-a(23) from Nathann Cohen, Jul 09 2011
a(24)-a(29) from Antal Iványi, Nov 15 2011
a(30) and a(31) corrected by Wang Kai, Jun 05 2016

A339560 Number of integer partitions of n that can be partitioned into distinct pairs of distinct parts, i.e., into a set of edges.

Original entry on oeis.org

1, 0, 0, 1, 1, 2, 2, 4, 5, 8, 8, 13, 17, 22, 28, 39, 48, 62, 81, 101, 127, 167, 202, 253, 318, 395, 486, 608, 736, 906, 1113, 1353, 1637, 2011, 2409, 2922, 3510, 4227, 5060, 6089, 7242, 8661, 10306, 12251, 14503, 17236, 20345, 24045, 28334, 33374, 39223, 46076

Offset: 0

Gus Wiseman, Dec 10 2020

nonn

Naturally, such a partition must have an even number of parts. Its multiplicities form a graphical partition (A000569, A320922), and vice versa.

			The a(3) = 1 through a(11) = 13 partitions (A = 10):
  (21)  (31)  (32)  (42)  (43)    (53)    (54)    (64)    (65)
              (41)  (51)  (52)    (62)    (63)    (73)    (74)
                          (61)    (71)    (72)    (82)    (83)
                          (3211)  (3221)  (81)    (91)    (92)
                                  (4211)  (3321)  (4321)  (A1)
                                          (4221)  (5221)  (4322)
                                          (4311)  (5311)  (4331)
                                          (5211)  (6211)  (4421)
                                                          (5321)
                                                          (5411)
                                                          (6221)
                                                          (6311)
                                                          (7211)
For example, the partition y = (4,3,3,2,1,1) can be partitioned into a set of edges in two ways:
  {{1,2},{1,3},{3,4}}
  {{1,3},{1,4},{2,3}},
so y is counted under a(14).

Eric Weisstein's World of Mathematics, Graphical partition.

A338916 allows equal pairs (x,x).
A339559 counts the complement in even-length partitions.
A339561 gives the Heinz numbers of these partitions.
A339619 counts factorizations of the same type.
A000070 counts non-multigraphical partitions of 2n, ranked by A339620.
A000569 counts graphical partitions, ranked by A320922.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A058696 counts partitions of even numbers, ranked by A300061.
A209816 counts multigraphical partitions, ranked by A320924.
A320655 counts factorizations into semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339617 counts non-graphical partitions of 2n, ranked by A339618.
A339655 counts non-loop-graphical partitions of 2n, ranked by A339657.
A339656 counts loop-graphical partitions, ranked by A339658.
A339659 counts graphical partitions of 2n into k parts.
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
Cf. A001055, A001221, A005117, A007717, A025065, A030229, A320893, A338899, A338903, A339564.

strs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strs[n/d],Min@@#>d&]],{d,Select[Rest[Divisors[n]],And[SquareFreeQ[#],PrimeOmega[#]==2]&]}]];
Table[Length[Select[IntegerPartitions[n],strs[Times@@Prime/@#]!={}&]],{n,0,15}]

A027187(n) = a(n) + A339559(n).

More terms from Jinyuan Wang, Feb 14 2025

A339561 Products of distinct squarefree semiprimes.

Original entry on oeis.org

1, 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 60, 62, 65, 69, 74, 77, 82, 84, 85, 86, 87, 90, 91, 93, 94, 95, 106, 111, 115, 118, 119, 122, 123, 126, 129, 132, 133, 134, 140, 141, 142, 143, 145, 146, 150, 155, 156, 158, 159, 161, 166

Offset: 1

Gus Wiseman, Dec 13 2020

nonn

First differs from A320911 in lacking 36.
A squarefree semiprime (A006881) is a product of any two distinct prime numbers.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct strict pairs (a set of edges);
(2) n can be factored into distinct squarefree semiprimes;
(3) the prime signature of n is graphical.

			The sequence of terms together with their prime indices begins:
      1: {}        55: {3,5}         91: {4,6}
      6: {1,2}     57: {2,8}         93: {2,11}
     10: {1,3}     58: {1,10}        94: {1,15}
     14: {1,4}     60: {1,1,2,3}     95: {3,8}
     15: {2,3}     62: {1,11}       106: {1,16}
     21: {2,4}     65: {3,6}        111: {2,12}
     22: {1,5}     69: {2,9}        115: {3,9}
     26: {1,6}     74: {1,12}       118: {1,17}
     33: {2,5}     77: {4,5}        119: {4,7}
     34: {1,7}     82: {1,13}       122: {1,18}
     35: {3,4}     84: {1,1,2,4}    123: {2,13}
     38: {1,8}     85: {3,7}        126: {1,2,2,4}
     39: {2,6}     86: {1,14}       129: {2,14}
     46: {1,9}     87: {2,10}       132: {1,1,2,5}
     51: {2,7}     90: {1,2,2,3}    133: {4,8}
For example, the number 1260 can be factored into distinct squarefree semiprimes in two ways, (6*10*21) or (6*14*15), so 1260 is in the sequence. The number 69300 can be factored into distinct squarefree semiprimes in seven ways:
  (6*10*15*77)
  (6*10*21*55)
  (6*10*33*35)
  (6*14*15*55)
  (6*15*22*35)
  (10*14*15*33)
  (10*15*21*22),
so 69300 is in the sequence. A complete list of all strict factorizations of 24 is: (2*3*4), (2*12), (3*8), (4*6), (24), all of which contain at least one number that is not a squarefree semiprime, so 24 is not in the sequence.

Eric Weisstein's World of Mathematics, Graphical partition.

A309356 is a kind of universal embedding.
A320894 is the complement in A028260.
A320911 lists all (not just distinct) products of squarefree semiprimes.
A339560 counts the partitions with these Heinz numbers.
A339661 has nonzero terms at these positions.
A001358 lists semiprimes, with squarefree case A006881.
A005117 lists squarefree numbers.
A320656 counts factorizations into squarefree semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A209816 counts multigraphical partitions (A320924).
- A320921 counts connected graphical partitions (A320923).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561 [this sequence]).
Cf. A001055, A001221, A002100, A007717, A030229, A112798, A320655, A320893, A338899, A338903, A339563, A339659.

sqs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sqs[n/d],Min@@#>d&]],{d,Select[Divisors[n],SquareFreeQ[#]&&PrimeOmega[#]==2&]}]];
Select[Range[100],sqs[#]!={}&]

A339561 \/ A320894 = A028260.

A339617 Number of non-graphical integer partitions of 2n.

Original entry on oeis.org

0, 1, 3, 6, 13, 25, 46, 81, 141, 234, 383, 615, 968, 1503, 2298, 3468, 5176, 7653, 11178, 16212, 23290, 33218, 46996, 66091, 92277, 128122, 176787, 242674, 331338, 450279, 608832, 819748, 1098907, 1467122, 1951020, 2584796, 3411998

Offset: 0

Gus Wiseman, Dec 13 2020

nonn

An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph. See A209816 for multigraphical partitions, A000070 for non-multigraphical partitions. Graphical partitions are counted by A000569.
The following are equivalent characteristics for any positive integer n:
(1) the prime indices of n can be partitioned into distinct strict pairs (a set of edges);
(2) n can be factored into distinct squarefree semiprimes;
(3) the prime signature of n is graphical.

			The a(1) = 1 through a(4) = 13 partitions:
  (2)  (4)    (6)      (8)
       (2,2)  (3,3)    (4,4)
       (3,1)  (4,2)    (5,3)
              (5,1)    (6,2)
              (3,2,1)  (7,1)
              (4,1,1)  (3,3,2)
                       (4,2,2)
                       (4,3,1)
                       (5,2,1)
                       (6,1,1)
                       (3,3,1,1)
                       (4,2,1,1)
                       (5,1,1,1)
For example, the partition (2,2,2,2) is not counted under a(4) because there are three possible graphs with the prescribed degrees:
  {{1,2},{1,3},{2,4},{3,4}}
  {{1,2},{1,4},{2,3},{3,4}}
  {{1,3},{1,4},{2,3},{2,4}}

Eric Weisstein's World of Mathematics, Graphical partition.

A006881 lists squarefree semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339659 counts graphical partitions of 2n into k parts.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A209816 counts multigraphical partitions (A320924).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 [this sequence] counts non-graphical partitions of 2n (A339618).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A007717, A025065, A320921, A320922, A338899, A339564, A339619, A339660, A339661.

prptns[m_]:=Union[Sort/@If[Length[m]==0,{{}},Join@@Table[Prepend[#,m[[ipr]]]&/@prptns[Delete[m,List/@ipr]],{ipr,Select[Prepend[{#},1]&/@Select[Range[2,Length[m]],m[[#]]>m[[#-1]]&],UnsameQ@@m[[#]]&]}]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n],Select[prptns[#],UnsameQ@@#&]=={}&]],{n,0,5}]

a(n) + A000569(n) = A000041(2*n).

A339618 Heinz numbers of non-graphical integer partitions of even numbers.

Original entry on oeis.org

3, 7, 9, 10, 13, 19, 21, 22, 25, 28, 29, 30, 34, 37, 39, 43, 46, 49, 52, 53, 55, 57, 61, 62, 63, 66, 70, 71, 75, 76, 79, 82, 84, 85, 87, 88, 89, 91, 94, 100, 101, 102, 107, 111, 113, 115, 116, 117, 118, 121, 129, 130, 131, 133, 134, 136, 138, 139, 146, 147

Offset: 1

Gus Wiseman, Dec 18 2020

nonn

An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph. Graphical partitions are counted by A000569.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.
The following are equivalent characteristics for any positive integer n:
(1) the multiset of prime indices of n can be partitioned into distinct strict pairs (a set of edges);
(2) n can be factored into distinct squarefree semiprimes;
(3) the unordered prime signature of n is graphical.

			The sequence of terms together with their prime indices begins:
      3: {2}         43: {14}        79: {22}
      7: {4}         46: {1,9}       82: {1,13}
      9: {2,2}       49: {4,4}       84: {1,1,2,4}
     10: {1,3}       52: {1,1,6}     85: {3,7}
     13: {6}         53: {16}        87: {2,10}
     19: {8}         55: {3,5}       88: {1,1,1,5}
     21: {2,4}       57: {2,8}       89: {24}
     22: {1,5}       61: {18}        91: {4,6}
     25: {3,3}       62: {1,11}      94: {1,15}
     28: {1,1,4}     63: {2,2,4}    100: {1,1,3,3}
     29: {10}        66: {1,2,5}    101: {26}
     30: {1,2,3}     70: {1,3,4}    102: {1,2,7}
     34: {1,7}       71: {20}       107: {28}
     37: {12}        75: {2,3,3}    111: {2,12}
     39: {2,6}       76: {1,1,8}    113: {30}
For example, there are three possible multigraphs with degrees (1,1,3,3):
  {{1,2},{1,2},{1,2},{3,4}}
  {{1,2},{1,2},{1,3},{2,4}}
  {{1,2},{1,2},{1,4},{2,3}}.
Since none of these is a graph, the Heinz number 100 belongs to the sequence.

Eric Weisstein's World of Mathematics, Graphical partition.

A181819 applied to A320894 gives this sequence.
A300061 is a superset.
A339617 counts these partitions.
A320922 ranks the complement, counted by A000569.
A006881 lists squarefree semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339659 counts graphical partitions of 2n into k parts.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A209816 counts multigraphical partitions (A320924).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618 [this sequence]).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001358, A007717, A050326, A320923, A338899.

strs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strs[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[#]]]&&strs[Times@@Prime/@nrmptn[#]]=={}&]

Equals A300061 \ A320922.

For all n, A181821(a(n)) and A304660(a(n)) belong to A320894.

A339655 Number of non-loop-graphical integer partitions of 2n.

Original entry on oeis.org

0, 0, 1, 3, 7, 14, 28, 51, 91, 156, 260, 425, 680, 1068, 1654, 2524, 3802, 5668, 8350, 12190, 17634, 25306, 36011, 50902, 71441, 99642

Offset: 0

Gus Wiseman, Dec 14 2020

An integer partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with equal source and target. See A339657 for the Heinz numbers, and A339656 for the complement.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct pairs;
(2) n can be factored into distinct semiprimes;
(3) the prime signature of n is loop-graphical.

			The a(2) = 1 through a(5) = 14 partitions (A = 10):
  (4)  (6)    (8)      (A)
       (4,2)  (4,4)    (5,5)
       (5,1)  (5,3)    (6,4)
              (6,2)    (7,3)
              (7,1)    (8,2)
              (5,2,1)  (9,1)
              (6,1,1)  (5,3,2)
                       (5,4,1)
                       (6,2,2)
                       (6,3,1)
                       (7,2,1)
                       (8,1,1)
                       (6,2,1,1)
                       (7,1,1,1)
For example, the seven normal loop-multigraphs with degrees y = (5,3,2) are:
  {{1,1},{1,1},{1,2},{2,2},{3,3}}
  {{1,1},{1,1},{1,2},{2,3},{2,3}}
  {{1,1},{1,1},{1,3},{2,2},{2,3}}
  {{1,1},{1,2},{1,2},{1,2},{3,3}}
  {{1,1},{1,2},{1,2},{1,3},{2,3}}
  {{1,1},{1,2},{1,3},{1,3},{2,2}}
  {{1,2},{1,2},{1,2},{1,3},{1,3}},
but since none of these is a loop-graph (because they are not strict), y is counted under a(5).

Eric Weisstein's World of Mathematics, Graphical partition.

A001358 lists semiprimes, with squarefree case A006881.
A006125 counts labeled graphs, with covering case A006129.
A062740 counts labeled connected loop-graphs.
A101048 counts partitions into semiprimes.
A320461 ranks normal loop-graphs.
A322661 counts covering loop-graphs.
A320655 counts factorizations into semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A209816 counts multigraphical partitions (A320924).
- A339655 (this sequence) counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A007717, A025065, A147878, A320732, A320921, A338898, A338902, A338912, A338913, A339659, A339660, A339662.

spsbin[{}]:={{}};spsbin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsbin[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpsbin[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@spsbin[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n],Select[mpsbin[#],UnsameQ@@#&]=={}&]],{n,0,5}]

A058696(n) = a(n) + A339656(n).

a(7)-a(25) from Andrew Howroyd, Jan 10 2024

A339656 Number of loop-graphical integer partitions of 2n.

Original entry on oeis.org

1, 2, 4, 8, 15, 28, 49, 84, 140, 229, 367, 577, 895, 1368, 2064, 3080, 4547, 6642, 9627, 13825, 19704, 27868, 39164, 54656, 75832, 104584

Offset: 0

Gus Wiseman, Dec 14 2020

An integer partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with two equal vertices. See A339658 for the Heinz numbers, and A339655 for the complement.
The following are equivalent characteristics for any positive integer n:
(1) the multiset of prime factors of n can be partitioned into distinct pairs, i.e., into a set of edges and loops;
(2) n can be factored into distinct semiprimes;
(3) the unordered prime signature of n is loop-graphical.

			The a(0) = 1 through a(4) = 15 partitions:
  ()  (2)    (2,2)      (3,3)          (3,3,2)
      (1,1)  (3,1)      (2,2,2)        (4,2,2)
             (2,1,1)    (3,2,1)        (4,3,1)
             (1,1,1,1)  (4,1,1)        (2,2,2,2)
                        (2,2,1,1)      (3,2,2,1)
                        (3,1,1,1)      (3,3,1,1)
                        (2,1,1,1,1)    (4,2,1,1)
                        (1,1,1,1,1,1)  (5,1,1,1)
                                       (2,2,2,1,1)
                                       (3,2,1,1,1)
                                       (4,1,1,1,1)
                                       (2,2,1,1,1,1)
                                       (3,1,1,1,1,1)
                                       (2,1,1,1,1,1,1)
                                       (1,1,1,1,1,1,1,1)
For example, there are four possible loop-graphs with degrees y = (2,2,1,1), namely
  {{1,1},{2,2},{3,4}}
  {{1,1},{2,3},{2,4}}
  {{1,2},{1,3},{2,4}}
  {{1,2},{1,4},{2,3}}
  {{1,3},{1,4},{2,2}},
so y is counted under a(3). On the other hand, there are two possible loop-multigraphs with degrees z = (4,2), namely
  {{1,1},{1,1},{2,2}}
  {{1,1},{1,2},{1,2}},
but neither of these is a loop-graph, so z is not counted under a(3).

Eric Weisstein's World of Mathematics, Graphical partition.

A339658 ranks these partitions.
A001358 lists semiprimes, with squarefree case A006881.
A006125 counts labeled graphs, with covering case A006129.
A027187 counts partitions of even length, ranked by A028260.
A062740 counts labeled connected loop-graphs.
A320461 ranks normal loop-graphs.
A320655 counts factorizations into semiprimes.
A322353 counts factorizations into distinct semiprimes.
A322661 counts covering loop-graphs.
A339845 counts the same partitions by length, or A339844 with zeros.
The following count vertex-degree partitions and give their Heinz numbers:
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A000569 counts graphical partitions (A320922).
- A058696 counts partitions of 2n (A300061).
- A209816 counts multigraphical partitions (A320924).
- A321728 is conjectured to count non-half-loop-graphical partitions of n.
- A339617 counts non-graphical partitions of 2n (A339618).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 [this sequence] counts loop-graphical partitions (A339658).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A001222, A025065, A095268, A101048, A320656, A320921, A338902, A338912, A338913, A339659.

spsbin[{}]:={{}};spsbin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsbin[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpsbin[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]& /@spsbin[Range[Length[set]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n],Select[mpsbin[#],UnsameQ@@#&]!={}&]],{n,0,5}]

A058696(n) = a(n) + A339655(n).

a(8)-a(25) from Andrew Howroyd, Jan 10 2024

A029889 Number of graphical partitions (degree-vectors for graphs with n vertices, allowing self-loops which count as degree 1; or possible ordered row-sum vectors for a symmetric 0-1 matrix).

Original entry on oeis.org

1, 2, 5, 14, 43, 140, 476, 1664, 5939, 21518, 78876, 291784, 1087441, 4077662, 15369327, 58184110, 221104527, 842990294, 3223339023

Offset: 0

torsten.sillke(AT)lhsystems.com

I call loops of degree one half-loops, so these are half-loop-graphs or graphs with half-loops. - Gus Wiseman, Dec 31 2020

			From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(3) = 14 sorted degree sequences:
  ()  (0)  (0,0)  (0,0,0)
      (1)  (1,0)  (1,0,0)
           (1,1)  (1,1,0)
           (2,1)  (2,1,0)
           (2,2)  (2,2,0)
                  (1,1,1)
                  (2,1,1)
                  (3,1,1)
                  (2,2,1)
                  (3,2,1)
                  (2,2,2)
                  (3,2,2)
                  (3,3,2)
                  (3,3,3)
For example, the half-loop-graph
  {{1,3},{3}}
has degrees (1,0,2), so (2,1,0) is counted under a(3). The half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees (3,2,2), so (3,2,2) is counted under a(3).
(End)

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).
Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.
Index entries for sequences related to graphical partitions

Cf. A000569, A004250, A029890, A029891.
Non-half-loop-graphical partitions are conjectured to be counted by A321728.
The covering case (no zeros) is A339843.
MM-numbers of half-loop-graphs are given by A340018 and A340019.
A004251 counts degree sequences of graphs, with covering case A095268.
A320663 counts unlabeled multiset partitions into singletons/pairs.
A339659 is a triangle counting graphical partitions.
A339844 counts degree sequences of loop-graphs, with covering case A339845.
Cf. A006125, A006129, A027187, A028260, A062740, A096373, A322661, A339560.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Subsets[Subsets[Range[n],{1,2}]]]],{n,0,5}] (* Gus Wiseman, Dec 31 2020 *)

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

a(n) = A029890(n) + A029891(n). - Andrew Howroyd, Apr 18 2021

a(0) = 1 prepended by Gus Wiseman, Dec 31 2020

A095268 Number of distinct degree sequences among all n-vertex graphs with no isolated vertices.

Original entry on oeis.org

1, 0, 1, 2, 7, 20, 71, 240, 871, 3148, 11655, 43332, 162769, 614198, 2330537, 8875768, 33924859, 130038230, 499753855, 1924912894, 7429160296, 28723877732, 111236423288, 431403470222, 1675316535350, 6513837679610, 25354842100894, 98794053269694, 385312558571890, 1504105116253904, 5876236938019298, 22974847399695092

Offset: 0

Eric W. Weisstein, May 31 2004

nonn

A002494 is the number of graphs on n nodes with no isolated points and A095268 is the number of these graphs having distinct degree sequences.
Now that more terms have been computed, we can see that this is not the self-convolution of any integer sequence. - Paul D. Hanna, Aug 18 2006
Is it true that a(n+1)/a(n) tends to 4? Is there a heuristic argument why this might be true? - Gordon F. Royle, Aug 29 2006
Previous values a(30) = 5876236938019300 from Lorand Lucz, Jul 07 2013 and a(31) = 22974847474172100 from Lorand Lucz, Sep 03 2013 are wrong. New values a(30) and a(31) independently computed Kai Wang and Axel Kohnert. - Vaclav Kotesovec, Apr 15 2016
In the article by A. Iványi, G. Gombos, L. Lucz, T. Matuszka: "Parallel enumeration of degree sequences of simple graphs II" is in the tables on pages 258 and 261 a wrong value a(31) = 22974847474172100, but in the abstract another wrong value a(31) = 22974847474172374. - Vaclav Kotesovec, Apr 15 2016
The asymptotic formula given below confirms that a(n+1)/a(n) tends to 4. - Tom Johnston, Jan 18 2023

			a(4) = 7 because a 4-vertex graph with no isolated vertices can have degree sequence 1111, 2211, 2222, 3111, 3221, 3322 or 3333.
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(3) = 7 sorted degree sequences (empty column indicated by dot):
  ()  .  (1,1)  (2,1,1)  (1,1,1,1)
                (2,2,2)  (2,2,1,1)
                         (2,2,2,2)
                         (3,1,1,1)
                         (3,2,2,1)
                         (3,3,2,2)
                         (3,3,3,3)
For example, the complete graph K_4 has degrees y = (3,3,3,3), so y is counted under a(4). On the other hand, the only half-loop-graphs (up to isomorphism) with degrees y = (4,2,2,1) are: {(1),(1,2),(1,3),(1,4),(2,3)} and {(1),(2),(3),(1,2),(1,3),(1,4)}; and since neither of these is a graph (due to having half-loops), y is not counted under a(4).
(End)

Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Table of n, a(n) for n = 0..1651 (terms 0 through 79 from Kai Wang)
Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Counting graphic sequences via integrated random walks, arXiv:2301.07022 [math.CO], 2023.
A. Iványi, L. Lucz, T. Matuszka and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapiantiae, Inform.4 (2) (2012) 260-288.
A. Iványi, G. Gombos, L. Lucz, and T. Matuszka, Parallel enumeration of degree sequences of simple graphs II, Acta Universitatis Sapientiae, Informatica, Volume 5, Issue 2 (Dec 2013).
A. Iványi, L. Lucz, T. F. Móri and P. Sótér, On Erdős-Gallai and Havel-Hakimi algorithms, Acta Univ. Sapiantiae, Inform. 3 (2) (2011) 230-268.
A. Kohnert, Number of different degree sequences of a graph with no isolated vertices, 2016.
Frank Ruskey, Alley CATs in Search of Good Homes
Kai Wang, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms. But a(30) and a(31) are different.
Eric Weisstein's World of Mathematics, Degree sequence
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

Cf. A002494, A004250, A007721 (analog for connected graphs), A271831.
Counting the same partitions by sum gives A000569.
Allowing isolated nodes gives A004251.
The version with half-loops is A029889, with covering case A339843.
Covering simple graphs are ranked by A309356 and A320458.
Graphical partitions are ranked by A320922.
The version with loops is A339844, with covering case A339845.
A006125 counts simple graphs, with covering case A006129.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A339659 is a triangle counting graphical partitions.
Cf. A007717, A096373, A181819, A320921, A322661, A339559, A339560.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&]]],{n,0,5}] (* Gus Wiseman, Dec 31 2020 *)

a(n) ~ c * 4^n / n^(3/4) for some c > 0. Computational estimates suggest c ≈ 0.074321. - Tom Johnston, Jan 18 2023

Edited by N. J. A. Sloane, Aug 26 2006
More terms from Gordon F. Royle, Aug 21 2006
a(21) and a(22) from Frank Ruskey, Aug 29 2006
a(23) from Frank Ruskey, Aug 31 2006
a(24)-a(29) from Matuszka Tamás, Jan 10 2013
a(30)-a(31) from articles by Kai Wang and Axel Kohnert, Apr 15 2016
a(0) = 1 and a(1) = 0 prepended by Gus Wiseman, Dec 31 2020

cp's OEIS Frontend

A004250 Number of partitions of n into 3 or more parts.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A004251 Number of graphical partitions (degree-vectors for simple graphs with n vertices, or possible ordered row-sum vectors for a symmetric 0-1 matrix with diagonal values 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339560 Number of integer partitions of n that can be partitioned into distinct pairs of distinct parts, i.e., into a set of edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A339561 Products of distinct squarefree semiprimes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339617 Number of non-graphical integer partitions of 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339618 Heinz numbers of non-graphical integer partitions of even numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339655 Number of non-loop-graphical integer partitions of 2n.

Views

Author

Keywords

Comments

Examples