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

%I #43 Mar 09 2024 14:23:40

%S 1,1,2,4,10,26,74,218,672,2126,6908,22876,77100,263514,911992,3189762,

%T 11261448,40083806,143713968,518594034,1882217168,6867064856,

%U 25172021144,92666294090,342467464612,1270183943200,4726473541216,17640820790092,66025467919972

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

%C 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.

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

%C The first few terms are the same as for A089429.

%C Column k=0 of A264869. - _Peter Bala_, Nov 27 2015

%C a(n) = A291680(n+1,n+1). - _Alois P. Heinz_, Aug 29 2017

%H Alois P. Heinz, <a href="/A206464/b206464.txt">Table of n, a(n) for n = 0..1000</a>

%F 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

%e The a(5)=26 strings for n=5 are (dots for zeros):

%e 1: [ . . . . . ]

%e 2: [ . . . . 1 ]

%e 3: [ . . . 1 . ]

%e 4: [ . . . 1 1 ]

%e 5: [ . . 1 . . ]

%e 6: [ . . 1 . 1 ]

%e 7: [ . . 1 1 . ]

%e 8: [ . . 1 1 1 ]

%e 9: [ . . 1 2 . ]

%e 10: [ . . 1 2 1 ]

%e 11: [ . 1 . . . ]

%e 12: [ . 1 . . 1 ]

%e 13: [ . 1 . 1 . ]

%e 14: [ . 1 . 1 1 ]

%e 15: [ . 1 1 . . ]

%e 16: [ . 1 1 . 1 ]

%e 17: [ . 1 1 1 . ]

%e 18: [ . 1 1 1 1 ]

%e 19: [ . 1 1 2 . ]

%e 20: [ . 1 1 2 1 ]

%e 21: [ . 1 2 . . ]

%e 22: [ . 1 2 . 1 ]

%e 23: [ . 1 2 1 . ]

%e 24: [ . 1 2 1 1 ]

%e 25: [ . 1 2 2 . ]

%e 26: [ . 1 2 2 1 ]

%p b:= proc(i, l) option remember;

%p `if`(i<=0, 1, add(b(i-1, j), j=0..min(l+1, i)))

%p end:

%p a:= n-> b(n-1, 0):

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Feb 08 2012

%t b[i_, l_] := b[i, l] = If[i <= 0, 1, Sum[b[i-1, j], {j, 0, Min[l+1, i]}]];

%t a[n_] := b[n-1, 0];

%t a /@ Range[0, 40] (* _Jean-François Alcover_, Nov 07 2020, after _Alois P. Heinz_ *)

%Y Cf. A080935, A080936, A264869, A291680.

%K nonn

%O 0,3

%A _Joerg Arndt_, Feb 08 2012