1
$\begingroup$

To find the number of ways to place positive integers into an array of size $N$ such that the product of the numbers is $K$. So the problem boils down to finding the numbers of ways to place the prime factors of $k$ into $N$ slots. For Example, if $N = 2$ and $K = 24$

Prime Factors of $24$: $2^3 \times 3^1$

So we have to find the number of ways of placing three 2's and one 3 in 2 slots. I saw the problem in the discussion forums and came to know that this can be done with the stars and bars concept. It is stated that the number of ways of placing three 2's and one 3 in 2 slots is equal to placing three 2's in 2 slots multiplied by placing one 3 in 2 slots.

placing three 2's in 2 slots (stars and bars) = $\binom{3+2-1}{3}$ = $\binom{4}{3}$

placing one 3 in 2 slots (stars and bars) = $\binom{1+2-1}{1}$ = $\binom{2}{1}$

So the total number of ways = $ \binom{4}{3} $ * $\binom{2}{1}$ = 4 * 2 = 8

The parts which I didn't understand is

  1. how the number of ways of placing three 2's and one 3 in 2 slots is equal to placing three 2's in 2 slots multiplied by placing one 3 in 2 slots
  2. why can't we apply the stars and bars concept to all of the prime factors like placing 4 (three 2's and one 3) into 2 slots.
$\endgroup$
0
$\begingroup$
  1. Because these choices are independent. You can divide the three twos as either $(2\times 2\times 2,-)$, $(2\times 2, 2)$, $(2, 2\times 2)$ or $(-, 2\times2\times 2)$. You can put the three either as $(3,-)$ or $(-,3)$. Now you can take any of the options for twos and combine it with any of the options for three, to get $4\times 2$ possibilities. E.g., taking the first option for each gives $(2\times2\times 2\times 3,1)$ (since there are no factors of $2$ or $3$ in the second slot), whereas taking the third and second gives $(2,2\times2\times3)$.

  2. If you place four things in two slots, there are $5$ ways to do this, but this doesn't distinguish which things go where, just how many. So splitting as three things in the first slot is just counted as one way by this method, but actually this could correspond to $(2\times2\times2, 3)$ or $(2\times 2\times3,2)$, which are different.

$\endgroup$
3
  • $\begingroup$ So by point 2., you mean to say that order is preserved so all ways won't get counted? $\endgroup$
    – Turtle
    Jan 25 '21 at 13:34
  • $\begingroup$ @Turtle Not all ways are counted because the formula assumes you are trying to distribute identical objects, but here the objects are not all the same (one is special, so you need to know where that one goes). $\endgroup$ Jan 25 '21 at 13:37
  • $\begingroup$ Thank you for the answer. $\endgroup$
    – Turtle
    Jan 25 '21 at 13:39

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.