A305962 -id:A305962 - cp's OEIS frontend

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

Alois P. Heinz, Jun 17 2018

A(n,k) counts strings [s_1, ..., s_n] with 1 <= s_i <= k + max(0, max_{j

			A(2,3) = 15: 11, 12, 13, 14, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 36.
A(4,1) = 15: 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 1234.
Square array A(n,k) begins:
  1,   1,    1,     1,      1,       1,       1,       1, ...
  0,   1,    2,     3,      4,       5,       6,       7, ...
  0,   2,    7,    15,     26,      40,      57,      77, ...
  0,   5,   31,    95,    214,     405,     685,    1071, ...
  0,  15,  164,   717,   2096,    4875,    9780,   17689, ...
  0,  52,  999,  6221,  23578,   67354,  160201,  335083, ...
  0, 203, 6841, 60619, 297692, 1044045, 2943277, 7117789, ...

Alois P. Heinz, Antidiagonals n = 0..150, flattened

Columns k=0-10 give: A000007, A000110, A002872, A306027, A306028, A306029, A306030, A306031, A306032, A306033, A306034.
Main diagonal gives A306025.
Antidiagonal sums give A306026.
Cf. A305962.

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);

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 *)

E.g.f. of column k: exp(Sum_{j=1..k} (exp(j*x)-1)/j).

A080337 Bisection of A080107.

Original entry on oeis.org

1, 3, 12, 59, 339, 2210, 16033, 127643, 1103372, 10269643, 102225363, 1082190554, 12126858113, 143268057587, 1778283994284, 23120054355195, 314017850216371, 4444972514600178, 65435496909148513, 999907522895563403, 15832873029742458796, 259377550023571768075

Offset: 1

Wouter Meeussen, Mar 18 2003

nonn

Number of symmetric positions of non-attacking rooks on upper-diagonal part of 2n X 2n chessboard.
Number of length-n restricted growth strings (RGS) [s(0),s(1),...,s(n-1)] where s(0)=0 and s(k)<=2+max(prefix) for k>=1, see example. - Joerg Arndt, Apr 25 2010
Number of achiral color patterns in a row or loop of length 2n-1. Two color patterns are equivalent if the colors are permuted. - Robert A. Russell, Apr 24 2018
Stirling transform of A005425(n-1) per Knuth reference. - Robert A. Russell, Apr 28 2018

			From _Joerg Arndt_, Apr 25 2010: (Start)
For n=0 there is one empty string (term a(0)=0 not included here); for n=1 there is one string [0]; for n=2 there are 3 strings [00], [01], and [02];
for n=3 there are a(3)=12 strings (in lexicographic order):
01: [000],
02: [001],
03: [002],
04: [010],
05: [011],
06: [012],
07: [013],
08: [020],
09: [021],
10: [022],
11: [023],
12: [024].
(End)
For a(3) = 12, both the row and loop patterns are AAAAA, AABAA, ABABA, ABBBA, AABCC, ABACA, ABBBC, ABCAB, ABCBA, ABCBD, ABCDA, and ABCDE. - _Robert A. Russell_, Apr 24 2018

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 765). - Robert A. Russell, Apr 28 2018

Alois P. Heinz, Table of n, a(n) for n = 1..514
Joerg Arndt, Matters Computational (The Fxtbook), section 17.3.4, pp. 364-366.
Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See pp. 18, 29.
J. Quaintance, Letter representations of rectangular m x n x p proper arrays, arXiv:math/0412244 [math.CO], 2004-2006.

Row sums of A140735.
Cf. A002872, A080107.
Column k=2 of A305962.

b:= proc(n, m) option remember; `if`(n=0, 1,
      add(b(n-1, max(m, j)), j=1..m+2))
    end:
a:= n-> b(n, -1):
seq(a(n), n=1..25);  # Alois P. Heinz, Jun 15 2018

Table[Sum[ Binomial[n, k] A002872[[k + 1]], {k, 0, n}], {n, 0, 24}]
Aodd[m_, k_] := Aodd[m, k] = If[m > 1, k Aodd[m-1, k] + Aodd[m-1, k-1]
  + Aodd[m-1, k-2], Boole[m==1 && k==1]]
