Kezdőlap


Cím:	Binominális együtthatók közti két összefüggés kombinatorikus értelmezéséről
Szerző(k):	Svédné Wachsberger Márta
Füzet:	1938/február, 161 - 162. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Ismeretes a binomiális együtthatók között a következő összefüggés:

\begin{matrix} (\binom{n}{0}) + (\binom{n}{1}) + (\binom{n}{2}) + ... + (\binom{n}{n - 1}) + (\binom{n}{n}) = 2^{n} . \end{matrix}

Ennek bizonyítását egyszerűen nyerhetjük, ha

{(1 + x)}^{n}

kifejtésében

x = 1

-et teszünk. Ha pedig az

\begin{matrix} {(1 + x)}^{n} = (\binom{n}{0}) + (\binom{n}{1}) x + (\binom{n}{2}) x^{2} + ... + (\binom{n}{n}) x^{n} \end{matrix}

egyenlet mindkét oldalát

x

szerint differeciáljuk és

x

helyébe

1

-et helyettesítünk, akkor

\begin{matrix} 1 (\binom{n}{1}) + 2 (\binom{n}{2}) + ... + n (\binom{n}{n}) = n \cdot 2^{n - 1} \end{matrix}

összefüggéshez jutunk.
Ennek a két összefüggésnek kombinatórikus értelmét óhajtjuk megvilágítani.

(\binom{n}{k})

jelenti az

n

elemből alkotható

k

-ad osztályú ismétlés nélküli kombinációk számát; azaz megadja, hányféleképpen választhatunk ki az

n

elemből

k

elemet. Ezt a kiválasztást úgy valósíthatjuk meg, hogy felírjuk sorban az összes elemeket és azoknak, melyeket kiválasztunk, ,,1'' szimbólumot, amelyeket pedig nem választunk ki, ,,0'' szimbólumot adunk. Így pl. 5 elem összes másodosztályú kombinációit a következő módon jellemezhetjük:

\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{matrix}

Ilyen módon 2 elemnek 5-öd osztályú ismétléses variációi keletkeztek,

(\binom{5}{2})

számban. Hasonlóképpen járhatunk el, ha az 5 elem összes 3-ad osztályú kombinációit akarjuk megvalósítani s í. t. Az 5 elem minden egyes kombinációjának megfelel 2 elemnek. ‐ t. i. 1 és 0 ‐ valamely 5-öd osztályú ismétléses variációja és viszont: az

(1

0)

elemek bármely 5-öd osztályú ismétléses variációjához tartozik az 5 elemből alkotható valamelyik ismétlés nélküli kombináció, azaz a

\begin{matrix} \sum_{i = 0}^{5} C_{5}^{i} = (\binom{5}{0}) + (\binom{5}{1}) + (\binom{5}{2}) + (\binom{5}{3}) + (\binom{5}{4}) + (\binom{5}{5}) \end{matrix}

számú kombinációk és

2^{5}

számú ismétléses variációk között egyértelmű vonatkozás áll fenn.
[Az

(\binom{5}{0})

számú kombinációnak megfelel a

\begin{matrix} 0, 0, 0, 0, 0 \end{matrix}

variáció].
Már most általában: az

(\binom{n}{0}) + (\binom{n}{1}) + ... + (\binom{n}{n})

összeg jelenti az

n

elemből alkotható összes kombinációk számát. Ez a szám tehát annyi lesz, ahányféle módon az 1-eseket és 0-kat elhelyezhetjük az

n

helyen. Ez azonban az

(1

0)

elemeknek

n

-ed osztályú ismétléses variációit jelenti, tehát számuk:

2^{n}

.
Képzeljük most már felírva az ilyen formában előállított kombinációkat és adjuk össze a sémában szereplő számokat. Ekkor

(\binom{n}{1})

csoportban egy 1-es szerepel, a többi szám 0, ezeknek összege tehát:

(\binom{n}{1}) 1

;

(\binom{n}{2})

csoport mindegyikében két 1-es szerepel, ezeknek összege:

(\binom{n}{2}) 2

;

(\binom{n}{k})

csoportban

k

darab

1

-es, ezeknek összege

(\binom{n}{k}) k

s. í. t. Ha tehát mindegyiket összeadjuk, akkor eredményül

\begin{matrix} 1 (\binom{n}{1}) + 2 (\binom{n}{2}) + ... + k (\binom{n}{k}) + ... + n (\binom{n}{n}) \end{matrix}

összeget nyerjük.
Másrészt világos, hogy ha az összes csoportokat felírjuk, azokban ugyanannyi 0 szerepel összesen, mint 1-es, hiszen két elem összes

n

-ed osztályú ismétléses variációiban mindegyik elem egyformán szerepel. A sémában a sorok száma összesen

2^{n}

, mindegyikben

n

szám szerepel, tehát az összesen szereplő számok száma

n \cdot 2^{n}

. Ezeknek a fele lesz 1-es, értékük tehát:

\begin{matrix} \frac{n \cdot 2^{n}}{2} = n \cdot 2^{n - 1} . \end{matrix}

Így

1 (\binom{n}{1}) + 2 (\binom{n}{2}) + ... + n (\binom{n}{n}) = n \cdot 2^{n - 1}

Budapest, 1937.

Svédné Wachsberger Márta
leánygimnáziumi tanárnő