Number of Growing Functions in [1,n] -> [1,n]: n^2-1

[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 I am not sure if its correct.

 

[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:

f₁: 1 -> 1; 2 -> 1
f₂: 1 -> 1; 2 -> 2
f₃: 1 -> 2; 2 -> 2

I related f₁ to the path that starts at the origin (0,0), and then moves right, up, up. I related f₂ to the path that goes right, up, right, up. I related f₃ 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

 

[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 can't find a correct answer.

 

[VietDao29]

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 can't find a correct answer.

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?

 

[kezman]

maybe I am 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

 

[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:
f₁ : f₁(1) = 1, f₁(2) = 1
(that's what AKG meant when he wrote: f₁: 1 -> 1; 2 -> 1).
f₂ : f₂(1) = 1, f₂(2) = 2
f₃ : f₃(1) = 2, f₃(2) = 2
Let's first look at f₁, we have 1 < 2, so f₁(1) = 1 <= f₁(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? :)

 

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

 

[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?

 

[kezman]

Yes that's 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 ().)

 

[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].

 

[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?

 

[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]?

 

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

 

[VietDao29]

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.

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:

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

is meaningless. And may I know what you really meant by graphical interpretation?
Please answer AKG's questions:

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]?

 

[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 don't have a program to draw it.

Sorry I wasnt clear.

 

[AKG]

For n=3, what are the 10?

 

[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)

 

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