A048495 a(n) = (n-1)*2^n + 2.

1, 2, 6, 18, 50, 130, 322, 770, 1794, 4098, 9218, 20482, 45058, 98306, 212994, 458754, 983042, 2097154, 4456450, 9437186, 19922946, 41943042, 88080386, 184549378, 385875970, 805306370, 1677721602, 3489660930, 7247757314

Offset

0,2

Comments

Binomial transform of 1 followed by the odd numbers (2n-1+2*0^n, or abs(A060747)). Binomial transform is A084643. - Paul Barry, Jun 09 2003

Total number of bits of all binary numbers less than 2^n (see example).

Total number of zero bits of all binary numbers less than 2^(n+1). - Olivier Gérard, Feb 25 2014.

Number of permutations of length n>0 avoiding the partially ordered pattern (POP) {1>2, 4>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second element, and the fourth element is larger than the third element. - Sergey Kitaev, Dec 08 2020

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.

Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

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

Formula

a(n) - 1 = Sum_{i=0..n-1} (n-i) * 2^(n-i-1) = n*2^(n-1) + (n-1)*2^(n-2) + (n-2)*2^(n-3) + ... + 1*(2^0). - Matthew Erbst (matt(AT)erbst.org), Apr 19 2006

a(n) = 2 * A002064(n-1), n >= 1. - Omar E. Pol, Sep 30 2012

a(n) = a(n-1) + (2^n - 2^(n-1)) * n = a(n-1) + n*2^(n-1). - Olivier Gérard, Feb 25 2014

G.f.: -(4*x^2-3*x+1) / ((x-1)*(2*x-1)^2). - Colin Barker, Jun 29 2014

Example

a(1)=2 : 0 1
a(2)=6 : 0 1 10 11
a(3)=18 : 0 1 10 11 100 101 110 111
a(4)=50 : 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111
...

Maple

A048495:=n->(n-1)*2^n + 2; seq(A048495(n), n=0..30); # Wesley Ivan Hurt, Jun 29 2014

Mathematica

f[n_]:=(n-1)2^n+2; Array[f, 29, 0] (* Robert G. Wilson v, Jun 29 2014 *)
LinearRecurrence[{5, -8, 4}, {1, 2, 6}, 30] (* Harvey P. Dale, Jan 23 2015 *)

Prog

(Magma) [(n-1)*2^n + 2: n in [0..30]]; // Vincenzo Librandi, Sep 25 2011
(PARI) a(n) = (n-1)*2^n + 2; \\ Joerg Arndt, Feb 25 2014
(PARI) Vec(-(4*x^2-3*x+1)/((x-1)*(2*x-1)^2) + O(x^100)) \\ Colin Barker, Jun 29 2014

Crossrefs

a(n) = T(1, n), array T given by A048494.

Cf. A002064, A060747, A084643.

Sequence in context: A197055 A258625 A062026 * A089380 A271897 A362067

Adjacent sequences: A048492 A048493 A048494 * A048496 A048497 A048498

Keyword

nonn,easy

Author

Clark Kimberling

Extensions

Better description from John W. Layman, May 04 1999

Status

approved