Kezdőlap


Feladat:	447. matematika feladat	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Bártfai P. , Csáki E. , Deseő Z. , Gyapjas F. , Kántor S. , Németh László , Németh Lehel , Pergel J. , Rockenbauer Magda , Rozsondai B. , Szabó J. , Tomor B. , Veszprém, Lovassy g. szakköre
Füzet:	1952/december, 151 - 152. oldal		PDF \| MathML
Témakör(ök):	Kombinatorikai leszámolási problémák, Permutációk, Feladat
Hivatkozás(ok):	Feladatok: 1952/április: 447. matematika feladat

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

a) Kiindulunk az 12 és 21 csoportból. Beiktatjuk a 3-at rendre a harmadik, második és első helyre, nyerjük a következő hat csoportot:

\begin{matrix} 123 & 132 & 312 & 213 & 231 & 321 \end{matrix}

Most sorban minden egyes csoportba beiktatjuk a 4-et rendre a negyedik, harmadik, második és első helyre:

\begin{matrix} 1234 & 1324 & 3124 & 2134 & 2314 & 3214 \\ 1243 & 1342 & 3142 & 2143 & 2341 & 3241 \\ 1423 & 1432 & 3412 & 2413 & 2431 & 3421 \\ 4123 & 4132 & 4312 & 4123 & 4231 & 4321 \end{matrix}

b) I. Legyen adott az

1, 2, ..., n

elemeknek egy permutációs füzete. Jelöljük

k_{1}

-gyel, azon elemek számát, amelyeket a 2 elem megelőz (tehát

k_{1} = 0

vagy 1, aszerint, amint 2 nem előzi meg a nálánál alacsonyabb rangú elemet, az 1-et, vagy megelőzi),

k_{2}

jelölje azon elemek számát, amelyeket a 3 megelőz

(0 \leq k_{2} \leq 2)

...

s. í. t.

...

k_{n - 1}

jelölje azon elemek számát, amelyeket az

n

megelőz

(0 \leq k_{n - 1} \leq n - 1)

.
Ha

k_{1} = 1

, akkor füzetünket megelőzték az összes olyan füzetek, amelyekben

k_{1} = 0

. Ez utóbbiak száma (valamint az előbbiek száma is) nyilván az összes permutációk fele, vagyis

n! / 2 \cdot k_{2}

lehet 0, 1, 2. A füzetek száma minden egyes esetben ugyanannyi, vagyis

n!

-nek a harmadrésze és így tovább.
Tehát ha a megadott füzetet jellemző

k_{1}, k_{2}, ..., k_{n - 1}

számokat meghatároztuk, akkor a füzet keresett rangszáma

\begin{matrix} N = k_{1} \frac{n!}{2} + k_{2} \cdot \frac{n!}{3} + k_{3} \frac{n!}{4} + ... + k_{n - 1} \frac{n!}{n!} + 1. \end{matrix}

Jelen esetünkben

\begin{matrix} n = 7 és k_{1} = 0, k_{2} = 2, k_{3} = 2, k_{4} = 4, k_{5} = 0, k_{6} = 2 \end{matrix}

és így

\begin{matrix} N = 0 \cdot \frac{7!}{2!} + 2 \cdot \frac{7!}{3!} + 2 \frac{7!}{4!} + 4 \frac{7!}{5!} + 0 \cdot \frac{7!}{6!} + 2 \frac{7!}{7!} + 1 = \\ = 2 \cdot 840 + 2 \cdot 210 + 4 \cdot 42 + 2 + 1 = 2271. \end{matrix}

II. Ha

k_{1}, k_{2}, ..., k_{n - 1}

-gyel jelöljük azon elemek számát, amelyeket a megadott füzetben az első, második,

...

n - 1

-edik helyen álló elem megelőz, akkor (L. IV. kötet 2. sz. 38. oldalt)

\begin{matrix} N = k_{1} (n - 1)! + k_{2} (n - 2)! + ... + k_{n - 1} \cdot 1! + 1. \end{matrix}

Jelen esetben

\begin{matrix} n = 7, k_{1} = 4, k_{2} = 2, k_{3} = 2, k_{4} = 0, k_{5} = 2, k_{6} = 0, \end{matrix}

és így

\begin{matrix} N = 4 \cdot 6! + 2 \cdot 5! + 2 \cdot 4! + 0 \cdot 3! + 2 \cdot 2! + 0 \cdot 1! + 1 = \\ = 2880 + 240 + 48 + 4 + 1 = 3173. \end{matrix}

Németh László (Gyula, Erkel F. g. IV. o. t.)