Kezdőlap


Feladat:	1272. matematika feladat	Korcsoport: 16-17	Nehézségi fok: -
Megoldó(k):	Barna Tibor , Czinczenheim József , Földesi Tamás , Harsányi János , Holzer Pál , Mandl Béla , Schwartz János , Somogyi Antal , Vajda József
Füzet:	1937/február, 174 - 175. oldal		PDF \| MathML
Témakör(ök):	Összefüggések binomiális együtthatókra, Binomiális együtthatók, Egészrész, törtrész függvények, Kombinatorikai leszámolási problémák, Kombinációk, Feladat
Hivatkozás(ok):	Feladatok: 1936/december: 1272. 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.

I. Megoldás. A szóbanforgó kombinációk között vannak olyanok, amelyekben egy elem sem ismétlődik. Ezek száma $(\binom{n}{k}) = (\binom{k}{o}) (\binom{n}{k})$ .^{$^{*}$}
Vannak köztük olyanok, amelyekben csak egy elem szerepel kétszer. Ezek az $n$ elem $(k - 1)$ -ik osztályú, ismétlés nélküli kombinációiból képezhetők úgy, hogy a kombinációkban szereplő $(k - 1)$ elem egyikét hozzákapcsoljuk. Így az $(\binom{n}{k - 1})$ számú csoport mindegyikéből $(\binom{k - 1}{1})$ új csoport nyerhető, összesen tehát $(\binom{k - 1}{1}) (\binom{n}{k - 1})$ .
Vannak köztük olyanok, amelyekben $2$ elem fordul elő kétszer. Ezek a $(k - 2)$ -ik oszt. ismétlés nélküli kombinációkból képezhetők úgy, hogy a bennük előforduló $(k - 2)$ elemből két-két elemet csatolunk hozzájuk. Így az $(\binom{n}{k - 2})$ számú csoport mindegyikből $(\binom{k - 2}{2})$ új csoport nyerhető, összesen tehát $(\binom{k - 2}{2}) (\binom{n}{k - 1})$ .
Általában nézzük azokat a csoportokat, amelyekben éppen $r$ számú elem fordul elő kétszer, tehát $2 r ≦ k$ .
Az ilyen csoportokat a $(k - r)$ oszt. ismétlés nélküli kombinációkból képezhetjük úgy, hogy a bennük előforduló $(k - r)$ elemből kiválasztunk $r$ elemet és ezeket csatoljuk hozzájuk. Így a $(\binom{n}{k - r})$ számú ‐ ismétlés nélküli csoport mindegyikéből $(\binom{k - r}{r})$ új ‐ ismétléses ‐ csoportot nyerünk, amelyben éppen $r$ elem éppen kétszer fordul elő; ezek száma tehát

\begin{matrix} (\binom{k - r}{r}) (\binom{n}{k - r}) . \end{matrix}

Ezen szorzatok értékét kell vennünk és összegeznünk, ha

\begin{matrix} r = 0, 1, 2, ... r \end{matrix}

Eszerint a keresett csoportok száma

\begin{matrix} \sum_{r - 0}^{[\frac{k}{2}]} (\binom{n}{k - r}) (\binom{k - r}{r}) \end{matrix}

ahol

[\frac{k}{2}]

jelenti a

\frac{k}{2}

-ben foglalt legnagyobb egész számot.
Földesi Tamás (Berzsenyi Dániel rg. VIII. o. Bp. V.).

II. Megoldás.

n

elem

k

-ad osztályú ismétléses kombinációk száma:

(\binom{n + k - 1}{k})

.
Ebből a számból ki kell vonnunk azon ismétléses kombinációk számát, melyben egy elem

2

-nél többször szerepel. Ezekben tehát egy elemnek legalább

3

-szor kell szerepelnie; a fennmaradó

k - 3

helyét valamennyi

n

elem

(k - 3)

-ad osztályú ismétléses kombinációi foglalják el. Így tehát egy bizonyos elem

(\binom{n + k - 4}{k - 3})

kombinációban szerepel legalább háromszor. Mivel pedig bármelyik elem szerepelhet ily módon, az így nyert összes kombinációk száma:

n (\binom{n + k - 4}{k - 3})

.
A szóbanforgó csoportok száma eszerint

\begin{matrix} (\binom{n + k - 1}{k}) - n (\binom{n + k - 4}{k - 3}) = \frac{(n - k - 1) (n + k - 2) ... (n + 1) n}{k!} - \\ - \frac{(n + k - 1) (n + k - 2) ... (n + 1) n^{2}}{(k - 3)!} . \end{matrix}

Mandl Béla (Zrinyi Miklós rg. VII. o. Bp. VIII.).

Jegyzet. A két megoldás egybevetéséből következik ezen összefüggés:

\begin{matrix} \sum_{r = 0}^{[\frac{k}{2}]} (\binom{n}{k - r}) (\binom{k - r}{r}) = (\binom{n + k - 1}{k}) - n (\binom{n + k - 4}{k - 3}) . \end{matrix}

^{$^{*}$}

(\binom{k}{o}) = (\binom{k}{k}) = 1