Jak najít počet kombinací: Diskrétní matematika, Kombinatorika, Teorie čísel

Kombinatorika je obor matematiky věnovaný řešení problémů výběru a uspořádání prvků určité množiny podle daných pravidel. Kombinatorika studuje kombinace a permutace objektů, uspořádání prvků, které mají specifikované vlastnosti. Častou otázkou v kombinatorických úlohách je: kolika způsoby….

Kombinatorické problémy také zahrnují problémy s konstrukcí magických čtverců, problémy s dekódováním a kódováním.

Zrod kombinatoriky jako oboru matematiky je spojen s pracemi velkých francouzských matematiků 17. století Blaise Pascala (1623–1662) a Pierra Fermata (1601–1665) o teorii hazardu. Tyto práce obsahovaly principy pro určování počtu kombinací prvků konečné množiny. Od 50. let 20. století se díky prudkému rozvoji kybernetiky obnovuje zájem o kombinatoriku.

Základní pravidla kombinatoriky jsou pravidlo součtu и pravidlo funguje.

Pokud lze vybrat nějaký prvek A n způsoby a prvek B lze vybrat m způsoby, pak lze provést volbu „buď A nebo B“. n + m způsobem.

Například, pokud je na talíři 5 jablek a 6 hrušek, pak lze jedno ovoce vybrat na 5 + 6 = 11 způsobů.

Pokud lze vybrat prvek A n způsoby a prvek B lze vybrat m metod, pak lze vybrat pár A a B n • m způsobem.

Pokud jsou například 2 různé obálky a 3 různé známky, můžete si vybrat obálku a známku 6 způsoby (2 • 3 = 6).

Pravidlo součinu platí také při zvažování prvků několika sad.

Pokud jsou například 2 různé obálky, 3 různé známky a 4 různé pohlednice, můžete si vybrat obálku, známku a pohlednici 24 způsoby (2 • 3 • 4 = 24).

Součin všech přirozených čísel od 1 do n včetně se nazývá n – faktoriál a značí se symbolem n!

Například 5! = 1 • 2 • 3 • 4 • 5 = 120.

Považuje se za 0! rovný 1.
Počet permutací z n je n!

Pokud jsou například 3 kuličky – červená, modrá a zelená, můžete je dát do řady 6 způsoby (3 • 2 • 1 = 3! = 6).

Někdy se kombinatorický problém řeší konstrukcí dřevo možné možnosti.

Vyřešme například předchozí úlohu o 3 koulích stavbou stromu.

Workshop na řešení úloh v kombinatorice.

1. Ve váze je 6 jablek, 5 hrušek a 4 švestky. Kolik možností je pro výběr jednoho ovoce?

2. Kolik možností je ke koupi jedné růže, pokud prodávají 3 šarlatové, 2 šarlatové a 4 žluté růže?

3. Z města A do města B vede pět silnic a z města B do města C tři silnice. Kolik cest přes B vede z A do C?

4. Kolika způsoby můžete vytvořit dvojici jedné samohlásky a jedné souhlásky slova „šátek“?

samohlásky: a, o – 2 ks.
souhlásky: p, l, t, k – 4 ks.

2 • 4 = 8

odpověď

: 8 způsobů.

5. Kolik tanečních párů lze sestavit z 8 chlapců a 6 dívek?

6. V jídelně jsou 4 první chody a 7 druhých chodů. Kolik různých variant oběda o dvou chodech si můžete objednat?

Odpověď: 28 možností.

7. Kolik různých dvouciferných čísel lze vytvořit z čísel 1, 4 a 7, pokud se čísla mohou opakovat?

1 číslice – 3 způsoby
2 číslice – 3 způsoby
3 číslice – 3 způsoby

3 • 3 = 9

odpověď

: 9 různých dvoumístných čísel.

8. Kolik různých trojciferných čísel lze vytvořit z čísel 3 a 5, lze-li čísla opakovat?

1 číslice – 2 způsoby
2 číslice – 2 způsoby
3 číslice – 2 způsoby

2 • 2 • 2 = 8

odpověď

: 8 různých čísel.

