How many nondecreasing functions $f:1,2, ldots, n to 1,2, ldots, n$ with $f(i)leq i$ are there?
Clash Royale CLAN TAG#URR8PPP
up vote
14
down vote
favorite
As in title, how to determine the number of nondecreasing functions $f:1,2, ldots, n to 1,2, ldots, n$ such that $f(i)leq i$, for all $i in 1,2, ldots, n $?
I know that there is in general $2n-1choosen-1$ nondecreasing functions.
I also have tried to solve the problem for small n's:
For n=1 we have one such function, for n=2 we have two such functions and for n=3 we have five such functions.
If we list all the possible values that functions can take for $n=3$, we see that there are as many functions as paths connecting all the columns's, for example f(1)=1, f(2)=2, f(3)=3. Starting with f(3)=3, at each step we can go "left" and "down" or remain "at the same level" but we cannot go "up", because then the function would be decreasing.
$f(1)=1$
$f(1)=2$ $f(2)=2$
$f(1)=3$ $f(2)=3$ $f(3)=3$
Having that said we can count how many nondecreasing sequences of the form $(a_1, a_2, ldots, a_n)$ we have such that $a_i = f(i)$.
functions discrete-mathematics
asked Aug 21 at 11:00
Jack Blackwell
966
 |Â
show 7 more comments
up vote
14
down vote
favorite
As in title, how to determine the number of nondecreasing functions $f:1,2, ldots, n to 1,2, ldots, n$ such that $f(i)leq i$, for all $i in 1,2, ldots, n $?
I know that there is in general $2n-1choosen-1$ nondecreasing functions.
I also have tried to solve the problem for small n's:
For n=1 we have one such function, for n=2 we have two such functions and for n=3 we have five such functions.
If we list all the possible values that functions can take for $n=3$, we see that there are as many functions as paths connecting all the columns's, for example f(1)=1, f(2)=2, f(3)=3. Starting with f(3)=3, at each step we can go "left" and "down" or remain "at the same level" but we cannot go "up", because then the function would be decreasing.
$f(1)=1$
$f(1)=2$ $f(2)=2$
$f(1)=3$ $f(2)=3$ $f(3)=3$
Having that said we can count how many nondecreasing sequences of the form $(a_1, a_2, ldots, a_n)$ we have such that $a_i = f(i)$.
functions discrete-mathematics
asked Aug 21 at 11:00
Jack Blackwell
966
1
What did you try so far? Did you find a pattern for $n = 1, 2, 3, 4, 5$?
– Ronald
Aug 21 at 11:05
1
Do you mean decreasing or strictly decreasing? As a constant function is (nonstrictly) decreasing, if you function can't be constant, the only possibility is the identity f(i)=i
– F.Carette
Aug 21 at 11:06
1
@F.Carette Nondecreasing is a word which never means what I think it ought to mean (to me it ought to mean that the function is not a decreasing function). It means "increasing (but not necessarily stricltly)". I think it was coined by someone who thought the word "increasing" ought to mean "strictly increasing", and then wanted a word for the non-strict meaning.
– Arthur
Aug 21 at 11:27
1
@JackBlackwell, both your exemple in comment and in question are wrong ($exists i, f(i)>i$). Your function needs to satisfy $f(1)=1$ no matter $n$. Then $f(2) in 1,2$,etc... I managed to build every solution step by step for n=1,..5, but I can't find a pattern in the number of solutions. Your question seems way more interesting that I thought
– F.Carette
Aug 21 at 11:37
2
Aren't these just the Catalan numbers? This is just patha in a square lattice that don't go above the diagonal: if $f(i-1)=f(i)$, go right, otherwise go up.
– Steve D
Aug 21 at 12:07
 |Â
