Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 17. 11. 2013 10:38
Kombinatorika-zakázaná posloupnost prvků.
Dobrý den,
je nějaký pěkný vzoreček pro řešení tohoto problému?
Máme k typů prvků. Počet prvků je pro naše potřeby nepodstatný-buď je nekonečný, nebo je dostačující pro všechny možnosti. Z prvků chceme poskládat řadu dlouhou n prvků. Počet možností zde je tedy n^k.
Co když však máme nějakou zakázanou posloupnost? Například, že za sebou v řadě nesmí být l prvků stejného typu.
Je proto nějaký pěkný vzoreček nebo to musím postupně dopočítat?
Děkuji
(Pokud je proto jednoduchý vzoreček, prosím o návod jak jej odvodit, ne jeho přesné znění.)
Offline
#2 17. 11. 2013 11:19
Re: Kombinatorika-zakázaná posloupnost prvků.
Ahoj ↑ dmk:,
Akoze vies pocet vsetkych moznosti, casto je mozne vypocitat pocet "zakazanych " moznosti. .. a potom vysledok je rozdiel
poslednych dvoch vypoctov.
Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT
Offline
#3 17. 11. 2013 12:11
Re: Kombinatorika-zakázaná posloupnost prvků.
Já bojuji s možností dvou a více zakázaných posloupností v řadě.
Má metoda spočívá v tom, že najdu všechna možná umístění zakázané posloupnosti a to vynásobím možnostmi jak "obsadit zbývající přihrádky". Jenže na to nemohu použít běžné n^k, protože v tom "zbytku" může vzniknout další zakázaná posloupnost. Posloupnosti mohou dokonce některé prvky sdílet. Nevím jak ošetřit to, abych některé možnosti nezapočítal vícekrát.
Příklad:
Prvky: 1,2,3
Počet: Neomezen
Zakázaná posloupnost: 21232
Celková délka: 14 prvků.
Běžný způsob:
Zakázaná posloupnost má pět prvků. Můžeme ji tedy umístit na deset různých míst. Tento počet vynásobíme možnostmi zaplnění zbývajících deseti polí. Celkem je to tedy 5*10^3 možností.
Jsou tu ale posloupnosti 21232 1111 21232. Tuto jsme započítali dvakrát.
Zde by to šlo jednoduše ošetřit mechanicky(posloupnost se opakuje maximálně dvakrát, odečteme tedy 4^3*rozložení kdy je posloupnost obsažena dvakrát). Jenže co v případech, kdy je zakázaná posloupnost výrazně kratší než celková posloupnost. Jde to nějak zkrátit, abych neřešil situaci zvlášť pro dvě zak. posl., tři zak. posl. čtyři......?
Offline
#4 17. 11. 2013 12:25 — Editoval vanok (17. 11. 2013 12:45)
Re: Kombinatorika-zakázaná posloupnost prvků.
V niektorych situaciach mozes pouzit toto
http://cs.wikipedia.org/wiki/Princip_inkluze_a_exkluze
Anglicka verzia je kompletnejsia.
Édit: v priklade co studujes vyssie, staci pre pocet zakazanych situacii, odpocitat od provizorneho vysledku tie co su pocitane dva krat.
Srdecne Vanok
The respect, the politeness are essential qualities...and also the willingness.
Do not judge the other one.
Ak odpovedam na nejaku otazku. MOJ PRINCIP NIE JE DAT ODPOVED ALE UKAZAT AKO SA K ODPOVEDI DOSTAT
Offline