A206464 Number of length-n Catalan-RGS (restricted growth strings) such that the RGS is a valid mixed-radix number in falling factorial basis.

1, 1, 2, 4, 10, 26, 74, 218, 672, 2126, 6908, 22876, 77100, 263514, 911992, 3189762, 11261448, 40083806, 143713968, 518594034, 1882217168, 6867064856, 25172021144, 92666294090, 342467464612, 1270183943200, 4726473541216, 17640820790092, 66025467919972

Offset: 0

Author

Joerg Arndt, Feb 08 2012

Keywords

• nonn

Comments

Catalan-RGS are strings with first digit d(0)=zero, and d(k+1) <= d(k)+1, falling factorial mixed-radix numbers have last digit <= 1, second last <= 2, etc.

The digits of the RGS are <= floor(n/2).

The first few terms are the same as for A089429.

Column k=0 of A264869. - Peter Bala, Nov 27 2015

a(n) = A291680(n+1,n+1). - Alois P. Heinz, Aug 29 2017

Examples

			The a(5)=26 strings for n=5 are (dots for zeros):
   1:  [ . . . . . ]
   2:  [ . . . . 1 ]
   3:  [ . . . 1 . ]
   4:  [ . . . 1 1 ]
   5:  [ . . 1 . . ]
   6:  [ . . 1 . 1 ]
   7:  [ . . 1 1 . ]
   8:  [ . . 1 1 1 ]
   9:  [ . . 1 2 . ]
  10:  [ . . 1 2 1 ]
  11:  [ . 1 . . . ]
  12:  [ . 1 . . 1 ]
  13:  [ . 1 . 1 . ]
  14:  [ . 1 . 1 1 ]
  15:  [ . 1 1 . . ]
  16:  [ . 1 1 . 1 ]
  17:  [ . 1 1 1 . ]
  18:  [ . 1 1 1 1 ]
  19:  [ . 1 1 2 . ]
  20:  [ . 1 1 2 1 ]
  21:  [ . 1 2 . . ]
  22:  [ . 1 2 . 1 ]
  23:  [ . 1 2 1 . ]
  24:  [ . 1 2 1 1 ]
  25:  [ . 1 2 2 . ]
  26:  [ . 1 2 2 1 ]
		

Links

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

Crossrefs

Cf. A080935, A080936, A264869, A291680.

Programs

Maple

b:= proc(i, l) option remember;
      `if`(i<=0, 1, add(b(i-1, j), j=0..min(l+1, i)))
    end:
a:= n-> b(n-1, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 08 2012

Mathematica

b[i_, l_] := b[i, l] = If[i <= 0, 1, Sum[b[i-1, j], {j, 0, Min[l+1, i]}]];
a[n_] := b[n-1, 0];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)

Formula

Conjecture: a(n) = Sum_{k = 0..floor(n/4)} (-1)^k * C(floor(n/2) + 1 - k, k + 1) * a(n - 1 - k), a(0) = 1. - Gionata Neri, Jun 17 2018