Matematické Fórum

mmumminek · 16. 03. 2012 18:17

Dobrý den.
Řeším následující problém a v kombinatorice nejsem moc dobrý.
Mám dvě množiny
$A,E\subseteq A$
Hledám počet možných kombinací (nezáleží na pořadí) těchto dvou množin bez opakování nejakého prvku. Vím že to je
$|A|\cdot (|E|-1)$ .
Problém se ale komplikuje, když hledám to samé ve třech nebo čtyřech množinách.
$A,B=A,E\subseteq A$
$A,B=A,C=A,E\subseteq A$
Tedy hledám tři (čtyři) prvky, každý z jedné množiny a nesmí tam být dva a více stejných.

Předem díky za pomoc, opravdu si nevím rady.

jardofpr · 18. 03. 2012 09:12

↑ mmumminek:

sú ešte nejaké iné obmedzenia na tie množiny?
mohol by si napísať zadanie konkrétneho príkladu? je to trochu nejasné

mmumminek · 18. 03. 2012 12:24

Příklad nemá konkrétní zadání, jde o výpočet náročnosti pro jeden algoritmus.
Zkusím to vysvětlit jinak.
Mám dvě množiny uzlů. Jedna je podmnožinou druhé. A potřebuji vypočítat kolik je možností, když hledám výběr dvou, tří nebo čtyř bodů. Z toho první bod je vždy z té podmnožiny a ostatní z té velké množiny. A hlavně se nesmí v mém výběru objevit stejný uzel dvakrát nebo vícekrát.

Snad to pomohlo.
:-)

jardofpr

↑ mmumminek:

aha takto .. ooookej..
predpokladám že tých uzlov je konečne veľa

Autor skryl část textu. Zobrazit/skrýt!

mmumminek

To vypadá dobře. A dává to i smysl.

ikdyž by měl být výledný vzorec
$\frac{k\cdot n}{2} + \frac{k(k-1)}{2}$
protože $k\cdot n$ je sice každý s každým, ale mně nezáleží na pořadí, takže je tam dvakrát více prvků. Proto tedy:
$\frac{k\cdot n}{2}$

Pokud tedy chci modifikovat zadání a přidám třetí uzel
$l\in A$
$l\in \{1,2,...,n\}$

Mám trojici bodů reprezentovanou
$\{i,j,l\}$
$i\neq j \wedge i\neq l \wedge j\neq l$

Počet možností pro dva body je tedy
$\frac{k\cdot n}{2} + \frac{k(k-1)}{2}$
a přidáním dalšího bodu vznikne
$(\frac{k\cdot n}{2} + \frac{k(k-1)}{2})\cdot (k+n-2)$
Protože dva body jiz jsou obsazené.
A poslední uprava pro čtvrtý bod, která opět náleží množině A.
$(\frac{k\cdot n}{2}+ \frac{k(k-1)}{2})\cdot (k+n-2)\cdot (k+n-3)$

Díky za pomoc. :-)

jardofpr

↑ mmumminek:

počet dvojíc $k.n + \frac{k(k-1)}{2}$ je v poriadku,
bral som do úvahy že nezáleží na poradí
$k.n$ reprezentuje mohutnosť množiny

$\{\,\, \{e_{i},a_{j}\in\mathbb{A}\}\,;\, i\in \{1,2,\dots,k\}\,,\,j\in\{1,2,\dots,n\}\,\,\}$
nič sa tam neopakuje, $a_{j}$ sú tie prvky $A$ ktoré nie sú v $E$
ak vezmeš polovičné množstvo, nebudeš mať všetky možnosti výberu, ktorý požaduješ

môžeš ďalšie vzťahy postaviť na počtoch dvojíc, ale nie tak jednoducho ako píšeš

ku každej dvojici $e_{i}, a_{j}$ môžeš vybrať $a_{k}$ alebo $e_{l}$ , kde $k\neq j\,,\,l \neq i$

počet možností výberu $a_{k}$ k dvojici $e_{i},a_{j}$ pre fixné $i$ tak, aby sa dodržali požiadavky je výber kombinácií dvoch prvkov bez opakovania z $A-E=\{ a_{1}, \dots, a_{n}\}$ ,
to je $\frac{n!}{2!(n-2)!}=\frac{n(n-1)}{2}$
pre každé $i$ je tento počet rovnaký
takže možností je celkovo $k\cdot\frac{n(n-1)}{2}$

vyberať $e_{l}$ k dvojici $e_{i}, a_{j}$ je tu to isté ako vyberať kombinácie bez opakovania dvoch prvkov z množiny $\{e_{1},\dots,e_{k}\}$ pre každé $a_{j}$
takže to bude $n\cdot \frac{k(k-1)}{2}$

okrem toho tam máš ešte dvojice $e_{i},e_{j}$
k tým netreba vyberať $a_{j}$ , to už je obsiahnuté v predošlom čísle

treba už len trojice $e_{i},e_{j},e_{k}$
to sú trojice bez opakovania z k-prvkovej množiny teda $\frac{k!}{k!(k-3)!}=\frac{k(k-1)(k-2)}{6}$

teda trojíc by sa malo dať vybrať
$\frac{kn}{2}(n+k-2)+\frac{k(k-1)(k-2)}{6}$

tvoj výpočet neberie do úvahy napríklad to že nezáleží na poradí

jardofpr

↑ mmumminek:

asi bude lepšie nestavať na dvojiciach a urobiť si všeobecný vzťah
$|E|=k\,,\,|A|=n+k$ a tak ako predtým $E \subseteq A$
$0<k\leq n$
treba vybrať $m$ uzlov tak že aspoň 1 z nich je z $E$ , ostatné z $A$ bez závislosti na poradí
kde $0<m\leq n$

výber môže obsahovať 1 až m prvkov z $E$ v prípade, že $m\leq k$
ak je $m >k$ , samozrejme tam môže byť najviac $k$ prvkov z $E$

teraz nech výber obsahuje $j$ prvkov z $E$ kde $0<j\leq k$
potom je v ňom $m-j$ prvkov z $A$

počet možností takéhoto výberu je $\bigg( \begin{array}{c} k \\ j \end{array} \bigg) \cdot \bigg( \begin{array}{c} n \\ m-j \end{array} \bigg)$ (to majú byť kombinačné čísla)

výsledok dostaneme spočítaním týchto hodnôt pre všetky $j$ ktoré prichádzajú do úvahy,
teda
$P(m) = \sum_{j=1}^{\min{\{k,m\}}}\bigg( \begin{array}{c} k \\ j \end{array} \bigg) \cdot \bigg( \begin{array}{c} n \\ m-j \end{array} \bigg)$

$P(m)$ bude počet možností výberu $m$ uzlov tak, ako potrebuješ

keď si za $m$ dosadíš 2 a 3, vyjdu ti tie vzorce čo som uviedol vyššie