OFFSET
1,4
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 (<s, v> = 0). - 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.
FORMULA
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
EXAMPLE
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
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 *)
PROG
(PARI) a(n) = 2^(n-1) - binomial(n, n\2); \\ Michel Marcus, Aug 13 2013
CROSSREFS
KEYWORD
nonn
AUTHOR
Matthijs Coster, Apr 29 2004
EXTENSIONS
Offset corrected by R. J. Mathar, Jun 04 2011
STATUS
approved