9. Kolik různých dvouciferných čísel lze sestavit z číslic 0, 1, 2, 3, lze-li číslice opakovat?

1 číslice – 3 způsoby
2 číslice – 4 způsoby

3 • 4 = 12

odpověď

: 12 různých čísel.

10. Kolik je trojciferných čísel, ve kterých jsou všechny cifry sudé?

Sudá čísla – 0, 2, 4, 6, 8.

1 číslice – 4 způsoby
2 číslice – 5 způsobů
3 číslice – 5 způsobů

4 • 5 • 5 = 100

odpověď

: Existuje 100 čísel.

11. Kolik je sudých trojciferných čísel?

1 číslice – 9 způsobů (1, 2, 3, 4, 5, 6, 7, 8, 9)
2. číslice – 10 způsobů (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
3. číslice – 5 způsobů (0, 2, 4, 6, 8)

9 • 10 • 5 = 450

odpověď

: Existuje 450 čísel.

12. Kolik různých trojciferných čísel lze sestavit ze tří různých číslic 4, 5, 6?

1 číslice – 3 způsoby
2 číslice – 2 způsoby
3. číslice – 1. způsob

3 • 2 • 1 = 6

odpověď

: 6 různých čísel.

13. Kolika způsoby můžete označit vrcholy trojúhelníku pomocí písmen A, B, C, D?

1 top – 4 způsoby
2 top – 3 způsoby
3 top – 2 způsoby

4 • 3 • 2 = 24

odpověď

: 24 způsobů.

14. Kolik různých trojciferných čísel lze sestavit z číslic 1, 2, 3, 4, 5 za předpokladu, že se ani jedna číslice neopakuje?

1 číslice – 5 způsobů
2 číslice – 4 způsoby
3 číslice – 3 způsoby

5 • 4 • 3 = 60

odpověď

: 60 různých čísel.

15. Kolik různých trojciferných čísel menších než 400 lze sestavit z číslic 1, 3, 5, 7, 9, lze-li kteroukoli z těchto číslic použít pouze jednou?

1 číslice – 2 způsoby
2 číslice – 4 způsoby
3 číslice – 3 způsoby

2 • 4 • 3 = 24

odpověď

: 24 různých čísel.

16. Kolika způsoby lze vyrobit vlajku sestávající ze tří vodorovných pruhů různých barev, pokud je materiál šesti barev?

1 pruh – 6 cest
2 pruh – 5 cest
3 pruhy – 4 cesty

6 • 5 • 4 = 120

odpověď

: 120 způsobů.

17. Ze třídy je vybráno 8 lidí s nejlepšími běžeckými výsledky. Kolika způsoby mohou vytvořit tým tří lidí, aby se zúčastnili štafetového závodu?

1 osoba – 8 způsobů
2 osoba – 7 způsobů
3 osoba – 6 způsobů

8 • 7 • 6 = 336

odpověď

: 336 způsobů.

18. Ve čtvrtek v první třídě by měly být čtyři vyučovací hodiny: psaní, čtení, matematika a tělesná výchova. Kolik různých možností rozvrhu můžete pro tento den vytvořit?

1 lekce – 4 způsoby
2 lekce – 3 způsoby
3 lekce – 2 způsoby
Lekce 4 – metoda 1

4 • 3 • 2 • 1 = 24

odpověď

: 24 možností.

19. V páté třídě se studuje 8 předmětů. Kolik různých možností rozvrhu lze vytvořit na pondělí, pokud by v tento den mělo být 5 lekcí a všechny lekce jsou jiné?

1 lekce – 8 možností
2 lekce – 7 možností
3 lekce – 6 možností
4 lekce – 5 možností
Lekce 5 – 4 možnosti

8 • 7 • 6 • 5 • 4 = 6720

odpověď

: 6720 možností.

20. Kód trezoru se skládá z pěti různých čísel. Kolik různých možností pro vytvoření šifry?

1 číslice – 5 způsobů
2 číslice – 4 způsoby
3 číslice – 3 způsoby
4 číslice – 2 způsoby
5. číslice – 1. způsob

5 • 4 • 3 • 2 • 1 = 120

odpověď

: 120 možností.

21. Kolika způsoby lze usadit 6 osob ke stolu se 6 příbory?

6 • 5 • 4 • 3 • 2 • 1 = 720

odpověď

: 720 způsobů.

22. Kolik sedmimístných telefonních čísel lze vytvořit, pokud vyloučíte čísla začínající nulou a 9?

1 číslice – 8 způsobů
2 číslice – 10 způsobů
3 číslice – 10 způsobů
4 číslice – 10 způsobů
5 číslice – 10 způsobů
6 číslice – 10 způsobů
7 číslice – 10 způsobů

8 • 10 • 10 • 10 • 10 • 10 • 10 = 8.000.000 XNUMX XNUMX

odpověď

: 8.000.000 možností.

23. Telefonní ústředna slouží účastníkům, jejichž telefonní čísla se skládají ze 7 číslic a začínají 394. Pro kolik účastníků je tato stanice určena?

Telefonní číslo 394

10 • 10 • 10 • 10 = 10.000

odpověď

: 10.000 XNUMX odběratelů.

24. K dispozici je 6 párů rukavic různých velikostí. Kolika způsoby si z nich lze vybrat jednu rukavici pro levou ruku a jednu pro pravou ruku, aby byly tyto rukavice různých velikostí?

Levé rukavice – 6 způsobů
Pravé rukavice – 5 způsobů (6. rukavice má stejnou velikost jako levá)

6 • 5 = 30

odpověď

: 30 způsobů.

25. Čísla 1, 2, 3, 4, 5 tvoří pětimístná čísla, ve kterých jsou všechny číslice různé. Kolik takových sudých čísel existuje?

5. číslice – 2 způsoby (dvě sudé číslice)
4 číslice – 4 způsoby
3 číslice – 3 způsoby
2 číslice – 2 způsoby
1. číslice – 1. způsob

2 • 4 • 3 • 2 • 1 = 48

odpověď

: 48 sudých čísel.

26. Kolik je čtyřciferných čísel složených z lichých číslic dělitelných 5?

Lichá čísla – 1, 3, 5, 7, 9.
Z toho se dělí na 5 – 5.

4 číslice – 1 cesta (číslice 5)
3 číslice – 4 způsoby
2 číslice – 3 způsoby
1 číslice – 2 způsoby

1 • 4 • 3 • 2 = 24

odpověď

: 24.

27. Kolik je pěticiferných čísel, ve kterých je třetí číslice 7 a poslední číslice sudá?

1 číslice – 9 způsobů (všechny kromě 0)
2 číslice – 10 způsobů
3 číslice – 1 cesta (číslice 7)
4 číslice – 10 způsobů
5. číslice – 5 způsobů (0, 2, 4, 6, 8)

9 • 10 • 1 • 10 • 5 = 4500

odpověď

: 4500 čísel.

28. Kolik je šesticiferných čísel, z nichž druhá číslice je 2, čtvrtá je 4, šestá je 6 a všechna ostatní jsou lichá?

1 číslice – 5 možností (od 1, 3, 5, 7, 9)
2 číslice – 1 možnost (číslice 2)
3. číslice – 5 možností
4 číslice – 1 možnost (číslice 4)
5. číslice – 5 možností
6 číslice – 1 možnost (číslice 6)

5 • 1 • 5 • 1 • 5 • 1 = 125

odpověď

: 125 čísel.

29.Kolik různých čísel menších než milion lze zapsat pomocí čísel 8 a 9?

Jednotlivé číslice – 2
Dvoumístné – 2 • 2 = 4
Trojciferná čísla – 2 • 2 • 2 = 8
Čtyřmístné – 2 • 2 • 2 • 2 =16
Pětimístná čísla – 2 • 2 • 2 • 2 • 2 = 32
Šestimístná čísla – 2 • 2 • 2 • 2 2 • 2 = 64

Pouze

: 2 + 4 + 8 + 16 + 32 + 64 = 126

odpověď

: 126 čísel.

30. Ve fotbalovém týmu je 11 lidí. Musíte si vybrat kapitána a jeho zástupce. Kolika způsoby to lze provést?

Kapitán – 11 způsobů
Zástupce – 10 způsobů

11 • 10 = 110

odpověď

: 110 způsobů.

31.Ve třídě je 30 lidí. Kolika způsoby si můžete vybrat ředitele a osobu odpovědnou za jízdenky?

Headman – 30 způsobů
Odpověď. pro vstupenky – 29 způsobů

30 • 29 = 870

odpověď

: 870 způsobů.

32. Výletu se účastní 12 chlapců, 10 dívek a 2 učitelé. Kolik možností pro skupiny tří osob ve službě (1 chlapec, 1 dívka, 1 učitel) lze vytvořit?

12 • 10 • 2 = 240

odpověď

: 240 způsobů.

33. Kolik kombinací čtyř písmen ruské abecedy (v abecedě je pouze 33 písmen) lze vytvořit za předpokladu, že se 2 sousední písmena liší?

1 písmeno – 33 způsobů
2 písmeno – 32 způsobů
3 písmeno – 32 způsobů
4 písmeno – 32 způsobů

33 • 32 • 32 • 32 = 1.081.344

odpověď

: 1.081.344 XNUMX XNUMX kombinací.

Pokud chcete položit novou otázku, nepřidávejte ji do existujícího tématu, ale vytvořte novou v kořenové sekci „Pomozte mi vyřešit/pochopit (M)“.

Pokud položíte novou otázku v existujícím tématu, pak pokud porušíte formát nebo jiná pravidla fóra, vaše zpráva a všechny odpovědi na ni mohou být bez varování smazány.

Nehledejte na tomto fóru zadarmo, pravidla zakazují účastníkům zveřejňovat hotová řešení standardních vzdělávacích problémů. Autor otázky musí uvést své pokusy o řešení a uvést konkrétní potíže.

Nezapomeňte si přečíst téma Pravidla této části, jinak může být vaše téma smazáno nebo přesunuto do karantény a nikdy nebudete vědět proč.

Jak najít počet kombinací

Na stránku 1 , 2 Další

Jak najít počet kombinací
13.01.2010, 11: 24

Naposledy upravil nill 13.01.2010, 11:39, celkem upraveno 1krát.

Tohle není učebnicový problém, ale problém pro skutečně funkční program.

Existuje pole požadovaných kombinací, každá kombinace obsahuje DVA prvky, z pole se vybírá vždy 1 kombinace, existuje 9 pokusů.

Musíte zjistit počet kombinací pro každý pokus.

1) Pro první pokus je počet kombinací roven počtu prvků v poli požadovaných kombinací

