login
Number A(n,k) of Dyck n-paths all of whose ascents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.
11

%I #26 May 03 2019 16:34:13

%S 1,1,1,1,1,1,1,1,2,1,1,1,1,5,1,1,1,1,2,14,1,1,1,1,1,5,42,1,1,1,1,1,2,

%T 12,132,1,1,1,1,1,1,6,30,429,1,1,1,1,1,1,2,16,79,1430,1,1,1,1,1,1,1,7,

%U 37,213,4862,1,1,1,1,1,1,1,2,22,83,584,16796,1

%N Number A(n,k) of Dyck n-paths all of whose ascents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

%C Lengths of descents are unrestricted.

%C For p>0 is column p asymptotic to a(n) ~ s^2 / (n^(3/2) * r^(n-1/2) * sqrt(2*Pi*p*(s-1)*(1+s/(1+p*(s-1))))), where r and s are real roots (0 < r < 1) of the system of equations r = p*(s-1)^2 / (s*(1-p+p*s)), (r*s)^p = (s-1-r*s)/(s-1). - _Vaclav Kotesovec_, Jul 16 2014

%H Alois P. Heinz, <a href="/A212382/b212382.txt">Antidiagonals n = 0..140, flattened</a>

%H Vaclav Kotesovec, <a href="/A212382/a212382_1.pdf">Asymptotic of subsequences of A212382</a>

%F G.f. of column k>0 satisfies: A_k(x) = 1+x*A_k(x)/(1-(x*A_k(x))^k), g.f. of column k=0: A_0(x) = 1/(1-x).

%F G.f. of column k>0 is series_reversion(B(x))/x where B(x) = x/(1 + x + x^(k+1) + x^(2*k+1) + x^(3*k+1) + ... ) = x/(1+x/(1-x^k)); for Dyck paths with allowed ascent lengths {u_1, u_2, ...} use B(x) = x/( 1 + sum(k>=1, x^{u_k} ) ). - _Joerg Arndt_, Apr 23 2016

%e A(0,k) = 1: the empty path.

%e A(3,0) = 1: UDUDUD.

%e A(3,1) = 5: UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD.

%e A(3,2) = 2: UDUDUD, UUUDDD.

%e A(5,3) = 6: UDUDUDUDUD, UDUUUUDDDD, UUUUDDDDUD, UUUUDDDUDD, UUUUDDUDDD, UUUUDUDDDD.

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 2, 1, 1, 1, 1, 1, 1, ...

%e 1, 5, 2, 1, 1, 1, 1, 1, ...

%e 1, 14, 5, 2, 1, 1, 1, 1, ...

%e 1, 42, 12, 6, 2, 1, 1, 1, ...

%e 1, 132, 30, 16, 7, 2, 1, 1, ...

%e 1, 429, 79, 37, 22, 8, 2, 1, ...

%p b:= proc(x, y, k, u) option remember;

%p `if`(x<0 or y<x, 0, `if`(x=0 and y=0, 1, b(x, y-1, k, true)+

%p `if`(u, add(b(x-(k*t+1), y, k, false), t=0..(x-1)/k), 0)))

%p end:

%p A:= (n, k)-> `if`(k=0, 1, b(n, n, k, true)):

%p seq(seq(A(n, d-n), n=0..d), d=0..15);

%p # second Maple program

%p A:= (n, k)-> `if`(k=0, 1, coeff(series(RootOf(

%p A||k=1+x*A||k/(1-(x*A||k)^k), A||k), x, n+1), x, n)):

%p seq(seq(A(n, d-n), n=0..d), d=0..15);

%t b[x_, y_, k_, u_] := b[x, y, k, u] = If[x<0 || y<x, 0, If[x == 0 && y == 0, 1, b[x, y-1, k, True] + If[u, Sum[b[x-(k*t+1), y, k, False], {t, 0, (x-1)/k}], 0]]]; A[n_, k_] := If[k == 0, 1, b[n, n, k, True]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 15}] // Flatten (* _Jean-François Alcover_, Jan 15 2014, translated from first Maple program *)

%Y Columns k=0-10 give: A000012, A000108, A101785, A212383, A212384, A212385, A212386, A212387, A212388, A212389, A212390.

%Y A(2n,n) gives A323229.

%K nonn,tabl

%O 0,9

%A _Alois P. Heinz_, May 12 2012