Permutation Partition Counting

189 Views Asked by At

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$

1

There are 1 best solutions below

2
On BEST ANSWER

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