Discrete mathematics

esraa said:
View attachment 23748


Can you please help me with this question?
Click to expand...

Sure. But what help do you need?

Have you done anything with part (a)? We'd like to see your work:

Posting Guidelines (Summary)

Welcome to our tutoring boards! :) This page summarizes the main points from our posting guidelines. As our name implies, we provide math help (primarily to students with homework). We do not generally post immediate answers or step-by-step solutions. We don't do your homework. We prefer to...
www.freemathhelp.com

In particular, this is a counting problem. What counting techniques have you learned?

If you have no idea how to start, my own first thought was to picture the graph of such a function. The domain is {1, 2, 3, 4, 5, 6, 7}, and the codomain is {1, 2, 3, 4, 5}. The graph will be 7 dots; if the function is monotone increasing, then each dot is either at or above the level of all those to its left.

My second thought was that if the function were strictly increasing, then no number could repeat, so it would amount to a choice of n out of m numbers -- a combination. But it isn't strictly increasing, so that some numbers can be used more than once; and m>n for part (a). But maybe some similar idea will work ...
 
The number of functions is n^m, how many of them are monotone increasing in terms of m and n? I think here should be a formula for this. In d and e some number is subtracted because of the condition given, in this case, how does the number of such functions change?
 
esraa said:
The number of functions is n^m, how many of them are monotone increasing in terms of m and n? I think here should be a formula for this. In d and e some number is subtracted because of the condition given, in this case, how does the number of such functions change?
Click to expand...

We can represent a monotone increasing function by just listing its values in order; for example, on from X_7 to X_5 might be {1, 2, 2, 4, 7,}. Any multiset of size 7 selected from X_5 corresponds to such a function. That might suggest some ideas.

Another way to represent the same function would be to indicate how many times each number from 1 through 7 occurs: (1, 2, 0, 1, 0, 0, 1).

Other ideas you might consider, if you have any experience with them, are partitions and stars-and-bars. You'll have to tell me what you've learned.

Once you solve (a), you can apply the same technique to the other parts.
 
Dr.Peterson said:
We can represent a monotone increasing function by just listing its values in order; for example, on from X_7 to X_5 might be {1, 2, 2, 4, 7,}. Any multiset of size 7 selected from X_5 corresponds to such a function. That might suggest some ideas.

Another way to represent the same function would be to indicate how many times each number from 1 through 7 occurs: (1, 2, 0, 1, 0, 0, 1).

Other ideas you might consider, if you have any experience with them, are partitions and stars-and-bars. You'll have to tell me what you've learned.

Once you solve (a), you can apply the same technique to the other parts.
Click to expand...
My examples aren't right; I actually had correct examples at first and hastily changed them, thinking they were wrong! A function from [MATH]X_7[/MATH] to [MATH]X_5[/MATH] would look like {1, 2, 2, 3, 5, 5, 5}, with a value from 1 to 5 for each of 7 inputs, and like (1, 2, 1, 0, 3), with counts for each element of [MATH]X_5[/MATH].
 
You must log in or register to reply here.
Top