cp's OEIS Frontend

A002697 a(n) = n*4^(n-1).

%I A002697 M4534 N1923 #226 Feb 16 2025 08:32:26
%S A002697 0,1,8,48,256,1280,6144,28672,131072,589824,2621440,11534336,50331648,
%T A002697 218103808,939524096,4026531840,17179869184,73014444032,309237645312,
%U A002697 1305670057984,5497558138880,23089744183296
%N A002697 a(n) = n*4^(n-1).
%C A002697 Coefficient of x^(2n-2) in Chebyshev polynomial T(2n) is -a(n).
%C A002697 Let M_n be the n X n matrix m_(i,j) = 1 + 2*abs(i-j); then det(M_n) = (-1)^(n-1)*a(n-1). - _Benoit Cloitre_, May 28 2002
%C A002697 Number of subsequences 00 in all words of length n+1 on the alphabet {0,1,2,3}. Example: a(2)=8 because we have 000,001,002,003,100,200,300 (the other 57=A125145(3) words of length 3 have no subsequences 00). a(n) = Sum_{k=0..n} k*A128235(n+1, k). - _Emeric Deutsch_, Feb 27 2007
%C A002697 Let P(A) be the power set of an n-element set A. Then a(n) = the sum of the size of the symmetric difference of x and y for every subset {x,y} of P(A). - _Ross La Haye_, Dec 30 2007 (See the comment from Bernard Schott below.)
%C A002697 Let P(A) be the power set of an n-element set A and B be the Cartesian product of P(A) with itself. Then remove (y,x) from B when (x,y) is in B and x != y and call this R35. Then a(n) = the sum of the size of the symmetric difference of x and y for every (x,y) of R35. [proposed edit of comment just above; by _Ross La Haye_]
%C A002697 The numbers in this sequence are the Wiener indices of the graphs of n-cubes (Boolean hypercubes). For example, the 3-cube is the graph of the standard cube whose Wiener index is 48. - _K.V.Iyer_, Feb 26 2009
%C A002697 From _Gary W. Adamson_, Sep 06 2009: (Start)
%C A002697 Starting (1, 8, 48, ...) = 4th binomial transform of [1, 4, 0, 0, 0, ...].
%C A002697 Equals the sum of terms in 2^n X 2^n semi-magic square arrays in which each row and column is composed of a binomial frequency of terms in the set (1, 3, 5, 7, ...).
%C A002697 The first few such arrays = [1] [1,3; 3,1]; /Q.
%C A002697   [1, 3, 5, 3;
%C A002697    3, 1, 3, 5;
%C A002697    5, 3, 1, 3;
%C A002697    3, 5, 3, 1]
%C A002697 (sum of terms = 48, with a binomial frequency of (1, 2, 1) as to (1, 3, 5) in each row and column)
%C A002697   [1, 3, 5, 3, 5, 7, 5, 3;
%C A002697    3, 1, 3, 5, 7, 5, 3, 5;
%C A002697    5, 3, 1, 3, 5, 3, 5, 7;
%C A002697    3, 5, 3, 1, 3, 5, 7, 5;
%C A002697    5, 7, 5, 3, 1, 3, 5, 3;
%C A002697    7, 5, 3, 5, 3, 1, 3, 5;
%C A002697    5, 3, 5, 7, 5, 3, 1, 3;
%C A002697    3, 5, 7, 5, 3, 5, 3, 1]
%C A002697 (sum of terms = 256, with each row and column composed of one 1, three 3's, three 5's, and one 7)
%C A002697 ... (End)
%C A002697 Let P(A) be the power set of an n-element set A and B be the Cartesian product of P(A) with itself. Then a(n) = the sum of the size of the intersection of x and y for every (x,y) of B. - _Ross La Haye_, Jan 05 2013
%C A002697 Following the last comment of Ross, A002699 is the similar sequence when "intersection" is replaced by "symmetric difference" and A212698 is the similar sequence when "intersection" is replaced by "union". - _Bernard Schott_, Jan 04 2013
%C A002697 Also, following the first comment of Ross, A082134 is the similar sequence when "symmetric difference" is replaced by "intersection" and A133224 is the similar sequence when "symmetric difference" is replaced by "union". - _Bernard Schott_, Jan 15 2013
%C A002697 Let [n] denote the set {1,2,3,...,n} and denote an n-permutation of the elements of [n] by p = p(1)p(2)p(3)...p(n), where p(i) is the i-th entry in the linear order given by p. Then (p(i),p(j)) is an inversion of p if i < j but p(i) > p(j). Denote the number of inversions of p by inv(p) and call a 2n-permutation p = p(1)p(2)...p(2n) 2-ordered if p(1) < p(3) < ... < p(2n-1) and p(2) < p(4) < ... < p(2n). Then Sum(inv(p)) = n*4^(n-1), where the sum is taken over all 2-ordered 2n-permutations of p. See Bona reference below. - _Ross La Haye_, Jan 21 2014
%C A002697 Sum over all peaks of Dyck paths of semilength n of the product of the x and y coordinates. - _Alois P. Heinz_, May 29 2015
%C A002697 Sum of the number of all edges over all j-dimensional subcubes of the boolean hypercube graph of dimension n, Q_n, for all j, so a(n) = Sum_{j=1..n} binomial(n,j)*2^(n-j) * j*2^(j-1). - _Constantinos Kourouzides_, Mar 24 2024
%D A002697 Miklos Bona, Combinatorics of Permutations, Chapman and Hall/CRC, 2004, pp. 1, 43, 64.
%D A002697 C. Lanczos, Applied Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 516.
%D A002697 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002697 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002697 Danny Rorabaugh, <a href="/A002697/b002697.txt">Table of n, a(n) for n = 0..1000</a>
%H A002697 F. Ellermann, <a href="/A001792/a001792.txt">Illustration of binomial transforms</a>
%H A002697 Samuele Giraudo, <a href="http://arxiv.org/abs/1603.01040">Pluriassociative algebras I: The pluriassociative operad</a>, arXiv:1603.01040 [math.CO], 2016.
%H A002697 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=414">Encyclopedia of Combinatorial Structures 414</a>
%H A002697 Milan Janjić, <a href="https://www.emis.de/journals/JIS/VOL21/Janjic2/janjic103.html">Pascal Matrices and Restricted Words</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
%H A002697 Constantinos Kourouzides, <a href="https://github.com/Constakour/A-double-counting-argument-on-the-hypercube-graph">A double counting argument on the hypercube graph</a>
%H A002697 Ross La Haye, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/LaHaye/lahaye5.html">Binary Relations on the Power Set of an n-Element Set</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
%H A002697 C. Lanczos, <a href="/A002457/a002457.pdf">Applied Analysis</a> (Annotated scans of selected pages)
%H A002697 Aleksandar Petojević, <a href="http://dx.doi.org/10.5937/MatMor0801037P">A Note about the Pochhammer Symbol</a>, Mathematica Moravica, Vol. 12-1 (2008), 37-42.
%H A002697 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A002697 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A002697 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%H A002697 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/WienerIndex.html">Wiener Index</a>
%H A002697 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (8,-16).
%F A002697 a(n) = n*4^(n-1).
%F A002697 G.f.: x/(1-4x)^2. a(n+1) is the convolution of powers of 4 (A000302). - _Wolfdieter Lang_, May 16 2003
%F A002697 Third binomial transform of n. E.g.f.: x*exp(4x). - _Paul Barry_, Jul 22 2003
%F A002697 a(n) = Sum_{k=0..n} k*binomial(2*n, 2*k). - _Benoit Cloitre_, Jul 30 2003
%F A002697 For n>=0, a(n+1) = Sum_{i+j+k+l=n} binomial(2i, i)*binomial(2j, j)*binomial(2k, k)*binomial(2l, l). - _Philippe Deléham_, Jan 22 2004
%F A002697 a(n) = Sum_{k=0..n} 4^(n-k)*binomial(n-k+1, k)*binomial(1, (k+1)/2)*(1-(-1)^k)/2. - _Paul Barry_, Oct 15 2004
%F A002697 Sum_{n>0} 1/a(n) = 8*log(2) - 4*log(3). - _Jaume Oliver Lafont_, Sep 11 2009
%F A002697 a(0) = 0, a(n) = 4*a(n-1) + 4^(n-1). - _Vincenzo Librandi_, Dec 31 2010
%F A002697 a(n+1) is the convolution of A000984 with A002457. - _Rui Duarte_, Oct 08 2011
%F A002697 a(0) = 0, a(1) = 1, a(n) = 8*a(n-1) - 16*a(n-2). - _Harvey P. Dale_, Jan 18 2012
%F A002697 a(n) = A002699(n)/2 = A212698(n)/3. - _Bernard Schott_, Jan 04 2013
%F A002697 G.f.: W(0)*x/2 , where W(k) = 1 + 1/( 1 - 4*x*(k+2)/( 4*x*(k+2) + (k+1)/W(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Aug 19 2013
%F A002697 Sum_{n>=1} (-1)^(n+1)/a(n) = 4*log(5/4). - _Amiram Eldar_, Oct 28 2020
%F A002697 a(n) = (1/2)*Sum_{k=0..n} k*binomial(2*n, k). Compare this with the formula of _Benoit Cloitre_ above. - _Wolfdieter Lang_, Nov 12 2021
%F A002697 a(n) = (-1)^(n-1)*det(M(n)) for n > 0, where M(n) is the n X n symmetric Toeplitz matrix whose first row consists of 1, 3, ..., 2*n-1. - _Stefano Spezia_, Aug 04 2022
%e A002697 From _Bernard Schott_, Jan 04 2013: (Start)
%e A002697 See the comment about intersection of X and Y.
%e A002697 If A={b,c}, then in P(A) we have:
%e A002697 {b}Inter{b}={b},
%e A002697 {b}Inter{b,c}={b},
%e A002697 {c}Inter{c}={c},
%e A002697 {c}Inter{b,c}={c},
%e A002697 {b,c}Inter{b}={b},
%e A002697 {b,c}Inter{c}={c},
%e A002697 {b,c}Inter{b,c}={b,c}
%e A002697 and : #{b}+ #{b}+ #{c}+ #{c}+ #{b}+ #{c}+ #{b,c} = 8 = 2*4^(2-1) = a(2).
%e A002697 The other intersections are empty.
%e A002697 (End)
%p A002697 A002697:=1/(4*z-1)**2; # conjectured by _Simon Plouffe_ in his 1992 dissertation
%p A002697 A002697:=n->n*4^(n-1): seq(A002697(n), n=0..30); # _Wesley Ivan Hurt_, Mar 30 2014
%t A002697 Table[n 4^(n - 1), {n, 0, 30}] (* _Harvey P. Dale_, Jan 18 2012 *)
%t A002697 LinearRecurrence[{8, -16}, {0, 1}, 30] (* _Harvey P. Dale_, Jan 18 2012 *)
%t A002697 CoefficientList[Series[x/(1 - 4 x)^2, {x, 0, 20}], x] (* _Eric W. Weisstein_, Sep 08 2017 *)
%o A002697 (PARI) a(n)=if(n<0,0,n*4^(n-1))
%o A002697 (Sage) [n*4^(n-1) for n in range(22)] # _Danny Rorabaugh_, Mar 27 2015
%Y A002697 Cf. A000051, A000302, A000984, A001792, A002457, A002699, A027656, A038231, A082134, A083672, A125145, A128235, A133224, A212698.
%K A002697 nonn,easy
%O A002697 0,3
%A A002697 _N. J. A. Sloane_