A093387 a(n) = 2^(n-1) - binomial(n, floor(n/2)).

0, 0, 1, 2, 6, 12, 29, 58, 130, 260, 562, 1124, 2380, 4760, 9949, 19898, 41226, 82452, 169766, 339532, 695860, 1391720, 2842226, 5684452, 11576916, 23153832, 47050564, 94101128, 190876696, 381753392, 773201629, 1546403258, 3128164186, 6256328372, 12642301534

Offset: 1

Author

Matthijs Coster, Apr 29 2004

Keywords

• nonn

Comments

Suppose n >= 3. Let e_1,...,e_n be n unit-vectors which generate Euclidean space R_n and let l_n = {x = sum a_i e_i | a_1 >= a_2 >= ... >= a_n >= 0 }. Consider the hypercube H_n with vertices h_1,...,h_{2^n} = {epsilon_1 e_1 + ... + epsilon_n e_n}.

For each element x in l_n we build 2^n "statements" by taking the inner product of x with h_i. We call a statement true if (x,h_i) > 0 and false if (x,h_i) < 0. Two vectors x and y are indistinguishable if all statements produced by x and y are equal.

For each set of indistinguishable vectors we choose one vector, which is called the representative. a(n) is the number of representatives.

Hankel transform is A127365. - Paul Barry, Jan 11 2007

Number of up-steps starting at level 0 in all dispersed Dyck paths of length n-1 (that is, in Motzkin paths of length n-1 with no (1,0)-steps at positive heights). - Emeric Deutsch, May 30 2011

Number of north-east paths of length n on the square lattice, starting with a north step, which ever visit a point strictly east of the main diagonal. Equivalently, the number of vectors v in [1,-1]^n with first coordinate v_1=1 for which there exists a vector s with strictly ordered, strictly positive entries (s_1 > s_2 > ... > s_n > 0) that is orthogonal to v ( = 0). - Isaac Grosof, Jan 16 2023

Examples

			a(5)=6 because, denoting U=(1,1), D=(1,-1), H=(1,0), in HHHH, HHUD, HUDH, UDHH, UDUD, and UUDD we have 0+1+1+1+2+1=6 U steps starting at level 0. - _Emeric Deutsch_, May 30 2011
a(5)=6 because there are 6 north-east paths starting with N which visit a point strictly east of the main diagonal: NNEEE, NENEE, NEENN, NEENE, NEEEN, NEEEE. - _Isaac Grosof_, Jan 16 2023
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Matthijs Coster, Sequences
• Matthijs Coster, Statements and Representatives, 2004.
• Vladimir Shevelev, A Mathar's conjecture, Seqfan, Nov 17 2017.

Crossrefs

Cf. A000079, A001405, A000108, A127365, A191310.

Programs

Maple

A093387:=n->2^(n-1)-binomial(n, floor(n/2)); seq(A093387(n), n=1..50); # Wesley Ivan Hurt, Dec 01 2013

Mathematica

Table[2^(n - 1) - Binomial[n, Floor[n/2]], {n, 50}] (* Wesley Ivan Hurt, Dec 01 2013 *)

PARI

a(n) = 2^(n-1) - binomial(n, n\2); \\ Michel Marcus, Aug 13 2013

Formula

a(n) = A000079(n-1) - A001405(n).

a(n+1) = Sum_{k=2..n} binomial(n, floor((n-k)/2)). - Paul Barry, Jan 11 2007

a(2n) = 2*a(2n-1). - Emeric Deutsch, May 30 2011

a(n+1) = Sum_{k>=0} k*A191310(n,k). - Emeric Deutsch, May 30 2011

G.f.: (1-sqrt(1-4*z^2))^2/(4*z*(1-2*z)). - Emeric Deutsch, May 30 2011

Conjecture: (n+1)*a(n) + 2*(-n-1)*a(n-1) + 4*(-n+2)*a(n-2) + 8*(n-2)*a(n-3) = 0. - R. J. Mathar, Nov 30 2012

a(2*n+1) = 2*a(2*n) + A000108(n). Together with the first formula by Emeric Deutsch, we have a simple system of recursions. Using them, we can prove Mathar's conjecture. For example, let n be odd, n=2*m+1. By the left hand side of Mathar's conjecture, we have (2*m+2)*a(2*m+1) - 2*(2*m+2)*a(2*m) - 4*(2*m-1)*a(2*m-1) + 8(2*m-1)*a(2*m-2) = (2*m+2)*(2*a(2*m) + A000108(m) - 2*a(2*m)) - 4*(2*m-1)*(2*a(2*m-2) + A000108(m-1) - 2*a(2*m-2)) = (2*m+2)*A000108(m) - 4*(2*m-1)*A000108(m-1) = 0, since A000108(m) = binomial(2*m, m)/(m+1). - Vladimir Shevelev, Nov 17 2017

Extensions

Offset corrected by R. J. Mathar, Jun 04 2011