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

%I #36 Aug 03 2021 15:01:21

%S 1,3,1,9,5,1,30,21,8,1,112,88,47,12,1,463,387,253,97,17,1,2095,1816,

%T 1345,675,184,23,1,10279,9123,7304,4418,1641,324,30,1,54267,48971,

%U 41193,28396,13276,3645,536,38,1,306298,279855,243152,183615,102244,36223,7473,842,47,1

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

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

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

%H Alois P. Heinz, <a href="/A270236/b270236.txt">Rows n = 1..141, flattened</a>

%F T(n,n) = 1.

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

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

%F Sum_{k=1..n} k * T(n,k) = A346772(n). - _Alois P. Heinz_, Aug 03 2021

%e 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.

%e 1;

%e 3,1;

%e 9,5,1;

%e 30,21,8,1;

%e 112,88,47,12,1;

%e 463,387,253,97,17,1;

%e 2095,1816,1345,675,184,23,1;

%e 10279,9123,7304,4418,1641,324,30,1;

%e 54267,48971,41193,28396,13276,3645,536,38,1;

%e 306298,279855,243152,183615,102244,36223,7473,842,47,1;

%e 1838320,1695902,1506521,1211936,770989,334751,90223,14303,1267,57,1;

%e 11677867,10856879,9799547,8237223,5795889,2965654,995191,207186,25820, 1839,68,1;

%p b:= proc(n, m) option remember; `if`(n=0, [1, 0], add((p->

%p [p[1], p[2]+p[1]*x^j])(b(n-1, max(m, j))), j=1..m+1))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 0)[2]):

%p seq(T(n), n=0..12); # _Alois P. Heinz_, Mar 14 2016

%t 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 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_ *)

%Y Cf. A070071 (row sums).

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

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

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

%K nonn,tabl

%O 1,2

%A _R. J. Mathar_, Mar 13 2016