A079491 Numerator of Sum_{k=0..n} binomial(n,k)/2^(k*(k-1)/2).

1, 2, 7, 45, 545, 12625, 564929, 49162689, 8361575425, 2789624383745, 1830776926245889, 2368773751202917377, 6053217182280501452801, 30595465072175429929979905, 306239118989330960523869667329, 6076268165073202122463201684865025

Offset

0,2

Comments

Conjecture: Also the number of loop-graphs on n vertices without any non-loop edge having loops at both ends, with formula a(n) = Sum_{k=0..n} binomial(n,k) 2^(k*(n-k) + binomial(k,2)). The unlabeled version is A339832. - Gus Wiseman, Jan 25 2024

The above conjecture is true since (n-k)*k + binomial(n-k,2) = binomial(n,2) - binomial(k,2) and A006125 gives the denominators for this sequence. - Andrew Howroyd, Feb 20 2024

References

D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, CRC Press, 1999, p. 113.

Links

G. C. Greubel, Table of n, a(n) for n = 0..80

Formula

E.g.f.: Sum_{n>=0} a(n)*x^n/n! = Sum_{n>=0} exp(2^n*x)*2^(n(n-1)/2)*x^n/n!. - Paul D. Hanna, Sep 14 2009

a(n) = Sum_{k=0..n} binomial(n,k) * 2^(binomial(n,2)-binomial(k,2)). - Andrew Howroyd, Feb 20 2024

Example

1, 2, 7/2, 45/8, 545/64, 12625/1024, 564929/32768, 49162689/2097152, ...

Maple

f := n->add(binomial(n, k)/2^(k*(k-1)/2), k=0..n);

Mathematica

Table[Numerator[Sum[Binomial[n, k]/2^Binomial[k, 2], {k, 0, n}]], {n, 0, 20}] (* G. C. Greubel, Jun 19 2019 *)

Prog

(PARI) {a(n)=n!*polcoeff(sum(k=0, n, exp(2^k*x +x*O(x^n))*2^(k*(k-1)/2)*x^k/k!), n)} \\ Paul D. Hanna, Sep 14 2009
(PARI) a(n) = sum(k=0, n, binomial(n, k)*2^(binomial(n, 2)-binomial(k, 2))) \\ Andrew Howroyd, Feb 20 2024
(Magma) [Numerator( (&+[Binomial(n, k)/2^Binomial(k, 2): k in [0..n]]) ): n in [0..20]]; // G. C. Greubel, Jun 19 2019
(Sage) [numerator( sum(binomial(n, k)/2^binomial(k, 2) for k in (0..n)) ) for n in (0..20)] # G. C. Greubel, Jun 19 2019

Crossrefs

Denominators are in A006125.

Cf. A079492.

The unlabeled version is A339832 (loop-graphs interpretation).

A000085, A100861, A111924 count set partitions into singletons or pairs.

A000666 counts unlabeled loop-graphs, covering A322700.

A006125 (shifted left) counts labeled loop-graphs, covering A322661.

A006129 counts labeled covering graphs, connected A001187.

Sequence in context: A326878 A153549 A348880 * A266908 A162046 A162047

Adjacent sequences: A079488 A079489 A079490 * A079492 A079493 A079494

Keyword

nonn,frac

Author

N. J. A. Sloane, Jan 20 2003

Status

approved