Displaying 1-10 of 13 results found.
Erroneous version of A020554.
(Formerly M3029 N1228)
+20
1
1, 3, 16, 139, 1750, 29388, 623909
REFERENCES
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Number of oriented multigraphs on n labeled arcs (without loops).
+10
29
1, 1, 7, 87, 1657, 43833, 1515903, 65766991, 3473600465, 218310229201, 16035686850327, 1356791248984295, 130660110400259849, 14177605780945123273, 1718558016836289502159, 230999008481288064430879, 34208659263890939390952225, 5549763869122023099520756513
COMMENTS
Generalized Bell numbers: a(n) = Sum_{k=2..2*n} A078739(n,k), n >= 1. Let B_{m}(x) = Sum_{j>=0} exp(j!/(j-m)!*x-1)/j! then
a(n) = n! [x^n] taylor(B_{2}(x)), where [x^n] denotes the coefficient of x^n in the Taylor series for B_{2}(x). a(n) is row 2 of the square array representation of A090210. - Peter Luschny, Mar 27 2011 Also the number of set partitions of {1,2,...,2n+1} such that the block |n+1| is a part but no block |m| with m < n+1. - Peter Luschny, Apr 03 2011
REFERENCES
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.
FORMULA
a(n) = e*Sum_{k>=0} ((k+2)!^n/(k+2)!)*(k!^n), n>=1.
a(n) = (1/e)*Sum_{k>=2} (k*(k-1))^n/k!, n >= 1. a(0) := 1. (From eq.(26) with r=2 of the Schork reference.)
E.g.f.: (1/e)*(2 + Sum_{k>=2} ((exp(k*(k-1)*x))/k!)) (from top of p. 4656 of the Schork reference).
a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*Bell(2*n-k). - Vladeta Jovovic, May 02 2004
EXAMPLE
Example: For n = 2 the a(2) = 7 are the number of set partitions of 5 such that the block |3| is a part but no block |m| with m < 3: 3|1245, 3|4|125, 3|5|124, 3|12|45, 3|14|25, 3|15|24, 3|4|5|12. - Peter Luschny, Apr 05 2011
MAPLE
add((-1)^(n+k)*binomial(n, k)*combinat[bell](n+k), k=0..n) end:
# Uses floating point arithmetic, increase working precision for large n.
if n=0 then 1 else r := [seq(3, i=1..n-1)]; s := [seq(1, i=1..n-1)];
exp(-x)*2^(n-1)*hypergeom(r, s, x); round(evalf(subs(x=1, %), 99)) fi end:
T := proc(n, k) option remember;
if n = 1 then 1
elif n = k then T(n-1, 1) - T(n-1, n-1)
else T(n-1, k) + T(n, k+1) fi end:
MATHEMATICA
f[n_] := f[n] = Sum[(k + 2)!^n/((k + 2)!*(k!^n)*E), {k, 0, Infinity}]; Table[ f[n], {n, 1, 16}]
(* Second program: *)
PROG
(PARI) a(n)={my(bell=serlaplace(exp(exp(x + O(x^(2*n+1)))-1))); sum(k=0, n, (-1)^k*binomial(n, k)*polcoef(bell, 2*n-k))} \\ Andrew Howroyd, Jan 13 2020
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 bicoverings of an n-set.
(Formerly M4559 N1941)
+10
24
1, 0, 1, 8, 80, 1088, 19232, 424400, 11361786, 361058000, 13386003873, 570886397340, 27681861184474, 1511143062540976, 92091641176725504, 6219762391554815200, 462595509951068027741, 37676170944802047077248, 3343539821715571537772071, 321874499078487207168905840
COMMENTS
Another description: number of proper 2-covers of [1,...,n].
REFERENCES
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 303, #40.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
E.g.f. for k-block bicoverings of an n-set is exp(-x-1/2*x^2*(exp(y)-1))*Sum_{i=0..inf} x^i/i!*exp(binomial(i, 2)*y).
The e.g.f.'s of A002718 (T(x)) and A060053 (V(x)) are related by T(x) = V(e^x-1). a(n) = Sum_{m=0..n + floor(n/2); k=0..n; s=0..min(m/2,k); t=0..m-2s} Stirling2(n,k) * k!/m! * binomial(m,2s) * A001147(s) * (-1)^(m+s+t) * binomial(m-2s,t) * binomial(t*(t-1)/2,k-s). Interpret m as the number of blocks in a bicovering, k the number of clumps of points that are always all together in blocks. This formula counts bicoverings by quotienting them to the clumpless case (an operation which preserves degree) and counting incidence matrices of those, and counts those matrices as the transposes of incidence matrices of labeled graphs with no isolated points and no isolated edges. - David Pasino, Jul 09 2016
EXAMPLE
For n=3, there are 8 collections of distinct subsets of {1,2,3} with the property that each of 1, 2, and 3 appears in exactly two subsets:
{1,2,3},{1,2},{3}
{1,2,3},{1,3},{2}
{1,2,3},{2,3},{1}
{1,2,3},{1},{2},{3}
{1,2},{1,3},{2,3}
{1,2},{1,3},{2},{3}
{1,2},{2,3},{1},{3}
{1,3},{2,3},{1},{2}
MATHEMATICA
nmax = 16; imax = 2*(nmax - 2); egf := E^(-x - 1/2*x^2*(E^y - 1))*Sum[(x^i/i!)*E^(Binomial[i, 2]*y), {i, 0, imax}]; fx = CoefficientList[Series[egf, {y, 0, imax}], y]*Range[0, imax]!; a[n_] := Drop[ CoefficientList[ Series[fx[[n + 1]], {x, 0, imax}], x], 3] // Total; Table[ a[n] , {n, 2, nmax}] (* Jean-François Alcover, Apr 04 2013 *)
Number of graphs with unlabeled (non-isolated) nodes and n labeled edges.
+10
20
1, 1, 2, 9, 70, 794, 12055, 233238, 5556725, 158931613, 5350854707, 208746406117, 9315261027289, 470405726166241, 26636882237942128, 1678097862705130667, 116818375064650241036, 8932347052564257212796, 746244486452472386213939, 67796741482683128375533560
REFERENCES
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.
FORMULA
E.g.f.: exp(-1+x/2)*Sum((1+x)^binomial(n, 2)/n!, n=0..infinity) [probably in the Labelle paper]. - Vladeta Jovovic, Apr 27 2004 The e.g.f.'s of A020554 (S(x)) and A014500 (U(x)) are related by S(x) = U(e^x-1). The e.g.f.'s of A014500 (U(x)) and A060053 (V(x)) are related by U(x) = e^x*V(x).
MAPLE
read("transforms") ;
A020556 := proc(n) local k; add((-1)^(n+k)*binomial(n, k)*combinat[bell](n+k), k=0..n) end proc:
A014500 := proc(n) local i, gexp, lexp;
gexp := [seq(1/2^i/i!, i=0..n+1)] ;
lexp := add( A020556(i)*((log(1+x))/2)^i/i!, i=0..n+1) ; lexp := taylor(lexp, x=0, n+1) ;
lexp := gfun[seriestolist](lexp, 'ogf') ;
CONV(gexp, lexp) ; op(n+1, %)*n! ; end proc:
MATHEMATICA
max = 20; A020556[n_] := Sum[(-1)^(n+k)*Binomial[n, k]*BellB[n+k], {k, 0, n}]; egf = Exp[x/2]*Sum[ A020556[n]*(Log[1+x]/2)^n/n!, {n, 0, max}] + O[x]^max; CoefficientList[egf, x]*Range[0, max-1]! (* Jean-François Alcover, Feb 19 2017, after Vladeta Jovovic *)
PROG
(PARI) \\ here egf1 is A020556 as e.g.f. egf1(n)={my(bell=serlaplace(exp(exp(x + O(x^(2*n+1)))-1))); sum(i=0, n, sum(k=0, i, (-1)^k*binomial(i, k)*polcoef(bell, 2*i-k))*x^i/i!) + O(x*x^n)}
seq(n)={my(B=egf1(n), L=log(1+x + O(x*x^n))/2); Vec(serlaplace(exp(x/2 + O(x*x^n))*sum(k=0, n, polcoef(B , k)*L^k)))} \\ Andrew Howroyd, Jan 13 2020
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.
T(n,k) = number of (n*k) X k binary arrays with rows in nonincreasing order and n ones in every column.
+10
19
1, 2, 1, 5, 3, 1, 15, 16, 4, 1, 52, 139, 39, 5, 1, 203, 1750, 862, 81, 6, 1, 877, 29388, 35775, 4079, 150, 7, 1, 4140, 624889, 2406208, 507549, 15791, 256, 8, 1, 21147, 16255738, 238773109, 127126912, 5442547, 52450, 410, 9, 1, 115975, 504717929, 32867762616
EXAMPLE
Array begins:
========================================================================
n\k| 1 2 3 4 5 6 7 8
---+--------------------------------------------------------------------
1 | 1 2 5 15 52 203 877 4140
2 | 1 3 16 139 1750 29388 624889 16255738
3 | 1 4 39 862 35775 2406208 238773109 32867762616
4 | 1 5 81 4079 507549 127126912 55643064708 38715666455777
5 | 1 6 150 15791 5442547 4762077620 8738543204786
6 | 1 7 256 52450 46757209 135029200594
7 | 1 8 410 154279 335279744
8 | 1 9 625 411180
9 | 1 10 915
...
All solutions for 6 X 2
..1..1....1..1....1..0....1..1
..1..1....1..1....1..0....1..0
..1..0....1..1....1..0....1..0
..0..1....0..0....0..1....0..1
..0..0....0..0....0..1....0..1
..0..0....0..0....0..1....0..0
PROG
(PARI)
WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); WeighT(v)[n]^k/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k, q=Vec(exp(O(x*x^m) + intformal((x^n-1)/(1-x)))/(1-x))); if(n==0, 1, sum(j=0, m, my(s=0); forpart(p=j, s+=D(p, n, k), [1, n]); s*q[#q-j]))} \\ Andrew Howroyd, Dec 12 2018
Number of non-isomorphic strict multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}.
+10
15
1, 1, 4, 14, 49, 173, 652, 2494
COMMENTS
Also the number of unlabeled multigraphs with n edges, allowing loops, spanning an initial interval of positive integers with no equivalent vertices (two vertices are equivalent if in every edge the multiplicity of the first is equal to the multiplicity of the second). For example, non-isomorphic representatives of the a(2) = 4 multigraphs are {(1,2),(1,3)}, {(1,1),(1,2)}, {(1,1),(2,2)}, {(1,1),(1,1)}.
EXAMPLE
Non-isomorphic representatives of the a(3) = 14 strict multiset partitions:
(112233),
(1)(12233), (11)(2233), (12)(1233), (112)(233),
(1)(2)(1233), (1)(12)(233), (1)(23)(123), (2)(11)(233), (11)(22)(33), (12)(13)(23),
(1)(2)(3)(123), (1)(2)(12)(33), (1)(2)(13)(23).
CROSSREFS
Cf. A001055, A007716, A007717, A007719, A020554, A020555, A045778, A050535, A053419, A061742, A094574, A162247, A316892, A316972.
Number of tri-coverings of a set.
+10
9
1, 1, 4, 39, 862, 35775, 2406208, 238773109, 32867762616, 6009498859909, 1412846181645855, 416415343791239162, 150747204270574506888, 65905473934553360340713, 34305461329980340135062217, 21003556204331356488142290707, 14967168378184553824642693791437
EXAMPLE
For n=2, a(2)=4, since if you have two sets of identical triples the A-brothers and the B-sisters, and you want to arrange them into a multiset of nonempty sets, where no one is allowed to cohabitate with his or her sibling, the following are possible 1.{{AB},{AB},{AB}} 2.{{AB},{AB},{A},{B}} 3.{{AB},{A},{A},{B},{B}} 4.{{A},{A},{A},{B},{B},{B}}.
MAPLE
Do SeqBrn(3, n); in the Maple package BABUSHKAS (see links) where n+1 is the number of desired terms.
Number of graphs with loops, having unlabeled (non-isolated) nodes and n labeled edges.
+10
5
1, 2, 7, 43, 403, 5245, 89132, 1898630, 49209846, 1517275859, 54669946851, 2269075206395, 107199678164289, 5707320919486026, 339510756324234931, 22400182888853554291, 1628654713107465602783, 129754625253841669625051
REFERENCES
G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.
FORMULA
E.g.f.: exp(-1+x/2)*Sum((1+x)^binomial(n+1, 2)/n!, n=0..infinity) [probably in the Labelle paper]. - Vladeta Jovovic, Apr 27 2004
Search completed in 0.077 seconds
|