User:Peter Luschny/StirlingFrobeniusNumbers

The Stirling-Frobenius
Numbers

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

Concerned with sequences: A225466 — A225479

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

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

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

In the following, the parameter $m$ is an integer $m\geq 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

${\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 $\left\langle {n \atop j}\right\rangle _{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).

$\left\{{n \atop k}\right\}$ A048993 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	$\left\{{n \atop k}\right\}_{2}$ A039755 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
$\left\{{n \atop k}\right\}_{3}$ A225468 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	$\left\{{n \atop k}\right\}_{4}$ A225469 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\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 $\sum _{k}a(n,k)b(k,j)(-1)^{n-k}=[j=n].$ We call the inverse numbers the Stirling-Frobenius cycle numbers.

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

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

${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{1}$ A132393 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	${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{2}$ A028338 and A039757 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
${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{3}$ A225470 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	${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{4}$ A225471 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\geq 1$ as

${\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\wedge }=m^{k}{\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}.$

$\left\{{n \atop k}\right\}_{1}^{\wedge }$ A048993 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	$\left\{{n \atop k}\right\}_{2}^{\wedge }$ A154537 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
$\left\{{n \atop k}\right\}_{3}^{\wedge }$ A225466 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	$\left\{{n \atop k}\right\}_{4}^{\wedge }$ A225467 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 ${\begin{Bmatrix}n\\k\end{Bmatrix}}_{m-1}^{\wedge }$ with the left hand side of triangle ${\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:

${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}^{\wedge }=m^{k}\,{\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}$

${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{1}^{\wedge }$ A132393 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	${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{2}^{\wedge }$ A161198 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
${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{3}^{\wedge }$ A225477 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	${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{4}^{\wedge }$ A225478 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

${\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\circ }=k!{\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}.$

$\left\{{n \atop k}\right\}_{1}^{\circ }$ A131689 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

$\left\{{n \atop k}\right\}_{2}^{\circ }$ A145901 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

$\left\{{n \atop k}\right\}_{3}^{\circ }$ A225472 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

$\left\{{n \atop k}\right\}_{4}^{\circ }$ A225473 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

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

${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{1}^{\circ }$ A225479  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

${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{2}^{\circ }$ A225475  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

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

${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{1}^{\otimes }$ A225479 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

${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{2}^{\otimes }$ A225474 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

${\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}}.$

$\left\{{n \atop k}\right\}_{1}^{\otimes }$ A131689 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

$\left\{{n \atop k}\right\}_{2}^{\otimes }$ A225476 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>n{\text{ or }}k<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

SF-S

${\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

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

A132393

A028338

A225470

A225471

SF-SS

${\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\wedge }=m^{k}\,{\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}$

A048993

A154537

A225466

A225467

SF-CS

${\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}^{\wedge }=m^{k}\,{\begin{vmatrix}\,n\,\\\,k\,\end{vmatrix}}_{m}$

A132393

A161198

A225477

A225478

SF-SO

${\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}^{\circ }=k!\,{\begin{Bmatrix}n\\k\end{Bmatrix}}_{m}$

A131689

A145901

A225472

A225473

SF-CO

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

A225479

A225475

SF-CSO

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

A225479

A225474

SF-SSO

${\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)