|
%I #126 Sep 08 2022 08:44:49
%S 1,1,3,4,11,16,42,64,163,256,638,1024,2510,4096,9908,16384,39203,
%T 65536,155382,262144,616666,1048576,2449868,4194304,9740686,16777216,
%U 38754732,67108864,154276028,268435456,614429672,1073741824,2448023843
%N a(n) = 2^(n-1) + ((1 + (-1)^n)/4)*binomial(n, n/2).
%C Inverse binomial transform of A027914. Hankel transform (see A001906 for definition) is {1, 2, 3, 4, ..., n, ...}. - _Philippe Deléham_, Jul 21 2005
%C 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
%C 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
%C Number of distinct symmetric staircase walks connecting opposite corners of a square grid of side n > 1. - _Christian Barrientos_, Nov 25 2018
%C From _Gus Wiseman_, Aug 20 2021: (Start)
%C 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:
%C (1) (2) (3) (4) (5)
%C (21) (31) (32)
%C (111) (112) (41)
%C (211) (113)
%C (122)
%C (212)
%C (221)
%C (311)
%C (1121)
%C (2111)
%C (11111)
%C The following relate to these compositions:
%C - The unordered version is A027193.
%C - The complement is counted by A058622.
%C - The reverse unordered version is A086543.
%C - The version for alternating sum >= 0 is A116406.
%C - The version for alternating sum < 0 is A294175.
%C - Ranked by A345917. (End)
%C 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
%D 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)
%H Alois P. Heinz, <a href="/A027306/b027306.txt">Table of n, a(n) for n = 0..1000</a>
%H F. Disanto, A. Frosini, and S. Rinaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Rinaldi/square.html">Square involutions</a>, J. Int. Seq. 14 (2011) # 11.3.5.
%H Zachary Hamaker and Eric Marberg, <a href="https://arxiv.org/abs/1802.09805">Atoms for signed permutations</a>, arXiv:1802.09805 [math.CO], 2018.
%H Donatella Merlini and Massimo Nocentini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Merlini/merlini5.html">Algebraic Generating Functions for Languages Avoiding Riordan Patterns</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
%F a(n) = Sum_{k=0..floor(n/2)} binomial(n,k).
%F 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).
%F E.g.f.: (exp(2x) + I_0(2x))/2.
%F O.g.f.: 2*x/(1-2*x)/(1+2*x-((1+2*x)*(1-2*x))^(1/2)). - _Vladeta Jovovic_, Apr 27 2003
%F a(n) = A008949(n, floor(n/2)); a(n) + a(n-1) = A248574(n), n > 0. - _Reinhard Zumkeller_, Nov 14 2014
%F From _Peter Bala_, Jul 21 2015: (Start)
%F a(n) = [x^n]( 2*x - 1/(1 - x) )^n.
%F O.g.f.: (1/2)*( 1/sqrt(1 - 4*x^2) + 1/(1 - 2*x) ).
%F Inverse binomial transform is (-1)^n*A246437(n).
%F 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)
%F a(n) = Sum_{k=1..floor((n+1)/2)} binomial(n-1,(2n+1-(-1)^n)/4 -k). - _Anthony Browne_, Jun 18 2016
%F 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
%e From _Gus Wiseman_, Aug 20 2021: (Start)
%e The a(0) = 1 through a(4) = 11 binary numbers with a majority of 1-bits (Gottfried's comment) are:
%e 1 11 101 1011 10011
%e 110 1101 10101
%e 111 1110 10110
%e 1111 10111
%e 11001
%e 11010
%e 11011
%e 11100
%e 11101
%e 11110
%e 11111
%e The version allowing an initial zero is A058622.
%e (End)
%p a:= proc(n) add(binomial(n, j), j=0..n/2) end:
%p seq(a(n), n=0..32); # _Zerinvary Lajos_, Mar 29 2009
%t Table[Sum[Binomial[n, k], {k, 0, Floor[n/2]}], {n, 1, 35}]
%t (* Second program: *)
%t 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 *)
%o (PARI) a(n)=if(n<0,0,(2^n+if(n%2,0,binomial(n, n/2)))/2)
%o (Haskell)
%o a027306 n = a008949 n (n `div` 2) -- _Reinhard Zumkeller_, Nov 14 2014
%o (Magma) [2^(n-1)+(1+(-1)^n)/4*Binomial(n, n div 2): n in [0..40]]; // _Vincenzo Librandi_, Jun 19 2016
%o (GAP) List([0..35],n->Sum([0..Int(n/2)],k->Binomial(n,k))); # _Muniru A Asiru_, Nov 27 2018
%Y a(n) = Sum{(k+1)T(n, m-k)}, 0<=k<=[ (n+1)/2 ], T given by A008315.
%Y Column k=2 of A226873. - _Alois P. Heinz_, Jun 21 2013
%Y Cf. A008949, A248574, A001405, A246437.
%Y The even bisection is A000302.
%Y The odd bisection appears to be A032443.
%Y Cf. A000984, A001700, A001791, A008549, A011782, A088218, A097805, A163493, A182616, A345197.
%K nonn,easy,walk
%O 0,3
%A _Clark Kimberling_
%E Better description from _Robert G. Wilson v_, Aug 30 2000 and from Yong Kong (ykong(AT)curagen.com), Dec 28 2000
| 