cp's OEIS Frontend

A118920 Triangle read by rows: T(n,k) is the number of Grand Dyck paths of semilength n that cross the x-axis k times (n>=1, k>=0).

%I A118920 #25 Oct 27 2021 11:26:42
%S A118920 2,4,2,10,8,2,28,28,12,2,84,96,54,16,2,264,330,220,88,20,2,858,1144,
%T A118920 858,416,130,24,2,2860,4004,3276,1820,700,180,28,2,9724,14144,12376,
%U A118920 7616,3400,1088,238,32,2,33592,50388,46512,31008,15504,5814,1596,304,36,2
%N A118920 Triangle read by rows: T(n,k) is the number of Grand Dyck paths of semilength n that cross the x-axis k times (n>=1, k>=0).
%C A118920 A Grand Dyck path of semilength n is a path in the half-plane x>=0, starting at (0,0), ending at (2n,0) and consisting of steps u=(1,1) and d=(1,-1).
%C A118920 Row sums are the central binomial coefficients (A000984). T(n,0)=2*A000108(n) (the Catalan numbers doubled). T(n,1)=2*A002057(n-2). Sum(k*T(n,k),k>=0)=2*A008549(n-1). For crossings of the x-axis in one direction, see A118919.
%C A118920 This triangle is related to paired pattern P_3 and P_4 defined in the Pan & Remmel link. - _Ran Pan_, Feb 01 2016
%H A118920 Ran Pan and Jeffrey B. Remmel, <a href="http://arxiv.org/abs/1601.07988">Paired patterns in lattice paths</a>, arXiv:1601.07988 [math.CO], 2016.
%F A118920 T(n,k) = 2*(k+1)*binomial(2*n,n-k-1)/n.
%F A118920 G.f.: G(t,z)=2*z*C^2/(1-t*z*C^2), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function.
%F A118920 More generally, the trivariate g.f. G=G(x,y,z), where x (y) marks number of downward (upward) crossings of the x-axis, is given by G = z*C^2*(2+(x+y)*z*C^2)/(1-x*y*z^2*C^4).
%F A118920 a(n) = 2 * A039598(n-1). - _Georg Fischer_, Oct 27 2021
%e A118920 T(3,1)=8 because we have ud|dudu,ud|dduu,udud|du,uudd|du,du|udud,du|uudd, dudu|ud and dduu|ud (the crossings of the x-axis are shown by |).
%e A118920 Triangle starts:
%e A118920    2;
%e A118920    4, 2;
%e A118920   10, 8, 2;
%e A118920   28,28,12, 2;
%e A118920   84,96,54,16,2;
%p A118920 T:=(n,k)->2*(k+1)*binomial(2*n,n-k-1)/n: for n from 1 to 11 do seq(T(n,k),k=0..n-1) od; # yields sequence in triangular form
%t A118920 Table[2 (k + 1) Binomial[2 n, n - k - 1]/n, {n, 10}, {k, 0, n - 1}] // Flatten (* _Michael De Vlieger_, Feb 01 2016 *)
%o A118920 (Sage) # Algorithm of L. Seidel (1877)
%o A118920 # Prints the first n rows of the triangle.
%o A118920 def A118920_triangle(n) :
%o A118920     D = [0]*(n+2); D[1] = 2
%o A118920     b = True; h = 1
%o A118920     for i in range(2*n) :
%o A118920         if b :
%o A118920             for k in range(h, 0, -1) : D[k] += D[k-1]
%o A118920             h += 1
%o A118920         else :
%o A118920             for k in range(1, h, 1) : D[k] += D[k+1]
%o A118920         b = not b
%o A118920         if b : print([D[z] for z in (1..h-1)])
%o A118920 A118920_triangle(10)  # _Peter Luschny_, Oct 19 2012
%o A118920 (PARI) T(n,k) = 2*(k+1)*binomial(2*n,n-k-1)/n \\ _Charles R Greathouse IV_, Feb 01 2016
%Y A118920 Cf. A000984, A000108, A002057, A008549, A039598, A118919.
%K A118920 nonn,tabl
%O A118920 1,1
%A A118920 _Emeric Deutsch_, May 06 2006