# Homework Help: Combinatory problem.

1. May 1, 2006

### kezman

How many x < y => f(x) < f(y) or f(x) = f(y) functions ("growing functions")are in [1,n] -> [1,n]?

my result was (n-1)n^2 but im not sure if its correct.

2. May 1, 2006

### AKG

No, that's way off. How did you come up with that, because it doesn't work for n = 1, 2, 3, i.e. small values of n that you could have checked for yourself? In fact, it doesn't work for any n. The way I found the answer was to find a correspondence between the set of functions in question, and the a special set of paths on the grid where each step in the path is either a move some whole number of spaces to the right or some whole number of spaces up.

For example, when n = 2, there are 3 such functions:

f1: 1 -> 1; 2 -> 1
f2: 1 -> 1; 2 -> 2
f3: 1 -> 2; 2 -> 2

I related f1 to the path that starts at the origin (0,0), and then moves right, up, up. I related f2 to the path that goes right, up, right, up. I related f3 to the path that goes right, right, up, up. If you want to solve it my way, then:

1) figure out how I'm relating these functions to these paths, and see generalize it for n > 2 (note that each function should correspond to a unique path, i.e. no two functions should correspond to the same path)
2) figure out some common trait that all of these paths have, that no other paths have
3) given some n, count the number of paths that have this trait

Last edited: May 1, 2006
3. May 1, 2006

### kezman

you are right I tested that formula for with 2 results after n>2

until now i have

3 with n=2
18 with n=3
48 with n=4

but I still cant find a correct answer.

4. May 1, 2006

### VietDao29

I don't know but how can you come up with those numbers? Here's what I get:
3, n = 2
10, n = 3
35, n = 4
126, n = 5
...
For n = 3, I have a total of 10 functions:
1 -> 1, 2 -> 1, 3 -> 1
1 -> 1, 2 -> 1, 3 -> 2
1 -> 1, 2 -> 1, 3 -> 3
1 -> 1, 2 -> 2, 3 -> 2
1 -> 1, 2 -> 2, 3 -> 3
1 -> 1, 2 -> 3, 3 -> 3
1 -> 2, 2 -> 2, 3 -> 2
1 -> 2, 2 -> 2, 3 -> 3
1 -> 2, 2 -> 3, 3 -> 3
1 -> 3, 2 -> 3, 3 -> 3
That's 10, how can you come up with 18?
Am I missing something?

Last edited: May 1, 2006
5. May 1, 2006

### kezman

maybe Im missing something...
I thought it was all the functions in the intervals [1,n] -> [1,n]
with n=2
(1,1) -> (2,1)
(1,1) -> (2,2)
(1,2) -> (2,2)
with n=3
(1,1) -> (2,1)
(1,1) -> (3,1)
(1,1) -> (2,2)
(1,1) -> (2,3)
(1,1) -> (3,2)
(1,1) -> (3,3)
(1,2) -> (2,2)
(1,2) -> (3,2)
(2,1) -> (3,1)
(2,1) -> (3,2)
(2,1) -> (3,3)
etc

6. May 2, 2006

### VietDao29

Hmm, I don't get what you wrote, what do you mean by:
(1,1) -> (2,1)
(1,1) -> (2,2)
(1,2) -> (2,2)
and:
(1,1) -> (2,1)
(1,1) -> (3,1)
(1,1) -> (2,2)
(1,1) -> (2,3)
(1,1) -> (3,2)
(1,1) -> (3,3)
(1,2) -> (2,2)
(1,2) -> (3,2)
(2,1) -> (3,1)
(2,1) -> (3,2)
(2,1) -> (3,3)???
--------------
Growing functions are the ones such that for every x < y, we have: f(x) <= f(y).
For n = 2, we have 3 such functions:
f1 : f1(1) = 1, f1(2) = 1
(that's what AKG meant when he wrote: f1: 1 -> 1; 2 -> 1).
f2 : f2(1) = 1, f2(2) = 2
f3 : f3(1) = 2, f3(2) = 2
Let's first look at f1, we have 1 < 2, so f1(1) = 1 <= f1(2) = 1, right? And that's a growing function.
Look at AKG's hints again and see if you can finish the problem.
Is it clearer? :)

7. May 2, 2006

### kezman

