|
|
A002416
|
|
a(n) = 2^(n^2).
|
|
119
|
|
|
1, 2, 16, 512, 65536, 33554432, 68719476736, 562949953421312, 18446744073709551616, 2417851639229258349412352, 1267650600228229401496703205376, 2658455991569831745807614120560689152, 22300745198530623141535718272648361505980416, 748288838313422294120286634350736906063837462003712
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
For n >= 1, a(n) is the number of n X n (0, 1) matrices.
Also number of directed graphs on n labeled nodes allowing self-loops (cf.A053763).
1/2^(n^2) is the Hankel transform of C(n, n/2)*(1 + (-1)^n)/(2*2^n), or C(2n, n)/4^n with interpolated zeros. -Paul Barry,Sep 27 2007
a(n) is also the order of the semigroup (monoid) of all binary relations on an n-set. -Abdullahi Umar,Sep 14 2008
With offset = 1, a(n) is the number of n X n (0, 1) matrices with an even number of 1's in every row and in every column. -Geoffrey Critzer,May 23 2013
a(n) is the number of functions from an n-set to its power set (by definition of function including the empty function only when n = 0). -Rick L. Shepherd,Dec 27 2014
|
|
REFERENCES
|
John M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995). -Abdullahi Umar,Sep 14 2008
|
|
LINKS
|
Eric Weisstein's World of Mathematics,01-Matrix.
|
|
FORMULA
|
a(n) = 2^n * Sum_{i = 0..C(n, 2)} C(C(n, 2), i)*3^i. The summation conditions on i, 0 <= i <= C(n, 2), the number of 1's above the main diagonal in the matrix representations of the relations on {1, 2,..., n}. -Geoffrey Critzer,Feb 18 2011
G.f.: 1 / (1 - 2^1*x / (1 - 2^1*(2^2-1)*x / (1 - 2^5 * x / (1 - 2^3*(2^4-1)*x / (1 - 2^9*x / (1 - 2^5*(2^6-1)*x /...)))))). -Michael Somos,May 12 2012
|
|
EXAMPLE
|
G.f. = 1 + 2*x + 16*x^2 + 512*x^3 + 65536*x^4 + 33554432*x^5 +...
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) a(n)=polresultant((x-1)^n, (x+1)^n, x) \\Ralf Stephan
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|