Question regarding number of non decreasing functions

combinatoricsfunctionspermutations

I have a question that requires me to find the number of non decreasing functions $f: A \longrightarrow B$ where $A=\{1,2,3,4,5\}$ and $B = \{-2,-1,0,1,2,3,4,5\}$

I tried doing this by finding the Total number of functions, which according to me is $8^5$. Then, I found the number of decreasing functions to be ${8 \choose 5}$ and there is only one way to order each of those combinations so number of decreasing functions is ${8 \choose 5}$. Correct me if I'm wrong here.

But here's why I don't get the next part, the answer for the number of non decreasing functions isn't $8^5- {8 \choose 5}$

  1. I don't get why this is, shouldn't the total number of functions $-$
    number of decreasing functions $=$ number of non-decreasing
    functions? I need a few counter examples to convince me otherwise and I can't seem to be able to come up with one, any help on this/visualizing it would be appreciated.
  2. The number of decreasing functions I found to be ${8 \choose 5}$, which isn't asked in the question, just something that I calculated. However, the question also does ask for the number of increasing functions $f:A\longrightarrow B$, and that answer is stated as ${8 \choose 5}$, which makes me question whether my number of decreasing functions is valid. A confirmation here would be highly appreciated too.

Thanks in advance! (I know that there is a similar question from 2015, but since I had some trouble understanding the answers, and also had further questions of my own, I decided to repost rather than posting on a ~6 year old thread)

Here's the link to the old question: Number of non-decreasing functions?

Best Answer

$1$ - "Non-decreasing function" does not mean "A function which is not decreasing". It means $\forall i,j \ \ i>j \implies f(i) \geq f(j) $. So, for example your method counts $(1,3,2,4,5)$ as non-decreasing, but it is not.

$2$ - To find the number of decreasing functions, you just pick $5$ elements and order them in the only possible way (since they have to be decreasing). To find the number of increasing functions, you pick $5$ elements and order them in the only possible way again! That is why the answers are the same.

Bonus: To find the number of non-decreasing functions, you have to choose $5$ elements, but this time, repetitions are allowed! So, at the end you are choosing $5$ elements from $8$ elements with repetitions and again you order them in the only possible way. It is clear that you can do this in $\binom{12}{5}$ ways.

Related Question