OFFSET
1,5
COMMENTS
The sequence k!*T(n,k) counts ways to partition [n] into a set of sets, then partition [k] into lists written on those sets, such that each set and its associated list are both nonempty.
Extension to nonpositive n,k is finicky
* the first formula and combinatorial wisdom suggest the 0th column and row should both begin (1,0,0,0...).
* the second (sum over hypergeometrics) extends the columns backwards according to their linear recurrences.
The first formula instead agrees with the second for n <= 0 < k, if Stirling2(n,j) is extended to negative n according to the linked page.
LINKS
Natalia L. Skirrow, above the Stirling triangles
FORMULA
T(n,k) = Sum_{j=0..k} C(k-1,j-1) * Stirling2(n,j).
T(n,k) = Sum_{j=1..k} C(k-1,j-1) * hypergeom([j-k],[j],1) * j^n / j!.
D-finite with recurrence T(n,k+1) = T(n,k) + (k+1)*T(n-1,k+1) - (2*k-1)*T(n-1,k) + (k-1)*T(n-1,k-1).
O.g.f.: hypergeom([1],[1-1/x],y/(y-1)) = -(y/(y-1))^(1/x) * gamma(-1/x,0,y/(y-1)) / (x*e^(y/(1-y))), where gamma is the lower incomplete gamma function. (Includes T(0,0) = 1.)
Column o.g.f.: f_k(x) = hypergeom([1-k],[2-1/x],1) / (1/x-1).
E.g.f.: e^((e^x-1) * y / (1-y)).
Column e.g.f.: (e^x-1) * hypergeom([1-k],[2],1-e^x).
Sequence T(n,k)/n! (for fixed k and n>=1) has:
Center of mass (expectation) = e*sqrt(k/(e-1)) + 1/(4*(e-1)) - 1/2 + O(k^(-1/2)).
Variance = e*(3*e/2 - 2)*sqrt(k)/(e-1)^(3/2) - (e^3-9*e^2/4+3*e/2)/(e-1)^2 + O(k^(-1/2)).
EXAMPLE
n\k|1 2 3 4 5 6 7 8
---+----------------------------------------
1 |1 1 1 1 1 1 1 1
2 |1 2 3 4 5 6 7 8
3 |1 4 8 13 19 26 34 43 (A034856)
4 |1 8 21 41 69 106 153 211
5 |1 16 56 131 252 431 681 1016
6 |1 32 153 429 940 1782 3068 4929
7 |1 64 428 1443 3599 7547 14121 24361
8 |1 128 1221 4981 14159 32822 66647 123244
MAPLE
T := (n, k) -> add(binomial(k-1, j-1)*Stirling2(n, j), j = 0..k):
for n from 1 to 8 do lprint(seq(T(n, k), k = 1..8)) od; # Peter Luschny, Aug 26 2025
MATHEMATICA
MatrixForm[Table[Table[Sum[Binomial[k-1, j-1]*StirlingS2[n, j], {j, 0, k}], {k, 1, 8}], {n, 1, 8}]]
MatrixForm[Table[Table[Sum[Binomial[k-1, j-1]*HypergeometricPFQ[{j-k}, {j}, 1]*j^n/j!, {j, 1, k}], {k, 1, 8}], {n, 1, 8}]] (* extends to negative n differently *)
PROG
(PARI) T(n, k) = sum(j=0, k, binomial(k-1, j-1) * stirling(n, j, 2)); \\ Michel Marcus, Sep 11 2025
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Natalia L. Skirrow, Aug 25 2025
STATUS
approved
