Counting Functions with Certain properties

[Sophdof1]

Hi - I have another counting functions question! My solution is as follows, but I am not 100% sure if I am correct.

Q: I have a function f which maps from {1,2,3,4,5,6} to {1,2,3}. I want to count how many functions f such that for all i,j belonging to {1,2,3,4,5,6} if i is less than or equal to j, then f(i) is less than or equal to f(j)

My solution:

There are 3 cases:

Case 1: The case that f(6) is 3.
Then there are 3 options (namely 1,2 or 3) each for f(5), f(4), ... f(1) so in total 3^5 = 243

Case 2: The case that f(6) is 2. Then there are 2 options (namely 2 or 1) for f(5), f(4), ... f(1) so then in total 2^5 = 32

Case 3 : The case that f(6) is 1. Then f(5), f(4), ... f(1) have 1 choice ( namely 1 ) so 1 such function.

So in total we have 276 such functions.


Am I correct - I have an exam tomorrow so would be very much appreciated if someone could answer

 

[Romsek]

I don't think you have case 1 correct. You don't have the choice of 1,2, or 3 for each item. For example once item k has selected 2 items (k-1) to 1 must be 2 or less.

I see this as a 6 digit base 3 number using digits 1-3, rather than 0-2.
The form of this number is (from the left, i.e. the leftmost digit corresponds to an input of 6, the rightmost an input of 1)

\(\displaystyle k ~3, ~k=0,~6\\
j ~2, ~j=0,~6-k \\
i ~1, ~i=0, ~6-j-k\)

I believe the total number of these can be written as

\(\displaystyle \sum \limits_{k=0}^6 \sum \limits_{j=0}^{6-k} \sum \limits_{i=0}^{6-j-k}~1 = 84\)