Number of permutation of ${ 1, 2 dots 2n}$ with even fixpoints and relating this to derangements.
$begingroup$
I am interested in determining $e_n$, the number of permutations of ${ 1,2 dots 2n}$ where we allow even numbers to be fixed points, but where odd numbers are not allowed to be fixed points.
This really feels like a homogeneous inclusion-exclusion principle. Because first we need to include all permutations, so $(2n)!$, now we have overcounted, so we subtract the ones that fix one element, but the ones that fix one element are part of the ones that fix two elements, so we subtracted too much, we need to compensate ...
I think this should be of the form
$$ e_n =sum_{k=0}^{2n} (-1) ^kbinom{2n}{k} (2k)! (2n-2k)!$$
I have not really taken into account here that we can only fix half of the elements though. How do I do this?
As a second part I want to show that this is equivalent to $$ e_n = sum_ {k=0}^n binom n k d_ {2n-k}$$
Where $d_{2n-k}$ denotes derangement of $2n-k$ elements.
Here it seems that we make some clever division. Again, we have $2n$ elements in total, but we decide to split it as follows: first we count all derangements of every single of the $2n$ elements, but here we are counting too little, because even elements can actually appear as fixpoints. We then count derangements of 2n-1 elements, where we simply allow $1$ element to be fixed, the binomial tells us how many elements there are that can be fixed. Now we fix two even elements $dots$ in the end we fix all even elements and the sum of all these permutations is $e_n$.
combinatorics proof-verification inclusion-exclusion
asked Jan 25 at 20:20
Wesley StrikWesley Strik
2,172424
$endgroup$
add a comment |
$begingroup$
I am interested in determining $e_n$, the number of permutations of ${ 1,2 dots 2n}$ where we allow even numbers to be fixed points, but where odd numbers are not allowed to be fixed points.
This really feels like a homogeneous inclusion-exclusion principle. Because first we need to include all permutations, so $(2n)!$, now we have overcounted, so we subtract the ones that fix one element, but the ones that fix one element are part of the ones that fix two elements, so we subtracted too much, we need to compensate ...
I think this should be of the form
$$ e_n =sum_{k=0}^{2n} (-1) ^kbinom{2n}{k} (2k)! (2n-2k)!$$
I have not really taken into account here that we can only fix half of the elements though. How do I do this?
As a second part I want to show that this is equivalent to $$ e_n = sum_ {k=0}^n binom n k d_ {2n-k}$$
Where $d_{2n-k}$ denotes derangement of $2n-k$ elements.
Here it seems that we make some clever division. Again, we have $2n$ elements in total, but we decide to split it as follows: first we count all derangements of every single of the $2n$ elements, but here we are counting too little, because even elements can actually appear as fixpoints. We then count derangements of 2n-1 elements, where we simply allow $1$ element to be fixed, the binomial tells us how many elements there are that can be fixed. Now we fix two even elements $dots$ in the end we fix all even elements and the sum of all these permutations is $e_n$.
combinatorics proof-verification inclusion-exclusion
asked Jan 25 at 20:20
Wesley StrikWesley Strik
2,172424
$endgroup$
$begingroup$
Is there good reason to imagine that the answer is sensible? What is the result for $n≤10$, say?
$endgroup$
– lulu
Jan 25 at 20:24
3
$begingroup$
When I try inclusion/exclusion I get $$sum_{k=0}^n(-1)^kbinom nk(2n-k)!.$$
$endgroup$
– Lord Shark the Unknown
Jan 25 at 20:35
$begingroup$
oh yeah, because you can only fix $0 leq k leq n$ elements. Not all of them obviously!
$endgroup$
– Wesley Strik
Jan 25 at 20:46
$begingroup$
I think I managed to answer my own question now :)
$endgroup$
– Wesley Strik
Jan 25 at 20:56
1
$begingroup$
See OEIS A033815
$endgroup$
– Henry
Jan 25 at 20:57
add a comment |
$begingroup$
I am interested in determining $e_n$, the number of permutations of ${ 1,2 dots 2n}$ where we allow even numbers to be fixed points, but where odd numbers are not allowed to be fixed points.
This really feels like a homogeneous inclusion-exclusion principle. Because first we need to include all permutations, so $(2n)!$, now we have overcounted, so we subtract the ones that fix one element, but the ones that fix one element are part of the ones that fix two elements, so we subtracted too much, we need to compensate ...
I think this should be of the form
$$ e_n =sum_{k=0}^{2n} (-1) ^kbinom{2n}{k} (2k)! (2n-2k)!$$
I have not really taken into account here that we can only fix half of the elements though. How do I do this?
As a second part I want to show that this is equivalent to $$ e_n = sum_ {k=0}^n binom n k d_ {2n-k}$$
Where $d_{2n-k}$ denotes derangement of $2n-k$ elements.
Here it seems that we make some clever division. Again, we have $2n$ elements in total, but we decide to split it as follows: first we count all derangements of every single of the $2n$ elements, but here we are counting too little, because even elements can actually appear as fixpoints. We then count derangements of 2n-1 elements, where we simply allow $1$ element to be fixed, the binomial tells us how many elements there are that can be fixed. Now we fix two even elements $dots$ in the end we fix all even elements and the sum of all these permutations is $e_n$.
combinatorics proof-verification inclusion-exclusion
asked Jan 25 at 20:20
Wesley StrikWesley Strik
2,172424
$endgroup$
I am interested in determining $e_n$, the number of permutations of ${ 1,2 dots 2n}$ where we allow even numbers to be fixed points, but where odd numbers are not allowed to be fixed points.
This really feels like a homogeneous inclusion-exclusion principle. Because first we need to include all permutations, so $(2n)!$, now we have overcounted, so we subtract the ones that fix one element, but the ones that fix one element are part of the ones that fix two elements, so we subtracted too much, we need to compensate ...
I think this should be of the form
$$ e_n =sum_{k=0}^{2n} (-1) ^kbinom{2n}{k} (2k)! (2n-2k)!$$
I have not really taken into account here that we can only fix half of the elements though. How do I do this?
As a second part I want to show that this is equivalent to $$ e_n = sum_ {k=0}^n binom n k d_ {2n-k}$$
Where $d_{2n-k}$ denotes derangement of $2n-k$ elements.
Here it seems that we make some clever division. Again, we have $2n$ elements in total, but we decide to split it as follows: first we count all derangements of every single of the $2n$ elements, but here we are counting too little, because even elements can actually appear as fixpoints. We then count derangements of 2n-1 elements, where we simply allow $1$ element to be fixed, the binomial tells us how many elements there are that can be fixed. Now we fix two even elements $dots$ in the end we fix all even elements and the sum of all these permutations is $e_n$.
combinatorics proof-verification inclusion-exclusion
combinatorics proof-verification inclusion-exclusion
asked Jan 25 at 20:20
Wesley StrikWesley Strik
2,172424
asked Jan 25 at 20:20
Wesley StrikWesley Strik
2,172424
edited Jan 25 at 20:57
Wesley Strik
asked Jan 25 at 20:20
Wesley StrikWesley Strik
2,172424
asked Jan 25 at 20:20
Wesley StrikWesley Strik
2,172424
asked Jan 25 at 20:20
Wesley StrikWesley Strik
2,172424
2,172424
$begingroup$
Is there good reason to imagine that the answer is sensible? What is the result for $n≤10$, say?
$endgroup$
– lulu
Jan 25 at 20:24
3
$begingroup$
When I try inclusion/exclusion I get $$sum_{k=0}^n(-1)^kbinom nk(2n-k)!.$$
$endgroup$
– Lord Shark the Unknown
Jan 25 at 20:35
$begingroup$
oh yeah, because you can only fix $0 leq k leq n$ elements. Not all of them obviously!
$endgroup$
– Wesley Strik
Jan 25 at 20:46
$begingroup$
I think I managed to answer my own question now :)
$endgroup$
– Wesley Strik
Jan 25 at 20:56
1
$begingroup$
See OEIS A033815
$endgroup$
– Henry
Jan 25 at 20:57
add a comment |
$begingroup$
Is there good reason to imagine that the answer is sensible? What is the result for $n≤10$, say?
$endgroup$
– lulu
Jan 25 at 20:24
3
$begingroup$
When I try inclusion/exclusion I get $$sum_{k=0}^n(-1)^kbinom nk(2n-k)!.$$
$endgroup$
– Lord Shark the Unknown
Jan 25 at 20:35
$begingroup$
oh yeah, because you can only fix $0 leq k leq n$ elements. Not all of them obviously!
$endgroup$
– Wesley Strik
Jan 25 at 20:46
$begingroup$
I think I managed to answer my own question now :)
$endgroup$
– Wesley Strik
Jan 25 at 20:56
1
$begingroup$
See OEIS A033815
$endgroup$
– Henry
Jan 25 at 20:57
$begingroup$
Is there good reason to imagine that the answer is sensible? What is the result for $n≤10$, say?
$endgroup$
– lulu
Jan 25 at 20:24
$begingroup$
Is there good reason to imagine that the answer is sensible? What is the result for $n≤10$, say?
$endgroup$
– lulu
Jan 25 at 20:24
3
3
$begingroup$
When I try inclusion/exclusion I get $$sum_{k=0}^n(-1)^kbinom nk(2n-k)!.$$
$endgroup$
– Lord Shark the Unknown
Jan 25 at 20:35
$begingroup$
When I try inclusion/exclusion I get $$sum_{k=0}^n(-1)^kbinom nk(2n-k)!.$$
$endgroup$
– Lord Shark the Unknown
Jan 25 at 20:35
$begingroup$
oh yeah, because you can only fix $0 leq k leq n$ elements. Not all of them obviously!
$endgroup$
– Wesley Strik
Jan 25 at 20:46
$begingroup$
oh yeah, because you can only fix $0 leq k leq n$ elements. Not all of them obviously!
$endgroup$
– Wesley Strik
Jan 25 at 20:46
$begingroup$
I think I managed to answer my own question now :)
$endgroup$
– Wesley Strik
Jan 25 at 20:56
$begingroup$
I think I managed to answer my own question now :)
$endgroup$
– Wesley Strik
Jan 25 at 20:56
1
1
$begingroup$
See OEIS A033815
$endgroup$
– Henry
Jan 25 at 20:57
$begingroup$
See OEIS A033815
$endgroup$
– Henry
Jan 25 at 20:57
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The idea is that we first forget the restriction and simply permute all objects. This gives us $2n!$ - we have definitely overcounted here. We need to subtract all permutations that fix one odd number and we need to pick which odd number this is, this gives us $binom{n}{1}(2n-1)!$. Now we removed the permutation that fixes number $x$, but which also happened to fix $y$ and the permutation that fixed $y$, but also happened to fix $x$- we removed it twice - oops! We need to add one such permutation that fixes two odd numbers else the amounts don't add up. We can do this in $binom{n}{2}(2n-2)!$ ways. We continue over and under counting by the principle of inclusion-exclusion and get.
$$ sum_{k=0}^n(-1)^kbinom nk(2n-k)!$$
answered Jan 25 at 20:56
Wesley StrikWesley Strik
2,172424
$endgroup$
add a comment |
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%2f3087581%2fnumber-of-permutation-of-1-2-dots-2n-with-even-fixpoints-and-relating-t%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The idea is that we first forget the restriction and simply permute all objects. This gives us $2n!$ - we have definitely overcounted here. We need to subtract all permutations that fix one odd number and we need to pick which odd number this is, this gives us $binom{n}{1}(2n-1)!$. Now we removed the permutation that fixes number $x$, but which also happened to fix $y$ and the permutation that fixed $y$, but also happened to fix $x$- we removed it twice - oops! We need to add one such permutation that fixes two odd numbers else the amounts don't add up. We can do this in $binom{n}{2}(2n-2)!$ ways. We continue over and under counting by the principle of inclusion-exclusion and get.
$$ sum_{k=0}^n(-1)^kbinom nk(2n-k)!$$
answered Jan 25 at 20:56
Wesley StrikWesley Strik
2,172424
$endgroup$
add a comment |
$begingroup$
The idea is that we first forget the restriction and simply permute all objects. This gives us $2n!$ - we have definitely overcounted here. We need to subtract all permutations that fix one odd number and we need to pick which odd number this is, this gives us $binom{n}{1}(2n-1)!$. Now we removed the permutation that fixes number $x$, but which also happened to fix $y$ and the permutation that fixed $y$, but also happened to fix $x$- we removed it twice - oops! We need to add one such permutation that fixes two odd numbers else the amounts don't add up. We can do this in $binom{n}{2}(2n-2)!$ ways. We continue over and under counting by the principle of inclusion-exclusion and get.
$$ sum_{k=0}^n(-1)^kbinom nk(2n-k)!$$
answered Jan 25 at 20:56
Wesley StrikWesley Strik
2,172424
$endgroup$
add a comment |
$begingroup$
The idea is that we first forget the restriction and simply permute all objects. This gives us $2n!$ - we have definitely overcounted here. We need to subtract all permutations that fix one odd number and we need to pick which odd number this is, this gives us $binom{n}{1}(2n-1)!$. Now we removed the permutation that fixes number $x$, but which also happened to fix $y$ and the permutation that fixed $y$, but also happened to fix $x$- we removed it twice - oops! We need to add one such permutation that fixes two odd numbers else the amounts don't add up. We can do this in $binom{n}{2}(2n-2)!$ ways. We continue over and under counting by the principle of inclusion-exclusion and get.
$$ sum_{k=0}^n(-1)^kbinom nk(2n-k)!$$
answered Jan 25 at 20:56
Wesley StrikWesley Strik
2,172424
$endgroup$
The idea is that we first forget the restriction and simply permute all objects. This gives us $2n!$ - we have definitely overcounted here. We need to subtract all permutations that fix one odd number and we need to pick which odd number this is, this gives us $binom{n}{1}(2n-1)!$. Now we removed the permutation that fixes number $x$, but which also happened to fix $y$ and the permutation that fixed $y$, but also happened to fix $x$- we removed it twice - oops! We need to add one such permutation that fixes two odd numbers else the amounts don't add up. We can do this in $binom{n}{2}(2n-2)!$ ways. We continue over and under counting by the principle of inclusion-exclusion and get.
$$ sum_{k=0}^n(-1)^kbinom nk(2n-k)!$$
answered Jan 25 at 20:56
Wesley StrikWesley Strik
2,172424
answered Jan 25 at 20:56
Wesley StrikWesley Strik
2,172424
answered Jan 25 at 20:56
Wesley StrikWesley Strik
2,172424
answered Jan 25 at 20:56
Wesley StrikWesley Strik
2,172424
2,172424
add a comment |
add a comment |
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%2f3087581%2fnumber-of-permutation-of-1-2-dots-2n-with-even-fixpoints-and-relating-t%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
$begingroup$
Is there good reason to imagine that the answer is sensible? What is the result for $n≤10$, say?
$endgroup$
– lulu
Jan 25 at 20:24
3
$begingroup$
When I try inclusion/exclusion I get $$sum_{k=0}^n(-1)^kbinom nk(2n-k)!.$$
$endgroup$
– Lord Shark the Unknown
Jan 25 at 20:35
$begingroup$
oh yeah, because you can only fix $0 leq k leq n$ elements. Not all of them obviously!
$endgroup$
– Wesley Strik
Jan 25 at 20:46
$begingroup$
I think I managed to answer my own question now :)
$endgroup$
– Wesley Strik
Jan 25 at 20:56
1
$begingroup$
See OEIS A033815
$endgroup$
– Henry
Jan 25 at 20:57