Kombinace

Každou k-tici z n-prvků, v níž nezáleží na pořadí, a ve které se každý prvek vyskytuje maximálně jednou, nazveme kombinací.

Počet všech kombinací bez opakování můžeme vyjádřit následujícím vzorcem.


K(k,\\; n) = {{V(k,\\; n)} \\over {k!}} = {{n \\cdot (n-1) \\cdots (n-k+1)} \\over {1\\cdot 2 \\cdots k}} = \\begin{pmatrix} n \\\\ k\\end{pmatrix}

Kde V(k,\\; n) je počet k-členných variací z n prvků. Výraz nejvíce vpravo čteme n nad k a nazýváme jej kombinačním číslem.

Kombinační číslo

Pro každé kombinační číslo platí:


K(k,\\; n) = \\begin{pmatrix}n \\\\ k \\end{pmatrix} = {{n!} \\over {k! \\cdot (n-k)!}}

Dále také platí:


\\begin{array}{l}

\\begin{pmatrix} n \\\\ k\\end{pmatrix} = \\begin{pmatrix} n \\\\ n - k\\end{pmatrix} \\\\
\\begin{pmatrix} n \\\\ 0\\end{pmatrix} = \\begin{pmatrix} n \\\\ n\\end{pmatrix} = 1 \\\\
\\begin{pmatrix} n \\\\ 1\\end{pmatrix} = n \\\\
\\begin{pmatrix} 0 \\\\ 0\\end{pmatrix} = 1 \\\\
\\begin{pmatrix} n \\\\ k\\end{pmatrix} + \\begin{pmatrix} n \\\\ k+1\\end{pmatrix} = \\begin{pmatrix} n+1 \\\\ k+1\\end{pmatrix}

\\end{array}

Kombinace s opakováním

Za předpokladu, že umožníme, aby se jednotlivé prvky opakovaly až k-krát (tj. až do maximálního počtu prvků), tak hovoříme o k-členné kombinaci s opakováním. Počet všech kombinací s opakováním lze vypočítat jako:


K'(k,\\; n) = \\begin{pmatrix} n+k-1 \\\\ k\\end{pmatrix}

Příklad

Vypište všechny dvoučlenné kombinace (bez opakování) prvků a,\\; b,\\; c,\\; d.

Řešení


K = \\{[a,\\; b],\\; [a,\\; c],\\; [a,\\; d],\\; [b,\\; c],\\; [b,\\; d],\\; [c,\\; d]\\}

Příklad

Vypište všechny dvoučlenné kombinace s opakováním prvků a,\\; b,\\; c,\\; d.

Řešení


K' = \\{[a,\\; b],\\; [a,\\; c],\\; [a,\\; d],\\; [b,\\; c],\\; [b,\\; d],\\; [c,\\; d],\\; [a,\\; a],\\; [b,\\; b],\\; [c,\\; c],\\; [d,\\; d]\\}

Příklad

Vypočtěte hodnotu kombinačního čísla \\begin{pmatrix} 7 \\\\ 5\\end{pmatrix}.

Řešení


\\begin{pmatrix} 7 \\\\ 5\\end{pmatrix} = \\begin{pmatrix} 7 \\\\ 2\\end{pmatrix} = {{7 \\cdot 6} \\over {2 \\cdot 1}} = 21

Příklad

V loterijní hře Sportka tipuje soutěžící 6 čísel ze 49. U tažených čísel nezáleží na pořadí, každé číslo může být vylosováno maximálně jednou.

Hlavní výhru získá hráč, který správně označí všechna čísla. Jakou šanci na hlavní výhru má hráč, který si vsadí jeden sloupeček (tj. má jeden tip)?

Řešení

Počet možností, kterými mohou výt čísla vylosována, vypočítáme jako kombinaci 6 prvků ze 49 bez opakování.


K(49,\\; 6) = \\begin{pmatrix} 49 \\\\ 6\\end{pmatrix} = {{49 \\cdot 48 \\cdot 47 \\cdot 46 \\cdot 45 \\cdot 44} \\over {6 \\cdot 5 \\cdot 4 \\cdot 3 \\cdot 2\\cdot 1}} = 13\\; 983\\; 816

Šance na výhru je rovna počtu tipů děleno počtem možností.


{1 \\over {13\\; 983\\; 816}} = 0,00000007151123 = 0,000007151123\\%

Hráč získá hlavní výhru s pravděpodobností 0,000007151123%.


Příklad

V obchodě prodávají 5 druhů cukroví. Kolika způsoby lze nakoupit 16 kusů cukroví?

Řešení

Jedná se o kombinaci s opakováním (jednotlivé druhy můžeme nakoupit vácekrát).


K'(5, 16) = \\begin{pmatrix} 20 \\\\ 5\\end{pmatrix} = {{20 \\cdot 19 \\cdot 18 \\cdot 17 \\cdot 16} \\over {5 \\cdot 4 \\cdot 3 \\cdot 2 \\cdot 1}} = 15\\;504

Cukroví lze nakoupit 232560 způsoby.


Kód

         /** Autor: Vaclav Kejr */
        public long KombinaceBezOpakovani(int k, int n)
        {
            try
            {
                long kombinace = 0;
                if (n >= 2 && n <= 10 && k >= n)
                {
                    int a = n + k - 1;
                    kombinace = this.Faktorial(a) / (this.Faktorial(k) * this.Faktorial(n - 1));
                }
                return kombinace;
            }
            catch (SystemException ex)
            {
                Console.WriteLine(ex.ToString());
                return -1;
            }
        }
        public long KombinaceOpakovani(int k, int n)
        {
            try
            {
                long kombinaceOpakovani = 0;
                if (k >= 2 && k <= 10 && n >= 2 && n <= 10)
                {
                    int a = n + k - 1;
                    int b = n - 1;
                    kombinaceOpakovani = this.Faktorial(a) / (this.Faktorial(k) * this.Faktorial(b));
                }
                return kombinaceOpakovani;
            }
            catch (SystemException ex)
            {
                Console.WriteLine(ex.ToString());
                return -1;
            }
        }      
        public long Faktorial(int n)
        {
            try
            {
                long faktor = 1;
                if (n < 1)
                {
                    throw new ArgumentException("Argument n < 1 !", n.ToString());
                }
                else if (n == 1)
                {
                    return faktor = 1;
                }
                else if (n >= 2 && n <= 20)
                {
                    for (int i = 2; i <= n; i++)
                    {
                        faktor *= i;
                    }
                    return faktor;
                }
                else
                {
                    throw new ArgumentException("Argument n > 20 !", n.ToString());
                }
            }
            catch (SystemException ex)
            {
                Console.WriteLine(ex.ToString());
                return -1;
            }
        }
         
         

Literatura

  • POLÁK, Josef. Přehled středoškolské matematiky. 8. vydání. Praha 4 : Prometheus, 2005. 608 s.







Doporučujeme