﻿ Stirling-Frobenius numbers

## The Stirling-Frobenius numbers

### Introduction

The Stirling-Frobenius numbers, as understood here, is a family of sequences of integer triangles which generalize the classical Stirling subset and Stirling cycle numbers. The generalization is based on a generalization of the Eulerian numbers and an identity discovered by Ferdinand Frobenius between the Stirling and the Eulerian numbers.

As the starting point we take formula (6.39) in Concrete Mathematics

$$k! \, \genfrac\{\}{0pt}{}{n}{k} = \sum_{j} \genfrac < > {0pt}{}{n}{j} \genfrac ( ) {0pt}{}{j}{n-k}.$$

$\genfrac\{\}{0pt}{}{n}{k}$ are the Stirling subset numbers and $\genfrac < > {0pt}{}{n}{j}$ the Eulerian numbers defined for integers $n \ge 0, \ k \ge 0$.

In the following, the parameter $m$ is an integer $m \ge 1$ and the value $m = 1$ always refers to the classical case. Unsurprisingly, also the case for $m = 2$ is contained in OEIS for some of the triangle sequences.

### Subset numbers  [SF-S]

The Stirling-Frobenius subset numbers are defined as

$$\genfrac\{\}{0pt}{}{n}{k}_{m} = \frac{1}{m^k k!} \sum_{j=0}^{n} \genfrac < > {0pt}{}{n}{j}_m \genfrac ( ) {0pt}{}{j}{n-k}.$$

Here $\genfrac < > {0pt}{}{n}{j}_m$ is the coefficient of $x^j$ of $A_{n,m}(x)$, the generalized Eulerian polynomial.  The case $m=1$ are the classical Stirling subset numbers (Concrete Mathematics, table 244).
 n\k 0 1 2 3 4 5 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1
 n\k 0 1 2 3 4 5 0 1 1 1 1 2 1 4 1 3 1 13 9 1 4 1 40 58 16 1 5 1 121 330 170 25 1
 n\k 0 1 2 3 4 5 0 1 1 2 1 2 4 7 1 3 8 39 15 1 4 16 203 159 26 1 5 32 1031 1475 445 40 1
 n\k 0 1 2 3 4 5 0 1 1 3 1 2 9 10 1 3 27 79 21 1 4 81 580 310 36 1 5 243 4141 3990 850 55 1

### Cycle numbers  [SF-C]

The Stirling-Frobenius subset numbers, for fixed $m \ge 1$, can be regarded as an infinite lower triangular matrix which can be inverted. Because we want the inverse numbers to be unsigned we use the inversion relation $\sum_k a(n,k)b(k,j)(-1)^{n-k}= [j=n].$ We call the inverse numbers the Stirling-Frobenius cycle numbers.

$$\genfrac | | {0pt}{}{n}{k}_m = \left( \genfrac\{\}{0pt}{}{n}{k}_m \right)^{-1}.$$

The case $m=1$ are the classical Stirling cycle numbers (Concrete Mathematics, table 245).

 n\k 0 1 2 3 4 5 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1
 n\k 0 1 2 3 4 5 0 1 1 1 1 2 3 4 1 3 15 23 9 1 4 105 176 86 16 1 5 945 1689 950 230 25 1
 n\k 0 1 2 3 4 5 0 1 1 2 1 2 10 7 1 3 80 66 15 1 4 880 806 231 26 1 5 12320 12164 4040 595 40 1
 n\k 0 1 2 3 4 5 0 1 1 3 1 2 21 10 1 3 231 131 21 1 4 3465 2196 446 36 1 5 65835 45189 10670 1130 55 1

### Scaled subset numbers   [SF-SS]

The scaled Stirling-Frobenius subset numbers are defined for $m \ge 1$ as

$$\genfrac\{\}{0pt}{}{n}{k}_m^{\wedge} = m^k \genfrac\{\}{0pt}{}{n}{k}_m.$$

 n\k 0 1 2 3 4 5 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1
 n\k 0 1 2 3 4 5 0 1 1 1 2 2 1 8 4 3 1 26 36 8 4 1 80 232 128 16 5 1 242 1320 1360 400 32
 n\k 0 1 2 3 4 5 0 1 1 2 3 2 4 21 9 3 8 117 135 27 4 16 609 1431 702 81 5 32 3093 13275 12015 3240 243
 n\k 0 1 2 3 4 5 0 1 1 3 4 2 9 40 16 3 27 316 336 64 4 81 2320 4960 2304 256 5 243 16564 63840 54400 14080 1024

The beauty of this sequence of sequences can be visualized by a helix similar constructed as the spiral of Theodorus: Cut out the number triangles and compose them in a contiguous fashion thereby identifying the right hand side of triangle $\genfrac\{\}{0pt}{}{n}{k}_{m-1}^{\wedge}$ with the left hand side of triangle $\genfrac\{\}{0pt}{}{n}{k}_m^{\wedge}$.

### Scaled cycle numbers  [SF-CS]

The Stirling-Frobenius cycle numbers have a scaled version, the scaled Stirling-Frobenius cycle numbers. They are defined as:

$$\genfrac | | {0pt}{}{n}{k}_m^{\wedge} = m^{k} \, \genfrac | | {0pt}{}{n}{k}_m$$

 n\k 0 1 2 3 4 5 0 1 1 0 1 2 0 1 1 3 0 2 3 1 4 0 6 11 6 1 5 0 24 50 35 10 1
 n\k 0 1 2 3 4 5 0 1 1 1 2 2 3 8 4 3 15 46 36 8 4 105 352 344 128 16 5 945 3378 3800 1840 400 32
 n\k 0 1 2 3 4 5 0 1 1 2 3 2 10 21 9 3 80 198 135 27 4 880 2418 2079 702 81 5 12320 36492 36360 16065 3240 243
 n\k 0 1 2 3 4 5 0 1 1 3 4 2 21 40 16 3 231 524 336 64 4 3465 8784 7136 2304 256 5 65835 180756 170720 72320 14080 1024

Note that

$$\genfrac | | {0pt}{}{n}{0}_m^{\wedge} = \sum_{k=0}^{n+1} (-1)^{k+1} \genfrac | | {0pt}{}{n+1}{k}_m^{\wedge} = \prod_{k=1}^{n} (mk-1).$$

### Ordered subset numbers  [SF-SO]

The Stirling-Frobenius subset numbers have an ordered version

$$\genfrac\{\}{0pt}{}{n}{k}_m^{\circ} = k! \, \genfrac\{\}{0pt}{}{n}{k}_m .$$

 n\k 0 1 2 3 4 5 0 1 1 0 1 2 0 1 2 3 0 1 6 6 4 0 1 14 36 24 5 0 1 30 150 240 120
 n\k 0 1 2 3 4 5 0 1 1 1 2 2 1 8 8 3 1 26 72 48 4 1 80 464 768 384 5 1 242 2640 8160 9600 3840
 n\k 0 1 2 3 4 5 0 1 1 2 3 2 4 21 18 3 8 117 270 162 4 16 609 2862 4212 1944 5 32 3093 26550 72090 77760 29160
 n\k 0 1 2 3 4 5 0 1 1 3 4 2 9 40 32 3 27 316 672 384 4 81 2320 9920 13824 6144 5 243 16564 127680 326400 337920 1228800

### Ordered cycle numbers  [SF-CO]

The Stirling-Frobenius cycle numbers have an ordered version

$$\genfrac | | {0pt}{}{n}{k}_m^{\circ} = k! \, \genfrac | | {0pt}{}{n}{k}_m .$$

 n\k 0 1 2 3 4 5 0 1 1 0 1 2 0 1 2 3 0 2 6 6 4 0 6 22 36 24 5 0 24 100 210 240 120
 n\k 0 1 2 3 4 5 0 1 1 1 1 2 3 4 2 3 15 23 18 6 4 105 176 172 96 24 5 945 1689 1900 1380 600 120

### Ordered scaled cycle numbers  [SF-CSO]

The scaled Stirling-Frobenius cycle numbers have an ordered version

$$\genfrac | | {0pt}{}{n}{k}_m^{\otimes} = k! \, m^k \genfrac | | {0pt}{}{n}{k}_m \, .$$

 n\k 0 1 2 3 4 5 0 1 1 0 1 2 0 1 2 3 0 2 6 6 4 0 6 22 36 24 5 0 24 100 210 240 120
 n\k 0 1 2 3 4 5 0 1 1 1 2 2 3 8 8 3 15 46 72 48 4 105 352 688 768 384 5 945 3378 7600 11040 9600 3840

### Ordered scaled subset numbers  [SF-SSO]

The scaled Stirling-Frobenius subset numbers have an ordered version

$$\genfrac\{\}{0pt}{}{n}{k}_m^{\otimes} = k! \, m^k \genfrac\{\}{0pt}{}{n}{k}_m = \sum_{j=0}^{n} \genfrac < > {0pt}{}{n}{j}_m \genfrac ( ) {0pt}{}{j}{n-k}.$$

 n\k 0 1 2 3 4 5 0 1 1 0 1 2 0 1 2 3 0 1 6 6 4 0 1 14 36 24 5 0 1 30 150 240 120
 n\k 0 1 2 3 4 5 0 1 1 1 1 2 1 4 2 3 1 13 18 6 4 1 40 116 96 24 5 1 121 660 1020 600 120

### Recurrences

The Stirling-Frobenius numbers can be computed by the following recurrence:

$$S_m(0, 0) = 1;$$ $$S_m(n, k) = 0 \text{ if } k \gt n \text{ or } k \lt 0;$$ $$S_m(n, k) = \alpha_m(n,k) S_m(n-1, k-1)+ \beta_m(n,k) S_m(n-1, k) .$$

Depending on the type of the numbers $\alpha_m(n,k)$ and $\beta_m(n,k)$ are defined as shown in the table below.

 Type $\alpha_m(n,k)$ $\beta_m(n,k)$ SF-S $1$ $m(k+1)-1$ SF-C $1$ $mn-1$ SF-SS $m$ $m(k+1)-1$ SF-CS $m$ $mn-1$ SF-SSO $k$ $m(k+1)-1$ SF-CO $k$ $mn-1$ SF-SO $mk$ $m(k+1)-1$ SF-CSO $mk$ $mn - 1$

This table amounts to a succinct systematization of the Stirling-Frobenius numbers and its variants.

### Summary

$$\genfrac\{\}{0pt}{}{n}{k}_m = \frac{1}{m^k k!} \sum_{j=0}^{n} \genfrac < > {0pt}{}{n}{j}_m \genfrac ( ) {0pt}{}{j}{n-k}$$
SF-S
 A048993 A039755 A225468 A225469
$$\genfrac | |{0pt}{}{n}{k}_m = \left( \genfrac\{\}{0pt}{}{n}{k}_m \right)^{-1}$$
SF-C
 A132393 A028338 A225470 A225471
$$\genfrac\{\}{0pt}{}{n}{k}_m^{\wedge} = m^k \, \genfrac\{\}{0pt}{}{n}{k}_m$$
SF-SS
 A048993 A154537 A225466 A225467
$$\genfrac | |{0pt}{}{n}{k}_m^{\wedge} = m^k \, \genfrac | |{0pt}{}{n}{k}_m$$
SF-CS
 A132393 A161198 A225477 A225478
$$\genfrac\{\}{0pt}{}{n}{k}_m^{\circ} = k! \, \genfrac\{\}{0pt}{}{n}{k}_m$$
SF-SO
 A131689 A145901 A225472 A225473
$$\genfrac | | {0pt}{}{n}{k}_m^{\circ} = k! \, \genfrac | | {0pt}{}{n}{k}_m$$
SF-CO
 A225479 A225475
$$\genfrac | | {0pt}{}{n}{k}_m^{\otimes} = k! \, m^k \, \genfrac | | {0pt}{}{n}{k}_m$$
SF-CSO
 A225479 A225474
$$\genfrac\{\}{0pt}{}{n}{k}_m^{\otimes} = k! \, {m^k} \genfrac\{\}{0pt}{}{n}{k}_m = \sum_{j=0}^{n} \genfrac < > {0pt}{}{n}{j}_m \genfrac ( ) {0pt}{}{j}{n-k}$$
SF-SSO
 A131689 A225476

### Program

@CachedFunction
def EulerianNumber(n, k, m) :
if n == 0: return 1 if k == 0 else 0
return (m*(n-k)+m-1)*EulerianNumber(n-1, k-1, m)
+ (m*k+1)*EulerianNumber(n-1, k, m)

def EulerianPolynomial(n, k, x):
return add(EulerianNumber(n, m, k)*x^m for m in (0..n))

