This site is supported by donations to The OEIS Foundation.

# The Stirling-Frobenius Numbers

KEYWORDS: Stirling numbers, Eulerian numbers, generalized Stirling numbers, generalized Eulerian numbers, Stirling-Frobenius numbers.

Concerned with sequences: A225466A225479

You can also read this post rendered with MathJax on my homepage

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

${\displaystyle k!\,{\begin{Bmatrix}n\\k\end{Bmatrix}}=\sum _{j}\left\langle {n \atop j}\right\rangle {\binom {j}{n-k}}.}$

${\displaystyle \left\{{n \atop k}\right\}\ }$ are the Stirling subset numbers and ${\displaystyle \left\langle {n \atop j}\right\rangle }$ the Eulerian numbers defined for integers ${\displaystyle n\geq 0,\ k\geq 0}$.

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

## Subset numbers  [SF-S]

The Stirling-Frobenius subset numbers are defined as

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}={\frac {1}{m^{k}k!}}\sum _{j=0}^{n}\left\langle {n \atop j}\right\rangle _{m}{\binom {j}{n-k}}.}$

Here ${\displaystyle \left\langle {n \atop j}\right\rangle _{m}}$ is the coefficient of ${\displaystyle x^{j}}$ of ${\displaystyle A_{n,m}(x)}$, the generalized Eulerian polynomial. The case ${\displaystyle 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 ${\displaystyle m\geq 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 ${\displaystyle \sum _{k}a(n,k)b(k,j)(-1)^{n-k}=[j=n].}$ We call the inverse numbers the Stirling-Frobenius cycle numbers.

${\displaystyle {\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}=\left({\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}\right)^{-1}.}$

The case ${\displaystyle 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 ${\displaystyle m\geq 1}$ as

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\wedge }=m^{k}{\begin{Bmatrix}n\\k\end{Bmatrix}}_{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 ${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{m-1}^{\wedge }}$ with the left hand side of triangle ${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{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:

${\displaystyle {\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}^{\wedge }=m^{k}\,{\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{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

## Ordered subset numbers  [SF-SO]

The Stirling-Frobenius subset numbers have an ordered version

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\circ }=k!{\begin{Bmatrix}n\\k\end{Bmatrix}}_{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

${\displaystyle {\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}^{\circ }=k!\,{\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{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

${\displaystyle {\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}^{\otimes }=\ k!\,m^{k}\ {\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{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

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\otimes }=k!\,m^{k}{\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}=\sum _{j=0}^{n}\left\langle {n \atop j}\right\rangle _{m}{\binom {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:

${\displaystyle S_{m}(0,0)=1;}$
${\displaystyle S_{m}(n,k)=0{\text{ if }}k>n{\text{ or }}k<0;}$
${\displaystyle 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 ${\displaystyle \alpha _{m}(n,k)}$ and ${\displaystyle \beta _{m}(n,k)}$ are defined as shown in the table below.

 Type ${\displaystyle \alpha _{m}(n,k)}$ ${\displaystyle \beta _{m}(n,k)}$ SF-S ${\displaystyle 1}$ ${\displaystyle m(k+1)-1}$ SF-C ${\displaystyle 1}$ ${\displaystyle mn-1}$ SF-SS ${\displaystyle m}$ ${\displaystyle m(k+1)-1}$ SF-CS ${\displaystyle m}$ ${\displaystyle mn-1}$ SF-SSO ${\displaystyle k}$ ${\displaystyle m(k+1)-1}$ SF-CO ${\displaystyle k}$ ${\displaystyle mn-1}$ SF-SO ${\displaystyle mk}$ ${\displaystyle m(k+1)-1}$ SF-CSO ${\displaystyle mk}$ ${\displaystyle mn-1}$

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

## Summary

SF-S

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}={\frac {1}{m^{k}k!}}\sum _{j=0}^{n}\left\langle {n \atop j}\right\rangle _{m}{\binom {j}{n-k}}}$
 A048993 A039755 A225468 A225469

SF-C

${\displaystyle {\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}=\left({\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}\right)^{-1}}$
 A132393 A028338 A225470 A225471

SF-SS

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\wedge }=m^{k}\,{\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}}$
 A048993 A154537 A225466 A225467

SF-CS

${\displaystyle {\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}^{\wedge }=m^{k}\,{\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}}$
 A132393 A161198 A225477 A225478

SF-SO

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\circ }=k!\,{\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}}$
 A131689 A145901 A225472 A225473

SF-CO

${\displaystyle {\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}^{\circ }=k!\,{\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}}$
 A225479 A225475

SF-CSO

${\displaystyle {\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}^{\otimes }=k!\,m^{k}\,{\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}}$
 A225479 A225474

SF-SSO

${\displaystyle {\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\otimes }=k!\,{m^{k}}{\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}=\sum _{j=0}^{n}\left\langle {n \atop j}\right\rangle _{m}{\binom {j}{n-k}}}$
 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)