User:Peter Luschny/Multifactorials

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

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\leq k\leq 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 → F_m,j(n) found in the database.

Subsequences of multifactorials.

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.

F_m,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 F_4,0(n) "quadruple factorial numbers". Looking at our definition F_4,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\leq k\leq 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 = 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.

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 F_m,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.

M_m(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\leq k\leq 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 = 0	m  = 1	m  = 2	m = 3	m = 4
	n°	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\leq k\leq mn}{k{\bmod {m}}=j}}k=m^{n}{\frac {\Gamma \left(n+{\frac {j}{m}}\right)}{\Gamma \left({\frac {j}{m}}\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.)

A_m,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.

$n^{(+m)}=\sum \limits _{\stackrel {1\leq k\leq n}{k{\bmod {m}}=n{\bmod {m}}}}k$

	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 F_m,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\leq k\leq 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
-P_k(n) for k < 0; P_k(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).