Multifactorial

The factorial of an integer n is the product of the positive integers up to n.

The double factorial of an even (odd) integer n is the product of the positive even (odd) integers up to n. For example,

8!! = 8 × 6 × 4 × 2

and

9!! = 9 × 7 × 5 × 3 × 1.

Double factorials come up fairly often, and sometimes triple, quadruple, or higher multifactorials do too.

In general, the k-factorial of n is the product of the positive integers up to n that are congruent to n mod k. Here’s how you might implement k-factorials in Python.

    from operator import mul
    from functools import reduce

    def multifactorial(n, k):
        return reduce(mul, [i for i in range(1, n+1) if (n-i)%k == 0], 1)

Update: As pointed out in the comments, multifactorial could be implemented more succinctly as

    def multifactorial(n, k):
        return reduce(mul, range(n, 0, -k), 1)

Factorial notation is a little awkward, and multifactorial notation is even more awkward. Someone seeing n!! for the first time might reasonably assume it means (n!)!, but it does not.

Adding exclamation points works, albeit awkwardly, for specific values of k, but not for variable numbers of k. One way I’ve seen to express k-factorials for variable k is to add a subscript (k) to the factorial:

n!_{(k)} \equiv n\underbrace{! \cdots !}_\text{$k$ times}

I’ve also seen the subscript on the exclamation point written as a superscript instead.

I’d like to suggest a different notation: Πk. by analogy with the Π function.

\Pi_k(n) = \prod_{\stackrel{1 \,\leq \,i \leq \,n}{i \,\equiv\, n \pmod{k}}} i

When k ≡ 1 the condition in (mod k) always holds, and we have factorial, i.e.

Π1(n) = Π(n) = n!.

One downside of this notation is that while the function Π is defined for all complex numbers (aside from singularities at negative integers) the function Πk is only defined for positive integer arguments. Still, in my opinion, this is less awkward than the alternatives I’ve seen.

By the way, the term “double factorial” seems backward. Maybe it should have been “half factorial” because you’re multiplying half as many numbers together, not twice as many. “Multifactorial” in general seems like an unfortunate name. Subfactorial might have been better, but unfortunately that name means something else.

I understand why someone may have come up with the idea of using two exclamation points for what we call double factorial; it would be hard to draw half an exclamation point. An advantage of the notation suggested here is that it suggests that there’s a variation on factorial somehow associated with k, but there’s no implication of multiplying or dividing by k.

Adding “mod k” as a subscript would be even more explicit than a subscript k. Someone who hadn’t seen

Πmod k (n)

before might be able to figure out what it means; I think they would at least easily remember what it means once told. And the presence of “mod” might suggest to the reader that the argument needs to be an integer.

4 thoughts on “Multifactorial

  1. Just being ‘that’ guy about the code.

    There’s a typo (intertools should be itertools)

    And I think more pythonic would be

    [i for i in range(n,0,-k)]

    and if I remember how iterators work in python even just

    range(n,0,-k) should work.

  2. Oops, and I forgot, reduce is now in functools (silly python). So here’s the complete code:

    from operator import mul
    from functools import reduce

    def multifactorial(n, k):
    return reduce(mul, range(n,0,-k), 1)

    for i in range(1,10):
    print([multifactorial(i, k) for k in range(1,4)])

  3. “By the way, the term “double factorial” seems backward. Maybe it should have been “half factorial”…”

    You’re right. We should discuss this at the bimonthly meeting.

  4. Is there a form of factorial that gets the product of only the first n numbers? For example 20!3 would multiply 20 * 19 * 18. When doing permutations in which r < n, the answer could be a simpler n!r instead of the nPr formula.

Comments are closed.