A020556 Number of oriented multigraphs on n labeled arcs (without loops).

1, 1, 7, 87, 1657, 43833, 1515903, 65766991, 3473600465, 218310229201, 16035686850327, 1356791248984295, 130660110400259849, 14177605780945123273, 1718558016836289502159, 230999008481288064430879, 34208659263890939390952225, 5549763869122023099520756513

Offset: 0

Author

Gilbert Labelle (gilbert(AT)lacim.uqam.ca) and Simon Plouffe

Keywords

• nonn

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

Examples

			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
		

References

• G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..288
• P. Blasiak, K. A. Penson and A. I. Solomon, The Boson Normal Ordering Problem and Generalized Bell Numbers, arXiv:quant-ph/0212072, 2002.
• P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, Phys. Lett. A 309 (2003) 198-205.
• P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem, arXiv:quant-ph/0402027, 2004.
• P. Codara, O. M. D'Antona, P. Hell, A simple combinatorial interpretation of certain generalized Bell and Stirling numbers, arXiv preprint arXiv:1308.1700 [cs.DM], 2013.
• G. Labelle, Counting enriched multigraphs according to the number of their edges (or arcs), Discrete Math., 217 (2000), 237-248.
• Peter Luschny, Set partitions
• G. Paquin, Dénombrement de multigraphes enrichis, Mémoire, Math. Dept., Univ. Québec à Montréal, 2004. [Cached copy, with permission]
• M. Riedel, Set partitions of unique elements from an n-by-m matrix where elements from the same row may not be in the same partition, Mathematics Stack Exchange.
• M. Schork, On the combinatorics of normal ordering bosonic operators and deforming it, J. Phys. A 36 (2003) 4651-4665.

Crossrefs

Cf. A020554, A014500, A020558, A090210, A095149, A106436, A182930.

Programs

Maple

A020556 := proc(n) local k;
add((-1)^(n+k)*binomial(n,k)*combinat[bell](n+k),k=0..n) end:
seq(A020556(n),n=0..17); # Peter Luschny, Mar 27 2011
# Uses floating point arithmetic, increase working precision for large n.
A020556 := proc(n) local r,s,i;
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:
seq(A020556(n),n=0..15); # Peter Luschny, Mar 30 2011
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:
A020556 := n -> T(2*n+1,n+1);
seq(A020556(n), n = 0..99); # Peter Luschny, Apr 03 2011

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: *)
a[n_] := Sum[(-1)^k*Binomial[n, k]*BellB[2n-k], {k, 0, n}]; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Jul 11 2017, after Vladeta Jovovic *)

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

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

a(n) = A095149(2n,n). - Alois P. Heinz, Dec 20 2018

a(n) = A106436(2n,n) = A182930(2n+1,n+1). - Alois P. Heinz, Jan 29 2019

Extensions

Edited by Robert G. Wilson v, Apr 30 2002