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

%I M3678 #73 Nov 20 2023 13:09:44

%S 1,0,1,4,41,768,27449,1887284,252522481,66376424160,34509011894545,

%T 35645504882731588,73356937912127722841,301275024444053951967648,

%U 2471655539737552842139838345,40527712706903544101000417059892,1328579255614092968399503598175745633

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

%C Also labeled graphs on n unisolated nodes (inverse binomial transform of A006125). - _Vladeta Jovovic_, Apr 09 2000

%C Also the number of edge covers of the complete graph K_n. - _Eric W. Weisstein_, Mar 30 2017

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

%H Alois P. Heinz, <a href="/A006129/b006129.txt">Table of n, a(n) for n = 0..50</a>

%H A. N. Bhavale, B. N. Waphare, <a href="https://ajc.maths.uq.edu.au/pdf/78/ajc_v78_p073.pdf">Basic retracts and counting of lattices</a>, Australasian J. of Combinatorics (2020) Vol. 78, No. 1, 73-99.

%H C. L. Mallows & N. J. A. Sloane, <a href="/A006123/a006123.pdf">Emails, May 1991</a>

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H R. Tauraso, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Tauraso/tauraso18.html">Edge cover time for regular graphs</a>, JIS 11 (2008) 08.4.4.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteGraph.html">Complete Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EdgeCover.html">Edge Cover</a>

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

%F 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

%F a(n) ~ 2^(n*(n-1)/2). - _Vaclav Kotesovec_, May 04 2015

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

%p a:= proc(n) option remember; `if`(n=0, 1,

%p 2^binomial(n, 2) - add(a(k)*binomial(n,k), k=0..n-1))

%p end:

%p seq(a(n), n=0..20); # _Alois P. Heinz_, Oct 26 2012

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

%t Table[Sum[(-1)^(n - k) Binomial[n, k] 2^Binomial[k, 2], {k, 0, n}], {n, 0, 20}] (* _Vaclav Kotesovec_, May 04 2015 *)

%o (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

%o (Python)

%o from sympy.core.cache import cacheit

%o from sympy import binomial

%o @cacheit

%o def a(n): return 1 if n==0 else 2**binomial(n, 2) - sum(a(k)*binomial(n, k) for k in range(n))

%o print([a(n) for n in range(21)]) # _Indranil Ghosh_, Aug 12 2017

%Y Row sums of A054548.

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

%K nonn,nice,easy

%O 0,4

%A _Colin Mallows_

%E More terms from _Vladeta Jovovic_, Apr 09 2000