MA 0027 - Diskrétní matematika
(čtena podruhé) Břetislav Fajmon
Verze textu: březen 2024
MA 0027 - Diskrétní matematika
1
Obsah
1 Výuka kombinatoriky na ZS 1
2 Výuka teorie grafů na ZS 1
3 Výuka psti (a statistiky) na ZS 1
4 Středoškolské kategorie kombinatoriky 2
5 Trojúhelníky p(n, k) a S (n, k) 3
6 Rozdělování předmětů do přihrádek 4
Úvod
Tento text je doplňkem semináře MA 0027 z diskrétni matematiky pro magisterské studium učitelství matematiky na ZS.
Břetislav Fajmon, březen 2024
1 Výuka kombinatoriky na ZS
2 Výuka teorie grafů na ZS
3 Výuka psti (a statistiky) na ZS
2
Katedra matematiky PedF MUNI v Brně
4   Středoškolské kategorie kombinatoriky
Návrhy příkladů:
1. Kolika způsoby lze na šachovnici 8x8 rozmístit osm šachových figurek věže tak, aby se žádné dvě věže neohrožovaly? (každá věž ohrožuje každou jinou figurku ve směru vodorovném i směru svislém, a to vpravo i vlevo, nahoře i dole)
2. Kolika způsoby lze rozestavit osm dětí do kruhu?
3. Kolika způsoby lze sestavit jednoduchý náhrdelník z osmi korálků, z nichž každý je jiné barvy než ty ostatní?
4. Kolik existuje navzájem různých injekcí pětiprvkové množiny X do osmiprvkové množiny Yl (prvky obou množin považujeme za rozlišitelné)
5. Kolik existuje navzájem různých bijekcí osmiprvkové množiny X na osmiprvkovou množinu Yl (prvky obou množin považujeme za rozlišitelné)
6. Úloha s vlajkami:
a) Kolik různých vlajek lze sestavit ze tří svislých pruhů navzájem různých barev (záleží na pořadí barev a vlajku nelze nijak obrátit, protože první svislý pruh se připevňuje k žerdi vlajky), jestliže po výběru ve stejném pořadí tyto tři pruhy sešijeme? Vybírat lze z barev žlutá, zelená, modrá, červená, bílá.
b) Kolik různých vlajek za podmínek v (a) obsahuje modrý pruh uprostřed?
c) Kolik různých vlajek za podmínek v (a) obsahuje modrý pruh, bez ohledu na jeho pozici?
7. Je dán pravidelný šestiúhelník a na každé jeho straně tři různé vnitřní body. Kolik trojúhelníků ABC existuje, mají-li mít trojúhelníky vrcholy A,B,C ležící v těchto bodech?
8. V rovině je dáno sedm bodů, z nichž žádné tři neleží na přímce. Kolik přímek je těmito body určeno?
9. Kolik různých dělitelů má číslo 23-55-710? Zkuste zdůvodnit-spočítat kombinatoricky, ne že byste všechny dělitele vypisovali.
10. Tři muži a dvě ženy hledají zaměstnání. Ve městě jsou tři závody, kde berou jen muže, dvě textilní továrny, kde berou jen ženy, a dva závody, kde přijímají muže i ženy. Kolika způsoby se může pětice rozmístit do těchto závodů? (v žádném závodě není omezen počet přijatých, a předpokládejte, že každý závod má zájem o všechny lidi dané kategorie)
11. V dnešní době není neobvyklé namísto jednoho jména dát narozenému dítěti jedno, dvě nebo tři jména. Kolika způsoby lze tímto moderním způsobem pojmenovat jedno dítě, jestliže chceme využít kalendář, který má 300 samostatných (nesložených) jmen?
MA 0027 - Diskrétní matematika
3
12. Další příklady viz jakákoli učebnice-skripta, kde se procvičují středoškolské kombinatorické kategorie.
Návrhy teoretických otázek:
1. Vyslovte kombinatorický princip součtu.
2. Vyslovte kombinatorický princip součinu.
3. Uveďte kombinatorický příklad, v jehož řešení se vyskytuje současně princip součtu i princip součinu. Zdůvodněte pečlivě, proč který princip používáte při řešení.
4. Zdůvodněte vzorec pro variace a uveďte typický příklad na variace, tj, ne na permutace.
5. Zdůvodněte vzorec pro permutace a uveďte typický příklad na permutace.
6. Zdůvodněte vzorec pro permutace s opakováním (opakují se tři a více objektů) a uveďte typický příklad.
7. Zdůvodněte vzorec pro kombinace a uveďte typický příklad.
8. Zdůvodněte vzorec pro kombinace s opakováním a uveďte typický příklad.
9. Dokažte vzorec pro konstrukci Pascalova trojúhelníku - následujícího řádku pomocí předchozího, tj. řádek začíná a končí jedničkou a ostatní hodnoty dopočteme podle vzorce... uveďte tento vzorec a dokažte ho s využitím GRAFICKÉ podpory.
10. Dokažte vzorec pro konstrukci Pascalova trojúhelníku - následujícího řádku pomocí předchozího, tj. řádek začíná a končí jedničkou a ostatní hodnoty dopočteme podle vzorce... uveďte tento vzorec a dokažte ho ALGEBRAICKY - bez využití grafické podpory.
11. Dokažte vzorec pro součet hodnot v n-tém řádku Pascalova trojúhelníku kombinatoricky, pomocí spojitosti s výběrem podmnožin ... napište tento vzorec a zdůvodněte ho.
12. Dokažte binomickou větu kombinatoricky ... zdůvodněte pouze, proč se v rozvoji (a + b)11 vyskytuje člen (1:L) • aa ■ b6.
13. Lze také binomickou větu využít pro důkaz vzorce pro součet hodnot v n-tém řádku Pascalova trojúhelníka? Jak?
5   Trojúhelníky p(n, k) a S(n, k)
Návrhy příkladů:
1. Kolik existuje surjekcí sedmiprvkové množiny na čtyřprvkovou množinu? Nesdělte jen výsledek, ale vyjádřete pomocí určité kombinatorické kategorie-pojmu.
4
Katedra matematiky PedF MUNI v Brně
2. Zadán je fakticky (číselně v zadání) trojúhelník P (n, k), prvních šest řádků - sestavte sami sedmý řádek s využitím jistého vzorce, konkrétně číselně.
3. Zadán je fakticky (číselně v zadání) trojúhelník S(n, k), prvních sedm řádků - sestavte sami osmý řádek s využitím jistého vzorce, konkrétně číselně.
4. Vytvořte prvních pět řádků trojúhelníku (p(n, k)).
5. Vytvořte prvních pět řádků trojúhelníku (S(n, k)). Návrhy teoretických otázek:
1. Dokažte vzorec pro konstrukci trojúhelníku p(n, k) - následujícího řádku pomocí předchozích řádků ... uveďte tento vzorec a dokažte ho.
2. Dokažte vzorec pro konstrukci Stirlingova trojúhelníku druhého druhu, tj. konstrukci následujícího řádku pomocí předchozího ... uveďte tento vzorec a dokažte ho.
3. Vyslovte a dokažte vzorec pro výpočet Bellova čísla Bn+i pomocí předchozích čísel Bn, Bn-i, ...: (dokažte například pro n = 4, tj. B5 = ...)
4. Je zadán pátý řádek Stirlingova trojúhelníka 2. druhu S(5,k) = (1; 15; 25; 10; 1) ... nakreslete Hasseho diagram všech možných rozkladů pětiprvkové množiny na podmnožiny, který se k tomuto řádku vztahuje (nemusíte kreslit celý Hasseho diagram, ale nakreslete aspoň část a naznačte, k čemu se vztahují jednotlivá čísla na daném řádku). Vysvětlete relaci uspořádání, jejíž Hasseho diagram kreslíte.
6   Rozdělování předmětů do přihrádek
Návrhy příkladů:
1. Kolika způsoby lze rozdělit 10 nerozlišitelných předmětů (např. zákusků jednoho druhu) do 5 nerozlišitelných šuplíků (neoznačených jménem, rozházených po zemi - je jedno, zda se např. tři zákusky nacházejí v daném šuplíku nebo nějakém jiném, rozhoduje jen jejich počet).
2. Kolik existuje v N řešení rovnice
X\ + X2 + X3 + X4 = 7,
kde řešení lišící se jen pořadím svých souřadnic nepovažujeme za různá? Nesdělte jen výsledek, ale vyjádřete pomocí určité kombinatorické kategorie-pojmu.
3. Jak se změní počet řešení rovnice v předchozím příkladu, jestliže hledáme xt z množiny No, tj. připouštíme navíc, že některá xt se rovnají nule? Nesdělte jen výsledek, ale vyjádřete pomocí určité kombinatorické kategorie-pojmu.
4. Dalšími příklady mohou být ty, které jsme počítali na cvičení. Měli byste umět použít správný vzorec ze čtyř možných vzorců rozdělování do přihrádek.
MA 0027 - Diskrétní matematika
5
Návrhy teoretických otázek:
1. Rozdělujeme n předmětů do k přihrádek ... kolik různých typů rozdělení máme vzhledem k předmětům rozlišitelným-nerozlišitelným, a jak se vypočte počet daných konfigurací v každém z případů?
Seznam literatury:
(Fuchs, 2011) E. Fuchs: Diskrétní matematika pro učitele. Universitas Masarykiana Brunensis, Brno 2011. Toto je nej důležitější materiál k celému kursu, zde najdete i trojúhelníky všech probíraných kombinatorických kategorií v tabulkách na konci.
(Nešetřil, Matoušek 2000) J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky. Univerzita Karlova, nakl. Karolinum, Praha 2000.
(Lint, Wilson 2001) J.H.van Lint, R.M.Wilson: A Course in Combinatorics. Cambridge 2001, Second Edition.
(UND 2017) Department of Mathematics, University of North Dakota: Discrete Mathematics. Electronic text, Second Corrected Edition 2017.