cp's OEIS Frontend

A087903 Triangle read by rows of the numbers T(n,k) (n > 1, 0 < k < n) of set partitions of n of length k which do not have a proper subset of parts with a union equal to a subset {1,2,...,j} with j < n.

%I A087903 #35 Apr 29 2025 14:36:57
%S A087903 1,1,1,1,4,1,1,11,9,1,1,26,48,16,1,1,57,202,140,25,1,1,120,747,916,
%T A087903 325,36,1,1,247,2559,5071,3045,651,49,1,1,502,8362,25300,23480,8260,
%U A087903 1176,64,1,1,1013,26520,117962,159736,84456,19404,1968,81,1,1,2036,82509,525608,998830,749154,253764,40944,3105,100,1
%N A087903 Triangle read by rows of the numbers T(n,k) (n > 1, 0 < k < n) of set partitions of n of length k which do not have a proper subset of parts with a union equal to a subset {1,2,...,j} with j < n.
%C A087903 Another version of the triangle T(n,k), 0 <= k <= n, given by [1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, ...] DELTA [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] where DELTA is the operator defined in A084938; see also A086329 for a triangle transposed. - _Philippe Deléham_, Jun 13 2004
%H A087903 G. C. Greubel, <a href="/A087903/b087903.txt">Rows n = 2..52 of the triangle, flattened</a>
%H A087903 V. E. Adler, <a href="http://arxiv.org/abs/1510.02900">Set partitions and integrable hierarchies</a>, arXiv:1510.02900 [nlin.SI], 2015.
%H A087903 Mercedes H. Rosas and Bruce E. Sagan, <a href="http://arxiv.org/abs/math/0208168">Symmetric functions in noncommuting variables</a>, arXiv:math/0208168 [math.CO], 2002, 2004.
%H A087903 Yves Le Jan, <a href="https://arxiv.org/abs/2504.16976">Loop clusters on complete graphs</a>, arXiv:2504.16976 [math.PR], 2025. See p. 6.
%H A087903 Margarete C. Wolf, <a href="http://dx.doi.org/10.1215/S0012-7094-36-00253-3">Symmetric Functions of Non-commutative Elements</a>, Duke Math. J., 2 (1936), 626-637.
%F A087903 T(n, n-1) = T(n,1) = 1.
%F A087903 T(n, n-2) = (n-2)^2.
%F A087903 T(n, 2) = A000295(n).
%F A087903 T(n, k) = S2(n-1, k) + Sum_{j=0..n-2} Sum_{d=0..k-1} (k-d-1)*T(n-j-1, k-d)*S2(j, d), where S2(n, k) is the Stirling number of the second kind.
%F A087903 Sum_{k = 1..n-1} T(n, k) = A074664(n). - _Philippe Deléham_, Jun 13 2004
%F A087903 G.f.: 1-1/(1+add(add(q^n t^k S2(n, k), k=1..n), n >= 1)) where S2(n, k) are the Stirling numbers of the 2nd kind A008277. - _Mike Zabrocki_, Sep 03 2005
%e A087903 T(2,1)=1 for {12};
%e A087903 T(3,1)=1, T(3,2) = 1 for {123}; {13|2};
%e A087903 T(4,1)=1, T(4,2)=4, T(4,3)=1 for {1234}; {14|23}, {13|24}, {124|3}, {134|2}; {14|2|3}.
%e A087903 From _Philippe Deléham_, Jul 16 2007: (Start)
%e A087903 Triangle begins:
%e A087903   1;
%e A087903   1,    1;
%e A087903   1,    4,     1;
%e A087903   1,   11,     9,      1;
%e A087903   1,   26,    48,     16,      1;
%e A087903   1,   57,   202,    140,     25,     1;
%e A087903   1,  120,   747,    916,    325,    36,     1;
%e A087903   1,  247,  2559,   5071,   3045,   651,    49,    1;
%e A087903   1,  502,  8362,  25300,  23480,  8260,  1176,   64,  1;
%e A087903   1, 1013, 26520, 117962, 159736, 84456, 19404, 1968, 81, 1;
%e A087903   ...
%e A087903 Triangle T(n,k), 0 <= k <= n, given by [1,0,2,0,3,0,4,0,...] DELTA [0,1,0,1,0,1,0,...] begins:
%e A087903   1;
%e A087903   1,    0;
%e A087903   1,    1,     0;
%e A087903   1,    4,     1,      0;
%e A087903   1,   11,     9,      1,      0;
%e A087903   1,   26,    48,     16,      1,     0;
%e A087903   1,   57,   202,    140,     25,     1,     0;
%e A087903   1,  120,   747,    916,    325,    36,     1,    0;
%e A087903   1,  247,  2559,   5071,   3045,   651,    49,    1,  0;
%e A087903   1,  502,  8362,  25300,  23480,  8260,  1176,   64,  1, 0;
%e A087903   1, 1013, 26520, 117962, 159736, 84456, 19404, 1968, 81, 1, 0;
%e A087903   ...
%e A087903 (End)
%p A087903 A := proc(n,k) option remember; local j,ell; if n<=0 or k>=n then 0; elif k=1 or k=n-1 then 1; else S2(n-1,k)+add(add((k-ell-1)*A(n-j-1,k-ell)*S2(j,ell),ell=0..k-1),j=0..n-2); fi; end: S2 := (n,k)->if n<0 or k>n then 0; elif k=n or k=1 then 1 else k*S2(n-1,k)+S2(n-1,k-1); fi:
%t A087903 nmax = 12; t[n_, k_] := t[n, k] = StirlingS2[n-1, k] + Sum[ (k-d-1)*t[n-j-1, k-d]*StirlingS2[j, d], {d, 0, k-1}, {j, 0, n-2}]; Flatten[ Table[ t[n, k], {n, 2, nmax}, {k, 1, n-1}]] (* _Jean-François Alcover_, Oct 04 2011, after given formula *)
%o A087903 (SageMath)
%o A087903 @CachedFunction # T = A087903
%o A087903 def T(n,k): return stirling_number2(n-1, k) + sum( sum( (k-m-1)*T(n-j-1, k-m)*stirling_number2(j, m) for m in (0..k-1) ) for j in (0..n-2) )
%o A087903 flatten([[T(n, k) for k in (1..n-1)] for n in (2..14)]) # _G. C. Greubel_, Jun 21 2022
%Y A087903 Cf. A000110, A000295, A008277, A055106, A074664.
%Y A087903 Cf. A055105.
%K A087903 easy,nonn,tabl
%O A087903 2,5
%A A087903 _Mike Zabrocki_, Oct 14 2003