show 7 more comments
up vote
14
down vote
favorite
up vote
14
down vote
favorite
As in title, how to determine the number of nondecreasing functions $f:1,2, ldots, n to 1,2, ldots, n$ such that $f(i)leq i$, for all $i in 1,2, ldots, n $?
I know that there is in general $2n-1choosen-1$ nondecreasing functions.
I also have tried to solve the problem for small n's:
For n=1 we have one such function, for n=2 we have two such functions and for n=3 we have five such functions.
If we list all the possible values that functions can take for $n=3$, we see that there are as many functions as paths connecting all the columns's, for example f(1)=1, f(2)=2, f(3)=3. Starting with f(3)=3, at each step we can go "left" and "down" or remain "at the same level" but we cannot go "up", because then the function would be decreasing.
$f(1)=1$
$f(1)=2$ $f(2)=2$
$f(1)=3$ $f(2)=3$ $f(3)=3$
Having that said we can count how many nondecreasing sequences of the form $(a_1, a_2, ldots, a_n)$ we have such that $a_i = f(i)$.
functions discrete-mathematics
asked Aug 21 at 11:00
Jack Blackwell
966
As in title, how to determine the number of nondecreasing functions $f:1,2, ldots, n to 1,2, ldots, n$ such that $f(i)leq i$, for all $i in 1,2, ldots, n $?
I know that there is in general $2n-1choosen-1$ nondecreasing functions.
I also have tried to solve the problem for small n's:
For n=1 we have one such function, for n=2 we have two such functions and for n=3 we have five such functions.
If we list all the possible values that functions can take for $n=3$, we see that there are as many functions as paths connecting all the columns's, for example f(1)=1, f(2)=2, f(3)=3. Starting with f(3)=3, at each step we can go "left" and "down" or remain "at the same level" but we cannot go "up", because then the function would be decreasing.
$f(1)=1$
$f(1)=2$ $f(2)=2$
$f(1)=3$ $f(2)=3$ $f(3)=3$
Having that said we can count how many nondecreasing sequences of the form $(a_1, a_2, ldots, a_n)$ we have such that $a_i = f(i)$.
functions discrete-mathematics
asked Aug 21 at 11:00
Jack Blackwell
966
edited Aug 21 at 11:40
asked Aug 21 at 11:00
Jack Blackwell
966
asked Aug 21 at 11:00
Jack Blackwell
966
asked Aug 21 at 11:00
Jack Blackwell
966
966
1
What did you try so far? Did you find a pattern for $n = 1, 2, 3, 4, 5$?
– Ronald
Aug 21 at 11:05
1
Do you mean decreasing or strictly decreasing? As a constant function is (nonstrictly) decreasing, if you function can't be constant, the only possibility is the identity f(i)=i
– F.Carette
Aug 21 at 11:06
1
@F.Carette Nondecreasing is a word which never means what I think it ought to mean (to me it ought to mean that the function is not a decreasing function). It means "increasing (but not necessarily stricltly)". I think it was coined by someone who thought the word "increasing" ought to mean "strictly increasing", and then wanted a word for the non-strict meaning.
– Arthur
Aug 21 at 11:27
1
@JackBlackwell, both your exemple in comment and in question are wrong ($exists i, f(i)>i$). Your function needs to satisfy $f(1)=1$ no matter $n$. Then $f(2) in 1,2$,etc... I managed to build every solution step by step for n=1,..5, but I can't find a pattern in the number of solutions. Your question seems way more interesting that I thought
– F.Carette
Aug 21 at 11:37
2
Aren't these just the Catalan numbers? This is just patha in a square lattice that don't go above the diagonal: if $f(i-1)=f(i)$, go right, otherwise go up.
– Steve D
Aug 21 at 12:07
 |Â
show 7 more comments
1
What did you try so far? Did you find a pattern for $n = 1, 2, 3, 4, 5$?
– Ronald
Aug 21 at 11:05
1
Do you mean decreasing or strictly decreasing? As a constant function is (nonstrictly) decreasing, if you function can't be constant, the only possibility is the identity f(i)=i
– F.Carette
Aug 21 at 11:06
1
@F.Carette Nondecreasing is a word which never means what I think it ought to mean (to me it ought to mean that the function is not a decreasing function). It means "increasing (but not necessarily stricltly)". I think it was coined by someone who thought the word "increasing" ought to mean "strictly increasing", and then wanted a word for the non-strict meaning.
– Arthur
Aug 21 at 11:27
1
@JackBlackwell, both your exemple in comment and in question are wrong ($exists i, f(i)>i$). Your function needs to satisfy $f(1)=1$ no matter $n$. Then $f(2) in 1,2$,etc... I managed to build every solution step by step for n=1,..5, but I can't find a pattern in the number of solutions. Your question seems way more interesting that I thought
– F.Carette
Aug 21 at 11:37
2
Aren't these just the Catalan numbers? This is just patha in a square lattice that don't go above the diagonal: if $f(i-1)=f(i)$, go right, otherwise go up.
– Steve D
Aug 21 at 12:07
1
1
What did you try so far? Did you find a pattern for $n = 1, 2, 3, 4, 5$?
– Ronald
Aug 21 at 11:05
What did you try so far? Did you find a pattern for $n = 1, 2, 3, 4, 5$?
– Ronald
Aug 21 at 11:05
1
1
Do you mean decreasing or strictly decreasing? As a constant function is (nonstrictly) decreasing, if you function can't be constant, the only possibility is the identity f(i)=i
– F.Carette
Aug 21 at 11:06
Do you mean decreasing or strictly decreasing? As a constant function is (nonstrictly) decreasing, if you function can't be constant, the only possibility is the identity f(i)=i
– F.Carette
Aug 21 at 11:06
1
1
@F.Carette Nondecreasing is a word which never means what I think it ought to mean (to me it ought to mean that the function is not a decreasing function). It means "increasing (but not necessarily stricltly)". I think it was coined by someone who thought the word "increasing" ought to mean "strictly increasing", and then wanted a word for the non-strict meaning.
– Arthur
Aug 21 at 11:27
@F.Carette Nondecreasing is a word which never means what I think it ought to mean (to me it ought to mean that the function is not a decreasing function). It means "increasing (but not necessarily stricltly)". I think it was coined by someone who thought the word "increasing" ought to mean "strictly increasing", and then wanted a word for the non-strict meaning.
– Arthur
Aug 21 at 11:27
1
1
@JackBlackwell, both your exemple in comment and in question are wrong ($exists i, f(i)>i$). Your function needs to satisfy $f(1)=1$ no matter $n$. Then $f(2) in 1,2$,etc... I managed to build every solution step by step for n=1,..5, but I can't find a pattern in the number of solutions. Your question seems way more interesting that I thought
– F.Carette
Aug 21 at 11:37
@JackBlackwell, both your exemple in comment and in question are wrong ($exists i, f(i)>i$). Your function needs to satisfy $f(1)=1$ no matter $n$. Then $f(2) in 1,2$,etc... I managed to build every solution step by step for n=1,..5, but I can't find a pattern in the number of solutions. Your question seems way more interesting that I thought
– F.Carette
Aug 21 at 11:37
2
2
Aren't these just the Catalan numbers? This is just patha in a square lattice that don't go above the diagonal: if $f(i-1)=f(i)$, go right, otherwise go up.
– Steve D
Aug 21 at 12:07
Aren't these just the Catalan numbers? This is just patha in a square lattice that don't go above the diagonal: if $f(i-1)=f(i)$, go right, otherwise go up.
– Steve D
Aug 21 at 12:07
 |Â
