login
Number A(n,k) of length-n restricted growth strings (RGS) with growth <= k and fixed first element; square array A(n,k), n>=0, k>=0, read by antidiagonals.
13

%I #19 May 28 2019 08:14:38

%S 1,1,1,1,1,1,1,1,2,1,1,1,3,5,1,1,1,4,12,15,1,1,1,5,22,59,52,1,1,1,6,

%T 35,150,339,203,1,1,1,7,51,305,1200,2210,877,1,1,1,8,70,541,3125,

%U 10922,16033,4140,1,1,1,9,92,875,6756,36479,110844,127643,21147,1

%N Number A(n,k) of length-n restricted growth strings (RGS) with growth <= k and fixed first element; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%C A(n,k) counts strings [s_1, ..., s_n] with 1 = s_1 <= s_i <= k + max_{j<i} s_j.

%H Alois P. Heinz, <a href="/A305962/b305962.txt">Antidiagonals n = 0..150, flattened</a>

%F A(n,k) = (n-1)! * [x^(n-1)] exp(x+Sum_{j=1..k} (exp(j*x)-1)/j) for n>0, A(0,k) = 1.

%e A(0,2) = 1: the empty string.

%e A(1,2) = 1: 1.

%e A(2,2) = 3: 11, 12, 13.

%e A(3,2) = 12: 111, 112, 113, 121, 122, 123, 124, 131, 132, 133, 134, 135.

%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, 3, 4, 5, 6, 7, 8, ...

%e 1, 5, 12, 22, 35, 51, 70, 92, ...

%e 1, 15, 59, 150, 305, 541, 875, 1324, ...

%e 1, 52, 339, 1200, 3125, 6756, 12887, 22464, ...

%e 1, 203, 2210, 10922, 36479, 96205, 216552, 435044, ...

%e 1, 877, 16033, 110844, 475295, 1530025, 4065775, 9416240, ...

%p b:= proc(n, k, m) option remember; `if`(n=0, 1,

%p add(b(n-1, k, max(m, j)), j=1..m+k))

%p end:

%p A:= (n, k)-> b(n, k, 1-k):

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

%p # second Maple program:

%p A:= (n, k)-> `if`(n=0, 1, (n-1)!*coeff(series(exp(x+add(

%p (exp(j*x)-1)/j, j=1..k)), x, n), x, n-1)):

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

%t b[n_, k_, m_] := b[n, k, m] = If[n==0, 1, Sum[b[n-1, k, Max[m, j]], {j, 1, m+k}]];

%t A[n_, k_] := b[n, k, 1-k];

%t Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* _Jean-François Alcover_, May 27 2019, after _Alois P. Heinz_ *)

%Y Columns k=0-10 give: A000012, A000110, A080337, A189845, A305964, A305965, A305966, A305967, A305968, A305969, A305970.

%Y Main diagonal gives: A305963.

%Y Antidiagonal sums give: A305971.

%Y Cf. A306024.

%K nonn,tabl

%O 0,9

%A _Alois P. Heinz_, Jun 15 2018