Matematické Fórum

Magicmaster · 04. 10. 2013 10:58

Zdravím. Řeším příklad a dostal jsem se do této fáze:
Mám $a$ prvků, ze kterých potřebuju udělat $b$ skupin tak, aby každý prvek byl vybrán právě jednou a každá ze skupin obsahovala alespoň jeden prvek. Přitom záleží na pořadí těchto prvků.

Tedy například: $(1, 2, 3, 4, 5) \rightarrow ((1,2), (3, 5), (4))$ , ale ne $\rightarrow ((1, 2, 4), (3, 5), ())$

Žádný z kombinatorických vzorců (variace, kombinace, permutace) ani jejich kombinace/podíl, atp. mi na to nejde nasadit..
Poradí někdo? :)

Formol · 04. 10. 2013 11:13

↑ Magicmaster:
Můj první nápad ti snad pomůže. Mezi a prvků musíš rozmístit b "zarážek", tedy výběr b prvků z a-1 možností. Abys zahrnul i skupiny, které jsou z nesousedních prvků, musíš zvážit všechny permutace a!. Ovšem tam se ti budou prvky opakovat a momentálně mě nenapadá, jak opakování vyloučit...

Magicmaster · 04. 10. 2013 16:58

Nikde nevidím jak upravit příspěvek, tak se opravím tady. Na pořadí prvků ve výsledných skupinách nezáleží.
Konkrétní příklad: mám 4 prvky, chci je rozdělit do 2 skupin. Vypadat to tedy bude takhle:

#1|#2

123|4
124|3
134|2
234|1
12|34
13|24
14|23
23|14
24|13
34|12
1|234
2|134
3|124
4|123

.. 14 možností

Ten způsob zarážkami jsem taky zkoušel, ale nepřišel jsem na to, jak spočítat v kolika případech budou alespoň dvě zarážky "na sobě", tj. bude jedna ze skupin prázdná.. :|

zdenek1 · 04. 10. 2013 17:30

↑ Magicmaster:
Tohle je příklad na inkluzi a exkluzi (PIE)

všech rozdělení tvých čtyř prvků je $2^4$ a odečteš případy, kdy je jedna skupina prázdná (2 možnosti)

Samozřejmě, pro obecný zápis to takto primitivně nepůjde. Ale začal bych tím, že bych si nastudoval něco o PIE

Matematické Fórum

#1 04. 10. 2013 10:58

Variace s opakováním obsahující alespoň jeden prvek od každého

#2 04. 10. 2013 11:13

Re: Variace s opakováním obsahující alespoň jeden prvek od každého

#3 04. 10. 2013 16:58

Re: Variace s opakováním obsahující alespoň jeden prvek od každého

#4 04. 10. 2013 17:30

Re: Variace s opakováním obsahující alespoň jeden prvek od každého

#5 04. 10. 2013 18:32 — Editoval Jj (04. 10. 2013 19:19) Příspěvek uživatele Jj byl skryt uživatelem Jj. Důvod: Nedotaženo

Zápatí