Derangements $p$ of $1,2,dots,n,n+1$ such that $n+1$ doesn't go to $n$
$begingroup$
Recall that the number or Derangements of $1,2,dots,n$ is a permutation $p$ such that $p(i) neq i$ for all $i$. We can express it with the recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$ or by the closed formula $$D_n =sum_{i=0}^n (-1)^i frac{n!}{i!}$$
Now we consider the number of permutations of $1,2,dots, n,n+1$ such that for all $1leq i leq n$ (not $n+1$), $p(i)neq i$, but also $p(n+1) neq n$. We need to express this number using $D_n$s.
I was thinking of first counting the number of permutations without the additional condition $p(n+1) neq n$ and received using inclusion-exclusion
$$sum_{r=0}^n (-1)^r binom{n}{r}(n+1-r)! = sum_{r=0}^n (-1)^r frac{n!}{r!}(n+1-r) =$$
$$sum_{r=0}^n (-1)^r frac{(n+1)!}{r!}- sum_{r=1}^n (-1)^r frac{n!}{(r-1)!}=$$
$$sum_{r=0}^n (-1)^r frac{(n+1)!}{r!}- nsum_{r=0}^{n-1} (-1)^{r+1} frac{(n-1)!}{r!}=$$
$$=D_{n+1}+nD_{n-1}$$
Now we need to subtract from this the number of permutations when $p(n+1)=n$, which I wasn't able to count.
Thanks in advance
combinatorics permutations inclusion-exclusion
$endgroup$
|
show 2 more comments
$begingroup$
Recall that the number or Derangements of $1,2,dots,n$ is a permutation $p$ such that $p(i) neq i$ for all $i$. We can express it with the recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$ or by the closed formula $$D_n =sum_{i=0}^n (-1)^i frac{n!}{i!}$$
Now we consider the number of permutations of $1,2,dots, n,n+1$ such that for all $1leq i leq n$ (not $n+1$), $p(i)neq i$, but also $p(n+1) neq n$. We need to express this number using $D_n$s.
I was thinking of first counting the number of permutations without the additional condition $p(n+1) neq n$ and received using inclusion-exclusion
$$sum_{r=0}^n (-1)^r binom{n}{r}(n+1-r)! = sum_{r=0}^n (-1)^r frac{n!}{r!}(n+1-r) =$$
$$sum_{r=0}^n (-1)^r frac{(n+1)!}{r!}- sum_{r=1}^n (-1)^r frac{n!}{(r-1)!}=$$
$$sum_{r=0}^n (-1)^r frac{(n+1)!}{r!}- nsum_{r=0}^{n-1} (-1)^{r+1} frac{(n-1)!}{r!}=$$
$$=D_{n+1}+nD_{n-1}$$
Now we need to subtract from this the number of permutations when $p(n+1)=n$, which I wasn't able to count.
Thanks in advance
combinatorics permutations inclusion-exclusion
$endgroup$
$begingroup$
The number of permutations of ${1,ldots,n+1}$ with $p(n+1)=n$ is simply the number of permutations of ${1,ldots,n}$; compose any such permutation with the transposition $(n n+1)$ yields a bijection between these sets of permutations.
$endgroup$
– Servaes
Dec 15 '18 at 9:42
$begingroup$
But in our case, we count the permutations with $p(i)neq i$, are you sure there is such bijection? Because when $n+1$ takes $n$'s place, we dont have to worry about $p(n) neq n$ anymore.
$endgroup$
– Theorem
Dec 15 '18 at 9:46
$begingroup$
Ah, so you mean to count the number of derangements with $p(n+1)neq n$? I only read your question at a glance, and commented on the last sentence.
$endgroup$
– Servaes
Dec 15 '18 at 9:49
$begingroup$
Yes, I didn't say exactly derangements because that would imply $p(n+1)neq n+1$, but it is very similar.
$endgroup$
– Theorem
Dec 15 '18 at 9:50
$begingroup$
In a derangement, $n+1$ is as likely to go to $n$ as to any given element of ${1,ldots,n}$.
$endgroup$
– Lord Shark the Unknown
Dec 15 '18 at 10:30
|
show 2 more comments
$begingroup$
Recall that the number or Derangements of $1,2,dots,n$ is a permutation $p$ such that $p(i) neq i$ for all $i$. We can express it with the recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$ or by the closed formula $$D_n =sum_{i=0}^n (-1)^i frac{n!}{i!}$$
Now we consider the number of permutations of $1,2,dots, n,n+1$ such that for all $1leq i leq n$ (not $n+1$), $p(i)neq i$, but also $p(n+1) neq n$. We need to express this number using $D_n$s.
I was thinking of first counting the number of permutations without the additional condition $p(n+1) neq n$ and received using inclusion-exclusion
$$sum_{r=0}^n (-1)^r binom{n}{r}(n+1-r)! = sum_{r=0}^n (-1)^r frac{n!}{r!}(n+1-r) =$$
$$sum_{r=0}^n (-1)^r frac{(n+1)!}{r!}- sum_{r=1}^n (-1)^r frac{n!}{(r-1)!}=$$
$$sum_{r=0}^n (-1)^r frac{(n+1)!}{r!}- nsum_{r=0}^{n-1} (-1)^{r+1} frac{(n-1)!}{r!}=$$
$$=D_{n+1}+nD_{n-1}$$
Now we need to subtract from this the number of permutations when $p(n+1)=n$, which I wasn't able to count.
Thanks in advance
combinatorics permutations inclusion-exclusion
$endgroup$
Recall that the number or Derangements of $1,2,dots,n$ is a permutation $p$ such that $p(i) neq i$ for all $i$. We can express it with the recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$ or by the closed formula $$D_n =sum_{i=0}^n (-1)^i frac{n!}{i!}$$
Now we consider the number of permutations of $1,2,dots, n,n+1$ such that for all $1leq i leq n$ (not $n+1$), $p(i)neq i$, but also $p(n+1) neq n$. We need to express this number using $D_n$s.
I was thinking of first counting the number of permutations without the additional condition $p(n+1) neq n$ and received using inclusion-exclusion
$$sum_{r=0}^n (-1)^r binom{n}{r}(n+1-r)! = sum_{r=0}^n (-1)^r frac{n!}{r!}(n+1-r) =$$
$$sum_{r=0}^n (-1)^r frac{(n+1)!}{r!}- sum_{r=1}^n (-1)^r frac{n!}{(r-1)!}=$$
$$sum_{r=0}^n (-1)^r frac{(n+1)!}{r!}- nsum_{r=0}^{n-1} (-1)^{r+1} frac{(n-1)!}{r!}=$$
$$=D_{n+1}+nD_{n-1}$$
Now we need to subtract from this the number of permutations when $p(n+1)=n$, which I wasn't able to count.
Thanks in advance
combinatorics permutations inclusion-exclusion
combinatorics permutations inclusion-exclusion
edited Dec 15 '18 at 12:49
Theorem
asked Dec 15 '18 at 9:38
TheoremTheorem
1,068513
1,068513
$begingroup$
The number of permutations of ${1,ldots,n+1}$ with $p(n+1)=n$ is simply the number of permutations of ${1,ldots,n}$; compose any such permutation with the transposition $(n n+1)$ yields a bijection between these sets of permutations.
$endgroup$
– Servaes
Dec 15 '18 at 9:42
$begingroup$
But in our case, we count the permutations with $p(i)neq i$, are you sure there is such bijection? Because when $n+1$ takes $n$'s place, we dont have to worry about $p(n) neq n$ anymore.
$endgroup$
– Theorem
Dec 15 '18 at 9:46
$begingroup$
Ah, so you mean to count the number of derangements with $p(n+1)neq n$? I only read your question at a glance, and commented on the last sentence.
$endgroup$
– Servaes
Dec 15 '18 at 9:49
$begingroup$
Yes, I didn't say exactly derangements because that would imply $p(n+1)neq n+1$, but it is very similar.
$endgroup$
– Theorem
Dec 15 '18 at 9:50
$begingroup$
In a derangement, $n+1$ is as likely to go to $n$ as to any given element of ${1,ldots,n}$.
$endgroup$
– Lord Shark the Unknown
Dec 15 '18 at 10:30
|
show 2 more comments
$begingroup$
The number of permutations of ${1,ldots,n+1}$ with $p(n+1)=n$ is simply the number of permutations of ${1,ldots,n}$; compose any such permutation with the transposition $(n n+1)$ yields a bijection between these sets of permutations.
$endgroup$
– Servaes
Dec 15 '18 at 9:42
$begingroup$
But in our case, we count the permutations with $p(i)neq i$, are you sure there is such bijection? Because when $n+1$ takes $n$'s place, we dont have to worry about $p(n) neq n$ anymore.
$endgroup$
– Theorem
Dec 15 '18 at 9:46
$begingroup$
Ah, so you mean to count the number of derangements with $p(n+1)neq n$? I only read your question at a glance, and commented on the last sentence.
$endgroup$
– Servaes
Dec 15 '18 at 9:49
$begingroup$
Yes, I didn't say exactly derangements because that would imply $p(n+1)neq n+1$, but it is very similar.
$endgroup$
– Theorem
Dec 15 '18 at 9:50
$begingroup$
In a derangement, $n+1$ is as likely to go to $n$ as to any given element of ${1,ldots,n}$.
$endgroup$
– Lord Shark the Unknown
Dec 15 '18 at 10:30
$begingroup$
The number of permutations of ${1,ldots,n+1}$ with $p(n+1)=n$ is simply the number of permutations of ${1,ldots,n}$; compose any such permutation with the transposition $(n n+1)$ yields a bijection between these sets of permutations.
$endgroup$
– Servaes
Dec 15 '18 at 9:42
$begingroup$
The number of permutations of ${1,ldots,n+1}$ with $p(n+1)=n$ is simply the number of permutations of ${1,ldots,n}$; compose any such permutation with the transposition $(n n+1)$ yields a bijection between these sets of permutations.
$endgroup$
– Servaes
Dec 15 '18 at 9:42
$begingroup$
But in our case, we count the permutations with $p(i)neq i$, are you sure there is such bijection? Because when $n+1$ takes $n$'s place, we dont have to worry about $p(n) neq n$ anymore.
$endgroup$
– Theorem
Dec 15 '18 at 9:46
$begingroup$
But in our case, we count the permutations with $p(i)neq i$, are you sure there is such bijection? Because when $n+1$ takes $n$'s place, we dont have to worry about $p(n) neq n$ anymore.
$endgroup$
– Theorem
Dec 15 '18 at 9:46
$begingroup$
Ah, so you mean to count the number of derangements with $p(n+1)neq n$? I only read your question at a glance, and commented on the last sentence.
$endgroup$
– Servaes
Dec 15 '18 at 9:49
$begingroup$
Ah, so you mean to count the number of derangements with $p(n+1)neq n$? I only read your question at a glance, and commented on the last sentence.
$endgroup$
– Servaes
Dec 15 '18 at 9:49
$begingroup$
Yes, I didn't say exactly derangements because that would imply $p(n+1)neq n+1$, but it is very similar.
$endgroup$
– Theorem
Dec 15 '18 at 9:50
$begingroup$
Yes, I didn't say exactly derangements because that would imply $p(n+1)neq n+1$, but it is very similar.
$endgroup$
– Theorem
Dec 15 '18 at 9:50
$begingroup$
In a derangement, $n+1$ is as likely to go to $n$ as to any given element of ${1,ldots,n}$.
$endgroup$
– Lord Shark the Unknown
Dec 15 '18 at 10:30
$begingroup$
In a derangement, $n+1$ is as likely to go to $n$ as to any given element of ${1,ldots,n}$.
$endgroup$
– Lord Shark the Unknown
Dec 15 '18 at 10:30
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Call a permutation $sigma$ of ${1,ldots,n+1}$ good if $sigma(i)neq i$ for all $1leq ileq n$ and and $sigma(n+1)neq n$.
Let $sigma$ be a good permutation, and let $a:=sigma(n+1)$ and $b:=sigma^{-1}(n+1)$, so that $aneq n$. If $aneq b$ then the permutation $(a n+1)sigma$ fixes $n+1$ and is a derangement of ${1,ldots,n}$. If $a=b$ then $(a n+1)sigma$ fixes $a$ and $n+1$, and is a derangement of ${1,ldots,n}setminus{a}$.
Conversely, for any derangement $sigma$ of ${1,ldots,n}$ and any $ain{1,ldots,n+1}$ with $aneq n$ the composition $(a n+1)sigma$ is good. Also, for any $ain{1,ldots,n-1}$ and any derangement $sigma$ of ${1,ldots,n}setminus{a}$ the composition $(a n+1)sigma$ is good.
This shows that the number of good permutations is $nD_n+(n-1)D_{n-1}$, where $D_m$ denotes the number of derangements of ${1,ldots,m}$.
$endgroup$
add a comment |
$begingroup$
These kind of problems (permutations with forbidden positions) can be elegantly solved using rook numbers/polynomials:
Let $P subseteq {1, ldots, n}^2$ be the diagram of forbidden positions. The number of permutations $p in S_n$ such that $(i,p(i)) notin P$ for all $i = 1, ldots, n$ is given by
$$sum_{k=0}^n (-1)^k(n-k)!r_k$$
where $r_k$ is the number of ways to place $k$ nonattacking rooks on the diagram $P$.
In our case the diagram e.g. for $n=4$ (the board is then $5 times 5$) is given by:
$0$ rooks can be placed in one way on $P$. To place $k$ rooks on $P$, one can place a rook on one of the two positions in the last column of $P$ in $2$ ways and then place $k-1$ rooks on $n-1$ remaining positions, or one can just place all $k$ rooks in the first $n-1$ columns, ignoring the last one. Hence
$$r_k = begin{cases}
1, text{ if }k=0\
2{n-1 choose k-1} + {n-1 choose k}, text{ if }k ge 1
end{cases} = begin{cases}
1, text{ if }k=0\
{n choose k} + {n-1 choose k-1}, text{ if }k ge 1
end{cases}$$
Therefore the result is
begin{align}
sum_{k=0}^n (-1)^k(n-k)!r_k &= sum_{k=0}^n (-1)^k(n-k)!{n choose k} + n! + sum_{k=1}^n (-1)^k(n-k)!{n-1 choose k-1} \
&= D_n + n! - sum_{j=0}^{n-1} (-1)^j((n-1)-j)!{n-1 choose j} \
&= D_n + n! - D_{n-1}
end{align}
$endgroup$
$begingroup$
Is there no simple solutions without pulling any big guns? The problem shouldn't be this complicated and I think I'm missing a key principle. (In addition I'm not sure the solution you achieved is correct)
$endgroup$
– Theorem
Dec 15 '18 at 11:23
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%2f3040322%2fderangements-p-of-1-2-dots-n-n1-such-that-n1-doesnt-go-to-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Call a permutation $sigma$ of ${1,ldots,n+1}$ good if $sigma(i)neq i$ for all $1leq ileq n$ and and $sigma(n+1)neq n$.
Let $sigma$ be a good permutation, and let $a:=sigma(n+1)$ and $b:=sigma^{-1}(n+1)$, so that $aneq n$. If $aneq b$ then the permutation $(a n+1)sigma$ fixes $n+1$ and is a derangement of ${1,ldots,n}$. If $a=b$ then $(a n+1)sigma$ fixes $a$ and $n+1$, and is a derangement of ${1,ldots,n}setminus{a}$.
Conversely, for any derangement $sigma$ of ${1,ldots,n}$ and any $ain{1,ldots,n+1}$ with $aneq n$ the composition $(a n+1)sigma$ is good. Also, for any $ain{1,ldots,n-1}$ and any derangement $sigma$ of ${1,ldots,n}setminus{a}$ the composition $(a n+1)sigma$ is good.
This shows that the number of good permutations is $nD_n+(n-1)D_{n-1}$, where $D_m$ denotes the number of derangements of ${1,ldots,m}$.
$endgroup$
add a comment |
$begingroup$
Call a permutation $sigma$ of ${1,ldots,n+1}$ good if $sigma(i)neq i$ for all $1leq ileq n$ and and $sigma(n+1)neq n$.
Let $sigma$ be a good permutation, and let $a:=sigma(n+1)$ and $b:=sigma^{-1}(n+1)$, so that $aneq n$. If $aneq b$ then the permutation $(a n+1)sigma$ fixes $n+1$ and is a derangement of ${1,ldots,n}$. If $a=b$ then $(a n+1)sigma$ fixes $a$ and $n+1$, and is a derangement of ${1,ldots,n}setminus{a}$.
Conversely, for any derangement $sigma$ of ${1,ldots,n}$ and any $ain{1,ldots,n+1}$ with $aneq n$ the composition $(a n+1)sigma$ is good. Also, for any $ain{1,ldots,n-1}$ and any derangement $sigma$ of ${1,ldots,n}setminus{a}$ the composition $(a n+1)sigma$ is good.
This shows that the number of good permutations is $nD_n+(n-1)D_{n-1}$, where $D_m$ denotes the number of derangements of ${1,ldots,m}$.
$endgroup$
add a comment |
$begingroup$
Call a permutation $sigma$ of ${1,ldots,n+1}$ good if $sigma(i)neq i$ for all $1leq ileq n$ and and $sigma(n+1)neq n$.
Let $sigma$ be a good permutation, and let $a:=sigma(n+1)$ and $b:=sigma^{-1}(n+1)$, so that $aneq n$. If $aneq b$ then the permutation $(a n+1)sigma$ fixes $n+1$ and is a derangement of ${1,ldots,n}$. If $a=b$ then $(a n+1)sigma$ fixes $a$ and $n+1$, and is a derangement of ${1,ldots,n}setminus{a}$.
Conversely, for any derangement $sigma$ of ${1,ldots,n}$ and any $ain{1,ldots,n+1}$ with $aneq n$ the composition $(a n+1)sigma$ is good. Also, for any $ain{1,ldots,n-1}$ and any derangement $sigma$ of ${1,ldots,n}setminus{a}$ the composition $(a n+1)sigma$ is good.
This shows that the number of good permutations is $nD_n+(n-1)D_{n-1}$, where $D_m$ denotes the number of derangements of ${1,ldots,m}$.
$endgroup$
Call a permutation $sigma$ of ${1,ldots,n+1}$ good if $sigma(i)neq i$ for all $1leq ileq n$ and and $sigma(n+1)neq n$.
Let $sigma$ be a good permutation, and let $a:=sigma(n+1)$ and $b:=sigma^{-1}(n+1)$, so that $aneq n$. If $aneq b$ then the permutation $(a n+1)sigma$ fixes $n+1$ and is a derangement of ${1,ldots,n}$. If $a=b$ then $(a n+1)sigma$ fixes $a$ and $n+1$, and is a derangement of ${1,ldots,n}setminus{a}$.
Conversely, for any derangement $sigma$ of ${1,ldots,n}$ and any $ain{1,ldots,n+1}$ with $aneq n$ the composition $(a n+1)sigma$ is good. Also, for any $ain{1,ldots,n-1}$ and any derangement $sigma$ of ${1,ldots,n}setminus{a}$ the composition $(a n+1)sigma$ is good.
This shows that the number of good permutations is $nD_n+(n-1)D_{n-1}$, where $D_m$ denotes the number of derangements of ${1,ldots,m}$.
edited Dec 15 '18 at 20:17
answered Dec 15 '18 at 19:57
ServaesServaes
27.5k34098
27.5k34098
add a comment |
add a comment |
$begingroup$
These kind of problems (permutations with forbidden positions) can be elegantly solved using rook numbers/polynomials:
Let $P subseteq {1, ldots, n}^2$ be the diagram of forbidden positions. The number of permutations $p in S_n$ such that $(i,p(i)) notin P$ for all $i = 1, ldots, n$ is given by
$$sum_{k=0}^n (-1)^k(n-k)!r_k$$
where $r_k$ is the number of ways to place $k$ nonattacking rooks on the diagram $P$.
In our case the diagram e.g. for $n=4$ (the board is then $5 times 5$) is given by:
$0$ rooks can be placed in one way on $P$. To place $k$ rooks on $P$, one can place a rook on one of the two positions in the last column of $P$ in $2$ ways and then place $k-1$ rooks on $n-1$ remaining positions, or one can just place all $k$ rooks in the first $n-1$ columns, ignoring the last one. Hence
$$r_k = begin{cases}
1, text{ if }k=0\
2{n-1 choose k-1} + {n-1 choose k}, text{ if }k ge 1
end{cases} = begin{cases}
1, text{ if }k=0\
{n choose k} + {n-1 choose k-1}, text{ if }k ge 1
end{cases}$$
Therefore the result is
begin{align}
sum_{k=0}^n (-1)^k(n-k)!r_k &= sum_{k=0}^n (-1)^k(n-k)!{n choose k} + n! + sum_{k=1}^n (-1)^k(n-k)!{n-1 choose k-1} \
&= D_n + n! - sum_{j=0}^{n-1} (-1)^j((n-1)-j)!{n-1 choose j} \
&= D_n + n! - D_{n-1}
end{align}
$endgroup$
$begingroup$
Is there no simple solutions without pulling any big guns? The problem shouldn't be this complicated and I think I'm missing a key principle. (In addition I'm not sure the solution you achieved is correct)
$endgroup$
– Theorem
Dec 15 '18 at 11:23
add a comment |
$begingroup$
These kind of problems (permutations with forbidden positions) can be elegantly solved using rook numbers/polynomials:
Let $P subseteq {1, ldots, n}^2$ be the diagram of forbidden positions. The number of permutations $p in S_n$ such that $(i,p(i)) notin P$ for all $i = 1, ldots, n$ is given by
$$sum_{k=0}^n (-1)^k(n-k)!r_k$$
where $r_k$ is the number of ways to place $k$ nonattacking rooks on the diagram $P$.
In our case the diagram e.g. for $n=4$ (the board is then $5 times 5$) is given by:
$0$ rooks can be placed in one way on $P$. To place $k$ rooks on $P$, one can place a rook on one of the two positions in the last column of $P$ in $2$ ways and then place $k-1$ rooks on $n-1$ remaining positions, or one can just place all $k$ rooks in the first $n-1$ columns, ignoring the last one. Hence
$$r_k = begin{cases}
1, text{ if }k=0\
2{n-1 choose k-1} + {n-1 choose k}, text{ if }k ge 1
end{cases} = begin{cases}
1, text{ if }k=0\
{n choose k} + {n-1 choose k-1}, text{ if }k ge 1
end{cases}$$
Therefore the result is
begin{align}
sum_{k=0}^n (-1)^k(n-k)!r_k &= sum_{k=0}^n (-1)^k(n-k)!{n choose k} + n! + sum_{k=1}^n (-1)^k(n-k)!{n-1 choose k-1} \
&= D_n + n! - sum_{j=0}^{n-1} (-1)^j((n-1)-j)!{n-1 choose j} \
&= D_n + n! - D_{n-1}
end{align}
$endgroup$
$begingroup$
Is there no simple solutions without pulling any big guns? The problem shouldn't be this complicated and I think I'm missing a key principle. (In addition I'm not sure the solution you achieved is correct)
$endgroup$
– Theorem
Dec 15 '18 at 11:23
add a comment |
$begingroup$
These kind of problems (permutations with forbidden positions) can be elegantly solved using rook numbers/polynomials:
Let $P subseteq {1, ldots, n}^2$ be the diagram of forbidden positions. The number of permutations $p in S_n$ such that $(i,p(i)) notin P$ for all $i = 1, ldots, n$ is given by
$$sum_{k=0}^n (-1)^k(n-k)!r_k$$
where $r_k$ is the number of ways to place $k$ nonattacking rooks on the diagram $P$.
In our case the diagram e.g. for $n=4$ (the board is then $5 times 5$) is given by:
$0$ rooks can be placed in one way on $P$. To place $k$ rooks on $P$, one can place a rook on one of the two positions in the last column of $P$ in $2$ ways and then place $k-1$ rooks on $n-1$ remaining positions, or one can just place all $k$ rooks in the first $n-1$ columns, ignoring the last one. Hence
$$r_k = begin{cases}
1, text{ if }k=0\
2{n-1 choose k-1} + {n-1 choose k}, text{ if }k ge 1
end{cases} = begin{cases}
1, text{ if }k=0\
{n choose k} + {n-1 choose k-1}, text{ if }k ge 1
end{cases}$$
Therefore the result is
begin{align}
sum_{k=0}^n (-1)^k(n-k)!r_k &= sum_{k=0}^n (-1)^k(n-k)!{n choose k} + n! + sum_{k=1}^n (-1)^k(n-k)!{n-1 choose k-1} \
&= D_n + n! - sum_{j=0}^{n-1} (-1)^j((n-1)-j)!{n-1 choose j} \
&= D_n + n! - D_{n-1}
end{align}
$endgroup$
These kind of problems (permutations with forbidden positions) can be elegantly solved using rook numbers/polynomials:
Let $P subseteq {1, ldots, n}^2$ be the diagram of forbidden positions. The number of permutations $p in S_n$ such that $(i,p(i)) notin P$ for all $i = 1, ldots, n$ is given by
$$sum_{k=0}^n (-1)^k(n-k)!r_k$$
where $r_k$ is the number of ways to place $k$ nonattacking rooks on the diagram $P$.
In our case the diagram e.g. for $n=4$ (the board is then $5 times 5$) is given by:
$0$ rooks can be placed in one way on $P$. To place $k$ rooks on $P$, one can place a rook on one of the two positions in the last column of $P$ in $2$ ways and then place $k-1$ rooks on $n-1$ remaining positions, or one can just place all $k$ rooks in the first $n-1$ columns, ignoring the last one. Hence
$$r_k = begin{cases}
1, text{ if }k=0\
2{n-1 choose k-1} + {n-1 choose k}, text{ if }k ge 1
end{cases} = begin{cases}
1, text{ if }k=0\
{n choose k} + {n-1 choose k-1}, text{ if }k ge 1
end{cases}$$
Therefore the result is
begin{align}
sum_{k=0}^n (-1)^k(n-k)!r_k &= sum_{k=0}^n (-1)^k(n-k)!{n choose k} + n! + sum_{k=1}^n (-1)^k(n-k)!{n-1 choose k-1} \
&= D_n + n! - sum_{j=0}^{n-1} (-1)^j((n-1)-j)!{n-1 choose j} \
&= D_n + n! - D_{n-1}
end{align}
edited Dec 15 '18 at 10:53
answered Dec 15 '18 at 10:47
mechanodroidmechanodroid
28.4k62548
28.4k62548
$begingroup$
Is there no simple solutions without pulling any big guns? The problem shouldn't be this complicated and I think I'm missing a key principle. (In addition I'm not sure the solution you achieved is correct)
$endgroup$
– Theorem
Dec 15 '18 at 11:23
add a comment |
$begingroup$
Is there no simple solutions without pulling any big guns? The problem shouldn't be this complicated and I think I'm missing a key principle. (In addition I'm not sure the solution you achieved is correct)
$endgroup$
– Theorem
Dec 15 '18 at 11:23
$begingroup$
Is there no simple solutions without pulling any big guns? The problem shouldn't be this complicated and I think I'm missing a key principle. (In addition I'm not sure the solution you achieved is correct)
$endgroup$
– Theorem
Dec 15 '18 at 11:23
$begingroup$
Is there no simple solutions without pulling any big guns? The problem shouldn't be this complicated and I think I'm missing a key principle. (In addition I'm not sure the solution you achieved is correct)
$endgroup$
– Theorem
Dec 15 '18 at 11:23
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%2f3040322%2fderangements-p-of-1-2-dots-n-n1-such-that-n1-doesnt-go-to-n%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$
The number of permutations of ${1,ldots,n+1}$ with $p(n+1)=n$ is simply the number of permutations of ${1,ldots,n}$; compose any such permutation with the transposition $(n n+1)$ yields a bijection between these sets of permutations.
$endgroup$
– Servaes
Dec 15 '18 at 9:42
$begingroup$
But in our case, we count the permutations with $p(i)neq i$, are you sure there is such bijection? Because when $n+1$ takes $n$'s place, we dont have to worry about $p(n) neq n$ anymore.
$endgroup$
– Theorem
Dec 15 '18 at 9:46
$begingroup$
Ah, so you mean to count the number of derangements with $p(n+1)neq n$? I only read your question at a glance, and commented on the last sentence.
$endgroup$
– Servaes
Dec 15 '18 at 9:49
$begingroup$
Yes, I didn't say exactly derangements because that would imply $p(n+1)neq n+1$, but it is very similar.
$endgroup$
– Theorem
Dec 15 '18 at 9:50
$begingroup$
In a derangement, $n+1$ is as likely to go to $n$ as to any given element of ${1,ldots,n}$.
$endgroup$
– Lord Shark the Unknown
Dec 15 '18 at 10:30