Matematické Fórum

Dobrý den (ráno, případně noc),

mám takový hloupý problém a nevím si rady, jak ho vyřešit. Nedávno jsem naprogramoval software pro různé manipulace s kombinacemi, pak jsem implementoval blacklisting, aby bylo možné kombinace obsahující zadaná čísla zahodit a dnes jsem implementoval opak - whitelisting, tedy aby bylo možné vybrat pouze kombinace obsahující zadaná čísla a zahodit všechny ostatní. S implementací problém nebyl, ale u toho whitelistingu neumím dopředu vypočítat, kolik těch kombinací bude. Umím je vygenerovat, takže pak jejich počet umím i tupě sečíst dohromady, ale nevím, podle jakého vzorce bych mohl dopředu vypočítat, kolik jich bude. Snad vše objasní následující schématické zobrazení:

Sloupec A: všechny 3-kombinace z 1..5
    počet kombinací = K(3,5) = 5! / (3! * 2!) = 120 / 12 = 10

Sloupec B: blacklist čísla "2" (tj. všechny kombinace, které neobsahují číslo "2").
    počet kombinací = K(3,4) = 4! / (3! * 1!) =  24 /  6 =  4

Sloupec C: whitelist čísla "1" (tj. všechny kombinace, které obsahují číslo "1").
    počet kombinací =                ??????              =  6

Sloupec D: blacklist čísla "2" a zároveň whitelist čísla "1".
    počet kombinací =                ??????              =  3


       A            B            C            D

 1.  1,2,3                 1.  1,2,3
 2.  1,2,4                 2.  1,2,4
 3.  1,2,5                 3.  1,2,5
 4.  1,3,4    1.  1,3,4    4.  1,3,4    1.  1,3,4
 5.  1,3,5    2.  1,3,5    5.  1,3,5    2.  1,3,5
 6.  1,4,5    3.  1,4,5    6.  1,4,5    3.  1,4,5
 7.  2,3,4            
 8.  2,3,5            
 9.  2,4,5            
10.  3,4,5    4.  3,4,5

Sloupec A je jasný, všechny 3-kombinace z množiny 5 prvků. Celkem 10 kombinací.
Obecný vzorec K(k,n).

Sloupec B je taky jasný, všechny kombinace bez jednoho čísla, to je vlastně jinými slovy všechny kombinace z množiny o 1 prvek menší. Celkem 4 kombinace.
Obecný vzorec pro b blacklistovaných prvků by byl K(k,n-b), kde b nesmí být větší než n-k.

Sloupec C - pouze kombinace, které obsahují konkrétní prvek. Vím, že takových kombinací je 6, ale nevím, jak se k tomu číslu dostat.

Sloupec D kumuluje podmínky sloupců B a C. Taky nevím, jak se dostat k číslu 3, ale předpokládám, že až budu vědět, jak vyřešit C, tak budu i vědět D.

Ještě jednou se omlouvám za asi hloupý dotaz :-)

//EDIT: tak po půlhodině tupého zírání na výše uvedenou tabulku a druhé půlhodině nevěřícného ověřování jsem asi došel k řešení.
Ono se vlastně todle (tabulka C):

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5

dá chápat jako todle:

1,2
1,3
1,4
2,3
2,4
3,4

což jsou všechny 2-kombinace ze 4 prvků. Na to by šlo koukat jako na podmnožinu, kde je o 1 méně prvků a jsou z nich vytvořeny (k-1)-kombinace.

Takže obecně by se to snad dalo vyjádřit tak, že pokud chci ze všech k-kombinací z množiny n prvků vybrat pouze takové kombinace, které obsahují pouze vybrané prvky (jejichž počet je w, přičemž w nesmí být větší než k), tak to lze vypočítat jako počet (k-w)-kombinací z množiny (n-w) prvků, neboli K(k-w,n-w). Kdyby w se rovnalo k (tedy ve výsledku by měla být pouze jedna jediná kombinace), tak by se to počítalo jako n! / ( 0! * (n-0)! ) = n! / n! = 1, což souhlasí.

A tím pádem řešení pro sloupec D, který kombinuje dohromady blacklisting i whitelisting by byl obecný vzorec K(k-w,n-b-w), což by v tomto konkrétním případě bylo K(2,3) = 3, což také souhlasí.

Tak jsem si asi odpověděl sám, hm, omlouvám se za zbytečné vlákno :-( Jen bych poprosil, kdyby mi to pro jistotu někdo mohl zkontrolovat, že si nepletu pojmy s dojmy.