I mean as a growing function that goes from point (x,y) to point (x,y) in the interval [a,b]
(2,1) -> (3,3) is a growing function in the interval [1,3] -> [1,3].Is like having a 3x3 square and joining all the points that make a growing function.

This is my (maybe wrong) interpretation of the problem.

Last edited: May 2, 2006
8. May 2, 2006

### AKG

Yes, you're interpreting the problem incorrectly. You need count the number of functions f : {1, 2, ..., n} -> {1, 2, ..., n} such that x < y implies f(x) < f(y) or f(x) = f(y). This is almost identical to what your original post says, because your original post is unambiguous, so I don't see how you're misinterpreting it. In fact, I have no clue as to what you are interpreting the question to even mean.

Do you know what a function is?

9. May 2, 2006

### kezman

Yes thats the problem if its defined as two sets A={1,...,n} and B= {1,...,n} and the function as f:A -> B
But the problem says all the growing functions of the closed intervals [1,n] -> [1,n](As far as I know as set is defined by {} and closed intervals by [] and open intervals by ().)

10. May 2, 2006

### AKG

As a subset of the naturals, the closed interval [1, n] IS EXACTLY the set {1, ..., n}. But even if you thought they were talking about, [1,n] as a subset of the reals, your answer still wouldn't make sense. Nothing you wrote looks anything like a function from [1,n] to [1,n], no matter how you interpret [1,n]. So, again, do you know what a function is?

Note that it's implied by the context that [1,n] is regarded as a subset of the naturals. As a subset of the reals, there are an infinite number of increasing functions form [1,n] to [1,n].

11. May 2, 2006

### kezman

if you want all growing functions that goes from an interval [1,n] to [1,n]
Graphically you have a square nXn where (joining all the points) all the constant lines and growing lines are all the growing functions.

f(2,1)-> (3,3) with f(x,y) -> (x,y) is a growing function?

12. May 2, 2006

### AKG

None of this makes any sense whatsoever. Forget growing functions for now, do you even know what a function is? What is an example of a function f : [1,n] -> [1,n]?

13. May 2, 2006

### kezman

Im sorry I had the wrong numbers in my paper. With n = 3 is 10
My numbers and the graphical interpretation were wrong indeed.

I was counting the number of functions with the graphical interpretation not by definition.

Last edited: May 2, 2006
14. May 2, 2006

### VietDao29

kezman, from the previous posts, I still don't think that you've understood the problem. Just be sure you understand it thoroughly before trying to solve it.
What you wrote like this:
is meaningless. And may I know what you really meant by graphical interpretation?

15. May 3, 2006

### kezman

what you wrote in n = 2
f1: 1 -> 1; 2 -> 1
f2: 1 -> 1; 2 -> 2
f3: 1 -> 2; 2 -> 2

I write it (x,y) -> (x,y) As the firsts and lasts "points" of the function(Graphically)
f1:(1,1) -> (2,1)
f2:(1,1) -> (2,2)
f3:(1,2) -> (2,2)

I did had my numbers wrong before with n = 3(plus I should have mentioned the middle point). There were 10 functions.

The graphical interpretation is just a "cartesian diagram" where I "draw" all the posible growing functions(According to n).
With n = 2 are 3 (two constants and one "growing")
and with n = 3 are 10
Unfortunately I dont have a program to draw it.

Sorry I wasnt clear.

Last edited: May 3, 2006
16. May 3, 2006

### AKG

For n=3, what are the 10?

17. May 4, 2006

### kezman

for n=3 with the first, middle and last point (Before I didnt mention the middle point, my mistake)
(1,1)-> (2,1)-> (3,1) (constant)
(1,1)-> (2,1)-> (3,2)
(1,1)-> (2,2)-> (3,2)
(1,1)-> (2,1)-> (3,3)
(1,1)-> (2,3)-> (3,3)
(1,2)-> (2,2)-> (3,2) (Constant)
(1,2)-> (2,2)-> (3,3)
(1,2)-> (2,3)-> (3,3)
(1,1)-> (2,2)-> (3,3) (Strict growing function)
(1,3)-> (2,3)-> (3,3) (constant)

18. May 4, 2006

### AKG

Yes, that's correct. Now to the problem of actually counting the number of functions that do this. Do you have any ideas of your own? Now that you understand the problem, you can go back to the hints I gave, or if anyone else gave hints, you can look at those.