2
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ You should at least link the relevant (old) question :) $\endgroup$ – Benjamin Wang Mar 6 at 7:54
  • $\begingroup$ @BenjaminWang Ok, editing it in! $\endgroup$ – Techie5879 Mar 6 at 7:56
  • $\begingroup$ You are wrong in thinking that the sampling is without replacement, which is what $\binom{8}{5}$ represents. Your query specifies non-decreasing functions rather than strictly increasing functions. This means that you can have two different elements in the domain map to the same element in the range. Therefore, the inelegant pedestrian approach is to assume that there will be $k$ distinct elements in the range, which receive a map : $k \in \{1,2,3,4,5\}.$ You then have to consider each $k$ separately. ...see next comment $\endgroup$ – user2661923 Mar 6 at 8:04
  • $\begingroup$ Note that if (for example), $k = 3$, that could be represented by range-values of either $\{1,1,1,2,3\}$ or $\{1,1,2,2,3\}.$ There may be a more elegant approach, however the approach that I have outlined is industrial-strength guaranteed to get the right enumeration. $\endgroup$ – user2661923 Mar 6 at 8:06
  • $\begingroup$ If I understand correctly, you mean that $\{1,2,3,4,5\} \longrightarrow {1,1,2,3,3}$ could be a mapping (for example)...is that correct? So when I'm subtracting the number of decreasing functions, shouldn't the answer have those cases in them too? And could you clarify my 2nd point? @user2661923 $\endgroup$ – Techie5879 Mar 6 at 8:08
3
$\begingroup$

$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.

$\endgroup$
1
1
$\begingroup$

You are interpreting the phrase "non-decreasing function" to mean "a function that is not a decreasing function"; if this were the case, then your answer would be correct. However, the standard definition of a non-decreasing function is a function that is non-strictly increasing, that is, a function $f(x)$ that satisfies $f(x) \le f(y)$ whenever $x<y$. There are more non-decreasing functions than increasing functions—for example, every increasing function is non-decreasing and every constant function is non-decreasing, and there others as well.

It is true, by the way, that the number of (strictly) increasing functions is the same as the number of (strictly) decreasing functions, namely $\binom85$.

$\endgroup$
5
  • $\begingroup$ So "non-decreasing" means non-strictly increasing? Okay that helps a bit.... Now my doubt is, if, I subtracted the number of strictly increasing functions from the number of total possible number of functions, why wouldn't I get the number of non-strictly increasing functions? I get a lot more than the answer $792$ What exactly do I get when I perform my method? What are the extra functions that I get but aren't counted as "non-decreasing"? $\endgroup$ – Techie5879 Mar 6 at 8:16
  • $\begingroup$ That's the same mistake again. "non-strictly increasing" doesn't mean "non (strictly increasing)", but rather "(non strictly) increasing". For example, $f(10)=20,f(11)=20,f(12)=30$ is a non-strictly increasing function; $f(10)=20,f(11)=30,f(12)=25$ is not. Read again the mathematical statement in the fourth line of my answer. $\endgroup$ – Greg Martin Mar 6 at 8:18
  • $\begingroup$ Ok, so non-strictly increasing means that $f(a) \not \lt f(b) \forall a>b$, Is that right? $\endgroup$ – Techie5879 Mar 6 at 8:21
  • $\begingroup$ Also, shouldn't a strictly increasing function also satisfy the definition of non decreasing function? Because in a strictly increasing function, we have $f(a)\gt f(b)$ when $a>b$ $\endgroup$ – Techie5879 Mar 6 at 8:24
  • 1
    $\begingroup$ Yes and yes to your last two comments! $\endgroup$ – Greg Martin Mar 6 at 9:06
1
$\begingroup$

$(1)$

Total number of functions = decreasing functions $+$ non-decreasing functions $+$ functions that are neither

As an example of the third type, $\{1,4,3,5,2\}$

$(2)$

$8 \choose 5$ is not the number of decreasing functions. It's the number of strictly-decreasing functions. I am inclined to believe that the textbook answer is wrong because increasing functions can be constant over an interval. The number of strictly-increasing functions is indeed $8 \choose 5$ because there is just one way to arrange them after choosing them.

Go through this link : https://en.m.wikipedia.org/wiki/Monotonic_function

$\endgroup$

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.