Displaying 1-10 of 102 results found.
page
1
2
3
4
5
6
7
8
9
10
11
Number of non-isomorphic strict multiset partitions of weight n.
+10
104
1, 1, 3, 8, 23, 63, 197, 588, 1892, 6140, 20734, 71472, 254090, 923900, 3446572, 13149295, 51316445, 204556612, 832467052, 3455533022, 14621598811, 63023667027, 276559371189, 1234802595648, 5606647482646, 25875459311317, 121324797470067, 577692044073205
COMMENTS
Also the number of nonnegative integer n X n matrices with sum of elements equal to n, under row and column permutations, with no equal rows (or alternatively, with no equal columns).
Also the number of non-isomorphic multiset partitions of weight n with no equivalent vertices. In a multiset partition, two vertices are equivalent if in every block the multiplicity of the first is equal to the multiplicity of the second.
EXAMPLE
Non-isomorphic representatives of the a(3) = 8 multiset partitions with no equivalent vertices (first column) and with no equal blocks (second column):
(111) <-> (111)
(122) <-> (1)(11)
(1)(11) <-> (122)
(1)(22) <-> (1)(22)
(2)(12) <-> (2)(12)
(1)(1)(1) <-> (123)
(1)(2)(2) <-> (1)(23)
(1)(2)(3) <-> (1)(2)(3)
PROG
(PARI)
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}
K(q, t, k)={EulerT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
a(n)={if(n==0, 1, my(s=0); forpart(q=n, my(p=sum(t=1, n, subst(x*Ser(K(q, t, n\t))/t, x, x^t))); s+=permcount(q)*polcoef(exp(p-subst(p, x, x^2)), n)); s/n!)} \\ Andrew Howroyd, Jan 21 2023
Number of non-isomorphic square multiset partitions of weight n.
+10
99
1, 1, 2, 4, 11, 27, 80, 230, 719, 2271, 7519, 25425, 88868, 317972, 1168360, 4392724, 16903393, 66463148, 266897917, 1093550522, 4568688612, 19448642187, 84308851083, 371950915996, 1669146381915, 7615141902820, 35304535554923, 166248356878549, 794832704948402, 3856672543264073, 18984761300310500
COMMENTS
A multiset partition or hypergraph is square if its length (number of blocks or edges) is equal to its number of vertices.
Also the number of square integer matrices with entries summing to n and no empty rows or columns, up to permutation of rows and columns.
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(4) = 11 multiset partitions:
1: {{1}}
2: {{1,1}}
{{1}, {2}}
3: {{1,1,1}}
{{1}, {2,2}}
{{2}, {1,2}}
{{1}, {2},{3}}
4: {{1,1,1,1}}
{{1}, {1,2,2}}
{{1}, {2,2,2}}
{{2}, {1,2,2}}
{{1,1}, {2,2}}
{{1,2}, {1,2}}
{{1,2}, {2,2}}
{{1}, {1}, {2,3}}
{{1}, {2}, {3,3}}
{{1}, {3}, {2,3}}
{{1}, {2}, {3}, {4}}
Non-isomorphic representatives of the a(4) = 11 square matrices:
. [4]
.
. [1 0] [1 0] [0 1] [2 0] [1 1] [1 1]
. [1 2] [0 3] [1 2] [0 2] [1 1] [0 2]
.
. [1 0 0] [1 0 0] [1 0 0]
. [1 0 0] [0 1 0] [0 0 1]
. [0 1 1] [0 0 2] [0 1 1]
.
. [1 0 0 0]
. [0 1 0 0]
. [0 0 1 0]
. [0 0 0 1]
MATHEMATICA
T[n_, k_] := M[k, k, n] - 2 M[k, k-1, n] + M[k-1, k-1, n];
a[0] = 1; a[n_] := Sum[T[n, k], {k, 1, n}];
PROG
a(n) = {if(n==0, 1, sum(i=1, n, M(i, i, n) - 2*M(i, i-1, n) + M(i-1, i-1, n)))} \\ Andrew Howroyd, Nov 15 2018 seq(n)={Vec(1 + sum(k=1, n, polcoef(G(k, n, n, y), k, y) - polcoef(G(k-1, n, n, y), k, y)))} \\ Andrew Howroyd, Jan 15 2024
CROSSREFS
Cf. A000219, A007716, A007718, A056156, A059201, A316980, A316983, A318795, A319560, A319616- A319646, A300913.
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 non-isomorphic multiset partitions of weight n in which (1) all parts have the same size and (2) each vertex appears the same number of times.
+10
47
1, 1, 4, 4, 10, 4, 21, 4, 26, 13, 28, 4, 128, 4, 39, 84, 150, 4, 358, 4, 956, 513, 86, 4, 12549, 1864, 134, 9582, 52366, 4, 301086, 4, 1042038, 407140, 336, 4690369, 61738312, 4, 532, 28011397, 2674943885, 4, 819150246, 4, 54904825372, 65666759973, 1303, 4, 4319823776760
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(6) = 21 multiset partitions:
(1) (11) (111) (1111) (11111) (111111)
(12) (123) (1122) (12345) (111222)
(1)(1) (1)(1)(1) (1234) (1)(1)(1)(1)(1) (112233)
(1)(2) (1)(2)(3) (11)(11) (1)(2)(3)(4)(5) (123456)
(11)(22) (111)(111)
(12)(12) (111)(222)
(12)(34) (112)(122)
(1)(1)(1)(1) (112)(233)
(1)(1)(2)(2) (123)(123)
(1)(2)(3)(4) (123)(456)
(11)(11)(11)
(11)(12)(22)
(11)(22)(33)
(11)(23)(23)
(12)(12)(12)
(12)(13)(23)
(12)(34)(56)
(1)(1)(1)(1)(1)(1)
(1)(1)(1)(2)(2)(2)
(1)(1)(2)(2)(3)(3)
(1)(2)(3)(4)(5)(6)
Number of symmetric matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.
+10
45
1, 1, 3, 9, 33, 125, 531, 2349, 11205, 55589, 291423, 1583485, 8985813, 52661609, 319898103, 2000390153, 12898434825, 85374842121, 580479540219, 4041838056561, 28824970996809, 210092964771637, 1564766851282299, 11890096357039749, 92151199272181629
COMMENTS
Number of normal semistandard Young tableaux of size n, where a tableau is normal if its entries span an initial interval of positive integers. - Gus Wiseman, Feb 23 2018
FORMULA
G.f.: Sum_{n>=0} Sum_{k=0..n} (-1)^(n-k)*C(n,k)*(1-x)^(-k)*(1-x^2)^(-C(k,2)).
G.f.: Sum_{n>=0} 2^(-n-1)*(1-x)^(-n)*(1-x^2)^(-C(n,2)). - Vladeta Jovovic, Dec 09 2009
EXAMPLE
a(4) = 33 because there are 1 such matrix of type 1 X 1, 7 matrices of type 2 X 2, 15 of type 3 X 3 and 10 of type 4 X 4, cf. A138177. The a(3) = 9 normal semistandard Young tableaux:
1 1 2 1 3 1 2 1 1 1 2 3 1 2 2 1 1 2 1 1 1
2 3 2 2 2
3
(End)
The a(4) = 33 matrices:
[4]
.
[30][21][20][11][10][02][01]
[01][10][02][11][03][20][12]
.
[200][200][110][101][100][100][100][100][011][010][010][010][001][001][001]
[010][001][100][010][020][011][010][001][100][110][101][100][020][010][001]
[001][010][001][100][001][010][002][011][100][001][010][002][100][101][110]
.
[1000][1000][1000][1000][0100][0100][0010][0010][0001][0001]
[0100][0100][0010][0001][1000][1000][0100][0001][0100][0010]
[0010][0001][0100][0010][0010][0001][1000][1000][0010][0100]
[0001][0010][0001][0100][0001][0010][0001][0100][1000][1000]
(End)
MAPLE
gf:= proc(j) local k, n; add(add((-1)^(n-k) *binomial(n, k) *(1-x)^(-k) *(1-x^2)^(-binomial(k, 2)), k=0..n), n=0..j) end: a:= n-> coeftayl(gf(n+1), x=0, n): seq(a(n), n=0..25); # Alois P. Heinz, Sep 25 2008
MATHEMATICA
Table[Sum[SeriesCoefficient[1/(2^(k+1)*(1-x)^k*(1-x^2)^(k*(k-1)/2)), {x, 0, n}], {k, 0, Infinity}], {n, 0, 20}] (* Vaclav Kotesovec, Jul 03 2014 *) multsubs[set_, k_]:=If[k==0, {{}}, Join@@Table[Prepend[#, set[[i]]]&/@multsubs[Drop[set, i-1], k-1], {i, Length[set]}]]; Table[Length[Select[multsubs[Tuples[Range[n], 2], n], And[Union[First/@#]==Range[Max@@First/@#], Union[Last/@#]==Range[Max@@Last/@#], Sort[Reverse/@#]==#]&]], {n, 5}] (* Gus Wiseman, Nov 14 2018 *)
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.
Number of non-isomorphic weight-n chains of distinct multisets whose dual is also a chain of distinct multisets.
+10
37
1, 1, 1, 4, 4, 9, 17, 28, 41, 75, 122, 192, 314, 484, 771, 1216, 1861, 2848, 4395, 6610, 10037
COMMENTS
The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
Also the number of plane partitions of n with no repeated rows or columns. For example, the a(6) = 17 plane partitions are:
6 51 42 321
.
5 4 41 31 32 31 22 221 211
1 2 1 2 1 11 2 1 11
.
3 21 21 111
2 2 11 11
1 1 1 1
(End)
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(5) = 9 chains:
1: {{1}}
2: {{1,1}}
3: {{1,1,1}}
{{1,2,2}}
{{1},{1,1}}
{{2},{1,2}}
4: {{1,1,1,1}}
{{1,2,2,2}}
{{1},{1,1,1}}
{{2},{1,2,2}}
5: {{1,1,1,1,1}}
{{1,1,2,2,2}}
{{1,2,2,2,2}}
{{1},{1,1,1,1}}
{{2},{1,1,2,2}}
{{2},{1,2,2,2}}
{{1,1},{1,1,1}}
{{1,2},{1,2,2}}
{{2,2},{1,2,2}}
MATHEMATICA
primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
ptnplane[n_]:=Union[Map[Reverse@*primeMS, Join@@Permutations/@facs[n], {2}]];
Table[Sum[Length[Select[ptnplane[Times@@Prime/@y], And[UnsameQ@@#, UnsameQ@@Transpose[PadRight[#]], And@@GreaterEqual@@@#, And@@(GreaterEqual@@@Transpose[PadRight[#]])]&]], {y, IntegerPartitions[n]}], {n, 10}] (* Gus Wiseman, Jan 18 2019 *)
Number of non-isomorphic set-systems of weight n contradicting a strict version of the axiom of choice.
+10
35
0, 0, 0, 0, 1, 1, 5, 12, 36, 97, 291
COMMENTS
A set-system is a finite set of finite nonempty sets. The weight of a set-system 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(5) = 1 through a(7) = 12 set-systems:
{{1},{2},{3},{2,3}} {{1},{2},{1,3},{2,3}} {{1},{2},{1,2},{3,4,5}}
{{1},{2},{3},{1,2,3}} {{1},{3},{2,3},{1,2,3}}
{{2},{3},{1,3},{2,3}} {{1},{4},{1,4},{2,3,4}}
{{3},{4},{1,2},{3,4}} {{2},{3},{2,3},{1,2,3}}
{{1},{2},{3},{4},{3,4}} {{3},{1,2},{1,3},{2,3}}
{{1},{2},{3},{1,3},{2,3}}
{{1},{2},{3},{2,4},{3,4}}
{{1},{2},{3},{4},{2,3,4}}
{{1},{3},{4},{2,4},{3,4}}
{{1},{4},{5},{2,3},{4,5}}
{{2},{3},{4},{1,2},{3,4}}
{{1},{2},{3},{4},{5},{4,5}}
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], UnsameQ@@#&&And@@UnsameQ@@@# && Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 8}]
CROSSREFS
Minimal multiset partitions of this type are ranked by A368187. Factorizations of this type are counted by A368413, complement A368414. Cf. A302545, A306005, A316983, A317533, A319616, A321155, A321405, A326031, A330223, A330227, A367905.
Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.
+10
33
1, 1, 1, 2, 20, 308, 5338, 105298, 2366704, 60065072, 1702900574, 53400243419, 1836274300504, 68730359299960, 2782263907231153, 121137565273808792, 5645321914669112342, 280401845830658755142, 14788386825536445299398, 825378055206721558026931, 48604149005046792753887416
COMMENTS
Unlike the connected case ( A057500), these graphs may have more than one cycle; for example, the graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}} has multiple cycles.
EXAMPLE
Non-isomorphic representatives of the a(4) = 20 graphs:
{}
{{1,2},{1,3},{2,3}}
{{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}]], Length[#]==Length[Union@@#]&]], {n, 0, 5}]
PROG
b(n) = sum(k=0, n, (-1)^(n-k) * binomial(n, k) * binomial(binomial(k, 2), n))
a(n) = sum(k=0, n, binomial(n, k) * b(k)) \\ Andrew Howroyd, Dec 29 2023
CROSSREFS
Counting all vertices (not just covered) gives A116508. A143543 counts simple labeled graphs by number of connected components.
Number of non-isomorphic weight-n antichains of (not necessarily distinct) multisets whose dual is also an antichain of (not necessarily distinct) multisets.
+10
32
1, 1, 4, 7, 19, 32, 81, 142, 337, 659, 1564
COMMENTS
The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(3) = 7 antichains:
1: {{1}}
2: {{1,1}}
{{1,2}}
{{1},{1}}
{{1},{2}}
3: {{1,1,1}}
{{1,2,3}}
{{1},{2,2}}
{{1},{2,3}}
{{1},{1},{1}}
{{1},{2},{2}}
{{1},{2},{3}}
CROSSREFS
Cf. A000219, A006126, A007716, A049311, A059201, A283877, A306007, A316980, A316983, A319558, A319560, A319616- A319646, A300913.
Search completed in 0.057 seconds
|