Se considera permutarile :
α= ( 1 2 3 4 ... n n+1 n+2 ... 2n )
2 4 6 8 ... 2n 1 3 ... 2n-1
β= ( 1 2 3 4 ... n n+1 n+2 ... 2n )
1 3 5 7 ... 2n-1 2 4 ... 2n
Să se determine numărul de inversiuni şi signatura permutărilor
Sa se determine n ∈ N stelat pentru care α este permutare para, respectiv β este permutare impara.
Răspunsuri la întrebare
Răspuns de
50
Salut,
Pentru permutarea α, numărul de inversiuni se calculează așa: pe a doua linie, iau fiecare termen de la stânga la dreapta, începând cu al doilea și număr câți termeni sunt mai mari decât cel analizat, termeni aflați la stânga termenului analizat.
Al doilea termen este 4, în stânga lui numărul de termeni mai mari decât el este 0.
Al treilea termen este 6, în stânga lui numărul de termeni mai mari decât el este tot 0.
Al patrulea termen este 8, în stânga lui numărul de termeni mai mari decât el este tot 0.
...
Termenul 2n este termenul de pe poziția n, în stânga lui nici un termen nu este mai mare decât 2n, deci numărul de termeni este tot 0.
Apoi, termenul de pe poziția n+1 este 1, mai mari decât el avem toți termenii de la 2, 4, 6, ..., 2n (din stânga lui 1), deci avem n termeni mai mari decât 1.
Apoi, termenul de pe poziția n+2 este 3, mai mari decât el avem toți termenii de la 4, 6, ..., 2n (din stânga lui 3), deci avem n -- 1 termeni mai mari decât 3.
...
Termenul de pe poziția 2n este 2n -- 1, mai mare decât el este doar 2n (din stânga lui 2n -- 1), deci avem un termen mai mare decât 2n -- 1.
Adunăm toate aceste valori: 0 + 0 + 0 + ... + 0 + n + n -- 1 + n -- 2 + ... + 1 = n*(n + 1)/2, unde 0 apare de n ori.
Suma este deci n(n + 1)/2, deci --1 la această putere (adică signatura permutării α) este:
Dacă n = 4k, cu k număr natural nenul, atunci n(n+1)/2 este par, deci permutarea este pară.
Dacă n = 4k+1, cu k număr natural nenul, atunci n(n+1)/2 este impar, deci permutarea este impară.
Dacă n = 4k+2, cu k număr natural nenul, atunci n(n+1)/2 este impar, deci permutarea este impară.
Dacă n = 4k+3, cu k număr natural nenul, atunci n(n+1)/2 este par, deci permutarea este pară.
Ai un model complet explicat, deci ai putea acum să încerci chiar tu să rezolvi problema pentru permutarea β. Spor la treabă !
Green eyes.
Pentru permutarea α, numărul de inversiuni se calculează așa: pe a doua linie, iau fiecare termen de la stânga la dreapta, începând cu al doilea și număr câți termeni sunt mai mari decât cel analizat, termeni aflați la stânga termenului analizat.
Al doilea termen este 4, în stânga lui numărul de termeni mai mari decât el este 0.
Al treilea termen este 6, în stânga lui numărul de termeni mai mari decât el este tot 0.
Al patrulea termen este 8, în stânga lui numărul de termeni mai mari decât el este tot 0.
...
Termenul 2n este termenul de pe poziția n, în stânga lui nici un termen nu este mai mare decât 2n, deci numărul de termeni este tot 0.
Apoi, termenul de pe poziția n+1 este 1, mai mari decât el avem toți termenii de la 2, 4, 6, ..., 2n (din stânga lui 1), deci avem n termeni mai mari decât 1.
Apoi, termenul de pe poziția n+2 este 3, mai mari decât el avem toți termenii de la 4, 6, ..., 2n (din stânga lui 3), deci avem n -- 1 termeni mai mari decât 3.
...
Termenul de pe poziția 2n este 2n -- 1, mai mare decât el este doar 2n (din stânga lui 2n -- 1), deci avem un termen mai mare decât 2n -- 1.
Adunăm toate aceste valori: 0 + 0 + 0 + ... + 0 + n + n -- 1 + n -- 2 + ... + 1 = n*(n + 1)/2, unde 0 apare de n ori.
Suma este deci n(n + 1)/2, deci --1 la această putere (adică signatura permutării α) este:
Dacă n = 4k, cu k număr natural nenul, atunci n(n+1)/2 este par, deci permutarea este pară.
Dacă n = 4k+1, cu k număr natural nenul, atunci n(n+1)/2 este impar, deci permutarea este impară.
Dacă n = 4k+2, cu k număr natural nenul, atunci n(n+1)/2 este impar, deci permutarea este impară.
Dacă n = 4k+3, cu k număr natural nenul, atunci n(n+1)/2 este par, deci permutarea este pară.
Ai un model complet explicat, deci ai putea acum să încerci chiar tu să rezolvi problema pentru permutarea β. Spor la treabă !
Green eyes.
Alte întrebări interesante