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
-
are the Stirling subset numbers and the Eulerian numbers defined for integers .
In the following, the parameter is an integer and the value always refers to the classical case. Unsurprisingly, also the case for is contained in OEIS for
some of the triangle sequences.
Subset numbers [SF-S]
The Stirling-Frobenius subset numbers are defined as
-
Here is the coefficient of of , the
generalized
Eulerian polynomial.
The case are the classical Stirling subset numbers (Concrete Mathematics, table 244).
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 |
|
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 |
|
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 |
|
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 , 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
We call the inverse numbers the Stirling-Frobenius cycle numbers.
-
The case are the classical Stirling
cycle numbers (Concrete Mathematics, table 245).
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 |
|
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 |
|
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 |
|
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 as
-
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 |
|
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 |
|
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 |
|
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
with
the left hand side of triangle .
Scaled cycle numbers [SF-CS]
The Stirling-Frobenius cycle numbers have a scaled version, the
scaled Stirling-Frobenius cycle numbers. They are defined as:
-
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 |
|
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 |
|
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 |
|
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
-
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 |
|
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 |
|
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 |
|
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
-
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 |
|
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
-
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 |
|
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
-
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 |
|
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:
-
-
-
Depending on the type of the numbers and are
defined as shown in the table below.
Type |
|
|
SF-S |
|
|
SF-C |
|
|
SF-SS |
|
|
SF-CS |
|
|
SF-SSO |
|
|
SF-CO |
|
|
SF-SO |
|
|
SF-CSO |
|
|
This table amounts to a succinct systematization of the Stirling-Frobenius numbers
and its variants.
Summary
SF-S
-
SF-C
-
SF-SS
-
SF-CS
-
SF-SO
-
SF-CO
-
SF-CSO
-
SF-SSO
-
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)