A306024 Number A(n,k) of length-n restricted growth strings (RGS) with growth <= k and first element in [k]; square array A(n,k), n>=0, k>=0, read by antidiagonals.
1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 7, 5, 0, 1, 4, 15, 31, 15, 0, 1, 5, 26, 95, 164, 52, 0, 1, 6, 40, 214, 717, 999, 203, 0, 1, 7, 57, 405, 2096, 6221, 6841, 877, 0, 1, 8, 77, 685, 4875, 23578, 60619, 51790, 4140, 0, 1, 9, 100, 1071, 9780, 67354, 297692, 652595, 428131, 21147, 0
Offset: 0
A189845 Number of length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(0)=0 and s(k)<=3+max(prefix) for k>=1.
1, 1, 4, 22, 150, 1200, 10922, 110844, 1236326, 14990380, 195895202, 2740062260, 40789039078, 643118787708, 10696195808162, 186993601880756, 3425688601198118, 65586903427253532, 1309155642001921026, 27185548811026532692, 586164185027289760806
Offset: 0
Keywords
Examples
For n=0 there is one empty string; for n=1 there is one string [0]; for n=2 there are 4 strings [00], [01], [02], and [03]; for n=3 there are a(3)=22 strings: 01: [ 0 0 0 ], 02: [ 0 0 1 ], 03: [ 0 0 2 ], 04: [ 0 0 3 ], 05: [ 0 1 0 ], 06: [ 0 1 1 ], 07: [ 0 1 2 ], 08: [ 0 1 3 ], 09: [ 0 1 4 ], 10: [ 0 2 0 ], 11: [ 0 2 1 ], 12: [ 0 2 2 ], 13: [ 0 2 3 ], 14: [ 0 2 4 ], 15: [ 0 2 5 ], 16: [ 0 3 0 ], 17: [ 0 3 1 ], 18: [ 0 3 2 ], 19: [ 0 3 3 ], 20: [ 0 3 4 ], 21: [ 0 3 5 ], 22: [ 0 3 6 ].
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..481 (first 67 terms from Vincenzo Librandi)
- Joerg Arndt, Matters Computational (The Fxtbook), section 17.3.4, pp. 364-366
Programs
-
Maple
b:= proc(n, m) option remember; `if`(n=0, 1, add(b(n-1, max(m, j)), j=1..m+3)) end: a:= n-> b(n, -2): seq(a(n), n=0..25); # Alois P. Heinz, Jun 15 2018 -
Mathematica
b[n_, m_] := b[n, m] = If[n==0, 1, Sum[b[n-1, Max[m, j]], {j, 1, m+3}]]; a[n_] := b[n, -2]; a /@ Range[0, 25] (* Jean-François Alcover, Nov 03 2020, after Alois P. Heinz *) -
PARI
x='x+O('x^66); egf=exp(x+sum(j=1,3, (exp(j*x)-1)/j)); /* (off by one!) */ concat([1], Vec(serlaplace(egf)))
Formula
E.g.f. of sequence starting 1,4,22,.. is exp(x+exp(x)+exp(2*x)/2+exp(3*x)/3-11/6) = exp(x+sum(j=1,3, (exp(j*x)-1)/j)) = 1+4*x+11*x^2+25*x^3+50*x^4+5461/60*x^5 +...
A355421 Expansion of e.g.f. exp(Sum_{k=1..3} (exp(k*x) - 1)).
1, 6, 50, 504, 5870, 76872, 1111646, 17522664, 298133054, 5433157512, 105396184478, 2165189912040, 46901678992958, 1067332196912136, 25435754924426270, 633014456504059368, 16411191933603611198, 442258823578968351624
Offset: 0
Keywords
Programs
-
PARI
my(N=20, x='x+O('x^N)); Vec(serlaplace(exp(sum(k=1, 3, exp(k*x)-1)))) -
PARI
a_vector(n) = my(v=vector(n+1)); v[1]=1; for(i=1, n, v[i+1]=sum(j=1, i, (1+2^j+3^j)*binomial(i-1, j-1)*v[i-j+1])); v;
Formula
a(0) = 1; a(n) = Sum_{k=1..n} (1 + 2^k + 3^k) * binomial(n-1,k-1) * a(n-k).
Comments
Examples
Links
Crossrefs
Programs
Maple
b:= proc(n, k, m) option remember; `if`(n=0, 1, add(b(n-1, k, max(m, j)), j=1..m+k)) end: A:= (n, k)-> b(n, k, 0): seq(seq(A(n, d-n), n=0..d), d=0..12); # second Maple program: A:= (n, k)-> n!*coeff(series(exp(add( (exp(j*x)-1)/j, j=1..k)), x, n+1), x, n): seq(seq(A(n, d-n), n=0..d), d=0..12);Mathematica
b[n_, k_, m_] := b[n, k, m] = If[n==0, 1, Sum[b[n-1, k, Max[m, j]], {j, 1, m+k}]]; A[n_, k_] := b[n, k, 0]; Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 27 2019, after Alois P. Heinz *)Formula