# Permutation Partition Counting

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$

• Surelly when you say $n! = w!(q!)!$ then the other factorization is $n! = w!(q-1)!!q!$, right? – Darth Geek Jul 24 '14 at 17:33
• Ah yes good catch, what I mean to say is $w!(q!-1)!q!$ – frogeyedpeas Jul 24 '14 at 17:35
• Ah, true. I guess I derped it too. – Darth Geek Jul 24 '14 at 17:36
• 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. – Darth Geek Jul 24 '14 at 17:41
• The OEIS sequence oeis.org/A034878 seems relevant here. – Barry Cipra Jul 24 '14 at 18:30

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