This site is supported by donations to The OEIS Foundation.
User:Peter Luschny/Multifactorials
Contents
- 1 Multifactorials
- 1.1 Definition.
- 1.2 Subsequences of multifactorials.
- 1.3 Sequences of multifactorials.
- 1.4 A new type of multifactorials.
- 1.5 Multigammas.
- 1.6 Summary I.
- 1.7 Was dem * recht ist, ist dem + billig.
- 1.8 Summary II.
- 1.9 Polygonal Numbers.
- 1.10 The double swinging factorial.
- 1.11 Related divisibility properties of the swinging factorial.
KEYWORDS: Factorial, multifactorials, modular factorials, double additorial, m-additorial, m-termial.
Concerned with sequences:
(m,j) | Multiplicative | Additive |
(1,0) | A000142 | A000217 |
(2,0) | A000165 | A002378 |
(2,1) | A001147 | A000290 |
(3,0) | A032031 | A045943 |
(3,1) | A007559 | A000326 |
(3,2) | A008544 | A005449 |
(4,0) | A047053 | A046092 |
(4,1) | A007696 | A000384 |
(4,2) | A001813 | A001105 |
(4,3) | A008545 | A014105 |
1 | A000142 | A000217 |
2 | A006882 | A002620 |
3 | A007661 | A001840 |
4 | A007662 | A130519 |
The notation for multifactorials n!! or n!!! or even n!!!! can be very confusing. Moreover, the definitions are often given as a bunch of formulas which more hide than explain the meaning of the multifactorial. However, a simple explicit mathematical definition can help.
The following definition covers all the special cases of multifactorials and could replace the more or less mysterious formulas which are often given as definitions.
Or in Maple speak:
F := proc(m, j, n) local k; mul(k, k = select(k -> k mod m = j, [$1 .. m*n])) end:
Now fix m and j. The table below shows some of the most important sequences n → Fm,j(n) found in the database.
Fm,j(n) | j = 0 | j = 1 | j = 2 | j = 3 |
k mod m = 0 | k mod m = 1 | k mod m = 2 | k mod m = 3 | |
m = 0 | A000012 | A000012 | A000012 | A000012 |
m = 1 | A000142 | A000012 | A000012 | A000012 |
m = 2 | A000165 | A001147 | A000012 | A000012 |
m = 3 | A032031 | A007559 | A008544 | A000012 |
m = 4 | A047053 | A007696 | A001813 | A008545 |
Let us give these sequences a name.
Fm,j(n) is the product of the positive integers k ≤ mn such that k mod m = j.
Now let us compare this with the actual names of these sequences found in the database:
F1,0(n) | A000142 | n! = 1*2*3*4*...*n |
F2,0(n) | A000165 | (2n)!! = 2^n*n! |
F2,1(n) | A001147 | (2n-1)!! = 1.3.5....(2n-1) |
F3,0(n) | A032031 | (3n)!!!=3^n*n! |
F3,1(n) | A007559 | (3*n-2)!!! with leading 1 added |
F3,2(n) | A008544 | product[ k=0..n-1 ] (3*k+2) |
F4,0(n) | A047053 | quadruple factorial numbers |
F4,1(n) | A007696 | (4*n+1)(!^4) = product[ k=0..n-1 ] (4*k+1) |
F4,2(n) | A001813 | (2n)!/n! |
F4,3(n) | A008545 | product[ k=0..n-1 ] (4*k+3) |
A bewildering collection. Typical question: "Should it not be "n!! = 1.3.5....(2n-1)"?
In the list above there are also names which are plain wrong like calling F4,0(n) "quadruple factorial numbers". Looking at our definition F4,0(n) is the product of the positive integers k ≤ 4n which are multiples of 4: 4, 4*8, 4*8*12, 4*8*12*16. And the case n = 0: As there are no positive integers less or equal 0 which are multiples of 4 the product is 1. Leading 1 included. However, these are not the 'quadruple factorial numbers'. To get the real multifactorials (which are A007662 in the quadruple case) we need a further step.
Zipping the rows in the above table up to the main diagonal gives the multifactorials, which is a function of two parameters, n and m. The parameter m is not given explicit; instead it is mangled into the notation, writing !(m) for !!..! (! m times).
n!(m) is the product of the positive integers k ≤ n such that k mod m = n mod m.
MF := (n,m) -> mul(k,k=select(k-> k mod m = n mod m,[$1..n])):
The multifactorials can be computed by a simple recursion.
f := (n,k) -> `if`(n<=0,1,n*f(n-k,k));
m = 0 | m = 1 | m = 2 | m = 3 | m = 4 | |
n° | n! | n!! | n!!! | n!!!! | |
n!(m) | A000012 | A000142 | A006882 | A007661 | A007662 |
Our approach demonstrates how the definition of multifactorials can be layered on the general three parameter definition which includes all the special cases ab initio without using a more than in one way misinterpretative notation and replacing a formula/notation zoo by a single definition.
There is also a second benefit of making the above definition the cornerstone of our exposition: it hints to a new type of multifactorials. The idea is a standard one: If you have three parameters try to express one of them by the two others. In the case of two parameters it is an often seen exercise to let one parameter be a multiple of the other. For instance consider the binomial C(n, k). Then C(2n, n) is the important central binomial. In similar vein we now replace in Fm,j(n) the parameter 'j' by 'n mod m'.
for m from 1 to 4 do seq(F(n, m, n mod m), n = 0..7) od; 1, 1, 2, 6, 24, 120, 720, 5040 1, 1, 8, 15, 384, 945, 46080, 135135 1, 1, 10, 162, 280, 12320, 524880, 1106560 1, 1, 12, 231, 6144, 9945, 665280, 40883535
And voilà. We have 'discovered' three new sequences which can be seen as generalizations of the factorial. Clearly the significance of these sequences is still to be found. But I am quite optimistic that meaningful combinatorial interpretations will be discovered.
In the case m = 2 we have:
a(2*n) =A006882(4*n) =4^n*Gamma(2*n+1) a(2*n+1)=A001147(2*n+1)=4^n*Gamma(2*n+3/2)/sqrt(Pi/4) In the case m = 3 we have:
a(3*n) =A032031(3*n) =3^(3*n) *Gamma(3*n+1) a(3*n-1)=A008544(3*n-1)=3^(3*n-1) *Gamma(3*n-1/3)/Gamma(2/3) a(3*n+1)=A007559(3*n+1)=3^(3*n+3/2)*Gamma(3*n+4/3)*Gamma(2/3)/(2*Pi)
Just to give the finishing touch we also include the case m = 0 by making use of the convention that the product over an empty set is 1 (which also avoids the indeterminate case 0 mod 0).
And we have to find a name. Hugo Pfoertner suggested the name m-modular factorial.
Mm(n) is the product of the positive integers k ≤ mn such that k mod m = n mod m.
M := proc(n, m) local k; mul(k, k = select(k -> k mod m = n mod m, [$1 .. m*n])) end:
m = 0 | m = 1 | m = 2 | m = 3 | m = 4 | |
n° | n' | n' ' | n' ' ' | n' ' ' ' | |
A000012 | A000142 | A190901 | A190903 | A000000 |
The Handbookof Mathematical Functions has been on the desktop of every working mathematician in the last 60 years. A page every reader has looked at least once was page 255, the mathematical properties of the Gamma function. There are five integer sequences:
AS6110 := n -> 4^n*GAMMA(n+1/4)/GAMMA(1/4): AS6111 := n -> 3^n*GAMMA(n+1/3)/GAMMA(1/3): AS6112 := n -> 2^n*GAMMA(n+1/2)/GAMMA(1/2): AS6113 := n -> 3^n*GAMMA(n+2/3)/GAMMA(2/3): AS6114 := n -> 4^n*GAMMA(n+3/4)/GAMMA(3/4): AS6110: 1, 1, 5, 45, 585, 9945, 208845 [A007696] AS6111: 1, 1, 4, 28, 280, 3640, 58240 [A007559] AS6112: 1, 1, 3, 15, 105, 945, 10395 [A001147] AS6113: 1, 2, 10, 80, 880, 12320, 209440 [A008544] AS6114: 1, 3, 21, 231, 3465, 65835, 1514205 [A008545]
This gives a second characterization of the sequences cross-referenced in the triangle above. However, note that the HMF misses A001813 which is
A001813 := n -> 4^n*GAMMA(n+2/4)/GAMMA(2/4): 1, 2, 12, 120, 1680, 30240, 665280
In a similar vein this list could be continued:
A101485 := n -> 2^(2*n)*GAMMA(2*n+1/2)/GAMMA(1/2): A067624 := n -> 2^(2*n)*GAMMA(2*n+2/2)/GAMMA(2/2): 1, 3, 105, 10395, 2027025, 654729075 1, 8, 384, 46080, 10321920, 3715891200
In other words:
A067624(n) = 4^n*(2*n)!
This formula would be a nice name, wouldn't it? But in fact the name of A067624 is
sqrt((1+cos(x))/2) = sum(n>=0,(-1)^n*x^(2*n)/a(n)).
I do not think this name is helpful for the average reader browsing the database. Why not put such formulas where they belong to: the formula section? But let us come back to our multigammas. Next in the row (case 3) is
a := n -> 3^(3*n)*GAMMA(3*n+1/3)/GAMMA(1/3): a := n -> 3^(3*n)*GAMMA(3*n+2/3)/GAMMA(2/3): a := n -> 3^(3*n)*GAMMA(3*n+3/3)/GAMMA(3/3): 1, 28, 58240, 608608000, 17961239296000 1, 80, 209440, 2504902400, 81359229952000 1, 162, 524880, 7142567040, 254561089305600
None of these sequences are in the database.
Putting things together we see that there is a single central equation behind most of the sequences which we have considered until now:
For and and |
This is the German equivalent for "What's sauce for the goose is sauce for the gander"
-- with obvious substitutes. So what are the additive equivalents of the
multifactorials? And how are they called?
Let us agree to call them in this
blog post 'm-addorials' replacing 'fact' from 'factor' by 'add' from 'addend'.
(If you have a better idea for naming these creatures please comment on the
discussion page.)
Am,j(n) is the sum of the positive integers k ≤ mn such that k mod m = j.
Am,j(n) | j = 0 | j = 1 | j = 2 | j = 3 |
k mod m = 0 | k mod m = 1 | k mod m = 2 | k mod m = 3 | |
m = 0 | A000004 | A000004 | A000004 | A000004 |
m = 1 | A000217 | A000004 | A000004 | A000004 |
m = 2 | A002378 | A000290 | A000004 | A000004 |
m = 3 | A045943 | A000326 | A005449 | A000004 |
m = 4 | A046092 | A000384 | A001105 | A014105 |
Again let us compare this with the actual names of these sequences found in the database:
A1,0(n) | A000217 | Triangular numbers: C(n+1,2) |
A2,0(n) | A002378 | Oblong (or promic, pronic, or heteromecic) numbers: n(n+1) |
A2,1(n) | A000290 | The squares: n^2 |
A3,0(n) | A045943 | Triangular matchstick numbers: 3n(n+1)/2 |
A3,1(n) | A000326 | Pentagonal numbers: n(3n-1)/2 |
A3,2(n) | A005449 | Second pentagonal numbers: n(3n+1)/2 |
A4,0(n) | A046092 | 2n(n+1) |
A4,1(n) | A000384 | Hexagonal numbers: n(2n-1) |
A4,2(n) | A001105 | 2 n^2 |
A4,3(n) | A014105 | Second hexagonal numbers: n(2n+1) |
As mangled notation - aka 'name decoration' - no longer frightens us we will write +(m) for ++..+ (+ m times).
n(+m) is the sum of the positive integers k ≤ n such that k mod m = n mod m.
m = 0 | m = 1 | m = 2 | m = 3 | m = 4 | |
n° | n+ | n++ | n+++ | n++++ | |
n(+m) | A000004 | A000217 | A002620 | A001840 | A130519 |
And their OEIS names:
n+ | A000217 | Triangular numbers: C(n+1,2) |
n++ | A002620 | Quarter-squares: floor(n/2)ceiling(n/2) |
n+++ | A001840 | Expansion of x/((1-x)^2(1-x^3)) |
n++++ | A130519 | Sum {0<=k<=n, floor(k/4)} |
Thus we see that the triangular numbers are the additive equivalents of the factorial numbers and the quarter-squares the equivalents of the double factorials. From our point of view A001840, the triple additorial numbers, are in need of a better name. Perhaps 'triple additorial numbers'?
The double additorial of a positive integer n is the sum of the positive integers ≤ n that have the same parity as n. This is a much better definition for A002620 compared to the current one involving 'floor' and 'ceiling' which are no genuine operations on the integers. In fact a conceptual cleanup of the database would eliminate all occurrences of 'floor' and 'ceil' in the definitions (provided this is feasible of course). After all the name of the encyclopedia is not The Encyclopedia of Truncated Floats.
But the real interesting question now is: Is there also a counterpart to the formula in summary I which related the product Fm,j(n) to the Gamma function? The answer is yes.
For and and |
This gives simultaneously an interpretation for all the polygonal numbers in the list above, triangular, square, pentagonal, hexagonal, heptagonal and many others, both for the 'first' and the 'second' flavor.
As I have not seen this formula before I would appreciate any pointer to the literature; please leave a comment on the discussion page.
The polygonal numbers are defined as
Although it is not clear what a polygon for k < 3 is, the polygonal numbers are defined for all integer k.
k\n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
-5 | 0 | −1 | 5 | 18 | 38 | 65 | 99 | |
-4 | 0 | −1 | 4 | 15 | 32 | 55 | 84 | |
-3 | 0 | −1 | 3 | 12 | 26 | 45 | 69 | |
-2 | 0 | −1 | 2 | 9 | 20 | 35 | 54 | A014107 |
-1 | 0 | −1 | 1 | 6 | 14 | 25 | 39 | A095794 |
0 | 0 | 1 | 0 | −3 | −8 | −15 | −24 |
A005563 A013648 |
1 | 0 | 1 | 1 | 0 | −2 | −5 | −9 |
A000096 A080956 |
2 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | A001477 |
3 | 0 | 1 | 3 | 6 | 10 | 15 | 21 | A000217, A089594 |
4 | 0 | 1 | 4 | 9 | 16 | 25 | 36 | A000290 A162395 |
5 | 0 | 1 | 5 | 12 | 22 | 35 | 51 | A000326 |
The double swinging factorial is defined recursively.
s := n -> `if`(n <= 0, 1, s(n-2) * `if`(n mod 2 = 0, 4/n, n));
The most important property of the double swinging factorial is
For odd indices the double factorial and the double swinging factorial coincide for integer values.
Let σ(n) denote the number of 1's in the representation of n in base 2. For even indices the double swinging factorial is a rational number with
Double swinging factorials can be expressed by factorials as
For σ(n) see A000120, for 2σ(n) see Gould's sequence A001316, for 2σ(n)-n n! see A049606 and for (2n-1)≀≀ see A001147.
A060632 GCD(n≀, 2^n)
A190906 GCD(n≀, 3^n)
A000000 GCD(n≀, 5^n)
Observe the interesting pattern below, generated by
A3 := n -> igcd(n!/iquo(n,2)!^2, 3^n): seq(A3(3*n), n=0..3^2-1); A5 := n -> igcd(n!/iquo(n,2)!^2, 5^n): seq(A5(5*n), n=0..5^2-1); A7 := n -> igcd(n!/iquo(n,2)!^2, 7^n): seq(A7(7*n), n=0..7^2-1);
1,3,1,9,3,9,1,3,1 1,5,1,5,1,25,5,25,5,25,1,5,1,5,1,25,5,25,5,25,1,5,1,5,1 1,7,1,7,1,7,1,49,7,49,7,49,7,49,1,7,1,7,1,7,1,49,7,49,7,.. ..49,7,49,1,7,1,7,1,7,1,49,7,49,7,49,7,49,1,7,1,7,1,7,1
The case m = 3 was published as A190906. Here you can see the graph of the (beginning of the) pattern. It is also nice to listen to the sequence: play. I prefer the Acoustic Grand Piano at a rate of 200 notes/min. :-)
Any explanation of this pattern is welcome (please use the discussion page).