Byłem pod wrażeniem elegancji w odpowiedzi na @whuber. Szczerze mówiąc musiałem dużo zapoznać się z nowymi koncepcjami, aby podążać za krokami w jego rozwiązaniu. Po spędzeniu dużo czasu postanowiłem opublikować to, co dostałem. Poniżej znajduje się egzegetyczna notatka do jego już zaakceptowanej odpowiedzi. W ten sposób nie ma próby oryginalności, a moim jedynym celem jest zapewnienie dodatkowych punktów zakotwiczenia, które pozwolą wykonać niektóre z tych czynności.
No i proszę…
2n
2. Czy możemy wyprowadzić wzór na odstępstwa?
n
d(n)=(n−1)[d(n−2)+d(n−1)]=
=nd(n−2)−d(n−2)+nd(n−1)−d(n−1)
d(n)−nd(n−1)=−[d(n−1)−(n−1)d(n−2)]
Zauważając teraz paralelność między LHS tego równania i częścią RHS w nawiasach, możemy kontynuować rekurencyjnie:
d(n)−nd(n−1)=−[d(n−1)−(n−1)d(n−2)]=
=(−1)2[d(n−2)−(n−2)d(n−3)]=⋯=(−1)n−2d(2)−2d(1)
d(n)=nd(n−1)+(−1)n
Praca wstecz:
d(2)=1
d(3)=3d(2)−1=3∗1−1
d(4)=4d(3)+1=4∗3∗1−4+1
d(5)=5d(4)−1=5∗4∗3∗1−5∗4+5−1
d(6)=6d(5)+1=6∗5∗4∗3∗1−6∗5∗4+6∗5−6+1=
=6!(12−13∗2+14∗3∗2−15∗4∗3∗2+16!)=
=6!(16!−15!+14!−13!+12!−11!+1)
Więc ogólnie
d(n)=n!(1−1+12!−13!+14!+⋯+1n!)
exx=−1
d(n)≈n!e
a,b,c,d,e,fb,d,a,c,f,ea -> b -> d -> c after which it returns to a
e -> f
(a b d c)(e f)
4
(2n)!2n2nn!p(2n)=(2n)!2nn!
Do R
symulacji:
1. paired <- function(x) crossprod(x[x] - 1:length(x))==0
x[x]
8Paul -> Maria
Maria -> Paul
Max -> John
John -> Max
Max -> Maria
Maria -> Max
Paul -> John
John -> Paul
i
1
2) good <- function(x) sum(x==1:length(x)) == 0
x(1,2,3,4,5,6,7,8)
3. Czyk.paired <- sum(i.good & i.paired)
istnieje wykluczenie sparowanych permutacji, takich jak powyższe na schemacie, które nie są odstępstwami:
v <- c(1,2,3,4,5,6,7,8)
w <- c(1,2,3,5,4,6,7,8)
(c("is v paired?" = paired(v), "is w paired?" = paired(w),
"is v a derang?" = good(w), "is w a derang?" = good(w)))
# not all paired permutations are derangements.