This site is supported by donations to The OEIS Foundation.

User:Peter Luschny/Multifactorials

From OeisWiki

Jump to: navigation, search

Multifactorials

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


Contents

Definition.

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.

F_{m,j}(n) = \prod\limits_{\stackrel {1 \le k \le mn }{k \bmod m = j}} k

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.

Subsequences of multifactorials.

Fm,j(n) j = 0j  = 1j  = 2j = 3
  k mod m = 0k mod m = 1k mod m = 2k 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) A000142n! = 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) A008544product[ k=0..n-1 ] (3*k+2)
F4,0(n) A047053quadruple 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) A008545product[ 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.

Sequences of multifactorials.

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.

n!^{(m)} = \prod\limits_{\stackrel {1 \le k \le n }{k \bmod m = n \bmod m}} k

 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.

 n!^{(k)} = \begin{cases}
1 & \text{if } n \leq 0 \\
n(n-k)!^{(k)} & \text{if } 0 < n
\end{cases}

f := (n,k) -> `if`(n<=0,1,n*f(n-k,k));
     m = 0m  = 1m  = 2m = 3m = 4
  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.

A new type of multifactorials.

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_{m}(n) = \prod\limits_{\stackrel {1 \le k \le mn }{k \bmod m = n \bmod m}} k
M := proc(n, m) local k;
mul(k, k = select(k -> k mod m = n mod m, [$1 .. m*n])) end:
  m = 0m  = 1m  = 2m = 3m = 4
 n'n' ' n' ' 'n' ' ' '
  A000012 A000142 A190901 A190903 A000000

Multigammas.

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.

Summary I.

Putting things together we see that there is a single central equation behind most of the sequences which we have considered until now:

For \scriptstyle m > 1 and \scriptstyle 0 < j < m and \scriptstyle n \geq 0

F_{m,j}(n) = \prod\limits_{\stackrel {1 \le k \le mn }{k \bmod m = j}} k  = m^n \frac{\Gamma\left(n+\frac jm \right)}{\Gamma\left(\frac jm \right)}

Was dem * recht ist, ist dem + billig.

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 = 0j  = 1j  = 2j = 3
  k mod m = 0k mod m = 1k mod m = 2k 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) A000217Triangular numbers: C(n+1,2)
A2,0(n) A002378Oblong (or promic, pronic, or heteromecic) numbers: n(n+1)
A2,1(n) A000290The squares: n^2
A3,0(n) A045943Triangular matchstick numbers: 3n(n+1)/2
A3,1(n) A000326Pentagonal numbers: n(3n-1)/2
A3,2(n) A005449Second pentagonal numbers: n(3n+1)/2
A4,0(n) A0460922n(n+1)
A4,1(n) A000384Hexagonal numbers: n(2n-1)
A4,2(n) A0011052 n^2
A4,3(n) A014105Second 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.

n^{(+m)} = \sum \limits_{\stackrel {1 \le k \le n }{k \bmod m = n \bmod m}} k

     m = 0m  = 1m  = 2m = 3m = 4
  n+ n++  n+++ n++++
n(+m) A000004 A000217 A002620 A001840 A130519

And their OEIS names:

n+ A000217Triangular numbers: C(n+1,2)
n++ A002620Quarter-squares: floor(n/2)ceiling(n/2)
n+++ A001840Expansion of x/((1-x)^2(1-x^3))
n++++ A130519Sum {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.

Summary II.

For \scriptstyle m > 1 and \scriptstyle 0 < j < m and \scriptstyle n \geq 0

A_{m,j}(n) = \sum\limits_{\stackrel {1 \le k \le mn }{k \bmod m = j}} k  = n \left(j + \frac{m(n-1)}{2} \right)

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.

Polygonal Numbers.

The polygonal numbers are defined as

P_k(n) = \sum\limits_{i=1}^n (k-2)i - (k - 3 ).

Although it is not clear what a polygon for k < 3 is, the polygonal numbers are defined for all integer k.

Polygonal Numbers
-Pk(n) for k < 0; Pk(n) for k ≥ 0.
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
A067998 A082562

A131386 A132411
1 0 1 1 0 −2 −5 −9

A000096 A080956
A132337 A161680

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

The double swinging factorial is defined recursively.

 n \wr\wr = \begin{cases}
1 & \text{if } n \leq 0 \\
(n-2)\wr\wr \ n^{[n \text{ odd}]} \left( \frac{4}{n} \right)^{[n \text{ even}]} & \text{if } 0 < n
\end{cases}

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

 n \wr = (n-1)\wr\wr \, n\wr\wr

For odd indices the double factorial and the double swinging factorial coincide for integer values.

 (2n-1) \wr \wr = (2n-1)!!

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

 \text{numerator}[(2n)\wr\wr] = 2^{\sigma(n)},
 \text{denominator}[(2n)\wr\wr] = 2^{\sigma(n)-n}n! \, .

Double swinging factorials can be expressed by factorials as

 (2n) \wr\wr = \frac{2^n}{n!},
 (2n-1)\wr \wr = \frac{(2n)!}{2^n n!},
 (2n-1)\wr \wr (2n) \wr\wr  = \frac{(2n)!}{n!^2}.

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.

Related divisibility properties of the swinging factorial.

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

Personal tools