A006129 a(0), a(1), a(2), ... satisfy Sum_{k=0..n} a(k)*binomial(n,k) = 2^binomial(n,2), for n >= 0.

1, 0, 1, 4, 41, 768, 27449, 1887284, 252522481, 66376424160, 34509011894545, 35645504882731588, 73356937912127722841, 301275024444053951967648, 2471655539737552842139838345, 40527712706903544101000417059892, 1328579255614092968399503598175745633

Offset: 0

Author

Colin Mallows

Keywords

• nonn
• nice
• easy

Comments

Also labeled graphs on n unisolated nodes (inverse binomial transform of A006125). - Vladeta Jovovic, Apr 09 2000

Also the number of edge covers of the complete graph K_n. - Eric W. Weisstein, Mar 30 2017

Examples

			2^binomial(n,2) = 1 + binomial(n,2) + 4*binomial(n,3) + 41*binomial(n,4) + 768*binomial(n,5) + ...
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..50
• A. N. Bhavale, B. N. Waphare, Basic retracts and counting of lattices, Australasian J. of Combinatorics (2020) Vol. 78, No. 1, 73-99.
• C. L. Mallows & N. J. A. Sloane, Emails, May 1991
• N. J. A. Sloane, Transforms
• R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4.
• Eric Weisstein's World of Mathematics, Complete Graph
• Eric Weisstein's World of Mathematics, Edge Cover

Crossrefs

Row sums of A054548.

Cf. A322661 (if loops allowed), A086193 (directed edges), A002494 (unlabeled).

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 1,
      2^binomial(n, 2) - add(a(k)*binomial(n,k), k=0..n-1))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Oct 26 2012

Mathematica

a = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, 20}]; Range[0, 20]! CoefficientList[Series[a/Exp[x], {x, 0, 20}], x] (* Geoffrey Critzer, Oct 21 2011 *)
Table[Sum[(-1)^(n - k) Binomial[n, k] 2^Binomial[k, 2], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, May 04 2015 *)

PARI

for(n=0,25, print1(sum(k=0,n,(-1)^(n-k)*binomial(n, k)*2^binomial(k, 2)), ", ")) \\ G. C. Greubel, Mar 30 2017

Python

from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def a(n): return 1 if n==0 else 2**binomial(n, 2) - sum(a(k)*binomial(n, k) for k in range(n))
print([a(n) for n in range(21)]) # Indranil Ghosh, Aug 12 2017

Formula

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*2^binomial(k, 2).

E.g.f.: A(x)/exp(x) where A(x) = Sum_{n>=0} 2^C(n,2) x^n/n!. - Geoffrey Critzer, Oct 21 2011

a(n) ~ 2^(n*(n-1)/2). - Vaclav Kotesovec, May 04 2015

Extensions

More terms from Vladeta Jovovic, Apr 09 2000