%I #24 Aug 06 2024 04:52:41
%S 1,1,3,7,19,49,139,379,1079,3011,8681,24641,71303,204359,594749,
%T 1717871,5012591,14552407,42601285,124209955,364300377,1065449397,
%U 3131483367,9182889013,27027421303,79418096239,234090990589,689093244919,2033346353509,5994168369289,17706646341619,52264890828619
%N Number of walks within N^2 (the first quadrant of Z^2) starting at (0,0) and consisting of n steps taken from {(-1, 0), (1, -1), (1, 1)}.
%H M. Alekseyev, <a href="https://mathoverflow.net/q/294510">Count the number of words in a set</a>, MathOverflow, 2018.
%H A. Bostan, <a href="https://citeseerx.ist.psu.edu/pdf/749aef4c6f3668e652b5074e5268346ccecc88c9">Computer Algebra for Lattice Path Combinatorics</a>, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.
%H Alin Bostan, <a href="https://specfun.inria.fr/bostan/HDR.pdf">Calcul Formel pour la Combinatoire des Marches</a> [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d’Informatique de Paris Nord, Université Paris 13, December 2017.
%H Bostan, Alin ; Chyzak, Frédéric; van Hoeij, Mark; Kauers, Manuel; Pech, Lucien <a href="https://doi.org/10.1016/j.ejc.2016.10.010">Hypergeometric expressions for generating functions of walks with small steps in the quarter plane.</a> Eur. J. Comb. 61, 242-275 (2017)
%H A. Bostan and M. Kauers, <a href="http://arxiv.org/abs/0811.2899">Automatic Classification of Restricted Lattice Walks</a>, arXiv:0811.2899 [math.CO], 2008-2009.
%H M. Bousquet-Mélou and M. Mishna, <a href="http://arxiv.org/abs/0810.4387">Walks with small steps in the quarter plane</a>, arXiv:0810.4387 [math.CO], 2008-2009.
%F a(n) = Sum_{j=0..[n/2]} Sum_{i=max(j,[(n+1)/2]-j)..n-j} (i-j+1)*(2*(i+j)-n+1)/(i+j+1) * n!/(i+1)!/j!/(n-i-j)!. - _Max Alekseyev_, Mar 06 2018
%F G.f.: -(1/(x-1))*(1/2+1/x*Int(x^2/(x+1)^(1/2)/(1-3*x)^(3/2)*(13/2+Int(((1-3*x)/(x+1))^(1/2)*((10-1/x^3)*hypergeom([1/4, 3/4],[1],64*x^4)+6*(8*x^2+1)*(10*x^2-3)*hypergeom([5/4,7/4],[2],64*x^4)),x)),x)). - _Mark van Hoeij_, Oct 13 2009
%t aux[i_Integer, j_Integer, n_Integer] := Which[Min[i, j, n] < 0 || Max[i, j] > n, 0, n == 0, KroneckerDelta[i, j, n], True, aux[i, j, n] = aux[-1 + i, -1 + j, -1 + n] + aux[-1 + i, 1 + j, -1 + n] + aux[1 + i, j, -1 + n]]; Table[Sum[aux[i, j, n], {i, 0, n}, {j, 0, n}], {n, 0, 25}]
%o (PARI) { A151266(n) = sum(j=0,n\2, sum(i=max(j,(n+1)\2-j),n-j, (i-j+1)*(2*(i+j)-n+1)/(i+j+1) * n!/(i+1)!/j!/(n-i-j)! )); } \\ _Max Alekseyev_, Mar 06 2018
%K nonn,walk,changed
%O 0,3
%A _Manuel Kauers_, Nov 18 2008
|