A339741 -id:A339741 - cp's OEIS frontend

A339846 Number of even-length factorizations of n into factors > 1.

1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 2, 0, 1, 1, 3, 0, 2, 0, 2, 1, 1, 0, 4, 1, 1, 1, 2, 0, 3, 0, 3, 1, 1, 1, 5, 0, 1, 1, 4, 0, 3, 0, 2, 2, 1, 0, 6, 1, 2, 1, 2, 0, 4, 1, 4, 1, 1, 0, 6, 0, 1, 2, 6, 1, 3, 0, 2, 1, 3, 0, 8, 0, 1, 2, 2, 1, 3, 0, 6, 3, 1, 0, 6, 1, 1, 1, 4, 0, 6, 1, 2, 1, 1, 1, 10, 0, 2, 2, 5, 0, 3, 0, 4, 3

Offset: 1

Gus Wiseman, Dec 28 2020

nonn

			The a(n) factorizations for n = 12, 16, 24, 36, 48, 72, 96, 120:
  2*6  2*8      3*8      4*9      6*8      8*9      2*48         2*60
  3*4  4*4      4*6      6*6      2*24     2*36     3*32         3*40
       2*2*2*2  2*12     2*18     3*16     3*24     4*24         4*30
                2*2*2*3  3*12     4*12     4*18     6*16         5*24
                         2*2*3*3  2*2*2*6  6*12     8*12         6*20
                                  2*2*3*4  2*2*2*9  2*2*3*8      8*15
                                           2*2*3*6  2*2*4*6      10*12
                                           2*3*3*4  2*3*4*4      2*2*5*6
                                                    2*2*2*12     2*3*4*5
                                                    2*2*2*2*2*3  2*2*2*15
                                                                 2*2*3*10

The case of set partitions (or n squarefree) is A024430.
The case of partitions (or prime powers) is A027187.
The ordered version is A174725, odd: A174726.
The odd-length factorizations are counted by A339890.
A001055 counts factorizations, with strict case A045778.
A001358 lists semiprimes, with squarefree case A006881.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A316439 counts factorizations by product and length.
A340102 counts odd-length factorizations into odd factors.
Cf. A002033, A007716, A027193, A050320, A058695, A074206, A236913, A320655, A320656, A320732.

g:= proc(n, k, t) option remember; `if`(n>k, 0, t)+
      `if`(isprime(n), 0, add(`if`(d>k, 0, g(n/d, d, 1-t)),
          d=numtheory[divisors](n) minus {1, n}))
    end:
