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, 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

Author

Peter Luschny, Nov 25 2022

Keywords

• nonn
• tabl

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.

Examples

			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;
		

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.

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.

Cf. A048993, A201637, A264428, A269939, A340264.

Programs

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

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

Formula

T(n, k) = Sum_{j=0..k} (-1)^(k - j)*binomial(j, k - j)*<>, where <> 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.