login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002697 a(n) = n*4^(n-1).
(Formerly M4534 N1923)
40
0, 1, 8, 48, 256, 1280, 6144, 28672, 131072, 589824, 2621440, 11534336, 50331648, 218103808, 939524096, 4026531840, 17179869184, 73014444032, 309237645312, 1305670057984, 5497558138880, 23089744183296 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Coefficient of x^(2n-2) in Chebyshev polynomial T(2n) is -a(n).

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

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

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.)

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]

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

From Gary W. Adamson, Sep 06 2009: (Start)

Starting (1, 8, 48, ...) = 4th binomial transform of [1, 4, 0, 0, 0, ...].

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, ...).

The first few such arrays = [1] [1,3; 3,1]; /Q.

  [1, 3, 5, 3;

   3, 1, 3, 5;

   5, 3, 1, 3;

   3, 5, 3, 1]

(sum of terms = 48, with a binomial frequency of (1, 2, 1) as to (1, 3, 5) in each row and column)

  [1, 3, 5, 3, 5, 7, 5, 3;

   3, 1, 3, 5, 7, 5, 3, 5;

   5, 3, 1, 3, 5, 3, 5, 7;

   3, 5, 3, 1, 3, 5, 7, 5;

   5, 7, 5, 3, 1, 3, 5, 3;

   7, 5, 3, 5, 3, 1, 3, 5;

   5, 3, 5, 7, 5, 3, 1, 3;

   3, 5, 7, 5, 3, 5, 3, 1]

(sum of terms = 256, with each row and column composed of one 1, three 3's, three 5's, and one 7)

... (End)

Sum_{n>0} 1/a(n) = 8*log(2) - 4*log(3). - Jaume Oliver Lafont, Sep 11 2009

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

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

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

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

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

REFERENCES

Miklos Bona, Combinatorics of Permutations, Chapman and Hall/CRC, 2004, pp. 1, 43, 64.

C. Lanczos, Applied Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 516.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Danny Rorabaugh, Table of n, a(n) for n = 0..1000

F. Ellermann, Illustration of binomial transforms

Samuele Giraudo, Pluriassociative algebras I: The pluriassociative operad, arXiv:1603.01040 [math.CO], 2016.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 414

Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.

Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.

C. Lanczos, Applied Analysis (Annotated scans of selected pages)

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

Eric Weisstein's World of Mathematics, Hypercube Graph

Eric Weisstein's World of Mathematics, Wiener Index

Index entries for linear recurrences with constant coefficients, signature (8,-16).

FORMULA

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

G.f.: x/(1-4x)^2. a(n+1) is the convolution of powers of 4 (A000302). - Wolfdieter Lang, May 16 2003

Third binomial transform of n. E.g.f.: x*exp(4x). - Paul Barry, Jul 22 2003

a(n) = Sum_{k=0..n} k*binomial(2*n, 2*k). - Benoit Cloitre, Jul 30 2003

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

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

a(0) = 0, a(n) = 4*a(n-1) + 4^(n-1). - Vincenzo Librandi, Dec 31 2010

a(n+1) is the convolution of A000984 with A002457. - Rui Duarte, Oct 08 2011

a(0) = 0, a(1) = 1, a(n) = 8*a(n-1) - 16*a(n-2). - Harvey P. Dale, Jan 18 2012

a(n) = A002699(n)/2 = A212698(n)/3. - Bernard Schott, Jan 04 2013

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

EXAMPLE

From Bernard Schott, Jan 04 2013: (Start)

See the comment about intersection of X and Y.

If A={b,c}, then in P(A) we have:

{b}Inter{b}={b},

{b}Inter{b,c}={b},

{c}Inter{c}={c},

{c}Inter{b,c}={c},

{b,c}Inter{b}={b},

{b,c}Inter{c}={c},

{b,c}Inter{b,c}={b,c}

and : #{b}+ #{b}+ #{c}+ #{c}+ #{b}+ #{c}+ #{b,c} = 8 = 2*4^(2-1) = a(2).

The other intersections are empty.

(End)

MAPLE

A002697:=1/(4*z-1)**2; # conjectured by Simon Plouffe in his 1992 dissertation

A002697:=n->n*4^(n-1): seq(A002697(n), n=0..30); # Wesley Ivan Hurt, Mar 30 2014

MATHEMATICA

Table[n 4^(n - 1), {n, 0, 30}] (* Harvey P. Dale, Jan 18 2012 *)

LinearRecurrence[{8, -16}, {0, 1}, 30] (* Harvey P. Dale, Jan 18 2012 *)

CoefficientList[Series[x/(1 - 4 x)^2, {x, 0, 20}], x] (* Eric W. Weisstein, Sep 08 2017 *)

PROG

(PARI) a(n)=if(n<0, 0, n*4^(n-1))

(Sage) [n*4^(n-1) for n in range(22)] # Danny Rorabaugh, Mar 27 2015

CROSSREFS

Cf. A000302, A002699, A027656, A038231, A082134, A083672, A125145, A128235, A133224, A212698.

Sequence in context: A305782 A292536 A242668 * A285063 A026761 A026706

Adjacent sequences:  A002694 A002695 A002696 * A002698 A002699 A002700

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 21:11 EST 2018. Contains 317278 sequences. (Running on oeis4.)