How many functions are there from $\{50, 51, 52, 53, 54\}$ to $\{50, 51, 52, 53, 54\}$ such that for all $x, f(x) \geq x?$

Question

I would think that 50 is the same as 50, 51 is larger or equal to 50 and 51, 52 is larger or equal to 52, 51, 50, etc. This eventually gives 1+2+3+4+5. Is this correct? My friend says you're supposed to multiply 5,4,3,2,1 together but that seems very wrong to me logically. Please help?

Answer 1

You are indeed supposed to multiply. The Rule of Product, also called the multiplication principle at times, can be paraphrased to say the following:

When you wish to count how many possible outcomes a scenario has, if you can describe every outcome via a sequence of choices such that:

• every outcome is described exactly once
• The number of choices available at each step in the sequence does not depend on the specific choices made in previous steps (though the choices available may change so long as the number doesn't change)

then the total number of outcomes is equal to the product of the number of choices available at each step.

Here, we approach via multiplication principle.

• Pick the value of $f(50)$ (five choices, it could be that $f(50)$ is equal to any one of $50,51,52,53,54$)
• Pick the value of $f(51)$ (four choices, it could be that $f(51)$ is equal to any one of $51,52,53,54$)
• $\vdots$
• Pick the value of $f(54)$ (only one choices, it must be $f(54)=54$)

Multiplying we have $5\cdot 4\cdot 3\cdot 2\cdot 1$ total outcomes.

---

The scenario in which you would add is the Rule of Sum, a.k.a. the addition principle. It states that to count how many possible outcomes a scenario has, if you can split it up (i.e. partition) into two (or more) possibilities where every outcome is contained in exactly one of those possibilities, i.e. there is no overlap and nothing missing, then the total number of outcomes is the sum of the number of outcomes of these smaller cases.