A357871 Total number of n-multisets of semi-Dyck paths from (0,0) to (n,n-2*j) for j=0..floor(n/2).

1, 1, 2, 5, 21, 183, 3424, 155833, 25962389, 10152021001, 18355563410823, 94826525443572702, 1720192707342762602561, 135432808172830648285721490, 25492564910167901918236137649748, 28315683468644276652408152922412713937, 65407605920313732627652296139090181364409413

Offset: 0

Author

Alois P. Heinz, Oct 17 2022

Keywords

• nonn

Examples

			a(3) = 5:
  {///, ///, ///},
  {//\, //\, //\},
  {//\, //\, /\/},
  {//\, /\/, /\/},
  {/\/, /\/, /\/}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..63
• Vaclav Kotesovec, Graph - the asymptotic ratio (5000 terms)
• Wikipedia, Counting lattice paths
• Wikipedia, Multiset

Crossrefs

Cf. A008315, A357825.

Programs

Maple

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, add(b(x-1, y+j), j=[-1, 1])))
    end:
a:= n-> add(binomial(b(n, n-2*j)+n-1, n), j=0..n/2):
seq(a(n), n=0..16);

Mathematica

b[x_, y_] := b[x, y] = If[y < 0 || y > x, 0, If[x == 0, 1, Sum[b[x-1, y+j], {j, {-1, 1}}]]];
a[n_] := Sum[Binomial[b[n, n-2*j]+n-1, n], {j, 0, n/2}];
Table[a[n], {n, 0, 16}] (* Jean-François Alcover, Nov 17 2022, after Alois P. Heinz *)
Table[Sum[Binomial[Binomial[n,k]*(n-2*k+1)/(n-k+1) + n - 1,n], {k,0,n/2}],{n,0,16}] (* Vaclav Kotesovec, Nov 17 2022 *)

Formula

a(n) = Sum_{j=0..floor(n/2)} binomial(A008315(n,j)+n-1,n).

From Vaclav Kotesovec, Nov 19 2022: (Start)

a(n)^(1/n) ~ exp(1/2) * 2^(n + 3/2) / (sqrt(Pi) * n^2).

Limit_{n->infinity} a(n) / (exp(n/2) * 2^(n^2 + 3*n/2) / (Pi^(n/2) * n^(2*n + 1/2))) does not exist, see also graph. (End)