OFFSET
0,2
COMMENTS
Row sums of A111636. - Peter Bala, Sep 30 2012
Column 2 of Table 2 in Read. - Peter Bala, Apr 11 2013
It appears that 5 does not divide a(n), that a(n) is even for n>0, that 3 divides a(2n) for n>0, that 7 divides a(6n+5), and that 13 divides a(12n+3). - Ralf Stephan, May 18 2013
REFERENCES
H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 79, Eq. 3.11.2.
LINKS
T. D. Noe, Table of n, a(n) for n = 0..50
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
S. R. Finch, Bipartite, k-colorable and k-colored graphs
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
A. Gainer-Dewar and I. M. Gessel, Enumeration of bipartite graphs and bipartite blocks, arXiv:1304.0139 [math.CO], 2013.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Acyclic orientation of graphs Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Martin Svatoš, Peter Jung, Jan Tóth, Yuyi Wang, and Ondřej Kuželka, On Discovering Interesting Combinatorial Integer Sequences, arXiv:2302.04606 [cs.LO], 2023, p. 17.
Eric Weisstein's World of Mathematics, k-Colorable Graph
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 88, Eq. 3.11.2.
FORMULA
a(n) = Sum_{k=0..n} binomial(n, k)*2^(k*(n-k)).
a(n) = 4 * A000683(n) + 2. - Vladeta Jovovic, Feb 02 2000
E.g.f.: Sum_{n>=0} exp(2^n*x)*x^n/n!. - Paul D. Hanna, Nov 27 2007
O.g.f.: Sum_{n>=0} x^n/(1 - 2^n*x)^(n+1). - Paul D. Hanna, Mar 08 2008
From Peter Bala, Apr 11 2013: (Start)
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then a generating function is E(x)^2 = 1 + 2*x + 6*x^2/(2!*2) + 26*x^3/(3!*2^3) + .... In general, E(x)^k, k = 1, 2, ..., is a generating function for labeled k-colored graphs (see Stanley). For other examples see A191371 (k = 3) and A223887 (k = 4).
If A(x) = 1 + 2*x + 6*x^2/2! + 26*x^3/3! + ... denotes the e.g.f. for this sequence then sqrt(A(x)) = 1 + x + 2*x^2/2! + 7*x^3/3! + ... is the e.g.f. for A047864, which counts labeled 2-colorable graphs. (End)
a(n) ~ c * 2^(n^2/4+n+1/2)/sqrt(Pi*n), where c = Sum_{k = -infinity..infinity} 2^(-k^2) = EllipticTheta[3, 0, 1/2] = 2.128936827211877... if n is even and c = Sum_{k = -infinity..infinity} 2^(-(k+1/2)^2) = EllipticTheta[2, 0, 1/2] = 2.12893125051302... if n is odd. - Vaclav Kotesovec, Jun 24 2013
EXAMPLE
For n=2, {1,2 black, not connected}, {1,2 white, not connected}, {1 black, 2 white, not connected}, {1 black, 2 white, connected}, {1 white, 2 black, not connected}, {1 white, 2 black, connected}.
G.f. = 1 + 2*x + 6*x^2 + 26*x^3 + 162*x^4 + 1442*x^5 + 18306*x^6 + ...
MATHEMATICA
Table[Sum[Binomial[n, k]2^(k(n-k)), {k, 0, n}], {n, 0, 20}] (* Harvey P. Dale, May 09 2012 *)
nmax = 20; CoefficientList[Series[Sum[E^(2^k*x)*x^k/k!, {k, 0, nmax}], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 05 2019 *)
PROG
(PARI) {a(n)=n!*polcoeff(sum(k=0, n, exp(2^k*x +x*O(x^n))*x^k/k!), n)} \\ Paul D. Hanna, Nov 27 2007
(PARI) {a(n)=polcoeff(sum(k=0, n, x^k/(1-2^k*x +x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Mar 08 2008
(PARI) N=66; x='x+O('x^N); egf = sum(n=0, N, exp(2^n*x)*x^n/n!);
Vec(serlaplace(egf)) \\ Joerg Arndt, May 04 2013
(Python)
from sympy import binomial
def a(n): return sum([binomial(n, k)*2**(k*(n - k)) for k in range(n + 1)]) # Indranil Ghosh, Jun 03 2017
(Magma)
A047863:= func< n | (&+[Binomial(n, k)*2^(k*(n-k)): k in [0..n]]) >;
[A047863(n): n in [0..40]]; // G. C. Greubel, Nov 03 2024
(SageMath)
def A047863(n): return sum(binomial(n, k)*2^(k*(n-k)) for k in range(n+1))
[A047863(n) for n in range(41)] # G. C. Greubel, Nov 03 2024
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
Better description from Christian G. Bower, Dec 15 1999
STATUS
approved