|
%I #111 Apr 07 2021 19:54:38
%S 1,9,49,225,961,3969,16129,65025,261121,1046529,4190209,16769025,
%T 67092481,268402689,1073676289,4294836225,17179607041,68718952449,
%U 274876858369,1099509530625,4398042316801,17592177655809,70368727400449,281474943156225,1125899839733761
%N a(n) = (2^n - 1)^2.
%C Number of n X n matrices over GF(2) with rank 1.
%C 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
%C Number of distinct lines through the origin in the n-dimensional lattice of side length 3. A001047 gives lines in the n-dimensional lattice of side length 2, A049691 gives lines in the 2-dimensional lattice of side length n. - _Joshua Zucker_, Nov 19 2003
%C a(n) is also the number of n-tuples 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^n-1)^2, namely the set of all pairs with each entry chosen from the 2^n-1 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
%C Partial sums of A165665. - _J. M. Bergot_, Dec 06 2014
%C Except for a(1)=4, the number of active (ON,black) cells at stage 2^n-1 of the two-dimensional cellular automaton defined by "Rule 737", based on the 5-celled von Neumann neighborhood. - _Robert Price_, May 23 2016
%C Apparently (with offset 0) also the number of active cells at state 2^n-1 of the automaton defined by "Rule 7". - _Robert Price_, Apr 12 2016
%C a(n) is the difference x-y 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) = (1111000-00001111)(base 2) = 240-15 = 225 = 15^2. The result follows readily by noting y=2^n-1 and x=2^(2*n)-1-y. Therefore x-y=2^(2*n)-2^(n+1)+1=(2^n-1)^2. - _Dennis P. Walsh_, Sep 19 2016
%C Also the number of dominating sets in the n-barbell graph. - _Eric W. Weisstein_, Jun 29 2017
%C For n > 1, also the number of connected dominating sets in the complete bipartite graph K_n,n. - _Eric W. Weisstein_, Jun 29 2017
%D Richard P. Stanley, Enumerative Combinatorics: Volume 1: Wadsworth & Brooks: 1986: p. 11.
%H Harry J. Smith, <a href="/A060867/b060867.txt">Table of n, a(n) for n = 1..200</a>
%H Michael Baake, Franz Gähler and Uwe Grimm, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Baake/baake3.html">Examples of substitution systems and their factors</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.14; <a href="http://arxiv.org/abs/1211.5466">arXiv preprint</a>, arXiv:1211.5466 [math.DS], 2012-2013. - From _N. J. A. Sloane_, Jan 03 2013
%H Franck Ramaharo, <a href="https://arxiv.org/abs/1807.05256">A one-variable bracket polynomial for some Turk's head knots</a>, arXiv:1807.05256 [math.CO], 2018.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Near-SquarePrime.html">Near-Square Prime</a>.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (7,-14,8).
%F a(n) = (2^n - 1)^2 = A000225(n)^2.
%F a(n) = sum_{j=1..n} sum_{k=1..n} binomial(n+j,n-k). - _Yalcin Aktar_, Dec 28 2011
%F G.f.: x*(1+2*x)/((1-x)(1-2*x)(1-4*x)). a(n) = 7*a(n-1)-14*a(n-2)+8*a(n-3). - _Colin Barker_, Feb 03 2012
%F E.g.f.: (1 - 2*exp(x) + exp(3*x))*exp(x). - _Ilya Gutkovskiy_, May 23 2016
%F Sum_{n>=1} 1/a(n) = A065443. - _Amiram Eldar_, Nov 12 2020
%e 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.
%p seq((Stirling2(n+1, 2))^2, n=1..25); # _Zerinvary Lajos_, Dec 20 2006
%t (2^Range[30] - 1)^2 (* _Harvey P. Dale_, Sep 15 2013 *)
%t LinearRecurrence[{7, -14, 8}, {1, 9, 49}, 30] (* _Harvey P. Dale_, Sep 15 2013 *)
%t Table[(2^n - 1)^2, {n, 30}] (* _Eric W. Weisstein_, Jun 29 2017 *)
%o (Sage) [stirling_number2(n+1,2)^2 for n in range(1,25)] # _Zerinvary Lajos_, Mar 14 2009
%o (PARI) for (n=1, 200, write("b060867.txt", n, " ", (2^n - 1)^2)) \\ _Harry J. Smith_, Jul 13 2009
%o (PARI) a(n) = (2^n - 1)^2; \\ _Michel Marcus_, Mar 11 2016
%Y Cf. A000225, A060704, A065443, A165665 (first differences)
%K nonn,easy
%O 1,2
%A Ahmed Fares (ahmedfares(AT)my-deja.com), May 04 2001
%E Description changed to formula by _Eric W. Weisstein_, Jun 29 2017
|
