login
A358623
Regular triangle read by rows. T(n, k) = {{n, k}}, where {{n, k}} are the second order Stirling set numbers (or second order Stirling numbers). T(n, k) for 0 <= k <= n.
1
1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 3, 0, 0, 0, 1, 10, 0, 0, 0, 0, 1, 25, 15, 0, 0, 0, 0, 1, 56, 105, 0, 0, 0, 0, 0, 1, 119, 490, 105, 0, 0, 0, 0, 0, 1, 246, 1918, 1260, 0, 0, 0, 0, 0, 0, 1, 501, 6825, 9450, 945, 0, 0, 0, 0, 0, 0, 1, 1012, 22935, 56980, 17325, 0, 0, 0, 0, 0, 0
OFFSET
0,13
COMMENTS
{{n, k}} are the number of k-quotient sets of an n-set having at least two elements in each equivalence class. This is the definition and notation (doubling the stacked delimiters of the Stirling set numbers) as given by Fekete (see link).
The formal definition expresses the second order Stirling set numbers as a binomial sum over second order Eulerian numbers (see the first formula below). The terminology 'associated Stirling numbers of second kind' used elsewhere should be dropped in favor of the more systematic one used here.
Also the Bell transform of sign(n) for n >= 0. For the definition of the Bell transform see A264428.
REFERENCES
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, Addison-Wesley, Reading, 2nd ed. 1994, thirty-fourth printing 2022.
LINKS
Antal E. Fekete, Apropos two notes on notation, Amer. Math. Monthly, 101 (1994), 771-778.
FORMULA
T(n, k) = Sum_{j=0..k} (-1)^(k - j)*binomial(j, k - j)*<<n - k + j, j>>, where <<n, k>> denote the second order Eulerian numbers (extending Knuth's notation).
T(n, k) = n!*[z^k][t^n] exp(z*(exp(t) - t - 1)).
T(n, k) = Sum_{j=0..k} (-1)^(k - j)*binomial(n, k - j)*{n - k + j, j}, where {n, k} denotes the Stirling set numbers.
T(n, k) = (n - 1) * T(n-2, k-1) + k * T(n-1, k) with suitable boundary conditions.
T(n + k, k) = A269939(n, k), which might be called the Ward set numbers.
EXAMPLE
Triangle T(n, k) starts:
[0] 1;
[1] 0, 0;
[2] 0, 1, 0;
[3] 0, 1, 0, 0;
[4] 0, 1, 3, 0, 0;
[5] 0, 1, 10, 0, 0, 0;
[6] 0, 1, 25, 15, 0, 0, 0;
[7] 0, 1, 56, 105, 0, 0, 0, 0;
[8] 0, 1, 119, 490, 105, 0, 0, 0, 0;
[9] 0, 1, 246, 1918, 1260, 0, 0, 0, 0, 0;
MAPLE
T := (n, k) -> add(binomial(n, k - j)*Stirling2(n - k + j, j)*(-1)^(k - j),
j = 0..k): for n from 0 to 9 do seq(T(n, k), k = 0..n) od;
# Using the e.g.f.:
egf := exp(z*(exp(t) - t - 1)): ser := series(egf, t, 12):
seq(print(seq(n!*coeff(coeff(ser, t, n), z, k), k = 0..n)), n = 0..9);
# Using second order Eulerian numbers:
A358623 := proc(n, k) if n = 0 then return 1 fi;
add(binomial(j, n - 2*k)*combinat:-eulerian2(n - k, n - k - j - 1), j = 0..n-k-1)
end: seq(seq(A358623(n, k), k = 0..n), n = 0..11);
PROG
(Python) # recursion over rows
from functools import cache
@cache
def StirlingSetOrd2(n: int) -> list[int]:
if n == 0: return [1]
if n == 1: return [0, 0]
rov: list[int] = StirlingSetOrd2(n - 2)
row: list[int] = StirlingSetOrd2(n - 1) + [0]
for k in range(1, n // 2 + 1):
row[k] = (n - 1) * rov[k - 1] + k * row[k]
return row
for n in range(9): print(StirlingSetOrd2(n))
# Alternative, using function BellMatrix from A264428.
def f(k: int) -> int:
return 1 if k > 0 else 0
print(BellMatrix(f, 9))
CROSSREFS
A008299 is an irregular subtriangle with more information.
A358622 (second order Stirling cycle numbers).
Cf. A000296 (row sums), alternating row sums (apart from sign): A000587, A293037, and A014182.
Sequence in context: A242434 A036873 A081130 * A360224 A174428 A308347
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Nov 25 2022
STATUS
approved