cp's OEIS Frontend

A175934 Number of lattice paths from (0,0) to (n,n) using steps S={(1,0),(0,1),(r,r)|0 that never go above the line y=x.

%I A175934 #55 Jan 08 2023 09:46:06
%S A175934 1,2,7,27,116,532,2554,12675,64507,334836,1765833,9434779,50962640,
%T A175934 277839361,1526834471,8448751385,47035469902,263260232668,
%U A175934 1480527858436,8361881707770,47409359120684,269736194796537,1539547726712437,8812663513352489,50579825742416942,291012706492224315,1678146650028389023
%N A175934 Number of lattice paths from (0,0) to (n,n) using steps S={(1,0),(0,1),(r,r)|0<r<=2} that never go above the line y=x.
%C A175934 Number of lattice paths of weight n that start in (0,0), end on the horizontal axis, never go below this axis, whose steps are of the following four kinds: h=(1,0) of weight 1, H=(1,0) of weight 2, u=(1,1) of weight 1, and d=(1,-1) of weight 0; the weight of a path is the sum of the weights of its steps. Example: a(2)=7 because we have hh, H, hud, udh, udud, uhd, and uudd. - _Emeric Deutsch_, Sep 09 2014
%H A175934 Alois P. Heinz, <a href="/A175934/b175934.txt">Table of n, a(n) for n = 0..1000</a>
%H A175934 J. P. S. Kung and A. de Mier, <a href="http://dx.doi.org/10.1016/j.jcta.2012.08.010">Catalan lattice paths with rook, bishop and spider steps</a>, Journal of Combinatorial Theory, Series A 120 (2013) 379-389. - From _N. J. A. Sloane_, Dec 27 2012
%F A175934 G.f.: (1 - x - x^2 - sqrt(x^4 + 2*x^3 - x^2 - 6*x + 1))/(2*x). - _Mark van Hoeij_, Apr 16 2013
%F A175934 G.f.: 1/(1 - x*(1 + x + 1/(1 - x*(1 + x + 1/...)))). - _Michael Somos_, Mar 30 2014
%F A175934 G.f. g = g(x) satisfies g = 1 + x*g + x^2*g + x*g^2. - _Emeric Deutsch_, Sep 09 2014
%F A175934 a(n) = Sum_{k=0..n} ((C(k)*Sum_{j=0..k+1} (binomial(k+1,j)*Sum_{i=0..n-k} (3^(j-i)*binomial(j,i)*binomial(k-j+1,n-3*k+2*j-i-2)*2^(2*(k-j)-n+1)*(-1)^(k-j+1))))), a(0)=1, a(1)=2, where C(k) = A000108(k). - _Vladimir Kruchinin_, Mar 01 2016
%F A175934 a(0) = 1, a(1) = 2; a(n) = 2 * a(n-1) + 3 * a(n-2) + Sum_{k=2..n-1} a(k) * a(n-k-1). - _Ilya Gutkovskiy_, Jul 20 2021
%F A175934 G.f.: 1/G(0), where G(k) = 1 - (2*x+x^2)/(1-x/G(k+1)) (continued fraction). - _Nikolaos Pantelidis_, Jan 08 2023
%e A175934 a(2)=7 because we can reach (2,2) in the following ways:
%e A175934 (1,0),(1,0),(0,1),(0,1);
%e A175934 (1,0),(0,1),(1,0),(0,1);
%e A175934 (1,0),(0,1),(1,1);
%e A175934 (1,0),(1,1),(0,1);
%e A175934 (1,1),(1,0),(0,1);
%e A175934 (1,1),(1,1);
%e A175934 (2,2).
%e A175934 G.f. = 1 + 2*x + 7*x^2 + 27*x^3 + 116*x^4 + 532*x^5 + 2554*x^6 + ...
%o A175934 (Sage)
%o A175934 n=20
%o A175934 M=[]
%o A175934 for posx in range(0,n+1):
%o A175934         for posy in range(0,n+1):
%o A175934             if posx==0:
%o A175934                 if posy==0:
%o A175934                     M.append([1])
%o A175934                 else:
%o A175934                     M.append([0])
%o A175934             else:
%o A175934                 if posy==0:
%o A175934                     M[0].append(0)
%o A175934                     M[0][posx]=M[0][posx]+M[0][posx-1]
%o A175934                 else:
%o A175934                     if posy>posx:
%o A175934                         M[posy].append(0)
%o A175934                     else:
%o A175934                         M[posy].append(0)
%o A175934                         M[posy][posx]=M[posy][posx-1]+M[posy][posx]
%o A175934                         M[posy][posx]=M[posy-1][posx]+M[posy][posx]
%o A175934                         for r in range(1,min(posx,posy,2)+1):
%o A175934                             M[posy][posx]=M[posy-r][posx-r]+M[posy][posx]
%o A175934 L=[]
%o A175934 for k in range(0,n+1):
%o A175934     L.append(M[k][k])
%o A175934 print(L)
%o A175934 (Maxima)
%o A175934 a(n):=if n<2 then n+1 else sum((binomial(2*k,k)*sum(binomial(k+1,j)*sum(3^(j-i)*binomial(j,i)*binomial(k-j+1,n-3*k+2*j-i-2)*(2)^(-n+2*(k-j)+1)*(-1)^(k-j+1),i,0,n-k),j,0,k+1))/(k+1),k,0,n); /* _Vladimir Kruchinin_, Mar 01 2016 */
%Y A175934 Cf. A175935, A175936, A175937, A175939.
%K A175934 nonn
%O A175934 0,2
%A A175934 _Eric Werley_, Dec 06 2010