Úloha 1.3: Počet zobrazení M do N

[mareksuppa]

Úloha 1.3. Nech $M$, $N$ sú konečné množiny, $M$ má $m$ prvkov a $N$ má $n$ prvkov. Koľko existuje zobrazení množiny $M$ do množiny $N$?

------

Každý z $m$ prvkov množiny $M$ sa môže zobraziť do $n$ prvkov z množiny $N$. Teda počet zobrazení množiny $M$ do množiny $N$ bude $m^n$.

[Martin Sleziak]

Každý z $m$ prvkov množiny $M$ sa môže zobraziť do $n$ prvkov z množiny $N$. Teda počet zobrazení množiny $M$ do množiny $N$ bude $m^n$.

Toto zrejme nebude dobre. Napríklad keď je množina $N$ jednoprvková, tak bude existovať jediné zobrazenie, konkrétne to bude konštantné zobrazenie; lebo mám jedinú možnosť kam sa prvky z $N$ dajú zobraziť.
Ale vám by vyšlo, že existuje $m^1=m$ zobrazení.
(BTW nezaškodilo by odpoveď aj nejako zdôvodniť - aspoň stručne. Keď by ste sa pokúsili vysvetliť, prečo má vyjsť práve taký výsledok, ako tvrdíte, tak by ste zrejme narazili na to, kde je vo vašom argumente problém.)

[mareksuppa]

Toto zrejme nebude dobre. Napríklad keď je množina $N$ jednoprvková, tak bude existovať jediné zobrazenie, konkrétne to bude konštantné zobrazenie; lebo mám jedinú možnosť kam sa prvky z $N$ dajú zobraziť.

Máte pravdu, dobre to určite nieje.

Len pre správnosť, nemysleli ste v druhej časti vety množinu $M$?

(BTW nezaškodilo by odpoveď aj nejako zdôvodniť - aspoň stručne. Keď by ste sa pokúsili vysvetliť, prečo má vyjsť práve taký výsledok, ako tvrdíte, tak by ste zrejme narazili na to, kde je vo vašom argumente problém.)

Máte znova pravdu, pokúsim sa o to aspoň teraz.

Môj prístup k tejto úlohe bol taký, že som si ju predstavil ako počet možností na vybratie hesla (množiny $M$) dĺžky $m$, pričom toto heslo sa môže skladať z $n$ znakov (prvkov množiny $N$) a tieto znaky sa môžu opakovať.

Pre každý z $m$ znakov hesla (množiny $M$) existuje $n$ znakov (prvkov množiny $N$), ktoré môže obsahovať. Z pohľadu kombinatoriky ide o variácie $m$-tej triedy z $n$ prvkov s opakovaním. Počet zobrazení množiny $M$ do množiny $N$ (možností vytvorenia hesla) teda bude $n^m$.

V mojom poslednom príspevku som pravdepodobne pre neskoršiu večernú hodinu prehodil poradie $m$ a $n$. Ďakujem za Vašu pripomienku. Aj keď phpBB fórum dovoľuje predchádzajúce príspevky upravovať, zrejme bude mať z pedagogického uhla pohľadu väčší zmysel, ak sa môj predchádzajúci príspevok nezmení.

[Martin Sleziak]

Len pre správnosť, nemysleli ste v druhej časti vety množinu $M$?

Áno, je to tak ako píšete.

K zdôvodneniu ešte doplním (len kvôli tomu, že si to je dobré uvedomiť) jednu drobnosť. Správne ste povedali, že na každom mieste máme $n$ možností výberu. Každý výber nám dáva zobrazenie a obrátene každému zobrazeniu zodpovedá nejaký takýto výber. Dôležité je však aj to, že na každej pozícii výber prvku nezávislý od toho, čo sme vybrali na iných pozíciach. (Napríklad ak by úloha znela vyrátať počet injektívnych zobrazení, tak by sme museli uvažovať inak. Ak sme niektorý prvok zvolili ako obraz jedného prvku, už ho nesmieme využiť na inej pozícii.)

Z tejto úlohy tiež vidíme, že (prinajmenšom v kombinatorických kontextoch a v diskrétnej matematike) má zmysel definovať $0^0=1$. Viac o tom, ako definujeme $0^0$ a prečo to tak robíme si môžete prečítať napríklad na MSE: Zero to the zero power - Is $0^0=1$?

Značím si za túto úlohu 1 bod.