Matematické Fórum

evik · 15. 03. 2008 20:21

Ahojte,
potřebuju poradit s příklady.

1)
Jsou dána přirozená čísla 1,2,...,m-1,m. Kolik z nich můžeme sestavit permutací takových, že lichá čísla zůstavají na lichých místech a sudá na místech sudých? (Lichým místem v permutaci a1,a2,a3,...am, se rozumí to místo, které přísluší prvku s lichým indexem. Analogicky to platí i pro místo sudé.)

2)
Kolik kombinací k-té třídy z n prvků 1,2,...n obsahuje určitý prvek 1 ?

Sama moc nerozumím ani těm zadáním, můžete se prosím na to někdo kouknout, jestli to umíte?
Děkuju

ttopi · 15. 03. 2008 21:48

Zkusil jsem si jentak na papírek dělat tu 1)
Pro n=1 je 1 permutace a je 1 kladná
pro n=2 jsou 2 permutace a z toho 1 kladná - to je 1/2
pro n=3 je 6 permutací, z toho 2 kladné - 1/3
pro n=4 je 24 permutací, z toho 6 kladných - 1/4
pro n=5 je 120 permutací, z toho 12 kladných - 1/10
pro n=6 je 720 permutací, z toho 36 kladných - 1/20

Jestli v tom někdo vidí nějaký rekurzivní vztah pro n jakékoliv, třeba pomůže víc, mě víc než tohle nenapadlo, ale vypadá to zajímavě :-)

robert.marik · 15. 03. 2008 22:06

Tam to bude dost divoké zejména až se dostaneme k dvoj a víceciferným číslům. Je ten první příklad skutečně celé zadání?

Kondr · 15. 03. 2008 23:18

K prvnímu příkladu:

Pokud je těch čísel 2n, máme n lichých pozic a n sudých pozic, na lichých pozicích můžeme pořadí čísel volit n! způsoby, na sudých také, dle pravidla součinu máme (n!)*(n!) možností.

Pokud je těch čísel 2n-1, máme n lichých pozic a n-1 sudých pozic, na lichých pozicích můžeme pořadí čísel volit n! způsoby, na sudých (n-1)!, dle pravidla součinu máme (n!)*(n-1)! možností.

Souhrně lze tedy počet možností vyjádřit jako
$\lceil m/2 \rceil!\cdot\lfloor m/2 \rfloor!$

To co počítal ttopi, tedy pravděpodobnost, že když náhodně když náhodně vybereme jednu z m! permutací, tak bude mít tuto vlastnost,
vyjde celkem pěkně:

$\frac{\lceil m/2 \rceil!\cdot\lfloor m/2 \rfloor!}{m!}=\frac{1}{m \choose \lceil m/2 \rceil}$

Přitom $\lceil \rceil$ značí zaokrouhlení nahoru, opačné závorky zaokrouhlení dolů.

Ke druhému:
Chceme z daných n prvků vybrat k tak, aby mezi nimi byla jednička. Když tam tu jedničku pevně vybereme, vybíráme už jen k-1 z n-1 čísel, na což máme ${n-1\choose k-1}$ možností.

ttopi · 15. 03. 2008 23:28

Já jsem ttopi :-)
Ještě mi prosímtě řekni, co znamená to m ?

Kondr · 15. 03. 2008 23:36

Ha, opraveno... "Robert Mařík" a ttopi jsou sice těžko zaměnitelná jména, ale po jedenácté hodině večer jsem s to generovat neuvěřitelné chyby, za což se vám oběma, pánové, omlouvám.
↑ ttopi: Pokud vidím dobře, tak m je to číslo v zadání :)

ttopi · 15. 03. 2008 23:41

↑ Kondr: Oh, samozřejmě, už to vidím, díky :-)

Matematické Fórum

#1 15. 03. 2008 20:21

Kombinatorika

#2 15. 03. 2008 21:48

Re: Kombinatorika

#3 15. 03. 2008 22:06

Re: Kombinatorika

#4 15. 03. 2008 23:18

Re: Kombinatorika

#5 15. 03. 2008 23:28

Re: Kombinatorika

#6 15. 03. 2008 23:36

Re: Kombinatorika

#7 15. 03. 2008 23:41

Re: Kombinatorika

Zápatí