Matematické Fórum

katrintn

Najdite pocet permutacii multi-mnoziny $\{m.1,n.2\}$ ked $m,n\in \mathbb{N}$ ktorý musí obsahovať m 1.

standyk · 10. 12. 2011 15:48

↑ katrintn:

Je to zadanie správne?
$\{m.1,m.2\}$ - načo ném potom je, že $m,\color{red}n\color{black}\in \mathbb{N}$

katrintn · 10. 12. 2011 15:52

uz som to opravila

katrintn · 10. 12. 2011 16:05

Oj nerozumiem tomu

standyk

↑ katrintn:

V tom prvom príspevku som sa pomýlil, tuto by už mal byť správny výsledok :) Ten vrchný mažem.

To som len inak zapísal to zadanie. Ten zápis $\{m.1,n.2\}$ znamená, že množina obsahuje m jednotiek a n dvojek. Preto som to tak rozpísal:
$\{\underbrace{1,1,1,\cdots,1}_{m},\underbrace{2,2,2,\cdots,2}_{n} \}$
Tá multimnožina teda obsahuje $m+n$ prvkov. My potrebujeme aby permutácia mala "m" jednotiek. Preto si to môžeme rozdeliť na viac častí:
1. ) Prvá skupinka permutácií bude obsahovať m jednotiek a n dvojok.
2.) Ďalšia skupinka permutácii bude obsahovať m jednotiek a (n-1) dvojok.
.......
n-1.) Predposledná skupinka permutácii bude obsahovať m jednotiek a 1 dvojku.
n.) Posledná permutácia bude obsahovať m jednotiek a žiadnu dvojku.

Ten prvý prípad hovorí že naša multimnožina bude obsahovať (m+n) prvkov. ale permutácia $$1,1,2,1,2,1$$ je iná ako $$1,2,2,1,1,1$$
Preto sa úloha transformuje na to ako vybrať pozície v tej permutácii na ktorej bude m jednotiek. Preto je prvý čiastkový výsledok počet m prvkových permutácii z (m+n) prvkov.
Čiastkový výsledok teda bude:
${m+n \choose m}$

Druhý prípad je rovnaký ako prvý akurát budeme vyberať z (m+(n-1)) prvkovej množiny m prvkov (pozícií) a teda dostávame:
${m+n-1 \choose m}$

Rovnko sa postupuje pri každom prípade:
Posledná pemrutácia bude počet m prvkových podmnožín z m prvkov a teda:
${m \choose m}$

Nakonci sčítame:
${m+n \choose m}+{m+n-1 \choose m} + \cdots +{m \choose m}=\sum\limits_{i=0}^{n}{m+i \choose m}=\color{blue} {m+n+1 \choose m} \color{black}$