2) Pro druhý a další pokusy je potřeba provést úplný výčet, tj. pokud je v poli požadovaných kombinací 16 prvků, tak nejprve vzít první prvek a spočítat, kolik požadovaných prvků v poli zbývá, pak druhý a tak dále.
to znamená, že pro výpočet počtu kombinací ve dvou pokusech je potřeba provést 16 * 16 výpočtů a pokud je například v poli více než 1000 prvků a 9 pokusů, pak je to 1000 * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 * 1000 výpočtů a myslím si, že žádný superpočítač se s tímto úkolem v reálném čase nevyrovná.

Proto se nabízí otázka: existuje nějaký vzorec pro zjednodušení těchto výpočtů?

Díval jsem se na faktoriál, ale ten se počítá pouze pro celá čísla a vše se dá snadno vypočítat pouze tehdy, pokud je například počet potřebných kombinací v poli 28 a počet různých prvků, které tyto kombinace tvoří, je 8, tedy k nalezení počtu kombinací ve dvou pokusech potřebujete 8! * 6! = 420, ve třech 8! * 6! * 4! = 2520

To znamená, že pokud existuje něco založené na faktoriálu, ale ne na celých číslech, pak si myslím, že problém je velmi snadno vyřešitelný.
Pokud víte, že to nelze v žádném případě vyřešit jinak než úplným vyzkoušením, dejte mi prosím vědět, protože s tímto problémem se potýkám už velmi dlouho.

