Mixing
The fraction of highly-increasing sequences among the set of non-decreasing sequences
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
The number of non-decreasing sequences in $0, 1, ldots, m^n$ is $binomm + nn$. Consider the following generalization of non-decreasing sequences. Set $x_0 = 0, x_n + 1 = m$ and call $(x_1, ldots, x_n) in 0, 1, ldots, m^n$ an $r$-increasing sequence if for all $i, jin0, 1, ldots, n + 1$, $i < j$, it holds that $x_j - x_i ge r(j - i - 1)$. Note that indices vary from $0$ to $n + 1$ and not from $1$ to $n$. Thus, in particular, I require that $x_2 ge r$.
Note that $r$-increasing sequences are non-decreasing (by definition $x_i + 1 - x_i ge 0 cdot r = 0$).
Question: what is the fraction of $r$-increasing sequences in the set of all non-decreasing sequences? at least asymptotically. Probably there are some close problems in the literature but I failed to find anything.
I managed to do only one extreme case, when $m = nr$ (note that this is the smallest possible value of $m$, since by definition $x_n + 1 - x_0 = m ge nr$). I claim that the number of $r$-increasing sequences in this case is exactly $(r + 1)^n$. More precisely, I claim that $(x_1, ldots, x_n)$ is $r$-increasing iff $x_iin(i - 1)r, ldots, ir$ for all $iin1, 2, ldots, n$. The $(Leftarrow)$ direction is simple: from these inequalities we can derive that
$$ x_j - x_i ge (j - 1)r - ir = (j - i - 1)r.$$
For the $(Rightarrow)$ direction observe that by definition $x_i - x_0 = x_ige (i - 1)r$ and $x_n+ 1 - x_i = nr - x_i ge (n - i)r$, i.e. $x_i le ir$.
This means that the fraction of $r$-increasing sequences is roughly $$(r+1)^n/binomn(r + 1)n approx (r + 1)^n/left(e(r + 1)right)^n = e^-n.$$
From that I would guess that in general this fraction is exponentialy small in $n cdot fracrnm = fracrn^2m$ (this is indeed the case when $fracrnm = 1$).
extremal-combinatorics
asked Jul 24 at 19:17
Sasha Kozachinskiy
41017
add a comment |Â
up vote
0
down vote
favorite
The number of non-decreasing sequences in $0, 1, ldots, m^n$ is $binomm + nn$. Consider the following generalization of non-decreasing sequences. Set $x_0 = 0, x_n + 1 = m$ and call $(x_1, ldots, x_n) in 0, 1, ldots, m^n$ an $r$-increasing sequence if for all $i, jin0, 1, ldots, n + 1$, $i < j$, it holds that $x_j - x_i ge r(j - i - 1)$. Note that indices vary from $0$ to $n + 1$ and not from $1$ to $n$. Thus, in particular, I require that $x_2 ge r$.
Note that $r$-increasing sequences are non-decreasing (by definition $x_i + 1 - x_i ge 0 cdot r = 0$).
Question: what is the fraction of $r$-increasing sequences in the set of all non-decreasing sequences? at least asymptotically. Probably there are some close problems in the literature but I failed to find anything.
I managed to do only one extreme case, when $m = nr$ (note that this is the smallest possible value of $m$, since by definition $x_n + 1 - x_0 = m ge nr$). I claim that the number of $r$-increasing sequences in this case is exactly $(r + 1)^n$. More precisely, I claim that $(x_1, ldots, x_n)$ is $r$-increasing iff $x_iin(i - 1)r, ldots, ir$ for all $iin1, 2, ldots, n$. The $(Leftarrow)$ direction is simple: from these inequalities we can derive that
$$ x_j - x_i ge (j - 1)r - ir = (j - i - 1)r.$$
For the $(Rightarrow)$ direction observe that by definition $x_i - x_0 = x_ige (i - 1)r$ and $x_n+ 1 - x_i = nr - x_i ge (n - i)r$, i.e. $x_i le ir$.
This means that the fraction of $r$-increasing sequences is roughly $$(r+1)^n/binomn(r + 1)n approx (r + 1)^n/left(e(r + 1)right)^n = e^-n.$$
From that I would guess that in general this fraction is exponentialy small in $n cdot fracrnm = fracrn^2m$ (this is indeed the case when $fracrnm = 1$).
extremal-combinatorics
asked Jul 24 at 19:17
Sasha Kozachinskiy
41017
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
The number of non-decreasing sequences in $0, 1, ldots, m^n$ is $binomm + nn$. Consider the following generalization of non-decreasing sequences. Set $x_0 = 0, x_n + 1 = m$ and call $(x_1, ldots, x_n) in 0, 1, ldots, m^n$ an $r$-increasing sequence if for all $i, jin0, 1, ldots, n + 1$, $i < j$, it holds that $x_j - x_i ge r(j - i - 1)$. Note that indices vary from $0$ to $n + 1$ and not from $1$ to $n$. Thus, in particular, I require that $x_2 ge r$.
Note that $r$-increasing sequences are non-decreasing (by definition $x_i + 1 - x_i ge 0 cdot r = 0$).
Question: what is the fraction of $r$-increasing sequences in the set of all non-decreasing sequences? at least asymptotically. Probably there are some close problems in the literature but I failed to find anything.
I managed to do only one extreme case, when $m = nr$ (note that this is the smallest possible value of $m$, since by definition $x_n + 1 - x_0 = m ge nr$). I claim that the number of $r$-increasing sequences in this case is exactly $(r + 1)^n$. More precisely, I claim that $(x_1, ldots, x_n)$ is $r$-increasing iff $x_iin(i - 1)r, ldots, ir$ for all $iin1, 2, ldots, n$. The $(Leftarrow)$ direction is simple: from these inequalities we can derive that
$$ x_j - x_i ge (j - 1)r - ir = (j - i - 1)r.$$
For the $(Rightarrow)$ direction observe that by definition $x_i - x_0 = x_ige (i - 1)r$ and $x_n+ 1 - x_i = nr - x_i ge (n - i)r$, i.e. $x_i le ir$.
This means that the fraction of $r$-increasing sequences is roughly $$(r+1)^n/binomn(r + 1)n approx (r + 1)^n/left(e(r + 1)right)^n = e^-n.$$
From that I would guess that in general this fraction is exponentialy small in $n cdot fracrnm = fracrn^2m$ (this is indeed the case when $fracrnm = 1$).
extremal-combinatorics
asked Jul 24 at 19:17
Sasha Kozachinskiy
41017
The number of non-decreasing sequences in $0, 1, ldots, m^n$ is $binomm + nn$. Consider the following generalization of non-decreasing sequences. Set $x_0 = 0, x_n + 1 = m$ and call $(x_1, ldots, x_n) in 0, 1, ldots, m^n$ an $r$-increasing sequence if for all $i, jin0, 1, ldots, n + 1$, $i < j$, it holds that $x_j - x_i ge r(j - i - 1)$. Note that indices vary from $0$ to $n + 1$ and not from $1$ to $n$. Thus, in particular, I require that $x_2 ge r$.
Note that $r$-increasing sequences are non-decreasing (by definition $x_i + 1 - x_i ge 0 cdot r = 0$).
Question: what is the fraction of $r$-increasing sequences in the set of all non-decreasing sequences? at least asymptotically. Probably there are some close problems in the literature but I failed to find anything.
I managed to do only one extreme case, when $m = nr$ (note that this is the smallest possible value of $m$, since by definition $x_n + 1 - x_0 = m ge nr$). I claim that the number of $r$-increasing sequences in this case is exactly $(r + 1)^n$. More precisely, I claim that $(x_1, ldots, x_n)$ is $r$-increasing iff $x_iin(i - 1)r, ldots, ir$ for all $iin1, 2, ldots, n$. The $(Leftarrow)$ direction is simple: from these inequalities we can derive that
$$ x_j - x_i ge (j - 1)r - ir = (j - i - 1)r.$$
For the $(Rightarrow)$ direction observe that by definition $x_i - x_0 = x_ige (i - 1)r$ and $x_n+ 1 - x_i = nr - x_i ge (n - i)r$, i.e. $x_i le ir$.
This means that the fraction of $r$-increasing sequences is roughly $$(r+1)^n/binomn(r + 1)n approx (r + 1)^n/left(e(r + 1)right)^n = e^-n.$$
From that I would guess that in general this fraction is exponentialy small in $n cdot fracrnm = fracrn^2m$ (this is indeed the case when $fracrnm = 1$).
extremal-combinatorics
asked Jul 24 at 19:17
Sasha Kozachinskiy
41017
asked Jul 24 at 19:17
Sasha Kozachinskiy
41017
asked Jul 24 at 19:17
Sasha Kozachinskiy
41017
asked Jul 24 at 19:17
Sasha Kozachinskiy
41017
41017
add a comment |Â
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f2861672%2fthe-fraction-of-highly-increasing-sequences-among-the-set-of-non-decreasing-sequ%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