OFFSET
0,3
COMMENTS
a(n) is the number of n X n matrices of 0's and 1's with the property that there is no index k such that both the k-th column and the k-th row consist of all zeros.
a(n) is the number of binary relations on n labeled vertices with no vertex of indegree and outdegree = 0. - Geoffrey Critzer, Oct 02 2012
REFERENCES
E. A. Bender and S. G. Williamson, Foundations of Combinatorics with Applications, Dover, 2005, exercise 4.1.6.
LINKS
Brian Drake, Table of n, a(n) for n = 0..50
FORMULA
a(n) = Sum_{k=0..n} (-1)^k*binomial(n,k)*2^((n-k)^2).
a(n) ~ 2^(n^2). - Vaclav Kotesovec, Oct 30 2017
MAPLE
N:=8: seq( sum(binomial(n, i)*2^((n-i)^2)*(-1)^(i), i=0..n), n=0..N);
MATHEMATICA
Table[Sum[(-1)^k Binomial[n, k] 2^(n-k)^2, {k, 0, n}], {n, 0, 20}] (* Geoffrey Critzer, Oct 02 2012 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Brian Drake, Feb 17 2010
STATUS
approved