Deduce $\tau _k (p^e) = {{e+k-1}\choose{k-2}}.$

26 Views Asked by At

Let $\tau_k(n)$ be the number of ordered factorizations of $n$ as the product of exactly $k$ positive integers so that $\tau _1(n)=1$ and $\tau _2(n) = \tau (n)$. For fixed $k$, show $\tau _k (p^e) < (e+1)^k$ to deduce $$\tau _k (p^e) = {{e+k-1}\choose{k-2}}.$$

First, I feel that the deduction to be made is $$\tau _k (p^e) = {{e+k-1}\choose{k-1}},$$ not $$\tau _k (p^e) = {{e+k-1}\choose{k-2}},$$ is this true? If not, why would what I suggested not hold? Also, it follows that $\tau_k (n)$ is multiplicative, which allows us to consider the case of prime powers, but I am not sure how the rest of the proof would follow from this. I showed that $\tau (n) \ll n^{\delta}$ for any $\delta >0$. The proof of this follows by considering $$f(n) = \frac{\tau (n)}{n^{\delta}}$$ and noting $f$ is multiplicative, but I am not sure if this helps much with the results we want to prove.

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, your objection is valid.

If $p$ is prime, and $e$ is a nonnegative integer, an ordered factorization of $p^e$ into $k$ positive integer factors has the form $$(p^{x_1})\cdots(p^{x_k})$$ where $x_1,...,x_k$ are nonnegative integers such that $$x_1 + \cdots + x_k = e$$ hence, by the stars-and-bars formula, it follows that $$\tau _k (p^e) = {{e+k-1}\choose{k-1}}$$