Displaying 1-10 of 66 results found.
Number of labeled n-node graphs with at most one cycle in each connected component.
+10
90
1, 1, 2, 8, 57, 608, 8524, 145800, 2918123, 66617234, 1704913434, 48300128696, 1499864341015, 50648006463048, 1847622972848648, 72406232075624192, 3033607843748296089, 135313823447621913500, 6402077421524339766058, 320237988317922139148736
COMMENTS
The total number of those graphs of order 5 is 608. The number of forests of trees on n labeled nodes of order 5 is 291, so the majority of the graphs of that kind have one or more unicycles.
Also the number of labeled graphs with n vertices satisfying a strict version of the axiom of choice. The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once. The connected case is A129271, complement A140638. The unlabeled version is A134964. - Gus Wiseman, Dec 22 2023
FORMULA
a(0) = 1; for n >=1, a(n) = Sum of n!prod_{j=1}^n\{ frac{ A129271(j)^{c_j} } { j!^{c_j}c_j! } } over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0. E.g.f.: sqrt(-LambertW(-x)/(x*(1+LambertW(-x))))*exp(-3/4 * LambertW(-x)^2). - Vladeta Jovovic, Sep 16 2008 a(n) ~ 2^(-1/4) * Gamma(3/4) * exp(-1/4) * n^(n-1/4) / sqrt(Pi) * (1-7*Pi/(12*Gamma(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Oct 08 2013
EXAMPLE
Below we see the 7 partitions of n=5 in the form c_1 + 2c_2 + ... + nc_n followed by the corresponding number of graphs. We consider the values of A129271(j) given by the table j|1|2|3| 4| 5|
----+-+-+-+--+---+
a(j)|1|1|4|31|347|
1*5 -> 5!1^5 / (1!^5 * 5!) = 1
2*1 + 1*3 -> 5!1^1 * 1^3 / (2!^1 * 1! * 1!^3 * 3!) = 10
2*2 + 1*1 -> 5!1^2 * 1^1 / (2!^2 * 2! * 1!^1 * 1!) = 15
3*1 + 1*2 -> 5!4^1 * 1^2 / (3!^1 * 1! * 1!^2 * 2!) = 40
3*1 + 2*1 -> 5!4^1 * 1^1 / (3!^1 * 1! * 2!^1 * 1!) = 40
4*1 + 1*1 -> 5!31^1 * 1^1 / (4!^1 * 1! * 1!^1 * 1!) = 155
5*1 -> 5!347^1 / (5!^1 * 1!) = 347
Total 608
MAPLE
cy:= proc(n) option remember; binomial(n-1, 2)*
add((n-3)!/(n-2-t)! *n^(n-2-t), t=1..n-2)
end:
T:= proc(n, k) option remember;
if k=0 then 1
elif k<0 or n<k then 0
else add(binomial(n-1, j)*((j+1)^(j-1)*T(n-j-1, k-j)
+cy(j+1)*T(n-j-1, k-j-1)), j=0..k)
fi
end:
a:= n-> add(T(n, k), k=0..n):
MATHEMATICA
nn=20; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Range[0, nn]!CoefficientList[ Series[ Exp[t/2-3t^2/4]/(1-t)^(1/2), {x, 0, nn}], x] (* Geoffrey Critzer, Sep 05 2012 *) Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Select[Tuples[#], UnsameQ@@#&]!={}&]], {n, 0, 5}] (* Gus Wiseman, Dec 22 2023 *)
PROG
(PARI) x='x+O('x^50); Vec(serlaplace(sqrt(-lambertw(-x)/(x*(1+ lambertw(-x))))*exp(-(3/4)*lambertw(-x)^2))) \\ G. C. Greubel, Nov 16 2017
CROSSREFS
A143543 counts graphs by number of connected components.
Number of acyclic digraphs (or DAGs) with n labeled nodes.
(Formerly M3113)
+10
74
1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425, 521939651343829405020504063, 18676600744432035186664816926721, 1439428141044398334941790719839535103, 237725265553410354992180218286376719253505
COMMENTS
Also the number of n X n real (0,1)-matrices with all eigenvalues positive. - Conjectured by Eric W. Weisstein, Jul 10 2003 and proved by McKay et al. 2003, 2004 Also the number of n X n real (0,1)-matrices with permanent equal to 1, up to permutation of rows/columns, cf. A089482. - Vladeta Jovovic, Oct 28 2009 Also the number of nilpotent elements in the semigroup of binary relations on [n]. - Geoffrey Critzer, May 26 2022 Also the number of sets of n nonempty subsets of {1..n} such that there is a unique way to choose a different element from each. For example, non-isomorphic representatives of the a(3) = 25 set-systems are:
{{1},{2},{3}}
{{1},{2},{1,3}}
{{1},{2},{1,2,3}}
{{1},{1,2},{1,3}}
{{1},{1,2},{2,3}}
{{1},{1,2},{1,2,3}}
(End)
REFERENCES
Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 310.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, Eq. (1.6.1).
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P Stanley, Enumerative Combinatorics I, 2nd. ed., p. 322.
LINKS
Zehao Jin, Mario Pasquato, Benjamin L. Davis, Tristan Deleu, Yu Luo, Changhyun Cho, Pablo Lemos, Laurence Perreault-Levasseur, Yoshua Bengio, Xi Kang, Andrea Valerio Maccio, and Yashar Hezaveh, A Data-driven Discovery of the Causal Connection between Galaxy and Black Hole Evolution, arXiv:2410.00965 [astro-ph.GA], 2024. See p. 33. Zehao Jin, Mario Pasquato, Benjamin L. Davis, Tristan Deleu, Yu Luo, Changhyun Cho, Pablo Lemos, Laurence Perreault-Levasseur, Yoshua Bengio, and Xi Kang, Causal Discovery in Astrophysics: Unraveling Supermassive Black Hole and Galaxy Coevolution, Astrophys. J. (2025) Vol. 979, 212. See 4.1. Laphou Lao, Zecheng Li, Songlin Hou, Bin Xiao, Songtao Guo, and Yuanyuan Yang, A Survey of IoT Applications in Blockchain Systems: Architecture, Consensus and Traffic Modeling, ACM Computing Surveys (CSUR, 2020) Vol. 53, No. 1, Article No. 18.
FORMULA
a(0) = 1; for n > 0, a(n) = Sum_{k=1..n} (-1)^(k+1)*C(n, k)*2^(k*(n-k))*a(n-k).
1 = Sum_{n=>0} a(n)*x^n/(1 + 2^n*x)^(n+1). - Paul D. Hanna, Oct 17 2009 1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + 2^n*x)^(n+m) for m>=1. - Paul D. Hanna, Apr 01 2011 log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 2^n*x)^n. - Paul D. Hanna, Apr 01 2011 Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is 1/E(-x) = Sum_{n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + x + 3*x^2/(2!*2) + 25*x^3/(3!*2^3) + 543*x^4/(4!*2^6) + ... (Stanley). Cf. A188457. - Peter Bala, Apr 01 2013 a(n) ~ n!*2^(n*(n-1)/2)/(M*p^n), where p = 1.488078545599710294656246... is the root of the equation Sum_{n>=0} (-1)^n*p^n/(n!*2^(n*(n-1)/2)) = 0, and M = Sum_{n>=1} (-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)) = 0.57436237330931147691667... Both references to the article "Acyclic digraphs and eigenvalues of (0,1)-matrices" give the wrong value M=0.474! - Vaclav Kotesovec, Dec 09 2013 [Response from N. J. A. Sloane, Dec 11 2013: The value 0.474 has a typo, it should have been 0.574. The value was taken from Stanley's 1973 paper.] exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 10*x^3 + 146*x^4 + 6010*x^5 + ... appears to have integer coefficients (cf. A188490). - Peter Bala, Jan 14 2016
EXAMPLE
For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.
MAPLE
p:=evalf(solve(sum((-1)^n*x^n/(n!*2^(n*(n-1)/2)), n=0..infinity) = 0, x), 50); M:=evalf(sum((-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)), n=1..infinity), 40); # program for evaluation of constants p and M in the asymptotic formula, Vaclav Kotesovec, Dec 09 2013
MATHEMATICA
a[0] = a[1] = 1; a[n_] := a[n] = Sum[ -(-1)^k * Binomial[n, k] * 2^(k*(n-k)) * a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 13}](* Jean-François Alcover, May 21 2012, after PARI *) Table[2^(n*(n-1)/2)*n! * SeriesCoefficient[1/Sum[(-1)^k*x^k/k!/2^(k*(k-1)/2), {k, 0, n}], {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, May 19 2015 *) Table[Length[Select[Subsets[Subsets[Range[n]], {n}], Length[Select[Tuples[#], UnsameQ@@#&]]==1&]], {n, 0, 5}] (* Gus Wiseman, Jan 01 2024 *)
PROG
(PARI) a(n)=if(n<1, n==0, sum(k=1, n, -(-1)^k*binomial(n, k)*2^(k*(n-k))*a(n-k)))
(PARI) {a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+2^k*x+x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Oct 17 2009
CROSSREFS
Cf. A055165, which counts nonsingular {0, 1} matrices and A085656, which counts positive definite {0, 1} matrices. These are the reverse-alternating sums of rows of A046860. The weakly connected case is A082402.
Number of sets of nonempty subsets of {1..n} satisfying a strict version of the axiom of choice.
+10
64
1, 2, 7, 61, 1771, 187223, 70038280, 90111497503, 397783376192189
COMMENTS
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.
EXAMPLE
The a(2) = 7 set-systems:
{}
{{1}}
{{2}}
{{1,2}}
{{1},{2}}
{{1},{1,2}}
{{2},{1,2}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n]]], Select[Tuples[#], UnsameQ@@#&]!={}&]], {n, 0, 3}]
CROSSREFS
The version without singletons is A367770. The complement allowing empty edges is A367901. These set-systems have ranks A367906. A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems.
A326031 gives weight of the set-system with BII-number n.
Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367862, A367905, A370636.
Number of labeled simple graphs with n vertices contradicting a strict version of the axiom of choice.
+10
61
0, 0, 0, 0, 7, 416, 24244, 1951352, 265517333, 68652859502, 35182667175398, 36028748718835272, 73786974794973865449, 302231454853009287213496, 2475880078568912926825399800, 40564819207303268441662426947840, 1329227995784915869870199216532048487
COMMENTS
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.
In the connected case, these are just graphs with more than one cycle.
EXAMPLE
Non-isomorphic representatives of the a(4) = 7 graphs:
{{1,2},{1,3},{1,4},{2,3},{2,4}}
{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Select[Tuples[#], UnsameQ@@#&]=={}&]], {n, 0, 5}]
CROSSREFS
The connected case is A140638 (graphs with more than one cycle). A143543 counts simple labeled graphs by number of connected components.
Cf. A057500, A116508, A326754, A355739, A355740, A367769, A367770, A367863, A367901, A367902, A367904.
Number of ways to choose a sequence of different binary indices, one of each binary index of n.
+10
61
1, 1, 1, 1, 2, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 0, 2, 1, 2, 1, 3, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 2, 2, 1, 1, 3, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 3, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 3, 2, 2, 1, 4, 1, 1, 0, 2, 1, 1, 0, 2, 0, 0, 0, 4, 1, 2, 0, 3, 0, 0, 0
COMMENTS
A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. For example, 18 has reversed binary expansion (0,1,0,0,1) and binary indices {2,5}.
EXAMPLE
352 has binary indices of binary indices {{2,3},{1,2,3},{1,4}}, and there are six possible choices (2,1,4), (2,3,1), (2,3,4), (3,1,4), (3,2,1), (3,2,4), so a(352) = 6.
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Table[Length[Select[Tuples[bpe/@bpe[n]], UnsameQ@@#&]], {n, 0, 100}]
PROG
(Python)
from itertools import count, islice, product
def bin_i(n): #binary indices
return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def a_gen(): #generator of terms
for n in count(0):
c = 0
for j in list(product(*[bin_i(k) for k in bin_i(n)])):
if len(set(j)) == len(j):
c += 1
yield c
CROSSREFS
Positions of positive terms are A367906. Positions of terms > 1 are A367909. A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Cf. A000612, A055621, A072639, A309326, A326031, A326675, A326702, A326753, A367902, A367903, A367904, A367912. BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers), A326783 (uniform), A326784 (regular), A326788 (simple), A330217 (achiral).
Numbers n such that it is not possible to choose a different binary index of each binary index of n.
+10
60
7, 15, 23, 25, 27, 29, 30, 31, 39, 42, 43, 45, 46, 47, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 71, 75, 77, 78, 79, 83, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 99, 101, 102, 103, 105, 106, 107, 108, 109, 110, 111, 113, 114, 115, 116, 117, 118, 119, 120, 121
COMMENTS
Also BII-numbers of set-systems (sets of nonempty sets) contradicting a strict version of the axiom of choice.
A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. A set-system is a finite set of finite nonempty sets. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary digits (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.
EXAMPLE
The set-system {{1},{2},{1,2},{1,3}} with BII-number 23 has choices (1,2,1,1), (1,2,1,3), (1,2,2,1), (1,2,2,3), but none of these has all different elements, so 23 is in the sequence.
The terms together with the corresponding set-systems begin:
7: {{1},{2},{1,2}}
15: {{1},{2},{1,2},{3}}
23: {{1},{2},{1,2},{1,3}}
25: {{1},{3},{1,3}}
27: {{1},{2},{3},{1,3}}
29: {{1},{1,2},{3},{1,3}}
30: {{2},{1,2},{3},{1,3}}
31: {{1},{2},{1,2},{3},{1,3}}
39: {{1},{2},{1,2},{2,3}}
42: {{2},{3},{2,3}}
43: {{1},{2},{3},{2,3}}
45: {{1},{1,2},{3},{2,3}}
46: {{2},{1,2},{3},{2,3}}
47: {{1},{2},{1,2},{3},{2,3}}
51: {{1},{2},{1,3},{2,3}}
MATHEMATICA
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
Select[Range[100], Select[Tuples[bpe/@bpe[#]], UnsameQ@@#&]=={}&]
PROG
(Python)
from itertools import count, islice, product
def bin_i(n): #binary indices
return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def a_gen(): #generator of terms
for n in count(1):
p = list(product(*[bin_i(k) for k in bin_i(n)]))
x = len(p)
for j in range(x):
if len(set(p[j])) == len(p[j]): break
if j+1 == x: yield(n)
CROSSREFS
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
Cf. A000612, A055621, A072639, A083323, A309326, A326702, A326753, A367769, A367901, A367902, A367912. BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers), A326783 (uniform), A326784 (regular), A326788 (simple), A330217 (achiral).
Number of n-vertex labeled simple graphs with n edges and no isolated vertices.
+10
52
1, 0, 0, 1, 15, 222, 3760, 73755, 1657845, 42143500, 1197163134, 37613828070, 1295741321875, 48577055308320, 1969293264235635, 85852853154670693, 4005625283891276535, 199166987259400191480, 10513996906985414443720, 587316057411626070658200, 34612299496604684775762261
FORMULA
a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n). - Andrew Howroyd, Dec 29 2023
EXAMPLE
Non-isomorphic representatives of the a(4) = 15 graphs:
{{1,2},{1,3},{1,4},{2,3}}
{{1,2},{1,3},{2,4},{3,4}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[#]==n&]], {n, 0, 5}]
PROG
(PARI) a(n) = sum(k=0, n, (-1)^(n-k) * binomial(n, k) * binomial(binomial(k, 2), n)) \\ Andrew Howroyd, Dec 29 2023
CROSSREFS
The non-covering version is A116508. A143543 counts simple labeled graphs by number of connected components.
Cf. A003465, A006126, A305000, A316983, A319559, A323817, A326754, A367769, A367901, A367902, A367903.
Number of labeled simple graphs covering n vertices and contradicting a strict version of the axiom of choice.
+10
41
0, 0, 0, 0, 7, 381, 21853, 1790135, 250562543, 66331467215, 34507857686001, 35645472109753873, 73356936892660012513, 301275024409580265134121, 2471655539736293803311467943, 40527712706903494712385171632959, 1328579255614092966328511889576785109
COMMENTS
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.
EXAMPLE
The a(4) = 7 graphs:
{{1,2},{1,3},{1,4},{2,3},{2,4}}
{{1,2},{1,3},{1,4},{2,3},{3,4}}
{{1,2},{1,3},{1,4},{2,4},{3,4}}
{{1,2},{1,3},{2,3},{2,4},{3,4}}
{{1,2},{1,4},{2,3},{2,4},{3,4}}
{{1,3},{1,4},{2,3},{2,4},{3,4}}
{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Select[Tuples[#], UnsameQ@@#&]=={}&]], {n, 0, 5}]
CROSSREFS
A143543 counts simple labeled graphs by number of connected components.
Number of factorizations of n into positive integers > 1 such that it is not possible to choose a different prime factor of each factor.
+10
41
0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 4, 0, 1, 0, 1, 0, 0, 0, 3, 1, 0, 2, 1, 0, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0, 3, 0, 0, 0, 1, 1, 0, 0, 7, 1, 1, 0, 1, 0, 3, 0, 3, 0, 0, 0, 2, 0, 0, 1, 10, 0, 0, 0, 1, 0, 0, 0, 10, 0, 0, 1, 1, 0, 0, 0, 7, 4, 0, 0, 2, 0, 0
COMMENTS
For example, the factorization f = 2*3*6 has two ways to choose a prime factor of each factor, namely (2,3,2) and (2,3,3), but neither of these has all different elements, so f is counted under a(36).
EXAMPLE
The a(1) = 0 through a(24) = 3 factorizations:
... 2*2 ... 2*4 3*3 .. 2*2*3 ... 2*8 . 2*3*3 . 2*2*5 ... 2*2*6
2*2*2 4*4 2*3*4
2*2*4 2*2*2*3
2*2*2*2
MATHEMATICA
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], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]=={}&]], {n, 100}]
CROSSREFS
The complement is counted by A368414.
Number of non-isomorphic multiset partitions of weight n contradicting a strict version of the axiom of choice.
+10
39
0, 0, 1, 3, 12, 37, 133, 433, 1516, 5209, 18555
COMMENTS
A multiset partition is a finite multiset of finite nonempty multisets. The weight of a multiset partition is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.
The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.
EXAMPLE
Non-isomorphic representatives of the a(2) = 1 through a(4) = 12 multiset partitions:
{{1},{1}} {{1},{1,1}} {{1},{1,1,1}}
{{1},{1},{1}} {{1,1},{1,1}}
{{1},{2},{2}} {{1},{1},{1,1}}
{{1},{1},{2,2}}
{{1},{1},{2,3}}
{{1},{2},{1,2}}
{{1},{2},{2,2}}
{{2},{2},{1,2}}
{{1},{1},{1},{1}}
{{1},{1},{2},{2}}
{{1},{2},{2},{2}}
{{1},{2},{3},{3}}
MATHEMATICA
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]& /@ sps[Complement[set, s]]] /@ Cases[Subsets[set], {i, ___}];
mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s, Flatten[MapIndexed[Table[#2, {#1}]&, #]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i, p[[i]]}, {i, Length[p]}])], {p, Permutations[Union@@m]}]]];
Table[Length[Union[brute/@Select[mpm[n], Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 6}]
CROSSREFS
The case of unlabeled graphs appears to be A140637, complement A134964. These multiset partitions have ranks A355529. Minimal multiset partitions of this type are ranked by A368187. Factorizations of this type are counted by A368413, complement A368414.
Search completed in 0.043 seconds
|