A027306 a(n) = 2^(n-1) + ((1 + (-1)^n)/4)*binomial(n, n/2).

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

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy
• walk

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

Examples

			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)
		

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.

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.

Programs

GAP

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

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

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

PARI

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

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

Extensions

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