Tessellate S.T.E.M.S - Mathematics - School - Set 3 - Problem 3

Probability Level 3

$n = p_1^{a_1}p_2^{a_2} ... p_r^{a_r}$ , where $p_i$ are distinct primes and $a_i \in \mathbb{Z}_{\geq 0}$ .

Find the number of ordered $k$ -tuples $(c_1,...,c_k)$ such that $\displaystyle \prod_{i=1}^k c_i = n$

This problem is a part of Tessellate S.T.E.M.S.

\prod_{i=1}^r \dbinom{a_i+k-1}{k-1}

\prod_{i=1}^k \dbinom{a_i + k -1}{r-1}

\prod_{i=1}^r \dbinom{a_i + r -1}{k-1}

\prod_{i=1}^r \dbinom{a_i + k -1}{r-1}

1 solution

Patrick Corn
Jan 9, 2018

Look at the vector ${\bf v} = \begin{pmatrix} a_1\\a_2\\\vdots\\a_r \end{pmatrix}.$ Representing $n$ as the product of $k$ positive integers (the problem should specify that the $c_i$ are positive) is the same as writing $\bf v$ as the sum of $k$ vectors whose entries are nonnegative integers. We can do this coordinate by coordinate. The number of ways of writing $a_i$ as a sum of $k$ nonnegative integers is $\binom{a_i+k-1}{k-1}$ --this is often called stars and bars --so the number of ways of writing $\bf v$ as a sum of $k$ vectors whose entries are nonnegative integers is the product of these.

Can you explain this in a more simpler way cuz I am not well up in the subject of VECTORS

Anu Radha - 3 years, 4 months ago

You don't need to think about vectors. You can just say: how many ways are there to write $a_1$ as the sum of $k$ nonnegative integers (the exponents of $p_1$ in the $c_k$ )? Stars and bars says $\binom{a_1+k-1}{k-1}.$ Then how many ways are there to write $a_2$ as the sum of $k$ nonnegative integers? And so on.

Patrick Corn - 3 years, 4 months ago

Tessellate S.T.E.M.S - Mathematics - School - Set 3 - Problem 3

1 solution

0 pending reports