monotone subsequences of permutation
$begingroup$
Prove that the number of permutations of ${1, ..., n}$ containing a monotone increasing or decreasing subsequence of length at least $3sqrt{n}$ is $o(n!)$.
(Hint: pick a random permutation, and show that with probability tending to 1 it does not contain a monotone subsequence of length $3sqrt{n}$.)
SOLUTION:
Let $k = 3sqrt{n}$. Let $π$ be a random permutation of ${1, ..., n}$ and for a $k$-element subset
$A ⊂ {1, ..., n}$, let $I(A)$ be the indicator random variable that $π$ is either monotone decreasing or increasing on $A$. Let $X = sum_{|A| = k} I(A)$. We have $E(I(A)) = 2/k!$, so
$$
E(X) = binom{n}{k} 2/k! leq 2(en/k)^k(e/k)^k = 2(e^2n/k^2)^k < 2 (0.9)^k
$$
But then, $P(X geq 1) leq E(X) < 2 (0.9)^k$, so as $n$ goes to infinity $P(X geq 1) = 0$, which means that the
number of permutations containing a monotone increasing or decreasing subsequence of length $k$ is $o(n!)$.
In the above solution, I understand everything perfectly except in the end how we decide the little-o. I see that for large $n$, a random permutation does not contain the subsequence we are looking for. However, how do we conclude that $lim_{n rightarrow infty} f(n)/n! = 0$, $f(n)$ being the number of permutations with the property?
combinatorics permutations asymptotics proof-explanation probabilistic-method
edited Jan 2 at 16:31
Alex Ravsky
42.4k32383
asked Dec 31 '18 at 18:40
user2694307user2694307
336311
$endgroup$
add a comment |
$begingroup$
Prove that the number of permutations of ${1, ..., n}$ containing a monotone increasing or decreasing subsequence of length at least $3sqrt{n}$ is $o(n!)$.
(Hint: pick a random permutation, and show that with probability tending to 1 it does not contain a monotone subsequence of length $3sqrt{n}$.)
SOLUTION:
Let $k = 3sqrt{n}$. Let $π$ be a random permutation of ${1, ..., n}$ and for a $k$-element subset
$A ⊂ {1, ..., n}$, let $I(A)$ be the indicator random variable that $π$ is either monotone decreasing or increasing on $A$. Let $X = sum_{|A| = k} I(A)$. We have $E(I(A)) = 2/k!$, so
$$
E(X) = binom{n}{k} 2/k! leq 2(en/k)^k(e/k)^k = 2(e^2n/k^2)^k < 2 (0.9)^k
$$
But then, $P(X geq 1) leq E(X) < 2 (0.9)^k$, so as $n$ goes to infinity $P(X geq 1) = 0$, which means that the
number of permutations containing a monotone increasing or decreasing subsequence of length $k$ is $o(n!)$.
In the above solution, I understand everything perfectly except in the end how we decide the little-o. I see that for large $n$, a random permutation does not contain the subsequence we are looking for. However, how do we conclude that $lim_{n rightarrow infty} f(n)/n! = 0$, $f(n)$ being the number of permutations with the property?
combinatorics permutations asymptotics proof-explanation probabilistic-method
edited Jan 2 at 16:31
Alex Ravsky
42.4k32383
asked Dec 31 '18 at 18:40
user2694307user2694307
336311
$endgroup$
1
$begingroup$
Hint: You showed that the probability of a random permutation having your desired property is roughly $(0.9)^k = e^{-c sqrt{n}}$. Thus, the number of permutations that have this property is $n!e^{-c sqrt{n}}$ which is $o(n!)$ since $ e^{-c sqrt{n}} rightarrow 0$.
$endgroup$
– Sandeep Silwal
Dec 31 '18 at 19:34
add a comment |
$begingroup$
Prove that the number of permutations of ${1, ..., n}$ containing a monotone increasing or decreasing subsequence of length at least $3sqrt{n}$ is $o(n!)$.
(Hint: pick a random permutation, and show that with probability tending to 1 it does not contain a monotone subsequence of length $3sqrt{n}$.)
SOLUTION:
Let $k = 3sqrt{n}$. Let $π$ be a random permutation of ${1, ..., n}$ and for a $k$-element subset
$A ⊂ {1, ..., n}$, let $I(A)$ be the indicator random variable that $π$ is either monotone decreasing or increasing on $A$. Let $X = sum_{|A| = k} I(A)$. We have $E(I(A)) = 2/k!$, so
$$
E(X) = binom{n}{k} 2/k! leq 2(en/k)^k(e/k)^k = 2(e^2n/k^2)^k < 2 (0.9)^k
$$
But then, $P(X geq 1) leq E(X) < 2 (0.9)^k$, so as $n$ goes to infinity $P(X geq 1) = 0$, which means that the
number of permutations containing a monotone increasing or decreasing subsequence of length $k$ is $o(n!)$.
In the above solution, I understand everything perfectly except in the end how we decide the little-o. I see that for large $n$, a random permutation does not contain the subsequence we are looking for. However, how do we conclude that $lim_{n rightarrow infty} f(n)/n! = 0$, $f(n)$ being the number of permutations with the property?
combinatorics permutations asymptotics proof-explanation probabilistic-method
edited Jan 2 at 16:31
Alex Ravsky
42.4k32383
asked Dec 31 '18 at 18:40
user2694307user2694307
336311
$endgroup$
Prove that the number of permutations of ${1, ..., n}$ containing a monotone increasing or decreasing subsequence of length at least $3sqrt{n}$ is $o(n!)$.
(Hint: pick a random permutation, and show that with probability tending to 1 it does not contain a monotone subsequence of length $3sqrt{n}$.)
SOLUTION:
Let $k = 3sqrt{n}$. Let $π$ be a random permutation of ${1, ..., n}$ and for a $k$-element subset
$A ⊂ {1, ..., n}$, let $I(A)$ be the indicator random variable that $π$ is either monotone decreasing or increasing on $A$. Let $X = sum_{|A| = k} I(A)$. We have $E(I(A)) = 2/k!$, so
$$
E(X) = binom{n}{k} 2/k! leq 2(en/k)^k(e/k)^k = 2(e^2n/k^2)^k < 2 (0.9)^k
$$
But then, $P(X geq 1) leq E(X) < 2 (0.9)^k$, so as $n$ goes to infinity $P(X geq 1) = 0$, which means that the
number of permutations containing a monotone increasing or decreasing subsequence of length $k$ is $o(n!)$.
In the above solution, I understand everything perfectly except in the end how we decide the little-o. I see that for large $n$, a random permutation does not contain the subsequence we are looking for. However, how do we conclude that $lim_{n rightarrow infty} f(n)/n! = 0$, $f(n)$ being the number of permutations with the property?
combinatorics permutations asymptotics proof-explanation probabilistic-method
combinatorics permutations asymptotics proof-explanation probabilistic-method
edited Jan 2 at 16:31
Alex Ravsky
42.4k32383
asked Dec 31 '18 at 18:40
user2694307user2694307
336311
edited Jan 2 at 16:31
Alex Ravsky
42.4k32383
asked Dec 31 '18 at 18:40
user2694307user2694307
336311
edited Jan 2 at 16:31
Alex Ravsky
42.4k32383
edited Jan 2 at 16:31
Alex Ravsky
42.4k32383
edited Jan 2 at 16:31
Alex Ravsky
42.4k32383
42.4k32383
asked Dec 31 '18 at 18:40
user2694307user2694307
336311
asked Dec 31 '18 at 18:40
user2694307user2694307
336311
asked Dec 31 '18 at 18:40
user2694307user2694307
336311
336311
1
$begingroup$
Hint: You showed that the probability of a random permutation having your desired property is roughly $(0.9)^k = e^{-c sqrt{n}}$. Thus, the number of permutations that have this property is $n!e^{-c sqrt{n}}$ which is $o(n!)$ since $ e^{-c sqrt{n}} rightarrow 0$.
$endgroup$
– Sandeep Silwal
Dec 31 '18 at 19:34
add a comment |
1
$begingroup$
Hint: You showed that the probability of a random permutation having your desired property is roughly $(0.9)^k = e^{-c sqrt{n}}$. Thus, the number of permutations that have this property is $n!e^{-c sqrt{n}}$ which is $o(n!)$ since $ e^{-c sqrt{n}} rightarrow 0$.
$endgroup$
– Sandeep Silwal
Dec 31 '18 at 19:34
1
1
$begingroup$
Hint: You showed that the probability of a random permutation having your desired property is roughly $(0.9)^k = e^{-c sqrt{n}}$. Thus, the number of permutations that have this property is $n!e^{-c sqrt{n}}$ which is $o(n!)$ since $ e^{-c sqrt{n}} rightarrow 0$.
$endgroup$
– Sandeep Silwal
Dec 31 '18 at 19:34
$begingroup$
Hint: You showed that the probability of a random permutation having your desired property is roughly $(0.9)^k = e^{-c sqrt{n}}$. Thus, the number of permutations that have this property is $n!e^{-c sqrt{n}}$ which is $o(n!)$ since $ e^{-c sqrt{n}} rightarrow 0$.
$endgroup$
– Sandeep Silwal
Dec 31 '18 at 19:34
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3057942%2fmonotone-subsequences-of-permutation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3057942%2fmonotone-subsequences-of-permutation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Hint: You showed that the probability of a random permutation having your desired property is roughly $(0.9)^k = e^{-c sqrt{n}}$. Thus, the number of permutations that have this property is $n!e^{-c sqrt{n}}$ which is $o(n!)$ since $ e^{-c sqrt{n}} rightarrow 0$.
$endgroup$
– Sandeep Silwal
Dec 31 '18 at 19:34