Displaying 1-10 of 15 results found.
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 self-dual multiset partitions of weight n.
+10
103
1, 1, 2, 4, 9, 17, 36, 72, 155, 319, 677, 1429, 3094, 6648, 14518, 31796, 70491, 156818, 352371, 795952, 1813580, 4155367, 9594425, 22283566, 52122379, 122631874, 290432439, 691831161, 1658270316, 3997272089, 9692519896, 23631827354, 57943821449, 142834652193
COMMENTS
Also the number of nonnegative integer square symmetric matrices with sum of elements equal to n, under row and column permutations.
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.
EXAMPLE
Non-isomorphic representatives of the a(4) = 9 self-dual multiset partitions:
(1111),
(1)(222), (2)(122), (11)(22), (12)(12),
(1)(1)(23), (1)(2)(33), (1)(3)(23),
(1)(2)(3)(4).
The a(4) = 9 square symmetric matrices:
. [4]
.
. [3 0] [2 0] [2 1] [1 1]
. [0 1] [0 2] [1 0] [1 1]
.
. [2 0 0] [1 1 0] [0 1 1]
. [0 1 0] [1 0 0] [1 0 0]
. [0 0 1] [0 0 1] [1 0 0]
.
. [1 0 0 0]
. [0 1 0 0]
. [0 0 1 0]
. [0 0 0 1]
Number of symmetric polynomial functions of degree n of a symmetric matrix (of indefinitely large size) under joint row and column permutations. Also number of multigraphs with n edges (allowing loops) on an infinite set of nodes.
+10
83
1, 2, 7, 23, 79, 274, 1003, 3763, 14723, 59663, 250738, 1090608, 4905430, 22777420, 109040012, 537401702, 2723210617, 14170838544, 75639280146, 413692111521, 2316122210804, 13261980807830, 77598959094772, 463626704130058, 2826406013488180, 17569700716557737
COMMENTS
Also the number of non-isomorphic multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018 Number of distinct n X 2n matrices with integer entries and rows sums 2, up to row and column permutations. - Andrew Howroyd, Sep 06 2018 a(n) is the number of unlabeled loopless multigraphs with n edges rooted at one vertex. - Andrew Howroyd, Nov 22 2020
REFERENCES
Huaien Li and David C. Torney, Enumerations of Multigraphs, 2002.
LINKS
Huaien Li and David C. Torney, Enumeration of unlabelled multigraphs, Ars Combin. 75 (2005) 171-188. MR2133219.
EXAMPLE
a(2) = 7 (here - denotes an edge, = denotes a pair of parallel edges and o is a loop):
oo
o o
o-
o -
=
--
- -
Non-isomorphic representatives of the a(2) = 7 multiset partitions of {1, 1, 2, 2}:
(1122),
(1)(122), (11)(22), (12)(12),
(1)(1)(22), (1)(2)(12),
(1)(1)(2)(2).
(End)
Non-isomorphic representatives of the a(1) = 1 through a(3) = 7 rooted loopless multigraphs (root shown as singleton):
{{1}} {{1},{1,2}} {{1},{1,2},{1,2}}
{{1},{2,3}} {{1},{1,2},{1,3}}
{{1},{1,2},{2,3}}
{{1},{1,2},{3,4}}
{{1},{2,3},{2,3}}
{{1},{2,3},{2,4}}
{{1},{2,3},{4,5}}
(End)
MATHEMATICA
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t k; s += t]; s!/m];
Kq[q_, t_, k_] := SeriesCoefficient[1/Product[g = GCD[t, q[[j]]]; (1 - x^(q[[j]]/g))^g, {j, 1, Length[q]}], {x, 0, k}];
RowSumMats[n_, m_, k_] := Module[{s=0}, Do[s += permcount[q]* SeriesCoefficient[Exp[Sum[Kq[q, t, k]/t x^t, {t, 1, n}]], {x, 0, n}], {q, IntegerPartitions[m]}]; s/m!];
a[n_] := RowSumMats[n, 2n, 2];
PROG
(PARI) \\ See A318951 for RowSumMats seq(n)={my(A=O(x*x^n)); Vec(G(2*n, x+A, [1]))} \\ Andrew Howroyd, Nov 22 2020
CROSSREFS
Cf. A000664, A002620, A007716, A007719, A020555, A050531, A050532, A050535, A052171, A053418, A053419, A094574, A316972, A316974, A318951, A339065.
EXTENSIONS
a(0)=1 prepended and a(16)-a(25) added by Max Alekseyev, Jun 21 2011
Number of loopless multigraphs on infinite set of nodes with n edges.
+10
46
1, 1, 3, 8, 23, 66, 212, 686, 2389, 8682, 33160, 132277, 550835, 2384411, 10709827, 49782637, 238998910, 1182772364, 6023860266, 31525780044, 169316000494, 932078457785, 5253664040426, 30290320077851, 178480713438362, 1073918172017297
COMMENTS
Also, a(n) is the number of n-rowed binary matrices with all row sums equal to 2, up to row and column permutation (see Jovovic's formula). Also, a(n) is the limit of A192517(m,n) as m grows. - Max Alekseyev, Oct 18 2017 Row sums of the triangle defined by the Multiset Transformation of A076864, 1 ;
0 1;
0 2 1;
0 5 2 1;
0 12 8 2 1;
0 33 22 8 2 1;
0 103 72 26 8 2 1;
0 333 229 87 26 8 2 1;
0 1183 782 295 92 26 8 2 1;
0 4442 2760 1036 315 92 26 8 2 1;
0 17576 10270 3735 1129 321 92 26 8 2 1;
0 72810 39770 13976 4117 1154 321 92 26 8 2 1;
0 314595 160713 54132 15547 4237 1161 321 92 26 8 2 1;
Also the number of non-isomorphic set multipartitions (multisets of sets) of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018
REFERENCES
Frank Harary and Edgar M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 88, Eq. (4.1.18).
EXAMPLE
Non-isomorphic representatives of the a(3) = 8 set multipartitions of {1, 1, 2, 2, 3, 3}:
(123)(123)
(1)(23)(123)
(12)(13)(23)
(1)(1)(23)(23)
(1)(2)(3)(123)
(1)(2)(13)(23)
(1)(1)(2)(3)(23)
(1)(1)(2)(2)(3)(3)
(End)
MATHEMATICA
seq[n_] := G[2n, x+O[x]^n, {}] // CoefficientList[#, x]&;
Number of factorizations of n into factors > 1 with no equivalent primes.
+10
29
1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 4, 1, 1, 1, 5, 1, 4, 1, 4, 1, 1, 1, 7, 2, 1, 3, 4, 1, 1, 1, 7, 1, 1, 1, 7, 1, 1, 1, 7, 1, 1, 1, 4, 4, 1, 1, 12, 2, 4, 1, 4, 1, 7, 1, 7, 1, 1, 1, 7, 1, 1, 4, 11, 1, 1, 1, 4, 1, 1, 1, 16, 1, 1, 4, 4, 1, 1, 1, 12, 5, 1, 1, 7, 1, 1
COMMENTS
In a factorization, two primes are equivalent if each factor has in its prime factorization the same multiplicity of both primes.
EXAMPLE
The a(36) = 7 factorizations are (2*2*3*3), (2*2*9), (2*3*6), (3*3*4), (2*18), (3*12), (4*9). Missing from this list are (6*6) and (36).
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]]}]];
dual[eds_]:=Table[First/@Position[eds, x], {x, Union@@eds}];
Table[Length[Select[facs[n], UnsameQ@@dual[primeMS/@#]&]], {n, 100}]
Number of multigraphs on n labeled edges (with loops). Also number of genetically distinct states amongst n individuals.
+10
28
1, 2, 9, 66, 712, 10457, 198091, 4659138, 132315780, 4441561814, 173290498279, 7751828612725, 393110572846777, 22385579339430539, 1419799938299929267, 99593312799819072788, 7678949893962472351181, 647265784993486603555551, 59357523410046023899154274
COMMENTS
Also the number of factorizations of (p_n#)^2. - David W. Wilson, Apr 30 2001 Also the number of multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018 a(n) gives the number of genetically distinct states for n diploid individuals in the case that maternal and paternal alleles transmitted to the individuals are not distinguished (if maternal and paternal alleles are distinguished, then the number of states is A000110(2n)). - Noah A Rosenberg, Aug 23 2022
REFERENCES
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. - N. J. A. Sloane, Dec 30 2018 E. Keith Lloyd, Math. Proc. Camb. Phil. Soc., vol. 103 (1988), 277-284.
A. Murthy, Generalization of partition function, introducing Smarandache factor partitions. Smarandache Notions Journal, Vol. 11, No. 1-2-3, Spring 2000.
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.
FORMULA
Lloyd's article gives a complicated explicit formula.
E.g.f.: exp(-3/2 + exp(x)/2)*Sum_{n>=0} exp(binomial(n+1, 2)*x)/n! [probably in the Labelle paper]. - Vladeta Jovovic, Apr 27 2004
EXAMPLE
The a(2) = 9 multiset partitions of {1, 1, 2, 2}:
(1122),
(1)(122), (2)(112), (11)(22), (12)(12),
(1)(1)(22), (1)(2)(12), (2)(2)(11),
(1)(1)(2)(2).
(End)
MAPLE
B := n -> combinat[bell](n):
P := proc(m, n) local k; global B; option remember;
if n = 0 then B(m) else
(1/2)*( P(m+2, n-1) + P(m+1, n-1) + add( binomial(n-1, k)*P(m, k), k=0..n-1) ); fi; end;
MATHEMATICA
max = 16; s = Series[Exp[-3/2 + Exp[x]/2]*Sum[Exp[Binomial[n+1, 2]*x]/n!, {n, 0, 3*max }], {x, 0, max}] // Normal; a[n_] := SeriesCoefficient[s, {x, 0, n}]*n!; Table[a[n] // Round, {n, 0, max} ] (* Jean-François Alcover, Apr 23 2014, after Vladeta Jovovic *) 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]]]];
Table[Length[mps[Ceiling[Range[1/2, n, 1/2]]]], {n, 5}] (* Gus Wiseman, Jul 18 2018 *)
Number of (<=2)-covers of an n-set.
+10
19
1, 1, 5, 40, 457, 6995, 136771, 3299218, 95668354, 3268445951, 129468914524, 5868774803537, 301122189141524, 17327463910351045, 1109375488487304027, 78484513540137938209, 6098627708074641312182, 517736625823888411991202, 47791900951140948275632148
COMMENTS
Also the number of strict multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. For example, the a(2) = 5 strict multiset partitions of {1, 1, 2, 2} are (1122), (1)(122), (2)(112), (11)(22), (1)(2)(12). - Gus Wiseman, Jul 18 2018
FORMULA
E.g.f: exp(-1-1/2*(exp(x)-1))*Sum(exp(x*binomial(n+1, 2))/n!, n=0..infinity) or exp((1-exp(x))/2)*Sum( A094577 (n)*(x/2)^n/n!, n=0..infinity).
EXAMPLE
These are set-systems covering {1..n} with vertex-degrees <= 2. For example, the a(3) = 40 covers are:
{123} {1}{23} {1}{2}{3} {1}{2}{3}{12}
{2}{13} {1}{2}{13} {1}{2}{3}{13}
{3}{12} {1}{2}{23} {1}{2}{3}{23}
{1}{123} {1}{3}{12} {1}{2}{13}{23}
{12}{13} {1}{3}{23} {1}{2}{3}{123}
{12}{23} {2}{3}{12} {1}{3}{12}{23}
{13}{23} {2}{3}{13} {2}{3}{12}{13}
{2}{123} {1}{12}{23}
{3}{123} {1}{13}{23}
{12}{123} {1}{2}{123}
{13}{123} {1}{3}{123}
{23}{123} {2}{12}{13}
{2}{13}{23}
{2}{3}{123}
{3}{12}{13}
{3}{12}{23}
{12}{13}{23}
{1}{23}{123}
{2}{13}{123}
{3}{12}{123}
(End)
MATHEMATICA
facs[n_]:=facs[n]=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
Table[Length[Select[facs[Array[Prime, n, 1, Times]^2], UnsameQ@@#&]], {n, 0, 6}] (* Gus Wiseman, Jul 18 2018 *) m = 20;
a094577[n_] := Sum[Binomial[n, k]*BellB[2 n - k], {k, 0, n}];
egf = Exp[(1 - Exp[x])/2]*Sum[a094577[n]*(x/2)^n/n!, {n, 0, m}] + O[x]^m;
CROSSREFS
Graphs with vertex-degrees <= 2 are A136281. Cf. A002718, A007716, A020554, A020555, A050535, A094574, A136284, A316974, A327104, A327106, A327229.
Number of multigraphs on n labeled edges (without loops).
+10
14
1, 1, 3, 16, 139, 1750, 29388, 624889, 16255738, 504717929, 18353177160, 769917601384, 36803030137203, 1984024379014193, 119571835094300406, 7995677265437541258, 589356399302126773920, 47609742627231823142029, 4193665147256300117666879
COMMENTS
Or, number of bicoverings of an n-set.
Or, number of 2-covers of [1,...,n].
Also the number of set multipartitions (multisets of sets) of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018
REFERENCES
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.
FORMULA
E.g.f.: exp(-3/2+exp(x)/2)*Sum(exp(binomial(n, 2)*x)/n!, n=0..infinity) [Comtet]. - Vladeta Jovovic, Apr 27 2004 E.g.f. (an equivalent version in Maple format): G:=exp(-1+(exp(z)-1)/2)*sum(exp(s*(s-1)*z/2)/s!, s=0..infinity);
The e.g.f.'s of A020554 (S(x)) and A014500 (U(x)) are related by S(x) = U(e^x-1).
EXAMPLE
The a(3) = 16 set multipartitions of {1, 1, 2, 2, 3, 3}:
(123)(123)
(1)(23)(123) (2)(13)(123) (3)(12)(123) (12)(13)(23)
(1)(1)(23)(23) (1)(2)(3)(123) (1)(2)(13)(23) (1)(3)(12)(23) (2)(2)(13)(13) (2)(3)(12)(13) (3)(3)(12)(12)
(1)(1)(2)(3)(23) (1)(2)(2)(3)(13) (1)(2)(3)(3)(12)
(1)(1)(2)(2)(3)(3)
(End)
MATHEMATICA
Ceiling[ CoefficientList[ Series[ Exp[ -1 + (Exp[ z ] - 1)/2 ]Sum[ Exp[ s(s - 1)z/2 ]/s!, {s, 0, 21} ], {z, 0, 9} ], z ] Table[ n!, {n, 0, 9} ] ] (* Mitch Harris, May 01 2004 *) 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]]]];
Table[Length[Select[mps[Ceiling[Range[1/2, n, 1/2]]], And@@UnsameQ@@@#&]], {n, 5}] (* Gus Wiseman, Jul 18 2018 *)
Number of independent polynomial invariants of symmetric matrix of order n.
+10
12
1, 2, 4, 11, 30, 95, 328, 1211, 4779, 19902, 86682, 393072, 1847264, 8965027, 44814034, 230232789, 1213534723, 6552995689, 36207886517, 204499421849, 1179555353219, 6942908667578, 41673453738272, 254918441681030, 1588256152307002, 10073760672179505
COMMENTS
Also, number of connected multigraphs with n edges (allowing loops) and any number of nodes.
Also the number of non-isomorphic connected multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018
FORMULA
Inverse Euler transform of A007717.
EXAMPLE
Non-isomorphic representatives of the a(3) = 11 connected multiset partitions of {1, 1, 2, 2, 3, 3}:
(112233),
(1)(12233), (12)(1233), (112)(233), (123)(123),
(1)(2)(1233), (1)(12)(233), (1)(23)(123), (12)(13)(23),
(1)(2)(3)(123), (1)(2)(13)(23).
(End)
MATHEMATICA
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++,
c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {};
For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t k; s += t]; s!/m];
Kq[q_, t_, k_] := SeriesCoefficient[1/Product[g = GCD[t, q[[j]]]; (1 - x^(q[[j]]/g))^g, {j, 1, Length[q]}], {x, 0, k}];
RowSumMats[n_, m_, k_] := Module[{s = 0}, Do[s += permcount[q]* SeriesCoefficient[ Exp[Sum[Kq[q, t, k]/t x^t, {t, 1, n}]], {x, 0, n}], {q, IntegerPartitions[m]}]; s/m!];
A007717 = Table[Print[n]; RowSumMats[n, 2 n, 2], {n, 0, 20}];
CROSSREFS
Cf. A002905, A007716, A007717, A007719, A020555, A050535, A053419, A076864, A191970, A316972, A316974.
Number of graphs with loops (symmetric relations) with n edges.
+10
12
1, 2, 5, 14, 38, 107, 318, 972, 3111, 10410, 36371, 132656, 504636, 1998361, 8224448, 35112342, 155211522, 709123787, 3342875421, 16234342515, 81102926848, 416244824068, 2192018373522, 11831511359378, 65387590986455, 369661585869273, 2135966349269550, 12604385044890628
COMMENTS
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. a(n) is the number of non-isomorphic multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n} with no equivalent vertices. For example, non-isomorphic representatives of the a(2) = 5 multiset partitions are (1)(122), (11)(22), (1)(1)(22), (1)(2)(12), (1)(1)(2)(2). - Gus Wiseman, Jul 18 2018 a(n) is the number of unlabeled simple graphs with n edges rooted at one vertex. - Andrew Howroyd, Nov 22 2020
PROG
seq(n)={my(A=O(x*x^n)); Vec(G(2*n, x+A, [1]))} \\ Andrew Howroyd, Nov 22 2020
CROSSREFS
Cf. A000664, A000666, A007716, A007717, A020555, A050535, A053419, A094574, A191970 (multisets), A316974, A339063.
Search completed in 0.011 seconds
|