a:= n-> `if`(n=1, 1, g(n$2, 0)):
seq(a(n), n=1..100);  # Alois P. Heinz, Dec 30 2020

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n],EvenQ@Length[#]&]],{n,100}]

A339846(n, m=n, e=1) = if(1==n, e, sumdiv(n, d, if((d>1)&&(d<=m), A339846(n/d, d, 1-e)))); \\ Antti Karttunen, Oct 22 2023

a(n) + A339890(n) = A001055(n).

Data section extended up to a(105) by Antti Karttunen, Oct 22 2023

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

A122848 Exponential Riordan array (1, x(1+x/2)).

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 3, 1, 0, 0, 3, 6, 1, 0, 0, 0, 15, 10, 1, 0, 0, 0, 15, 45, 15, 1, 0, 0, 0, 0, 105, 105, 21, 1, 0, 0, 0, 0, 105, 420, 210, 28, 1, 0, 0, 0, 0, 0, 945, 1260, 378, 36, 1, 0, 0, 0, 0, 0, 945, 4725, 3150, 630, 45, 1, 0, 0, 0, 0, 0, 0, 10395, 17325, 6930, 990, 55, 1, 0, 0

Offset: 0

Paul Barry, Sep 14 2006

Entries are Bessel polynomial coefficients. Row sums are A000085. Diagonal sums are A122849. Inverse is A122850. Product of A007318 and A122848 gives A100862.
T(n,k) is the number of self-inverse permutations of {1,2,...,n} having exactly k cycles. - Geoffrey Critzer, May 08 2012
Bessel numbers of the second kind. For relations to the Hermite polynomials and the Catalan (A033184 and A009766) and Fibonacci (A011973, A098925, and A092865) matrices, see Yang and Qiao. - Tom Copeland, Dec 18 2013.
Also the inverse Bell transform of the double factorial of odd numbers Product_{k= 0..n-1} (2*k+1) (A001147). For the definition of the Bell transform see A264428 and for cross-references A265604. - Peter Luschny, Dec 31 2015

			Triangle begins:
    1
    0    1
    0    1    1
    0    0    3    1
    0    0    3    6    1
    0    0    0   15   10    1
    0    0    0   15   45   15    1
    0    0    0    0  105  105   21    1
    0    0    0    0  105  420  210   28    1
    0    0    0    0    0  945 1260  378   36    1
From _Gus Wiseman_, Jan 12 2021: (Start)
As noted above, a(n) is the number of set partitions of {1..n} into k singletons or pairs. This is also the number of set partitions of subsets of {1..n} into n - k pairs. In the first case, row n = 5 counts the following set partitions:
  {{1},{2,3},{4,5}}  {{1},{2},{3},{4,5}}  {{1},{2},{3},{4},{5}}
  {{1,2},{3},{4,5}}  {{1},{2},{3,4},{5}}
  {{1,2},{3,4},{5}}  {{1},{2,3},{4},{5}}
  {{1,2},{3,5},{4}}  {{1,2},{3},{4},{5}}
  {{1},{2,4},{3,5}}  {{1},{2},{3,5},{4}}
  {{1},{2,5},{3,4}}  {{1},{2,4},{3},{5}}
  {{1,3},{2},{4,5}}  {{1},{2,5},{3},{4}}
  {{1,3},{2,4},{5}}  {{1,3},{2},{4},{5}}
  {{1,3},{2,5},{4}}  {{1,4},{2},{3},{5}}
  {{1,4},{2},{3,5}}  {{1,5},{2},{3},{4}}
  {{1,4},{2,3},{5}}
  {{1,4},{2,5},{3}}
  {{1,5},{2},{3,4}}
  {{1,5},{2,3},{4}}
  {{1,5},{2,4},{3}}
In the second case, we have:
  {{1,2},{3,4}}  {{1,2}}  {}
  {{1,2},{3,5}}  {{1,3}}
  {{1,2},{4,5}}  {{1,4}}
  {{1,3},{2,4}}  {{1,5}}
  {{1,3},{2,5}}  {{2,3}}
  {{1,3},{4,5}}  {{2,4}}
  {{1,4},{2,3}}  {{2,5}}
  {{1,4},{2,5}}  {{3,4}}
  {{1,4},{3,5}}  {{3,5}}
  {{1,5},{2,3}}  {{4,5}}
  {{1,5},{2,4}}
  {{1,5},{3,4}}
  {{2,3},{4,5}}
  {{2,4},{3,5}}
  {{2,5},{3,4}}
(End)

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Peter Bala, Generalized Dobinski formulas
Richell O. Celeste, Roberto B. Corcino, and Ken Joffaniel M. Gonzales, Two Approaches to Normal Order Coefficients, Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.5.
Tom Copeland, Infinitesimal Generators, the Pascal Pyramid, and the Witt and Virasoro Algebras
H. Han and S. Seo, Combinatorial proofs of inverse relations and log-concavity for Bessel numbers, Eur. J. Combinat. 29 (7) (2008) 1544-1554. [From _R. J. Mathar_, Mar 20 2009]
Robert S. Maier, Boson Operator Ordering Identities from Generalized Stirling and Eulerian Numbers, arXiv:2308.10332 [math.CO], 2023. See p. 18.
S. Yang and Z. Qiao, The Bessel Numbers and Bessel Matrices, Journal of Mathematical Research & Exposition, July, 2011, Vol. 31, No. 4, pp. 627-636. [From _Tom Copeland_, Dec 18 2013]

Cf. A001497, A008275, A039755, A096713, A104556, A113278, A130757.
Row sums are A000085.
Column sums are A001515.
Same as A049403 but with a first column k = 0.
The same set partitions counted by number of pairs are A100861.
Reversing rows gives A111924 (without column k = 0).
A047884 counts standard Young tableaux by size and greatest row length.
A238123 counts standard Young tableaux by size and least row length.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A322661 counts labeled covering half-loop-graphs.
A339742 counts factorizations into distinct primes or squarefree semiprimes.
Cf. A000110, A000258, A320732, A321729, A339741, A339887.

# The function BellMatrix is defined in A264428.
BellMatrix(n -> `if`(n<2,1,0), 9); # Peter Luschny, Jan 27 2016

t[n_, k_] := k!*Binomial[n, k]/((2 k - n)!*2^(n - k)); Table[ t[n, k], {n, 0, 11}, {k, 0, n}] // Flatten
(* Second program: *)
rows = 12;
t = Join[{1, 1}, Table[0, rows]];
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 0, rows}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 23 2018,after Peter Luschny *)
sbs[{}]:={{}};sbs[set:{i_,_}]:=Join@@Function[s,(Prepend[#1,s]&)/@sbs[Complement[set,s]]]/@Cases[Subsets[set],{i}|{i,_}];
Table[Length[Select[sbs[Range[n]],Length[#]==k&]],{n,0,6},{k,0,n}] (* Gus Wiseman, Jan 12 2021 *)

{T(n,k)=if(2*kn, 0, n!/(2*k-n)!/(n-k)!*2^(k-n))} /* Michael Somos, Oct 03 2006 */

# uses[inverse_bell_transform from A265605]
multifact_2_1 = lambda n: prod(2*k + 1 for k in (0..n-1))
inverse_bell_matrix(multifact_2_1, 9) # Peter Luschny, Dec 31 2015

Number triangle T(n,k) = k!*C(n,k)/((2k-n)!*2^(n-k)).
T(n,k) = A001498(k,n-k). - Michael Somos, Oct 03 2006
E.g.f.: exp(y(x+x^2/2)). - Geoffrey Critzer, May 08 2012
Triangle equals the matrix product A008275*A039755. Equivalently, the n-th row polynomial R(n,x) is given by the Type B Dobinski formula R(n,x) = exp(-x/2)*Sum_{k>=0} P(n,2*k+1)*(x/2)^k/k!, where P(n,x) = x*(x-1)*...*(x-n+1) denotes the falling factorial polynomial. Cf. A113278. - Peter Bala, Jun 23 2014
From Daniel Checa, Aug 28 2022: (Start)
E.g.f. for the m-th column: (x^2/2+x)^m/m!.
T(n,k) = T(n-1,k-1) + (n-1)*T(n-2,k-1) for n>1 and k=1..n, T(0,0) = 1. (End)

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

A382075 Numbers whose prime indices can be partitioned into a set of sets with distinct sums.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 26, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 50, 51, 52, 53, 55, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82, 83, 84

Offset: 1

Gus Wiseman, Mar 19 2025

nonn

First differs from A212167 in having 3600.
First differs from A335433 in lacking 72.
First differs from A339741 in having 1080.
First differs from A345172 in lacking 72.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
Also numbers that can be written as a product of squarefree numbers with distinct sums of prime indices.

			The prime indices of 1080 are {1,1,1,2,2,2,3}, and {{1},{2},{1,2},{1,2,3}} is a partition into a set of sets with distinct sums, so 1080 is in the sequence.

Twice-partitions of this type are counted by A279785, see also A358914.
These are positions of terms > 0 in A381633, see A321469, A381078, A381634.
For constant instead of strict blocks see A381635, A381636, A381716.
Normal multiset partitions into sets with distinct sums are counted by A381718.
The complement is A381806, counted by A381990.
The case of a unique choice is A381870, counted by A382079, see A382078.
Partitions of this type are counted by A381992.
For distinct blocks instead of block-sums we have A382200, complement A293243.
MM-numbers of multiset partitions into sets with distinct sums are A382201.
Normal multisets of this type are counted by A382216, see also A382214.
A001055 counts multiset partitions of prime indices, strict A045778.
A050320 counts multiset partitions of prime indices into sets.
A050326 counts multiset partitions of prime indices into distinct sets.
A055396 gives least prime index, greatest A061395.
A056239 adds up prime indices, row sums of A112798.
A317141 counts coarsenings of prime indices, refinements A300383.
Cf. A089259, A270995, A293511, A318360, A381441, A382077.
Cf. A000720, A001222, A005117, A050345, A292432, A302494.

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]]]];
Select[Range[100],Length[Select[mps[prix[#]], And@@UnsameQ@@@#&&UnsameQ@@Total/@#&]]>0&]

A382200 Numbers that can be written as a product of distinct squarefree numbers.

Original entry on oeis.org

Offset: 1

Gus Wiseman, Mar 21 2025

nonn

First differs from A339741 in having 1080.
First differs from A382075 in having 18000.
These are positions of positive terms in A050326, complement A293243.
Also numbers whose prime indices can be partitioned into distinct sets.
Differs from A212167, which does not include 18000 = 2^4*3^2*5^3, for example. - R. J. Mathar, Mar 23 2025

			The prime indices of 1080 are {1,1,1,2,2,2,3}, and {{1},{2},{1,2},{1,2,3}} is a partition into a set of sets, so 1080 is in the sequence.
We have 18000 = 2*5*6*10*30, so 18000 is in the sequence.

Robert Israel, Table of n, a(n) for n = 1..10000

Twice-partitions of this type are counted by A279785, see also A358914.
Normal multisets not of this type are counted by A292432, strong A292444.
The complement is A293243, counted by A050342.
The case of a unique choice is A293511.
MM-numbers of multiset partitions into distinct sets are A302494.
For distinct block-sums instead of blocks we have A382075, counted by A381992.
Partitions of this type are counted by A382077, complement A382078.
Normal multisets of this type are counted by A382214, strong A381996.
A001055 counts multiset partitions of prime indices, strict A045778.
A050320 counts multiset partitions of prime indices into sets.
A050326 counts multiset partitions of prime indices into distinct sets.
A317141 counts coarsenings of prime indices, refinements A300383.
Cf. A000720, A001222, A005117, A050345, A089259, A116539, A270995, A381441, A382201, A382216.

N:= 1000: # to get all terms <= N
A:= Vector(N):
A[1]:= 1:
for n from 2 to N do
  if numtheory:-issqrfree(n) then
      S:= [$1..N/n]; T:= n*S; A[T]:= A[T]+A[S]
    fi;
od:
remove(t -> A[t]=0, [$1..N]); # Robert Israel, Apr 21 2025

sqfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sqfacs[n/d],Min@@#>d&]],{d,Select[Rest[Divisors[n]],SquareFreeQ]}]];
Select[Range[100],Length[sqfacs[#]]>0&]

A322353 Number of factorizations of n into distinct semiprimes; a(1) = 1 by convention.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 2, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 2, 1, 1, 1, 1, 0, 2, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0

Offset: 1

Antti Karttunen, Dec 06 2018

nonn

A semiprime (A001358) is a product of any two prime numbers. In the even case, these factorizations have A001222(n)/2 factors. - Gus Wiseman, Dec 31 2020

Records 1, 2, 3, 4, 5, 9, 13, 15, 17, ... occur at 1, 60, 210, 840, 1260, 4620, 27720, 30030, 69300, ...

			a(4) = 1, as there is just one way to factor 4 into distinct semiprimes, namely as {4}.
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(n) factorizations for n = 60, 210, 840, 1260, 4620, 12600, 18480:
  4*15   6*35    4*6*35    4*9*35    4*15*77    4*6*15*35    4*6*10*77
  6*10   10*21   4*10*21   4*15*21   4*21*55    4*6*21*25    4*6*14*55
         14*15   4*14*15   6*10*21   4*33*35    4*9*10*35    4*6*22*35
                 6*10*14   6*14*15   6*10*77    4*9*14*25    4*10*14*33
                           9*10*14   6*14*55    4*10*15*21   4*10*21*22
                                     6*22*35    6*10*14*15   4*14*15*22
                                     10*14*33                6*10*14*22
                                     10*21*22
                                     14*15*22
(End)

Unlabeled multiset partitions of this type are counted by A007717.
The version for partitions is A112020, or A101048 without distinctness.
The non-strict version is A320655.
Positions of zeros include A320892.
Positions of nonzero terms are A320912.
The case of squarefree factors is A339661, or A320656 without distinctness.
Allowing prime factors gives A339839, or A320732 without distinctness.
A322661 counts loop-graphs, ranked by A320461.
A001055 counts factorizations, with strict case A045778.
A001358 lists semiprimes, with squarefree case A006881.
A027187 counts partitions of even length, ranked by A028260.
A037143 lists primes and semiprimes.
A338898/A338912/A338913 give the prime indices of semiprimes.
A339846 counts even-length factorizations, with ordered version A174725.
Cf. A001221, A006125, A006129, A028260, A320893, A338915, A339841.

Table[Count[Subsets[Select[Divisors[n], PrimeOmega[#] == 2 &]], ?(Times @@ # == n &)], {n, 105}] (* _Michael De Vlieger, Dec 11 2020 *)

A322353(n, m=n) = if(1==n, 1, my(s=0); fordiv(n, d, if((2==bigomega(d)&&(d<=m)), s += A322353(n/d, d-1))); (s)); \\ Antti Karttunen, Dec 10 2020

a(n) = Sum_{d|n} (-1)^A001222(d) * A339839(n/d). - Gus Wiseman, Dec 31 2020

A339888 Number of non-isomorphic multiset partitions of weight n into singletons or strict pairs.

Original entry on oeis.org

1, 1, 3, 5, 13, 23, 55, 104, 236, 470, 1039, 2140, 4712, 9962, 21961, 47484, 105464, 232324, 521338, 1167825, 2651453, 6031136, 13863054, 31987058, 74448415, 174109134, 410265423, 971839195, 2317827540, 5558092098, 13412360692, 32542049038, 79424450486

Offset: 0

Gus Wiseman, Jan 09 2021

nonn

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 13 multiset partitions:
  {{1}}  {{1,2}}    {{1},{2,3}}    {{1,2},{1,2}}
         {{1},{1}}  {{2},{1,2}}    {{1,2},{3,4}}
         {{1},{2}}  {{1},{1},{1}}  {{1,3},{2,3}}
                    {{1},{2},{2}}  {{1},{1},{2,3}}
                    {{1},{2},{3}}  {{1},{2},{1,2}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{2},{2},{1,2}}
                                   {{1},{1},{1},{1}}
                                   {{1},{1},{2},{2}}
                                   {{1},{2},{2},{2}}
                                   {{1},{2},{3},{3}}
                                   {{1},{2},{3},{4}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

The version for set partitions is A000085, with ordered version A080599.
The case of integer partitions is 1 + A004526(n), ranked by A003586.
Non-isomorphic multiset partitions are counted by A007716.
The case without singletons is A007717.
The version allowing non-strict pairs (x,x) is A320663.
A001190 counts rooted trees with out-degrees <= 2, ranked by A292050.
A339742 counts factorizations into distinct primes or squarefree semiprimes.
A339887 counts factorizations into primes or squarefree semiprimes.
Cf. A001055, A007718, A316983, A319616, A320656, A321729, A339740, A339741.

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
gs(v) = {sum(i=2, #v, sum(j=1, i-1, my(g=gcd(v[i], v[j])); g*x^(2*v[i]*v[j]/g))) + sum(i=1, #v, my(r=v[i]); (1 + (1+r)%2)*x^r + ((r-1)\2)*x^(2*r))}
a(n)={if(n==0, 1, my(s=0); forpart(p=n, s+=permcount(p)*EulerT(Vec(gs(p) + O(x*x^n), -n))[n]); s/n!)} \\ Andrew Howroyd, Apr 16 2021

Terms a(11) and beyond from Andrew Howroyd, Apr 16 2021

A368598 Number of non-isomorphic n-element sets of singletons or pairs of elements of {1..n}, or unlabeled loop-graphs with n edges and up to n vertices.

Original entry on oeis.org

1, 1, 2, 6, 17, 52, 173, 585, 2064, 7520, 28265, 109501, 437394, 1799843, 7629463, 33302834, 149633151, 691702799, 3287804961, 16058229900, 80533510224, 414384339438, 2185878202630, 11811050484851, 65318772618624, 369428031895444, 2135166786135671, 12601624505404858

Offset: 0

Gus Wiseman, Jan 05 2024

nonn

It doesn't matter for this sequence whether we use loops such as {x,x} or half-loops such as {x}.

			Non-isomorphic representatives of the a(0) = 1 through a(4) = 17 set-systems:
  {}  {{1}}  {{1},{2}}    {{1},{2},{3}}        {{1},{2},{3},{4}}
             {{1},{1,2}}  {{1},{2},{1,2}}      {{1},{2},{3},{1,2}}
                          {{1},{2},{1,3}}      {{1},{2},{3},{1,4}}
                          {{1},{1,2},{1,3}}    {{1},{2},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}    {{1},{2},{1,2},{3,4}}
                          {{1,2},{1,3},{2,3}}  {{1},{2},{1,3},{1,4}}
                                               {{1},{2},{1,3},{2,3}}
                                               {{1},{2},{1,3},{2,4}}
                                               {{1},{3},{1,2},{2,4}}
                                               {{1},{1,2},{1,3},{1,4}}
                                               {{1},{1,2},{1,3},{2,3}}
                                               {{1},{1,2},{1,3},{2,4}}
                                               {{1},{1,2},{2,3},{3,4}}
                                               {{2},{1,2},{1,3},{1,4}}
                                               {{4},{1,2},{1,3},{2,3}}
                                               {{1,2},{1,3},{1,4},{2,3}}
                                               {{1,2},{1,3},{2,4},{3,4}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Eric Weisstein's World of Mathematics, Graph Loop.

For any number of edges of any size we have A000612, covering A055621.
For any number of edges we have A000666, A054921, A322700.
The labeled version is A014068.
Counting by weight gives A320663, or A339888 with loops {x,x}.
The covering case is A368599.
For edges of any size we have A368731, covering A368186.
Row sums of A368836.
A000085 counts set partitions into singletons or pairs.
A001515 counts length-n set partitions into singletons or pairs.
A100861 counts set partitions into singletons or pairs by number of pairs.
A111924 counts set partitions into singletons or pairs by length.
Cf. A001434, A007716, A007717, A058891, A070166, A122848, A124059, A283877, A302545, A322661, A339741, A339887, A370168.

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]}, {i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Subsets[Subsets[Range[n],{1,2}],{n}]]],{n,0,5}]

a(n) = polcoef(G(n, O(x*x^n)), n) \\ G defined in A070166. - Andrew Howroyd, Jan 09 2024

a(n) = A070166(n, n). - Andrew Howroyd, Jan 09 2024

Terms a(7) and beyond from Andrew Howroyd, Jan 09 2024

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

A339846 Number of even-length factorizations of n into factors > 1.

Views

Author

Keywords

Examples

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

A122848 Exponential Riordan array (1, x(1+x/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A382075 Numbers whose prime indices can be partitioned into a set of sets with distinct sums.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A382200 Numbers that can be written as a product of distinct squarefree numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A322353 Number of factorizations of n into distinct semiprimes; a(1) = 1 by convention.

Views

Author

Keywords

Comments

Examples