Table[Sum[Aodd[m, k], {k, 1, 2m-1}], {m, 1, 30}] (* Robert A. Russell, Apr 24 2018 *)
x[n_] := x[n] = If[n<2, n+1, 2x[n-1] + (n-1) x[n-2]]; (* A005425 *)
Table[Sum[StirlingS2[n, k] x[k-1], {k, 0, n}], {n, 30}] (* Robert A. Russell, Apr 28 2018, after Knuth reference *)

x='x+O('x^66);
egf=exp(x+exp(x)+exp(2*x)/2-3/2); /* = 1 +3*x +6*x^2 +59/6*x^3 +113/8*x^4 +... */
Vec(serlaplace(egf)) /* Joerg Arndt, Apr 29 2011 */

Binomial transform of A002872 (sorting numbers).
E.g.f.: exp(x+exp(x)+exp(2*x)/2-3/2) = exp(x+sum(j=1,2, (exp(j*x)-1)/j ) ). - Joerg Arndt, Apr 29 2011
From Robert A. Russell, Apr 24 2018: (Start)
Aodd[n,k] = [n>1]*(k*Aodd[n-1,k]+Aodd[n-1,k-1]+Aodd[n-1,k-2])+[n==1]*[k==1]
a(n) = Sum_{k=1..2n-1} Aodd[n,k]. (End)
a(n) = Sum_{k=0..n} Stirling2(n, k)*A005425(k-1). (from Knuth reference) - Robert A. Russell, Apr 28 2018

Comment corrected by Wouter Meeussen, Aug 14 2009

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.

Original entry on oeis.org

1, 1, 4, 22, 150, 1200, 10922, 110844, 1236326, 14990380, 195895202, 2740062260, 40789039078, 643118787708, 10696195808162, 186993601880756, 3425688601198118, 65586903427253532, 1309155642001921026, 27185548811026532692, 586164185027289760806

Offset: 0

Joerg Arndt, Apr 29 2011

nonn

			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 ].

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

Cf. A080337, A000110, A306027.

Column k=3 of A305962.

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

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 *)

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)))

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 +...

A305963 Number of length-n restricted growth strings (RGS) with growth <= n and fixed first element.

Original entry on oeis.org

1, 1, 3, 22, 305, 6756, 216552, 9416240, 530764089, 37498693555, 3235722405487, 334075729235172, 40587204883652869, 5722676826879812177, 925590727478445526747, 170032646641380554970304, 35173161711207720944899921, 8132124409499796317194563900

Offset: 0

Alois P. Heinz, Jun 15 2018

nonn

			a(2) = 3: 11, 12, 13.
a(3) = 22: 111, 112, 113, 114, 121, 122, 123, 124, 125, 131, 132, 133, 134, 135, 136, 141, 142, 143, 144, 145, 146, 147.

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

Main diagonal of A305962.

Cf. A306025.

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-> b(n$2, 1-n):
seq(a(n), n=0..20);
# second Maple program:
a:= n-> `if`(n=0, 1, (n-1)!*coeff(series(exp(x+add(
           (exp(j*x)-1)/j, j=1..n)), x, n), x, n-1)):
seq(a(n), n=0..20);

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_] := b[n, n, 1 - n];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 21 2022, after Alois P. Heinz *)

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

a(n) = A305962(n,n).

A305964 Number of length-n restricted growth strings (RGS) with growth <= four and fixed first element.

Original entry on oeis.org

1, 1, 5, 35, 305, 3125, 36479, 475295, 6811205, 106170245, 1784531879, 32117927231, 615413731205, 12493421510405, 267608512061159, 6026688403933967, 142256385130774229, 3509899012049396645, 90301862963332188839, 2417349828110572405823, 67201548131159391828677

Offset: 0

Alois P. Heinz, Jun 15 2018

nonn

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

Column k=4 of A305962.

Cf. A306028.

b:= proc(n, m) option remember; `if`(n=0, 1,
      add(b(n-1, max(m, j)), j=1..m+4))
    end:
a:= n-> b(n, -3):
seq(a(n), n=0..25);
# second Maple program:
a:= n-> `if`(n=0, 1, (n-1)!*coeff(series(exp(x+add(
           (exp(j*x)-1)/j, j=1..4)), x, n), x, n-1)):
seq(a(n), n=0..25);

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

A305965 Number of length-n restricted growth strings (RGS) with growth <= five and fixed first element.

Original entry on oeis.org

