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

Table of n, a(n) for n=0..77.

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.

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

Sequence in context: A242434 A036873 A081130 * A360224 A174428 A308347

Adjacent sequences: A358620 A358621 A358622 * A358624 A358625 A358626

Keyword

nonn,tabl

Author

Peter Luschny, Nov 25 2022

Status

approved