login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A027306 a(n) = 2^(n-1) + ((1 + (-1)^n)/4)*binomial(n, n/2). 71
1, 1, 3, 4, 11, 16, 42, 64, 163, 256, 638, 1024, 2510, 4096, 9908, 16384, 39203, 65536, 155382, 262144, 616666, 1048576, 2449868, 4194304, 9740686, 16777216, 38754732, 67108864, 154276028, 268435456, 614429672, 1073741824, 2448023843 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Inverse binomial transform of A027914. Hankel transform (see A001906 for definition) is {1, 2, 3, 4, ..., n, ...}. - Philippe Deléham, Jul 21 2005

Number of walks of length n on a line that starts at the origin and ends at or above 0. - Benjamin Phillabaum, Mar 05 2011

Number of binary integers (i.e., with a leading 1 bit) of length n+1 which have a majority of 1-bits. E.g., for n+1=4: (1011, 1101, 1110, 1111) a(3)=4. - Toby Gottfried, Dec 11 2011

Number of distinct symmetric staircase walks connecting opposite corners of a square grid of side n > 1. - Christian Barrientos, Nov 25 2018

From Gus Wiseman, Aug 20 2021: (Start)

Also the number of integer compositions of n + 1 with alternating sum > 0, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. These compositions are ranked by A345917. For example, the a(0) = 1 through a(4) = 11 compositions are:

  (1)  (2)  (3)    (4)    (5)

            (21)   (31)   (32)

            (111)  (112)  (41)

                   (211)  (113)

                          (122)

                          (212)

                          (221)

                          (311)

                          (1121)

                          (2111)

                          (11111)

The following relate to these compositions:

- The unordered version is A027193.

- The complement is counted by A058622.

- The reverse unordered version is A086543.

- The version for alternating sum >= 0 is A116406.

- The version for alternating sum < 0 is A294175.

- Ranked by A345917. (End)

The Gauss congruences a(n*p^k) == a(n^p^(k-1)) (mod p^k) hold for prime p and positive integers n and k. - Peter Bala, Jan 07 2022

REFERENCES

A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.1.6)

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

F. Disanto, A. Frosini, and S. Rinaldi, Square involutions, J. Int. Seq. 14 (2011) # 11.3.5.

Zachary Hamaker and Eric Marberg, Atoms for signed permutations, arXiv:1802.09805 [math.CO], 2018.

Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

FORMULA

a(n) = Sum_{k=0..floor(n/2)} binomial(n,k).

Odd terms are 2^(n-1). Also a(2n) - 2^(2n-1) is given by A001700. a(n) = 2^n + (n mod 2)*binomial(n, (n-1)/2).

E.g.f.: (exp(2x) + I_0(2x))/2.

O.g.f.: 2*x/(1-2*x)/(1+2*x-((1+2*x)*(1-2*x))^(1/2)). - Vladeta Jovovic, Apr 27 2003

a(n) = A008949(n, floor(n/2)); a(n) + a(n-1) = A248574(n), n > 0. - Reinhard Zumkeller, Nov 14 2014

From Peter Bala, Jul 21 2015: (Start)

a(n) = [x^n]( 2*x - 1/(1 - x) )^n.

O.g.f.: (1/2)*( 1/sqrt(1 - 4*x^2) + 1/(1 - 2*x) ).

Inverse binomial transform is (-1)^n*A246437(n).

exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + ... is the o.g.f. for A001405. (End)

a(n) = Sum_{k=1..floor((n+1)/2)} binomial(n-1,(2n+1-(-1)^n)/4 -k). - Anthony Browne, Jun 18 2016

D-finite with recurrence: n*a(n) + 2*(-n+1)*a(n-1) + 4*(-n+1)*a(n-2) + 8*(n-2)*a(n-3) = 0. - R. J. Mathar, Aug 09 2017

EXAMPLE

From Gus Wiseman, Aug 20 2021: (Start)

The a(0) = 1 through a(4) = 11 binary numbers with a majority of 1-bits (Gottfried's comment) are:

  1   11   101   1011   10011

           110   1101   10101

           111   1110   10110

                 1111   10111

                        11001

                        11010

                        11011

                        11100

                        11101

                        11110

                        11111

The version allowing an initial zero is A058622.

(End)

MAPLE

a:= proc(n) add(binomial(n, j), j=0..n/2) end:

seq(a(n), n=0..32); # Zerinvary Lajos, Mar 29 2009

MATHEMATICA

Table[Sum[Binomial[n, k], {k, 0, Floor[n/2]}], {n, 1, 35}]

(* Second program: *)

a[0] = a[1] = 1; a[2] = 3; a[n_] := a[n] = (2(n-1)(2a[n-2] + a[n-1]) - 8(n-2) a[n-3])/n; Array[a, 33, 0] (* Jean-François Alcover, Sep 04 2016 *)

PROG

(PARI) a(n)=if(n<0, 0, (2^n+if(n%2, 0, binomial(n, n/2)))/2)

(Haskell)

a027306 n = a008949 n (n `div` 2)  -- Reinhard Zumkeller, Nov 14 2014

(MAGMA) [2^(n-1)+(1+(-1)^n)/4*Binomial(n, n div 2): n in [0..40]]; // Vincenzo Librandi, Jun 19 2016

(GAP) List([0..35], n->Sum([0..Int(n/2)], k->Binomial(n, k))); # Muniru A Asiru, Nov 27 2018

CROSSREFS

a(n) = Sum{(k+1)T(n, m-k)}, 0<=k<=[ (n+1)/2 ], T given by A008315.

Column k=2 of A226873. - Alois P. Heinz, Jun 21 2013

Cf. A008949, A248574, A001405, A246437.

The even bisection is A000302.

The odd bisection appears to be A032443.

Cf. A000984, A001700, A001791, A008549, A011782, A088218, A097805, A163493, A182616, A345197.

Sequence in context: A001641 A007382 A127804 * A239024 A026676 A142870

Adjacent sequences:  A027303 A027304 A027305 * A027307 A027308 A027309

KEYWORD

nonn,easy,walk

AUTHOR

Clark Kimberling

EXTENSIONS

Better description from Robert G. Wilson v, Aug 30 2000 and from Yong Kong (ykong(AT)curagen.com), Dec 28 2000

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 5 05:47 EDT 2022. Contains 355087 sequences. (Running on oeis4.)