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

Author

R. J. Mathar, Mar 13 2016

Keywords

• nonn
• tabl

Comments

The RG functions used here are defined by f(1)=1, f(j) <= 1+max_{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

Examples

			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;
		

Links

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

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.

Programs

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

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.