Re: Jak zjistit počet kombinací
13.01.2010, 11: 31

Vážený člen

Naposledy upravil meduza 13.01.2010. ledna 11 v 34:1, celkem upraveno XNUMXkrát.

Pro začátek dejte čárky, to se nedá číst. A vysvětlete, o jaké “kombinace” se jedná. Zkrátka druhá věta není jasná (alespoň pro mě).

Re: Jak zjistit počet kombinací
13.01.2010, 11: 32

Vážený člen

Mluvím jen o faktoriálu.
Existuje Stirlingův vzorec. Lze jej použít na neceločíselné hodnoty argumentu. To znamená, že se ve skutečnosti ukáže jako „faktoriál“ libovolného čísla.

Re: Jak zjistit počet kombinací
13.01.2010, 11: 50

No, tady je skutečný příklad

existuje pole 16 kombinací, které se skládají z čísel od 1 do 8

1) 1 – 5
2) 1 – 6
3) 1 – 7
4) 1 – 8
5) 2 5 – XNUMX XNUMX
6) 2 – 6
7) 2-7
8) 2-8
9) 3-5
10) 3-6
11) 3-7
12) 3-8
13) 4-5
14) 4-6
15) 4-7
16) 4-8

1) počet kombinací na první pokus je 16

2) počet kombinací při druhém pokusu je 16*9=144

