комбинаторика


  • комбинаторика
  • принцип вероятности подмножества

  • всего число перестановок n элементов есть n!

    всего способов отобразить n-элементное множество в m-элементное существует m^n

    всего способов выбрать k элементов из n элементов существует n! / [k! * (n-k)!]

    если множества A и B конечны и |A| = m, |B| = n, то множество A × B тоже конечно и содержит m*n элементов

    комбинаторный выбор

  • n - размер генеральной совокупности
  • k - размер выборки
  • упорядоченный выбор: выборки считаются различными, если они отличаются составом ИЛИ порядком
  • неупорядоченный выбор: выборки считаются различными, ТОЛЬКО если они отличаются составом
  • выбор без возврата: выбранные элементы изымаются из совокупности (выборка без повторений)
  • выбор с возвратом: выбранные элементы возвращаются в совокупность (выборка с повторениями)
  • число исходов

    упорядоченныйнеупорядоченный
    с возвратом n^k (n + k - 1)! / [k! * (n - 1)!]
    без возврата n! / [k! * (n - k)!] n! / (n - k)!

    примеры

      неупорядоченный упорядоченный
    с возвратом кубик в нардах, монета в орлянке подбор пароля
    без возврата раздача карт в покере , спортлото однослоговый алфавит

    пример

    дважды подбросим монету. если учитывать порядок, то исходов получится 4, и все они равновозможны, то есть имеют вероятность по 1/4: (герб,герб), (решка,решка), (решка,герб), (герб,решка)

    если порядок не учитывать, то получим три исхода: (два герба), (две решки), (герб, решка). первые два исхода имеют вероятность 1/4, а последний — вероятность 1/2

    пример

    из колоды в 52 карты раздаются две. сколько комбинаций для игры можно при этом получить?

       нас интересует выбор упорядоченный. значит N = 52! / (2! * 50!) = 51 * 26 = 1326 
    
    сколькими способами можно осуществить подобную раздачу?
       теперь нас интересует выбор неупорядоченный. значит N = 52! / 50! = 51 * 52 = 2652
    

    пример

    в алфавите десять символов. грамматика не позволяет повтор символа в слове и требует длины слова от двух до четырех символов (включительно). сколько слов в словаре?

       налицо упорядоченный выбор без возврата. тогда N = (10, 2) + (10, 3) + (10, 4) = 375 
    

    пример

    у вас сто ключевых слов интерпретатора. вы хотите задать длину любого ключевого слова в два символа, но без дублирования. какой минимальный размер алфавита должен при этом быть?

       пробуем 12:                       12!/(2!*10!) = 66
       маловато, пробуем 13:             13!/(2!*11!) = 78
       добавим еще       14:             14!/(2!*12!) = 91
       чего-то медленно оно растет, 15:  15!((2!*13!) = 105
       ура!
    


    принцип вероятности подмножества

    пусть есть вектор u из базиса n-мерного пространства. тогда для случайно выбранного вектора v:

                        p(<u> • <v> ≠ 0) = 1/2
    
    где • - скалярное произведение векторов