A270236 Triangle T(n,p) read by rows: the number of occurrences of p in the restricted growth functions of length n.

1, 3, 1, 9, 5, 1, 30, 21, 8, 1, 112, 88, 47, 12, 1, 463, 387, 253, 97, 17, 1, 2095, 1816, 1345, 675, 184, 23, 1, 10279, 9123, 7304, 4418, 1641, 324, 30, 1, 54267, 48971, 41193, 28396, 13276, 3645, 536, 38, 1, 306298, 279855, 243152, 183615, 102244, 36223, 7473, 842, 47, 1

Offset

1,2

Comments

The RG functions used here are defined by f(1)=1, f(j) <= 1+max_{i<j} f(i).

T(n,p) is the number of elements in the p-th subset in all set partitions of [n]. - Joerg Arndt, Mar 14 2016

Links

Alois P. Heinz, Rows n = 1..141, flattened

Formula

T(n,n) = 1.

Conjecture: T(n,n-1) = 2+n*(n-1)/2 for n>1.

Conjecture: T(n+1,n-1) = 2+n*(n+1)*(3*n^2-5*n+26)/24 for n>1.

Sum_{k=1..n} k * T(n,k) = A346772(n). - Alois P. Heinz, Aug 03 2021

Example

The two restricted growth functions of length 2 are (1,1) and (1,2). The 1 appears 3 times and the 2 once, so T(2,1)=3 and T(2,2)=1.
1;
3,1;
9,5,1;
30,21,8,1;
112,88,47,12,1;
463,387,253,97,17,1;
2095,1816,1345,675,184,23,1;
10279,9123,7304,4418,1641,324,30,1;
54267,48971,41193,28396,13276,3645,536,38,1;
306298,279855,243152,183615,102244,36223,7473,842,47,1;
1838320,1695902,1506521,1211936,770989,334751,90223,14303,1267,57,1;
11677867,10856879,9799547,8237223,5795889,2965654,995191,207186,25820, 1839,68,1;

Maple

b:= proc(n, m) option remember; `if`(n=0, [1, 0], add((p->
      [p[1], p[2]+p[1]*x^j])(b(n-1, max(m, j))), j=1..m+1))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)[2]):
seq(T(n), n=0..12);  # Alois P. Heinz, Mar 14 2016

Mathematica

b[n_, m_] := b[n, m] = If[n == 0, {1, 0}, Sum[Function[p, {p[[1]], p[[2]] + p[[1]]*x^j}][b[n-1, Max[m, j]]], {j, 1, m+1}]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, 0][[2]] ]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Apr 07 2016, after Alois P. Heinz *)

Crossrefs

Cf. A070071 (row sums).

Column p=1-10 gives: A124427, A270494, A270495, A270496, A270497, A270498, A270499, A270500, A270501, A270502.

T(2n+1,n+1) gives A270529.

Cf. A000110, A185105, A285362, A286416, A346772.

Sequence in context: A331257 A112626 A050155 * A140714 A112932 A337680

Adjacent sequences: A270233 A270234 A270235 * A270237 A270238 A270239

Keyword

nonn,tabl

Author

R. J. Mathar, Mar 13 2016

Status

approved