def SF_S(n, k, m):  # StirlingFrobeniusSubsetNumbers
return add(EulerianNumber(n, j, m)*binomial(j, n - k)
for j in (0..n))/(factorial(k)*m^k)

def SF_SS(n, k, m): # StirlingFrobeniusScaledSubsetNumbers
return add(EulerianNumber(n, j, m)*binomial(j, n - k)
for j in (0..n))/factorial(k)

def SF_SO(n, k, m): # StirlingFrobeniusOrderedSubsetNumbers
return add(EulerianNumber(n, j, m)*binomial(j, n - k)
for j in (0..n))

def SF_SSO(n, k, m): # StirlingFrobeniusOrderedScaledSubsetNumbers
return add(EulerianNumber(n, j, m)*binomial(j, n - k)
for j in (0..n))/m^k

def SignInv(F, m, d):  # SignedInversion
M = matrix(ZZ, d + 1)
for n in (0..d) :
for k in (0..n) :
M[n, k] = (-1)^(n-k)*F(n, k, m)
return M.inverse()

@CachedFunction
def SF_CM(n, m):  # StirlingFrobeniusCycleMatrix
return SignInv(SF_S, m, n)

def SF_C(n, k, m):  # StirlingFrobeniusCycleNumbers
M = SignInv(SF_S, m, n)
return M[n, k]

def SF_CS(n, k, m):  # StirlingFrobeniusScaledCycleNumbers
M = SignInv(SF_S, m, n)
return M[n, k] * m^k

def SF_CO(n, k, m):  # StirlingFrobeniusOrderedCycleNumbers
M = SignInv(SF_S, m, n)
return M[n, k] * factorial(k)

def SF_CSO(n, k, m):  # StirlingFrobeniusOrderedScaledCycleNumbers
M = SignInv(SF_S, m, n)
return M[n, k] * m^k * factorial(k)

@CachedFunction
def rSF_S(n, k, m):  # StirlingFrobeniusSubsetNumbers
if k > n or k < 0 : return 0
if n == 0 and k == 0: return 1
return rSF_S(n-1, k-1, m) + (m*(k+1)-1)*rSF_S(n-1, k, m)

@CachedFunction
def rSF_C(n, k, m):  # StirlingFrobeniusCycleNumbers
if k > n or k < 0 : return 0
if n == 0 and k == 0: return 1
return rSF_C(n-1, k-1, m) + (m*n-1)*rSF_C(n-1, k, m)

@CachedFunction
def rSF_SS(n, k, m):  # StirlingFrobeniusScaledSubsetNumbers
if k > n or k < 0 : return 0
if n == 0 and k == 0: return 1
return m*rSF_SS(n-1, k-1, m) + (m*(k+1)-1)*rSF_SS(n-1, k, m)

@CachedFunction
def rSF_CS(n, k, m):  # StirlingFrobeniusScaledCycleNumbers
if k > n or k < 0 : return 0
if n == 0 and k == 0: return 1
return m*rSF_CS(n-1, k-1, m) + (m*n-1)*rSF_CS(n-1, k, m)

@CachedFunction
def rSF_SO(n, k, m):  # StirlingFrobeniusOrderedSubsetNumbers
if k > n or k < 0 : return 0
if n == 0 and k == 0: return 1
return m*k*rSF_SO(n-1, k-1, m) + (m*(k+1)-1)*rSF_SO(n-1, k, m)

@CachedFunction
def rSF_CO(n, k, m):  # StirlingFrobeniusOrderedCycleNumbers
if k > n or k < 0 : return 0
if n == 0 and k == 0: return 1
return k*rSF_CO(n-1, k-1, m) + (m*n-1)*rSF_CO(n-1, k, m)

@CachedFunction
def rSF_CSO(n, k, m):  # StirlingFrobeniusOrderedCycleNumbers
if k > n or k < : return 0
if n == 0 and k == 0: return 1
return m*k*rSF_CSO(n-1, k-1, m) + (m*n-1)*rSF_CSO(n-1, k, m)

@CachedFunction
def rSF_SSO(n, k, m): # StirlingFrobeniusSubsetScaledOrdered
if k > n or k < 0 : return 0
if n == 0 and k == 0: return 1
return k*rSF_SSO(n-1, k-1, m) + (m*(k+1)-1)*rSF_SSO(n-1, k, m)