

A060867


a(n) = (2^n  1)^2.


37



1, 9, 49, 225, 961, 3969, 16129, 65025, 261121, 1046529, 4190209, 16769025, 67092481, 268402689, 1073676289, 4294836225, 17179607041, 68718952449, 274876858369, 1099509530625, 4398042316801, 17592177655809
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Number of n X n matrices over GF(2) with rank 1.
Let M_2(n) be the 2 X 2 matrix M_2(n)(i,j)=i^n+j^n; then a(n)=det(M_2(n)).  Benoit Cloitre, Apr 21 2002
Number of distinct lines through the origin in the ndimensional lattice of side length 3. A001047 gives lines in the ndimensional lattice of side length 2, A049691 gives lines in the 2dimensional lattice of side length n.  Joshua Zucker, Nov 19 2003
a(n) is also the number of ntuples with each entry chosen from the subsets of {1,2} such that the intersection of all n entries is empty. See example. This may be shown by exhibiting a bijection to a set whose cardinality is obviously (2^n1)^2, namely the set of all pairs with each entry chosen from the 2^n1 proper subsets of {1,..,n}, i.e., for both entries {1,..,n} is forbidden. The bijection is given by (X_1,..,X_n) > (Y_1,Y_2) where for each j in {1,2} and each i in {1,..,n}, i is in Y_j if and only if j is in X_i. For example, a(2)=9, because the nine pairs of subsets of {1,2} with empty intersection are: ({},{}), ({},{1}), ({},{2}), ({},{1,2}), ({1},{}), ({2},{}), ({1,2},{}), ({1},{2}), ({2},{1}).  Peter C. Heinig (algorithms(AT)gmx.de), Apr 13 2007
Partial sums of A165665.  J. M. Bergot, Dec 06 2014
Except for a(1)=4, the number of active (ON,black) cells at stage 2^n1 of the twodimensional cellular automaton defined by "Rule 737", based on the 5celled von Neumann neighborhood.  Robert Price, May 23 2016
Apparently (with offset 0) also the number of active cells at state 2^n1 of the automaton defined by "Rule 7".  Robert Price, Apr 12 2016
a(n) is the difference xy where positive integer x has binary form of n leading ones followed by n zeros and nonnegative integer y has binary form of n leading zeros followed by n ones. For example, a(4) = (111100000001111)(base 2) = 24015 = 225 = 15^2. The result follows readily by noting y=2^n1 and x=2^(2*n)1y. Therefore xy=2^(2*n)2^(n+1)+1=(2^n1)^2.  Dennis P. Walsh, Sep 19 2016
Also the number of dominating sets in the nbarbell graph.  Eric W. Weisstein, Jun 29 2017
For n > 1, also the number of connected dominating sets in the complete bipartite graph K_n,n.  Eric W. Weisstein, Jun 29 2017


REFERENCES

Stanley, R. P., Enumerative Combinatorics: Volume 1: Wadsworth & Brooks: 1986: p. 11.


LINKS

Harry J. Smith, Table of n, a(n) for n = 1..200
M. Baake, F. Gahler and U. Grimm, Examples of substitution systems and their factors, arXiv preprint arXiv:1211.5466 [math.DS], 2012.  From N. J. A. Sloane, Jan 03 2013
Michael Baake, Franz GĂ¤hler, and Uwe Grimm, Examples of Substitution Systems and Their Factors, Journal of Integer Sequences, Vol. 16 (2013), #13.2.14.
Franck Ramaharo, A onevariable bracket polynomial for some Turk's head knots, arXiv:1807.05256 [math.CO], 2018.
Eric Weisstein's World of Mathematics, NearSquare Prime
Index entries for linear recurrences with constant coefficients, signature (7, 14, 8).


FORMULA

a(n) = (2^n  1)^2 = A000225(n)^2.
a(n) = sum_{j=1..n} sum_{k=1..n} binomial(n+j,nk).  Yalcin Aktar, Dec 28 2011
G.f.: x*(1+2*x)/((1x)(12*x)(14*x)). a(n) = 7*a(n1)14*a(n2)+8*a(n3).  Colin Barker, Feb 03 2012
E.g.f.: (1  2*exp(x) + exp(3*x))*exp(x).  Ilya Gutkovskiy, May 23 2016


EXAMPLE

a(2) = 9 because there are 10 (the second element in sequence A060704) singular 2 X 2 matrices over GF(2), that have rank <= 1 of which only the zero matrix has rank zero so a(2) = 10  1 = 9.


MAPLE

[seq ((stirling2(n, 2))^2, n=2..23)]; # Zerinvary Lajos, Dec 20 2006


MATHEMATICA

(2^Range[30]  1)^2 (* Harvey P. Dale, Sep 15 2013 *)
LinearRecurrence[{7, 14, 8}, {1, 9, 49}, 30] (* Harvey P. Dale, Sep 15 2013 *)
Table[(2^n  1)^2, {n, 30}] (* Eric W. Weisstein, Jun 29 2017 *)


PROG

(Sage) [stirling_number2(n, 2)^2 for n in xrange(2, 24)] # Zerinvary Lajos, Mar 14 2009
(PARI) for (n=1, 200, write("b060867.txt", n, " ", (2^n  1)^2)) \\ Harry J. Smith, Jul 13 2009
(PARI) a(n) = (2^n  1)^2; \\ Michel Marcus, Mar 11 2016


CROSSREFS

Cf. A000225, A060704, A165665 (first differences)
Sequence in context: A003297 A012248 A080026 * A192814 A228018 A081655
Adjacent sequences: A060864 A060865 A060866 * A060868 A060869 A060870


KEYWORD

nonn,easy


AUTHOR

Ahmed Fares (ahmedfares(AT)mydeja.com), May 04 2001


EXTENSIONS

Description changed to formula by Eric W. Weisstein, Jun 29 2017


STATUS

approved



