|
|
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
|
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
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.
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
|
F. Disanto, A. Frosini, and S. Rinaldi, Square involutions, J. Int. Seq. 14 (2011) # 11.3.5.
|
|
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) = [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
|
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:
|
|
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)
(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.
The odd bisection appears to be A032443.
|
|
KEYWORD
|
nonn,easy,walk
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Better description from Robert G. Wilson v, Aug 30 2000 and from Yong Kong (ykong(AT)curagen.com), Dec 28 2000
|
|
STATUS
|
approved
|
|
|
|