A276312 Number of up-down sequences of length n and values in {1,2,...,n}.

1, 1, 1, 5, 31, 246, 2353, 26585, 345775, 5094220, 83833256, 1524414737, 30353430420, 656851828075, 15350023574061, 385261255931365, 10335781852020335, 295166535640444376, 8939894824857438940, 286234265613041061128, 9659753724363828753408

Offset: 0

Author

Alois P. Heinz, Aug 29 2016

Keywords

• nonn

Examples

			a(0) = 1: the empty sequence.
a(1) = 1: 1.
a(2) = 1: 12.
a(3) = 5: 121, 131, 132, 231, 232.
a(4) = 31: 1212, 1213, 1214, 1312, 1313, 1314, 1323, 1324, 1412, 1413, 1414, 1423, 1424, 1434, 2312, 2313, 2314, 2323, 2324, 2412, 2413, 2414, 2423, 2424, 2434, 3412, 3413, 3414, 3423, 3424, 3434.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..413

Crossrefs

A diagonal of A050446, A050447.

Cf. A276313.

Programs

Maple

b:= proc(n, k, t) option remember; `if`(n=0, 1,
      add(b(n-1, k, k-j), j=1..t-1))
    end:
a:= n-> b(n, n+1$2):
seq(a(n), n=0..25);

Mathematica

b[n_, k_, t_] := b[n, k, t] = If[n==0, 1, Sum[b[n-1, k, k-j], {j, 1, t-1}]];
a[n_] := b[n, n+1, n+1];
a /@ Range[0, 25] (* Jean-François Alcover, Dec 29 2020, after Alois P. Heinz *)

Formula

a(n) ~ exp(-1/2) * 2^(n+2) * n^n / Pi^(n+1). - Vaclav Kotesovec, Aug 30 2016