1, 1, 6, 51, 541, 6756, 96205, 1530025, 26775550, 509861195, 10472109149, 230368347780, 5396308081285, 133949699318945, 3508794554854054, 96648143868171171, 2790590111082279405, 84231759174460743700, 2651416546964399982909, 86848041397350751409257

Offset: 0

Alois P. Heinz, Jun 15 2018

nonn

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

Column k=5 of A305962.

Cf. A306029.

b:= proc(n, m) option remember; `if`(n=0, 1,
      add(b(n-1, max(m, j)), j=1..m+5))
    end:
a:= n-> b(n, -4):
seq(a(n), n=0..25);
# second Maple program:
a:= n-> `if`(n=0, 1, (n-1)!*coeff(series(exp(x+add(
           (exp(j*x)-1)/j, j=1..5)), x, n), x, n-1)):
seq(a(n), n=0..25);

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

A305966 Number of length-n restricted growth strings (RGS) with growth <= six and fixed first element.

Original entry on oeis.org

1, 1, 7, 70, 875, 12887, 216552, 4065775, 84022595, 1889844292, 45857269017, 1191971998455, 32996489835190, 968034453578997, 29972909437783507, 975944207096597110, 33313664777283768535, 1188852507118147925627, 44246989258071738375272, 1713739685432232160181115

Offset: 0

Alois P. Heinz, Jun 15 2018

nonn

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

Column k=6 of A305962.

Cf. A306030.

b:= proc(n, m) option remember; `if`(n=0, 1,
      add(b(n-1, max(m, j)), j=1..m+6))
    end:
a:= n-> b(n, -5):
seq(a(n), n=0..25);
# second Maple program:
a:= n-> `if`(n=0, 1, (n-1)!*coeff(series(exp(x+add(
           (exp(j*x)-1)/j, j=1..6)), x, n), x, n-1)):
seq(a(n), n=0..25);

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

A305967 Number of length-n restricted growth strings (RGS) with growth <= seven and fixed first element.

Original entry on oeis.org

1, 1, 8, 92, 1324, 22464, 435044, 9416240, 224382116, 5820361008, 162900823428, 4884515258224, 155992931417316, 5280138035455024, 188639017788288836, 7087660960768335472, 279189959071013966500, 11498108706476961892400, 493881446025566760548100

Offset: 0

Alois P. Heinz, Jun 15 2018

nonn

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

Column k=7 of A305962.

Cf. A306031.

b:= proc(n, m) option remember; `if`(n=0, 1,
      add(b(n-1, max(m, j)), j=1..m+7))
    end:
a:= n-> b(n, -6):
seq(a(n), n=0..25);
# second Maple program:
a:= n-> `if`(n=0, 1, (n-1)!*coeff(series(exp(x+add(
           (exp(j*x)-1)/j, j=1..7)), x, n), x, n-1)):
seq(a(n), n=0..25);

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

A305968 Number of length-n restricted growth strings (RGS) with growth <= eight and fixed first element.

Original entry on oeis.org

1, 1, 9, 117, 1905, 36585, 802221, 19664325, 530764089, 15596609985, 494555435781, 16802009359677, 608027982857169, 23322183958778553, 944242763282027421, 40207158379868421429, 1795007963258388557673, 83786699444454149125041, 4079132811705470375924277

Offset: 0

Alois P. Heinz, Jun 15 2018

nonn

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

Column k=8 of A305962.

Cf. A306032.

b:= proc(n, m) option remember; `if`(n=0, 1,
      add(b(n-1, max(m, j)), j=1..m+8))
    end:
a:= n-> b(n, -7):
seq(a(n), n=0..25);
# second Maple program:
a:= n-> `if`(n=0, 1, (n-1)!*coeff(series(exp(x+add(
           (exp(j*x)-1)/j, j=1..8)), x, n), x, n-1)):
seq(a(n), n=0..25);

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

Showing 1-10 of 12 results. Next

cp's OEIS Frontend

A305971 Antidiagonal sums of A305962.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A080337 Bisection of A080107.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A305963 Number of length-n restricted growth strings (RGS) with growth <= n and fixed first element.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A305964 Number of length-n restricted growth strings (RGS) with growth <= four and fixed first element.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A305965 Number of length-n restricted growth strings (RGS) with growth <= five and fixed first element.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A305966 Number of length-n restricted growth strings (RGS) with growth <= six and fixed first element.