La n være et naturlig tall. For to permutasjoner $p=(p_1,p_2,\dots,p_n)$ og $q=(q_1,q_2,\dots,q_n)$ av $\{1,2,\dots,n\}$ definerer vi avstanden mellom disse ved $d(p,q)=\sum_{i=1}^n |p_i-q_i|$. For eksempel vil avstanden mellom (1,3,2) og (2,3,1) være 1+0+1=2.
La $1_n=(1,2,\dots,n)$ slik at $d=d(p,1_n)=\sum_{i=1}^n |p_i-i|$.
4 oppgaver:
a) Vis at d alltid er et partall.
b) Hva vil gjennomsnittverdien av d være hvis vi beregner den for alle permutasjoner p?
c) Hva er maksimumsverdien av d?
d) For hvor mange ulike permutasjoner p oppnås denne verdien?
Avstand mellom permutasjoner
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
a) Siden spørsmålet går ut på å vise at differansen er like kan vi jobbe modulo $2$.
Differansen mellom to permutasjoner kan nå uttrykkes som $d(p,q) \equiv \sum_{i=1}^n p_i-q_i$ uten absoluttegn dersom vi regner modulo $2$, siden $-1\equiv 1$.
Enhver permutasjon kan uttrykkes som en serie av transposisjoner. Dersom $r$ er en transposisjon av $p$ og $q$ er en transposisjon av $r$ kan vi nå uttrykke differansen som $d(p,q) \equiv \sum_{i=1}^n p_i-q_i = \sum_{i=1}^n (p_i-r_i)+(r_i-q_i) = d(p,r)+d(r,q)$ modulo $2$. Induktivt vil derfor differansen mellom to permutasjoner $p_1$ og $p_k$ som består av $k-1$ antall transposisjoner kunne skrives som $d(p_1,p_k) \equiv \sum_{i=1}^{k-1} d(p_i,p_{i+1})$. Siden $d(p_i,p_{i+1})\equiv 0$ modulo $2$ for en transposisjon, vil $d(p_1,p_k)\equiv 0$ , altså vil differansen mellom to permutasjoner alltid være et partall. Det følger som et spesialtilfelle at $d$ er et partall.
b) Forventningsverdien til differansen mellom to permutasjoner blir $E[d(p,1_n)] = E[\sum_{i=1}^n |p_i- i|] = \sum_{i=1}^n E[|p_i- i|]$, der $p_i$-ene er betraktet som stokastiske variabler. Dette skulle holde til tross for at de ikke er statistisk uavhengige.
$i=1$:
$E[|p_1-1|]=\frac{0+1+2+...+(n-1)}{n}=\frac{(n-1)n}{2n}$,
$i=2$:
$E[|p_2-2|]=\frac{1+0+1+2+3+...+(n-2)}{n}=\frac{1+\frac12(n-2)(n-1)}{n}$
etc.
Generelt er
$E[|p_i-i|]=\frac{\sum_{k=0}^{i-1}k + \sum_{j=0}^{n-i}j}{n} = \frac{(i-1)i+(n-i)(n-i+1)}{2n}$
Det skal da gi etter litt algebra og summering at
$E[d(p,1_n)] = \sum_{i=1}^{n} \frac{(i-1)i+(n-i)(n-i+1)}{2n} = \frac{n^2-1}{3}$
Differansen mellom to permutasjoner kan nå uttrykkes som $d(p,q) \equiv \sum_{i=1}^n p_i-q_i$ uten absoluttegn dersom vi regner modulo $2$, siden $-1\equiv 1$.
Enhver permutasjon kan uttrykkes som en serie av transposisjoner. Dersom $r$ er en transposisjon av $p$ og $q$ er en transposisjon av $r$ kan vi nå uttrykke differansen som $d(p,q) \equiv \sum_{i=1}^n p_i-q_i = \sum_{i=1}^n (p_i-r_i)+(r_i-q_i) = d(p,r)+d(r,q)$ modulo $2$. Induktivt vil derfor differansen mellom to permutasjoner $p_1$ og $p_k$ som består av $k-1$ antall transposisjoner kunne skrives som $d(p_1,p_k) \equiv \sum_{i=1}^{k-1} d(p_i,p_{i+1})$. Siden $d(p_i,p_{i+1})\equiv 0$ modulo $2$ for en transposisjon, vil $d(p_1,p_k)\equiv 0$ , altså vil differansen mellom to permutasjoner alltid være et partall. Det følger som et spesialtilfelle at $d$ er et partall.
b) Forventningsverdien til differansen mellom to permutasjoner blir $E[d(p,1_n)] = E[\sum_{i=1}^n |p_i- i|] = \sum_{i=1}^n E[|p_i- i|]$, der $p_i$-ene er betraktet som stokastiske variabler. Dette skulle holde til tross for at de ikke er statistisk uavhengige.
$i=1$:
$E[|p_1-1|]=\frac{0+1+2+...+(n-1)}{n}=\frac{(n-1)n}{2n}$,
$i=2$:
$E[|p_2-2|]=\frac{1+0+1+2+3+...+(n-2)}{n}=\frac{1+\frac12(n-2)(n-1)}{n}$
etc.
Generelt er
$E[|p_i-i|]=\frac{\sum_{k=0}^{i-1}k + \sum_{j=0}^{n-i}j}{n} = \frac{(i-1)i+(n-i)(n-i+1)}{2n}$
Det skal da gi etter litt algebra og summering at
$E[d(p,1_n)] = \sum_{i=1}^{n} \frac{(i-1)i+(n-i)(n-i+1)}{2n} = \frac{n^2-1}{3}$
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Ser fint ut dette. På den første er du nesten i mål etter det første argumentet:
Siden p og q er permutasjoner av samme endelige mengde er summen av p_i lik summen av q_i, og d er 0 mod 2.plutarco skrev:a) Siden spørsmålet går ut på å vise at differansen er like kan vi jobbe modulo $2$.
Differansen mellom to permutasjoner kan nå uttrykkes som $d(p,q) \equiv \sum_{i=1}^n p_i-q_i$ uten absoluttegn dersom vi regner modulo $2$, siden $-1\equiv 1$.
La $q$ være en permutasjon
\begin{pmatrix}
1 & 2 & 3 & \cdots & n\\
q_1 & q_2 & q_3 & \cdots & q_n
\end{pmatrix}
, som svarer til maksimal $d$. Anta at $q_1\neq n$. Da fins en $n+1>k>1$ slik at $q_k=n$. Siden $q_1-1 + q_k - k =q_1-1+n-k \leq n-1+|q_1-k|$ må permutasjonen
\begin{pmatrix}
1 & 2 & 3 & \cdots & k & \cdots & n\\
q_k=n & q_2 & q_3 & \cdots & q_1 & \cdots & q_n
\end{pmatrix}
ha samme maksimale distanse til $1_n$. Vi kan nå benytte samme type argument helt til vi ender opp med at permutasjonen
\begin{pmatrix}
1 & 2 & 3 & \cdots & n\\
n & n-1 & n-2 & \cdots & 1
\end{pmatrix}
har maksimal distanse til $1_n$. Altså er maks $d=\sum_{k=0}^{n-1} |(n-k) - (1+k)|=2\left ( \lceil \frac{1-n}{2} \rceil+n-1\right )\left (\lfloor \frac{n-1}{2}\rfloor +1 \right )$
\begin{pmatrix}
1 & 2 & 3 & \cdots & n\\
q_1 & q_2 & q_3 & \cdots & q_n
\end{pmatrix}
, som svarer til maksimal $d$. Anta at $q_1\neq n$. Da fins en $n+1>k>1$ slik at $q_k=n$. Siden $q_1-1 + q_k - k =q_1-1+n-k \leq n-1+|q_1-k|$ må permutasjonen
\begin{pmatrix}
1 & 2 & 3 & \cdots & k & \cdots & n\\
q_k=n & q_2 & q_3 & \cdots & q_1 & \cdots & q_n
\end{pmatrix}
ha samme maksimale distanse til $1_n$. Vi kan nå benytte samme type argument helt til vi ender opp med at permutasjonen
\begin{pmatrix}
1 & 2 & 3 & \cdots & n\\
n & n-1 & n-2 & \cdots & 1
\end{pmatrix}
har maksimal distanse til $1_n$. Altså er maks $d=\sum_{k=0}^{n-1} |(n-k) - (1+k)|=2\left ( \lceil \frac{1-n}{2} \rceil+n-1\right )\left (\lfloor \frac{n-1}{2}\rfloor +1 \right )$
-
mrcreosote
- Guru
- Innlegg: 1995
- Registrert: 10/10-2006 20:58
Bra argument!plutarco skrev:La $q$ være en permutasjon
\begin{pmatrix}
1 & 2 & 3 & \cdots & n\\
q_1 & q_2 & q_3 & \cdots & q_n
\end{pmatrix}
, som svarer til maksimal $d$. Anta at $q_1\neq n$. Da fins en $n+1>k>1$ slik at $q_k=n$. Siden $q_1-1 + q_k - k =q_1-1+n-k \leq n-1+|q_1-k|$ må permutasjonen
\begin{pmatrix}
1 & 2 & 3 & \cdots & k & \cdots & n\\
q_k=n & q_2 & q_3 & \cdots & q_1 & \cdots & q_n
\end{pmatrix}
ha samme maksimale distanse til $1_n$. Vi kan nå benytte samme type argument helt til vi ender opp med at permutasjonen
\begin{pmatrix}
1 & 2 & 3 & \cdots & n\\
n & n-1 & n-2 & \cdots & 1
\end{pmatrix}
har maksimal distanse til $1_n$. Altså er maks $d=\sum_{k=0}^{n-1} |(n-k) - (1+k)|=2\left ( \lceil \frac{1-n}{2} \rceil+n-1\right )\left (\lfloor \frac{n-1}{2}\rfloor +1 \right )$
Summen kan forenkles til [tex]\lfloor\frac{n^2}2\rfloor[/tex], for eksempel ved å behandle tilfellene n like og n ulike hver for seg. (Dette er også et hint til oppgave d!)