4
$\begingroup$

Consider the number $n!$ for some integer $n$

In how many ways can $n!$ be expressed as

$$a_1!a_2!\cdots a_n!$$

for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as $\Omega(n)$

Consider the value of $10!$

$$10! = 7!6!$$ $$10! = 7!5!3!$$

Thus we know that $\Omega(10)\ge 3$

We note that if a number can be expressed as

$$n! = w!(q!)!$$

for integers $w,q$ then another factorization arises naturally as:

$$n! = w!(q!-1)!q!$$

such as with the case above

We also note that given a composite number $Q!$ in order for it to be factorized $L! | L > P_\max$ must be in the factorization where $P_\max$ is the largest prime less than $Q$

Naturally this implies to us that $\Omega(n)$ for $n \in \ \lbrace \text{Primes} \rbrace = 1$

$\endgroup$
  • $\begingroup$ Surelly when you say $n! = w!(q!)!$ then the other factorization is $n! = w!(q-1)!!q!$, right? $\endgroup$ – Darth Geek Jul 24 '14 at 17:33
  • $\begingroup$ Ah yes good catch, what I mean to say is $w!(q!-1)!q!$ $\endgroup$ – frogeyedpeas Jul 24 '14 at 17:35
  • $\begingroup$ Ah, true. I guess I derped it too. $\endgroup$ – Darth Geek Jul 24 '14 at 17:36
  • 1
    $\begingroup$ Also, you say that if $Q$ is a composite, then $Q!$ must have $P_\max !$ in it's factorization. I see that $\max \lbrace a_i\rbrace_{1\leq i\leq n} \geq P_\max$. But I don't see why that must be an equality. In fact, for $n = 120!$ we have $n = 119!5!$ but $119$ is not prime. $\endgroup$ – Darth Geek Jul 24 '14 at 17:41
  • 1
    $\begingroup$ The OEIS sequence oeis.org/A034878 seems relevant here. $\endgroup$ – Barry Cipra Jul 24 '14 at 18:30
2
$\begingroup$

Let $\omega(n)$ be the amount of ways you can express $n$ as $a_0!a_1!\cdots a_k!$. Then obviously $\omega(n!) = \Omega(n)$. Since $n\geq \max \lbrace a_i\rbrace_{1\leq i\leq n} \geq P_\max$.

Then $\max\lbrace a_i\rbrace$ can be any number, $k$, between $P_\max$ and $n$.

For each of those numbers, we have $n! = (k!)\cdot(\frac{n!}{k!})$ so we need to express $\frac{n!}{k!}$ as a product of factorials. We have $\omega\left(\frac{n!}{k!}\right)$ ways to do that (note that for cerain $k$'s, $\omega = 0$).

Therefore we have a "recursive" formula for $\Omega (n)$ in terms of $\omega$:

$$\omega(n!) = \Omega (n) = \sum_{k=P_\max}^{n!}\omega\left(\frac{n!}{k!}\right) $$.

$\endgroup$
  • $\begingroup$ explain the upper bound, I'm not seeing why it must be true $\endgroup$ – frogeyedpeas Jul 24 '14 at 19:48
  • $\begingroup$ @frogeyedpeas It turns out it's not an upper bound. It's in fact an equality. I edited my answer to explain it. $\endgroup$ – Darth Geek Jul 24 '14 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.