This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/StirlingFrobeniusNumbers

From OeisWiki

Jump to: navigation, search

The Stirling-Frobenius
Numbers

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

Concerned with sequences: A225466A225479

Contents

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

 \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 xj of An,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 \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

a(n,k)b(k,j)( − 1)nk = [j = n].
k

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 \ge 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:

Sm(0,0) = 1;
Sm(n,k) = 0 if k > n or k < 0;
Sm(n,k) = αm(n,k)Sm(n − 1,k − 1) + βm(n,k)Sm(n − 1,k).

Depending on the type of the numbers αm(n,k) and βm(n,k) are defined as shown in the table below.

Type αm(n,k) β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)
Personal tools