show 7 more comments
1 Answer
1
active
oldest
votes
up vote
10
down vote
accepted
These are just the Catalan numbers. Plot points in the $ntimes n$ grid, with coordinates $(i, f(i))$. Then connect the bottom-left corner to the upper-right corner by going through the points (and never going above the diagonal).
In this picture, the yellow line represents the function:
$$ f(1) = 1, f(2) = 1, f(3) = 2 $$
and the blue line represents the function
$$ f(1) = 1, f(2) = 2, f(3) = 2 $$
[Green is where they overlap.]
The Catalan numbers count the number of paths below the diagonal. And the points you've plotted uniquely identify such a path.
answered Aug 21 at 12:11
Steve D
2,4521620
Nice, thank You very much for the solution.
– Jack Blackwell
Aug 21 at 13:47
4
Using the explicit expression $frac1n + 1 2 n choose n$ for the $n$th Catalan number and the formula for the number of nondecreasing functions gives that the fraction of nondecreasing functions that satisfy the above condition is just $2 / (n + 1)$, $n > 0$.
– Travis
Aug 21 at 14:30
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
10
down vote
accepted
These are just the Catalan numbers. Plot points in the $ntimes n$ grid, with coordinates $(i, f(i))$. Then connect the bottom-left corner to the upper-right corner by going through the points (and never going above the diagonal).
In this picture, the yellow line represents the function:
$$ f(1) = 1, f(2) = 1, f(3) = 2 $$
and the blue line represents the function
$$ f(1) = 1, f(2) = 2, f(3) = 2 $$
[Green is where they overlap.]
The Catalan numbers count the number of paths below the diagonal. And the points you've plotted uniquely identify such a path.
answered Aug 21 at 12:11
Steve D
2,4521620
Nice, thank You very much for the solution.
– Jack Blackwell
Aug 21 at 13:47
4
Using the explicit expression $frac1n + 1 2 n choose n$ for the $n$th Catalan number and the formula for the number of nondecreasing functions gives that the fraction of nondecreasing functions that satisfy the above condition is just $2 / (n + 1)$, $n > 0$.
– Travis
Aug 21 at 14:30
add a comment |Â
up vote
10
down vote
accepted
These are just the Catalan numbers. Plot points in the $ntimes n$ grid, with coordinates $(i, f(i))$. Then connect the bottom-left corner to the upper-right corner by going through the points (and never going above the diagonal).
In this picture, the yellow line represents the function:
$$ f(1) = 1, f(2) = 1, f(3) = 2 $$
and the blue line represents the function
$$ f(1) = 1, f(2) = 2, f(3) = 2 $$
[Green is where they overlap.]
The Catalan numbers count the number of paths below the diagonal. And the points you've plotted uniquely identify such a path.
answered Aug 21 at 12:11
Steve D
2,4521620
Nice, thank You very much for the solution.
– Jack Blackwell
Aug 21 at 13:47
4
Using the explicit expression $frac1n + 1 2 n choose n$ for the $n$th Catalan number and the formula for the number of nondecreasing functions gives that the fraction of nondecreasing functions that satisfy the above condition is just $2 / (n + 1)$, $n > 0$.
– Travis
Aug 21 at 14:30
add a comment |Â
up vote
10
down vote
accepted
up vote
10
down vote
accepted
These are just the Catalan numbers. Plot points in the $ntimes n$ grid, with coordinates $(i, f(i))$. Then connect the bottom-left corner to the upper-right corner by going through the points (and never going above the diagonal).
In this picture, the yellow line represents the function:
$$ f(1) = 1, f(2) = 1, f(3) = 2 $$
and the blue line represents the function
$$ f(1) = 1, f(2) = 2, f(3) = 2 $$
[Green is where they overlap.]
The Catalan numbers count the number of paths below the diagonal. And the points you've plotted uniquely identify such a path.
answered Aug 21 at 12:11
Steve D
2,4521620
These are just the Catalan numbers. Plot points in the $ntimes n$ grid, with coordinates $(i, f(i))$. Then connect the bottom-left corner to the upper-right corner by going through the points (and never going above the diagonal).
In this picture, the yellow line represents the function:
$$ f(1) = 1, f(2) = 1, f(3) = 2 $$
and the blue line represents the function
$$ f(1) = 1, f(2) = 2, f(3) = 2 $$
[Green is where they overlap.]
The Catalan numbers count the number of paths below the diagonal. And the points you've plotted uniquely identify such a path.
answered Aug 21 at 12:11
Steve D
2,4521620
edited Aug 21 at 12:43
answered Aug 21 at 12:11
Steve D
2,4521620
answered Aug 21 at 12:11
Steve D
2,4521620
answered Aug 21 at 12:11
Steve D
2,4521620
2,4521620
Nice, thank You very much for the solution.
– Jack Blackwell
Aug 21 at 13:47
4
Using the explicit expression $frac1n + 1 2 n choose n$ for the $n$th Catalan number and the formula for the number of nondecreasing functions gives that the fraction of nondecreasing functions that satisfy the above condition is just $2 / (n + 1)$, $n > 0$.
– Travis
Aug 21 at 14:30
add a comment |Â
Nice, thank You very much for the solution.
– Jack Blackwell
Aug 21 at 13:47
4
Using the explicit expression $frac1n + 1 2 n choose n$ for the $n$th Catalan number and the formula for the number of nondecreasing functions gives that the fraction of nondecreasing functions that satisfy the above condition is just $2 / (n + 1)$, $n > 0$.
– Travis
Aug 21 at 14:30
Nice, thank You very much for the solution.
– Jack Blackwell
Aug 21 at 13:47
Nice, thank You very much for the solution.
– Jack Blackwell
Aug 21 at 13:47
4
4
Using the explicit expression $frac1n + 1 2 n choose n$ for the $n$th Catalan number and the formula for the number of nondecreasing functions gives that the fraction of nondecreasing functions that satisfy the above condition is just $2 / (n + 1)$, $n > 0$.
– Travis
Aug 21 at 14:30
Using the explicit expression $frac1n + 1 2 n choose n$ for the $n$th Catalan number and the formula for the number of nondecreasing functions gives that the fraction of nondecreasing functions that satisfy the above condition is just $2 / (n + 1)$, $n > 0$.
– Travis
Aug 21 at 14:30
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2889737%2fhow-many-nondecreasing-functions-f-1-2-ldots-n-to-1-2-ldots-n-w%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
What did you try so far? Did you find a pattern for $n = 1, 2, 3, 4, 5$?
– Ronald
Aug 21 at 11:05
1
Do you mean decreasing or strictly decreasing? As a constant function is (nonstrictly) decreasing, if you function can't be constant, the only possibility is the identity f(i)=i
– F.Carette
Aug 21 at 11:06
1
@F.Carette Nondecreasing is a word which never means what I think it ought to mean (to me it ought to mean that the function is not a decreasing function). It means "increasing (but not necessarily stricltly)". I think it was coined by someone who thought the word "increasing" ought to mean "strictly increasing", and then wanted a word for the non-strict meaning.
– Arthur
Aug 21 at 11:27
1
@JackBlackwell, both your exemple in comment and in question are wrong ($exists i, f(i)>i$). Your function needs to satisfy $f(1)=1$ no matter $n$. Then $f(2) in 1,2$,etc... I managed to build every solution step by step for n=1,..5, but I can't find a pattern in the number of solutions. Your question seems way more interesting that I thought
– F.Carette
Aug 21 at 11:37
2
Aren't these just the Catalan numbers? This is just patha in a square lattice that don't go above the diagonal: if $f(i-1)=f(i)$, go right, otherwise go up.
– Steve D
Aug 21 at 12:07