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

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.

A338914 Number of integer partitions of n of even length whose greatest multiplicity is at most half their length.

Original entry on oeis.org

1, 0, 0, 1, 1, 2, 3, 4, 6, 9, 11, 16, 23, 29, 39, 53, 69, 90, 118, 150, 195, 249, 315, 398, 506, 629, 789, 982, 1219, 1504, 1860, 2277, 2798, 3413, 4161, 5051, 6137, 7406, 8948, 10765, 12943, 15503, 18571, 22153, 26432, 31432, 37352, 44268, 52444, 61944, 73141

Offset: 0

Gus Wiseman, Dec 09 2020

nonn

These are also integer partitions that can be partitioned into not necessarily distinct edges (pairs of distinct parts). For example, (3,3,2,2) can be partitioned as {{2,3},{2,3}}, so is counted under a(10), but (4,2,2,2) and (4,2,1,1,1,1) cannot be partitioned into edges. The multiplicities of such a partition form a multigraphical partition (A209816, A320924).

			The a(3) = 1 through a(10) = 11 partitions:
  (21)  (31)  (32)  (42)    (43)    (53)    (54)      (64)
              (41)  (51)    (52)    (62)    (63)      (73)
                    (2211)  (61)    (71)    (72)      (82)
                            (3211)  (3221)  (81)      (91)
                                    (3311)  (3321)    (3322)
                                    (4211)  (4221)    (4321)
                                            (4311)    (4411)
                                            (5211)    (5221)
                                            (222111)  (5311)
                                                      (6211)
                                                      (322111)

Eric Weisstein's World of Mathematics, Graphical partition.

A096373 counts the complement in even-length partitions.
A320911 gives the Heinz numbers of these partitions.
A339560 is the strict case.
A339562 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.
A320656 counts factorizations into squarefree semiprimes.
A320921 counts connected graphical partitions, ranked by A320923.
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.
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).
- 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, A001221, A005117, A007717, A030229, A320655, A322353, A338899, A338903.

Table[Length[Select[IntegerPartitions[n],EvenQ[Length[#]]&&Max@@Length/@Split[#]<=Length[#]/2&]],{n,0,30}]

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

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

A338915 Number of integer partitions of n that have an even number of parts and cannot be partitioned into distinct pairs of not necessarily distinct parts.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 1, 1, 4, 2, 6, 6, 12, 12, 20, 22, 38, 42, 60, 73, 101, 124, 164, 203, 266, 319, 415, 507, 649, 786, 983, 1198, 1499, 1797, 2234, 2673, 3303, 3952, 4826, 5753, 6999, 8330, 10051, 11943, 14357, 16956, 20322, 23997, 28568, 33657, 39897, 46879

Offset: 0

Gus Wiseman, Dec 10 2020

nonn

The multiplicities of such a partition form a non-loop-graphical partition (A339655, A339657).

			The a(7) = 1 through a(12) = 12 partitions:
  211111  2222      411111    222211      222221      3333
          221111    21111111  331111      611111      222222
          311111              511111      22211111    441111
          11111111            22111111    32111111    711111
                              31111111    41111111    22221111
                              1111111111  2111111111  32211111
                                                      33111111
                                                      42111111
                                                      51111111
                                                      2211111111
                                                      3111111111
                                                      111111111111
For example, the partition y = (3,2,2,1,1,1,1,1) can be partitioned into pairs in just three ways:
  {{1,1},{1,1},{1,2},{2,3}}
  {{1,1},{1,1},{1,3},{2,2}}
  {{1,1},{1,2},{1,2},{1,3}}
None of these is strict, so y is counted under a(12).

Eric Weisstein's World of Mathematics, Graphical partition.

The Heinz numbers of these partitions are A320892.
The complement in even-length partitions is A338916.
A000070 counts non-multigraphical partitions of 2n, ranked by A339620.
A000569 counts graphical partitions, ranked by A320922.
A001358 lists semiprimes, with squarefree case A006881.
A058696 counts partitions of even numbers, ranked by A300061.
A209816 counts multigraphical partitions, ranked by A320924.
A320655 counts factorizations into semiprimes.
A322353 counts factorizations into distinct 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.
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).
- 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, A320656, A320732, A320893, A338898, A338902.

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

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

More terms from Jinyuan Wang, Feb 14 2025

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.

A338916 Number of integer partitions of n that can be partitioned into distinct pairs of (possibly equal) parts.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 5, 6, 8, 12, 16, 21, 28, 37, 49, 64, 80, 104, 135, 169, 216, 268, 341, 420, 527, 654, 809, 991, 1218, 1488, 1828, 2213, 2687, 3262, 3934, 4754, 5702, 6849, 8200, 9819, 11693, 13937, 16562, 19659, 23262, 27577, 32493, 38341, 45112, 53059, 62265

Offset: 0

Gus Wiseman, Dec 10 2020

nonn

The multiplicities of such a partition form a loop-graphical partition (A339656, A339658).

			The a(2) = 1 through a(10) = 16 partitions:
  (11)  (21)  (22)  (32)    (33)    (43)    (44)    (54)      (55)
              (31)  (41)    (42)    (52)    (53)    (63)      (64)
                    (2111)  (51)    (61)    (62)    (72)      (73)
                            (2211)  (2221)  (71)    (81)      (82)
                            (3111)  (3211)  (3221)  (3222)    (91)
                                    (4111)  (3311)  (3321)    (3322)
                                            (4211)  (4221)    (3331)
                                            (5111)  (4311)    (4222)
                                                    (5211)    (4321)
                                                    (6111)    (4411)
                                                    (222111)  (5221)
                                                    (321111)  (5311)
                                                              (6211)
                                                              (7111)
                                                              (322111)
                                                              (421111)
For example, the partition (4,2,1,1,1,1) can be partitioned into {{1,1},{1,2},{1,4}}, and thus is counted under a(10).

Eric Weisstein's World of Mathematics, Graphical partition.

A320912 gives the Heinz numbers of these partitions.
A338915 counts the complement in even-length partitions.
A339563 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.
A058696 counts partitions of even numbers, ranked by A300061.
A209816 counts multigraphical partitions, ranked by A320924.
A320655 counts factorizations into semiprimes.
A322353 counts factorizations into distinct 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.
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).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A007717, A025065, A320656, A320732, A320893, A320921, A338898, A338902, A339564.

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

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

More terms from Jinyuan Wang, Feb 14 2025

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

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

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

A338914 Number of integer partitions of n of even length whose greatest multiplicity is at most half their length.

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

A338915 Number of integer partitions of n that have an even number of parts and cannot be partitioned into distinct pairs of not necessarily distinct parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links