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,3

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.

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.

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

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

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 *)

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

Crossrefs

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

Sequence in context: A360237 A279845 A231447 * A303061 A007803 A034219

Adjacent sequences: A020553 A020554 A020555 * A020557 A020558 A020559

Keyword

nonn

Author

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

Extensions

Edited by Robert G. Wilson v, Apr 30 2002

Status

approved