A358622 - OEIS

%I #28 Nov 25 2022 08:16:22

%S 1,0,0,0,1,0,0,2,0,0,0,6,3,0,0,0,24,20,0,0,0,0,120,130,15,0,0,0,0,720,

%T 924,210,0,0,0,0,0,5040,7308,2380,105,0,0,0,0,0,40320,64224,26432,

%U 2520,0,0,0,0,0,0,362880,623376,303660,44100,945,0,0,0,0,0

%N Regular triangle read by rows. T(n, k) = [[n, k]], where [[n, k]] are the second order Stirling cycle numbers (or second order reciprocal Stirling numbers). T(n, k) for 0 <= k <= n.

%C [[n, k]] are the number of permutations of an n-set having at least two elements in each orbit. These permutations have no fixed points and therefore [[n, k]] is the number of k-orbit derangements of an n-set. This is the definition and notation (doubling the stacked delimiters of the Stirling cycle numbers) as given by Fekete (see link).

%C The formal definition expresses the second order Stirling cycle numbers as a binomial sum over second order Eulerian numbers (see the first formula below). The terminology 'associated Stirling numbers of first kind' used elsewhere should be dropped in favor of the more systematic one used here.

%C Also the Bell transform of the factorial numbers with 0! = 0. For the definition of the Bell transform see A264428.

%D Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, Addison-Wesley, Reading, 2nd ed. 1994, thirty-fourth printing 2022.

%H Antal E. Fekete, <a href="http://www.jstor.org/stable/2974533">Apropos two notes on notation</a>, Amer. Math. Monthly, 101 (1994), 771-778.

%F T(n, k) = Sum_{j=0..n-k} binomial(j, n - 2*k)*<<n - k, j>>, where <<n, k>> denote the second order Eulerian numbers (extending Knuth's notation).

%F T(n, k) = [x^n] (-x)^n * hypergeom([-n, x], [], -1/x).

%F T(n, k) = n!*[z^k][t^n] (exp(t)*(1 - t))^(-z). (Compare with (exp(t)/(1 - t))^z, which is the e.g.f. of the Sylvester polynomials A341101.)

%F T(n, k) = [x^k] (-1)^n * n! * L(n, -x - n, -x), where L(n, a, x) is the n-th generalized Laguerre polynomial.

%F T(n, k) = Sum_{j=0..k} binomial(n, k - j)*[n - k + j, j]*(-1)^(k - j), where [n, k] denotes the (signless) Stirling cycle numbers.

%F T(n, k) = (n - 1) * (T(n-2, k-1) + T(n-1, k)) with suitable boundary conditions.

%F T(n + k, k) = A269940(n, k), which might be called the Ward cycle numbers.

%e Triangle T(n, k) starts:

%e [0] 1;

%e [1] 0,     0;

%e [2] 0,     1,     0;

%e [3] 0,     2,     0,     0;

%e [4] 0,     6,     3,     0,    0;

%e [5] 0,    24,    20,     0,    0,  0;

%e [6] 0,   120,   130,    15,    0,  0,  0;

%e [7] 0,   720,   924,   210,    0,  0,  0,  0;

%e [8] 0,  5040,  7308,  2380,  105,  0,  0,  0,  0;

%e [9] 0, 40320, 64224, 26432, 2520,  0,  0,  0,  0,  0;

%p P := (n, x) -> (-x)^n*hypergeom([-n, x], [], 1/x):

%p row := n -> seq(coeff(simplify(P(n, x)), x, k), k = 0..n):

%p for n from 0 to 9 do row(n) od;

%p # Alternative:

%p T := (n, k) -> add(binomial(n, k - j)*abs(Stirling1(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;

%p # Using the e.g.f.:

%p egf := (exp(t)*(1 - t))^(-z): ser := series(egf, t, 12):

%p seq(print(seq(n!*coeff(coeff(ser, t, n), z, k), k=0..n)), n = 0..9);

%p # Using second order Eulerian numbers:

%p A358622 := proc(n, k) local j;

%p add(binomial(j, n - 2*k)*combinat:-eulerian2(n - k, j), j = 0..n-k) end:

%p seq(seq(A358622(n, k), k = 0..n), n = 0..12);

%p # Using generalized Laguerre polynomials:

%p P := (n, x) -> (-1)^n*n!*LaguerreL(n, -n - x, -x):

%p row := n -> seq(coeff(simplify(P(n, x)), x, k), k = 0..n):

%p seq(print(row(n)), n = 0..9);

%o (Python) # recursion over rows

%o from functools import cache

%o @cache

%o def StirlingCycleOrd2(n: int) -> list[int]:

%o     if n == 0: return [1]

%o     if n == 1: return [0, 0]

%o     rov: list[int] = StirlingCycleOrd2(n - 2)

%o     row: list[int] = StirlingCycleOrd2(n - 1) + [0]

%o     for k in range(1, n // 2 + 1):

%o         row[k] = (n - 1) * (rov[k - 1] + row[k])

%o     return row

%o for n in range(9): print(StirlingCycleOrd2(n))

%o # Alternative, using function BellMatrix from A264428.

%o from math import factorial

%o def f(k: int) -> int:

%o     return factorial(k) if k > 0 else 0

%o print(BellMatrix(f, 9))

%Y A008306 is an irregular subtriangle with more information.

%Y Cf. A000166 (row sums), A024000 (alternating row sums).

%Y Cf. A130534, A201637, A341101, A264428, A269940.

%K nonn,tabl

%O 0,8

%A _Peter Luschny_, Nov 23 2022