mateforum.ro

Pentru o permutare \( \sigma=(i_1...i_n) \) a lui \( (1,2,...,n) \) definim \( D(\sigma)=\sum_{k=1}^n|i_k-k| \). Fie \( Q(n,d) \) numarul permutarilor \( \sigma \) ale lui \( (1,2,...,n) \) pentru care \( D(\sigma)=d \). Demonstrati ca daca \( d\geq 2n \) atunci \( Q(n,d) \) este numar par.

IMC 2008

Ideea de rezolvare e mai complicata, si nu se vede daca nu ai mai facut asa ceva inainte...

Se considera determinantul \( \Delta(x)=|\ x^{|i-j|}\ |_{1\leq i,j \leq n} \), adica elementul de pe linia \( i \) si coloana \( j \) este egal cu \( x^{|i-j|} \).

Folosind definitia determinantului, obtinem ca \( \Delta(x)=\sum_{\sigma \in S_n}x^{D(\sigma)}(-1)^{Inv(\sigma)} \), unde \( Inv(\sigma) \) este numarul inversunilor lui \( \sigma \).. Astfel \( Q(n,d) \) are aceeasi paritate cu coeficientul lui \( x^{d} \) in \( \Delta(x) \). \( (\circ) \).

Calculam acum in alt mod pe \( \Delta(x) \):
Pentru \( k \) de la \( n \) la 2 (descrescator) scadem din linia \( k \) linia \( k-1 \) inmultita cu \( x \). Obtinem un determinant care are pe diagonala principala \( 1-x^2 \) in afara de coltul stanga sus unde este 1[/tex] si toate elementele care nu sunt pe prima linie sau pe diagonala principala sunt 0[/tex]. Astfel, se arata simplu ca \( \Delta(x)=(1-x^2)^{n-1} \). De aici se observa clar ca pentru \( d\geq 2n \) coeficientul lui \( x^d \) in \( \Delta(x) \) este 0. Din \( (\circ) \) rezulta ca pentru \( d\geq 2n\ Q(n,d) \) este numar par.

Probabil se poate face mai simplu ,tot ce trebuie aratat este ca numarul permutarilor \( \sigma \) ,care au \( D(\sigma)=d\ge 2n ,\sigma^2=e \) este par .Pt ca pt o permutare \( \sigma,\sigma^2\not=e =>\sigma\not=\sigma^{-1} \) iar \( D(\sigma^{-1})=D(\sigma) \) deci pe acestea le putem grupa in cupluri de forma \( (\sigma,\sigma^{-1}) \).