Toto je velmi jednoduchý případ, protože při výběru jakéhokoli prvku stále existuje 9 možných možností.

Takže potřebuji vzorec, jak nějak získat toto číslo 9, aniž bych musel procházet všechny možné možnosti (ve většině případů to samozřejmě nebude celé číslo).

Re: Jak zjistit počet kombinací
13.01.2010, 14: 25

Vážený člen

nic
Stále není jasné, co chcete. Zkuste podrobně popsat postup extrakce.

Let — spousta kombinací. Musíte určit, kolik různých devítek existuje Můžeš to vytáhnout v 9 pokusech?

— St 13. ledna 2010 15:31:17 —

Tady je tvůj příklad. Já jsem to pochopil takto. Vzali z 16 prvků. 1 z 16 vytáhneme 16 způsoby. Vytáhli jsme. Zbývá 15. A odkud se pak vzalo 9? Nebo 144? Vytáhneme 2 různé prvky z bez ohledu na pořadí je to možné -tými způsoby. Můžete vytáhnout 2 různé prvky s ohledem na pořadí – různými způsoby. Vezměte 2 prvky, případně identické, bez ohledu na pořadí, můžete – různými způsoby. Odkud pochází číslo 144?

Re: Jak zjistit počet kombinací
13.01.2010, 14: 40
Citace:
Vylosujte 1 z 16 16 způsoby. Vylosováno. Zbývá 15.

nezbývá jich 15, ale přesně 9
to znamená, že pokud odstraníte první prvek z pole, pak bude nemožné vybrat možnosti, které obsahují buď 1, nebo 5.

a ukázalo se, že zbývá ještě 9 možností

a pokud počítáte pro každý ze 16 prvků
pak dostaneme 1*9*16=144

Doufám, že je teď všechno jasné

Re: Jak zjistit počet kombinací
13.01.2010, 14: 59

Vážený člen

Nic, chápu. Zkusím to formulovat.
Let — tato sada kombinací. Na -a v tomto kroku vybereme nějaký pár a my počítáme Je to rovno bez všech párů obsahujících prvky nebo . Nech to být Pak musíme najít ( — počet pokusů) (odhad shora, zdola). Navíc musí být nalezen pro libovolnou posloupnost vylosovaných dvojic .

Pokud ano, tak z hlavy: problém je složitý, musíte alespoň hádat, jak by se dal uspořádat. , jinak je to příliš mnoho. I když se můžete pokusit najít odhady shora.
Zde máte ve svém příkladu — Kartézský součin. Pokud by tedy v obecném případě bylo , a . Pak a pak pro počet pokusů o kombinace bude roven Navíc to nezávisí na posloupnosti. V příkladu .

Jak to máte obecně zařízené?

Je také snadné vypočítat počet kombinací v případě, kdy je sjednocení kartézských součinů s různými prvky. Můžete se pokusit přijít s nějakým optimálním výčtem, abyste minimalizovali počet kombinací.