0
$\begingroup$

In case of permutation with repetition, we have formula = $n^r$

How do you decide which thing will be $n$ and which will be $r$?

Like in this question:

Your mother-in-law buys 1000 small gifts to give to relatives for Christmas. Each of the 1000 things is different. There are 25 relatives to give gifts to. How many ways are there to distribute the gifts?

The correct answer is $25^{1000}$

But why can't it be $1000^{25}$?

Please help me if you know any trick or any way to determine what is $n$ in the question and what is $r$.

$\endgroup$
8
  • 2
    $\begingroup$ You can give every gift to one of the 25 people, this gives you 25 options per gift and that choice has to be made 1000 times. Meaning the total number of ways to distribute them is $25\cdot25\cdot25\dots25 = 25^{1000}$. $\endgroup$ Apr 2 at 23:25
  • 2
    $\begingroup$ $n$ is the number of choices, $r$ is the number of times you have to make that choice $\endgroup$ Apr 2 at 23:27
  • 1
    $\begingroup$ Can't we think like this? Each person has an option of $1000$ gifts then as we have $25$ people so total number of ways is $1000 \cdot 1000 \cdot 1000 \dots 1000 = 1000^{25}$. $\endgroup$
    – Raj Ishu
    Apr 2 at 23:29
  • 5
    $\begingroup$ Regardless of the details here, I often find it useful to do the same problem with smaller numbers. If there's only one present, then you have $25$ choices of recipient. If there's only one recipient, there's only $1$ way to satisfy the rules (I'm guessing). $\endgroup$
    – lulu
    Apr 2 at 23:32
  • 2
    $\begingroup$ $1000^{25}$ is like the $25$ people go into a warehouse with $1000$ types of gifts, then each choose a gift and leave. Different people may choose the same type of gift, and some types of gift may be chosen by none. $\endgroup$
    – peterwhy
    Apr 3 at 0:06

1 Answer 1

3
$\begingroup$

Suppose you have an action comprises of $r$ smaller independent actions, each has $n$ possible ways to do, then the total number of ways to do that action is $N = n^r$

So $25^{1000}$ is the number of ways to gift 1000 gifts to 25 people, each gift is independently given to single person. A person may have more than one gift.

$1000^{25}$ is the number of ways for 25 people to independently choose a gift out of 1000 gifts. Each person can only choose one gift. A gift may be chosen by more than one person

Since the question asked for the number of ways to distribute gifts, so we expect each gift is given to a single person, hence we choose the former formula

$\endgroup$
2
  • $\begingroup$ what if in second case there is no restriction of 1 person can only choose 1 gift then what will be the answer? $\endgroup$
    – Raj Ishu
    Apr 8 at 3:13
  • $\begingroup$ @RajIshu then for any pair of gift-receiver, there are two possibilities: either that is chosen, or not, which is independent of all other pairs. There are $1000 \cdot 25 = 25000$ such independent pairs, therefore there are $2^{25000}$ possibilities $\endgroup$
    – ioveri
    Apr 8 at 3:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .