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).
$ \genfrac\{\}{0pt}{}{n}{k}_1 $ 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
$ \genfrac\{\}{0pt}{}{n}{k}_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
$ \genfrac\{\}{0pt}{}{n}{k}_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
$ \genfrac\{\}{0pt}{}{n}{k}_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 \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).

$ \genfrac | | {0pt}{}{n}{k}_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
$ \genfrac | | {0pt}{}{n}{k}_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
$ \genfrac | | {0pt}{}{n}{k}_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
$ \genfrac | | {0pt}{}{n}{k}_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 \ge 1 $ as

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

$ \genfrac\{\}{0pt}{}{n}{k}_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
$ \genfrac\{\}{0pt}{}{n}{k}_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
$ \genfrac\{\}{0pt}{}{n}{k}_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
$ \genfrac\{\}{0pt}{}{n}{k}_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 $\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 $$

$ \genfrac | | {0pt}{}{n}{k}_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
$ \genfrac | | {0pt}{}{n}{k}_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
$ \genfrac | | {0pt}{}{n}{k}_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
$ \genfrac | | {0pt}{}{n}{k}_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

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 . $$

$ \genfrac\{\}{0pt}{}{n}{k}_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
$ \genfrac\{\}{0pt}{}{n}{k}_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
$ \genfrac\{\}{0pt}{}{n}{k}_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
$ \genfrac\{\}{0pt}{}{n}{k}_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

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

$ \genfrac | | {0pt}{}{n}{k}_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
$ \genfrac | | {0pt}{}{n}{k}_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

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

$ \genfrac | | {0pt}{}{n}{k}_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
$ \genfrac | | {0pt}{}{n}{k}_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

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

$ \genfrac\{\}{0pt}{}{n}{k}_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
$ \genfrac\{\}{0pt}{}{n}{k}_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 \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)