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


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

k-сочетанием без повторений называется любое k-элементное подмножество n-элементного множества

k-сочетанием с повторениями называется любое k-мультимножество над n-множеством


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

k-перестановкой без повторений называется упорядоченное k-подмножество n-элементного множества

k-перестановкой с повторениями называется любой элемент декартовой степени X^k


если есть N состояний системы, то для описания каждого состояния понадобится log₂N бит

с помощью n бит можно описать 2ⁿ состояний системы


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


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

мощность декартова произведения k конечных множеств есть произведение их мощностей

      |X1 × X2 × ... × Xk | = |X1| · |X2| · ... · |Xk|
например пусть в аудитории находятся 32 студента одной группы, 24 студента другой группы и 17 студентов третьей группы. тройку, состоящую из представителей каждой группы, можно выбрать 32·24·17 способами

если некоторый элемент из множества A можно выбрать k способами, и, вне зависимости от выбора этого элемента, можно n способами выбрать некоторый элемент множества B, то выбор элемента из множества A или из множества B можно осуществить k + n способами

      |A ∪ B| = |A| + |B| 

предположим, что A и B являются подмножествами некоторого множества X. в этом случае у множества A⊂X и множества B⊂X имеются дополнения к ним - множества A' и B', причем

    A ∪ A' = B ∪ B' = X 
рассмотрим теперь пересечение A'∩B' дополнений множеств A и B. количество элементов в этом пересечении можно сосчитать так:
    |A' ∩ B'| = |(A ∪ B)'| = |X| − |A ∪ B| = |X| − |A| − |B| + |A ∩ B|  
это равенство называется принципом включения-исключения. и вот пример его использования: пусть в аудитории находятся 30 человек, 20 человек из которых знают английский, 12 - французский, а 6 человек знают оба языка. сколько человек не знает ни один из этих иностранных языков? ответ, согласно принципу включения-исключения, следующий:
    N = 30 − 20 − 12 + 6 = 4 


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

введем обозначения :

определим тип выбора из совокупности как :

число исходов

упорядоченныйнеупорядоченный
с возвратом 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

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

      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
ура!

пример

сколькими способами можно разложить по двум карманам девять монет различного достоинства? рассматриваемый пример является типичной задачей, которая естественным образом сводится к схеме раскладки предметов по ящикам. в роли ящиков здесь выступают левый и правый карман, а в роли предметов - девять различных монет. поэтому ответ в этой задаче - 2^9=512 способов


размещения

для размещения r шаров по n ящикам может быть применены:

необходимо отметить тот факт, что ящики при этом - различимы (для всех трех случаев). это важно


по статистике Больцмана для каждого шара возможно n независимых исходов эксперимента (в какой именно ящик будет помещен именно этот РАЗЛИЧИМЫЙ шар), поэтому совместимые РАЗЛИЧИМЫЕ шары можно разместить

                 n ^ r
различными способами. например для трех шаров a b c и двух ящиков 1 2:

1 2
a b c -
- a b c
a b c
a c b
b c a
c a b
b a c
a b c
2^3 = 8
пример

TODO

если шаров меньше, чем ящиков, то формула не меняется. например для двух шаров a b и трех ящиков 1 2 3 :

1 2 3
a b - -
- a b -
- - a b
a b -
b a -
a - b
b - a
- a b
- b a
3^2 = 9
пример

TODO


если же используется статистика Бозе, то число вариантов упаковки совместимых неразличимых шаров составит

           binomial ( n + r - 1 
                        n - 1   )
если n > r

и

           binomial ( n + r - 1
                          r     )
если n ≤ r

например для двух неразличимых совместимых шаров x x и двух ящиков 1 2:

1 2
x x -
x x
- x
binomial (2 + 2 - 1, 2) = binomial (3,2) = 3

например для двух неразличимых совместимых шаров x x и трех ящиков 1 2 3 :

1 2 3
x x - -
x x -
x - x
- - x x
- x x
- x x -
binomial (2 + 3 - 1, 3 - 1) = binomial (4,2) = 6

например для трех неразличимых совместимых шаров x x x и двух ящиков 1 2 :

1 2
x x x -
- x x x
x x x
x x x
binomial (2 + 3 - 1, 3) = binomial (4,3) = 4

например для двух неразличимых совместимых шаров x x и четырех ящиков 1 2 3 4 :

1 2 3 4
x x - - -
x x - -
x - x -
x - - x
- x x - -
- x x -
- x - x
- - x x
- - x x -
- - - x x
binomial (2 + 4 - 1, 4 - 1) = binomial (5,3) = 10

например для четырех неразличимых совместимых шаров x x x x и двух ящиков 1 2:

1 2
x x x x -
x x x x
x x x x
x x x x
- x x x x
binomial (2 + 4 - 1, 4) = binomial (5,4) = 5


если использовать статистикy Ферми, то размещение можно сделать

          ( n
            r )
различными способами. например для двух одинаковых несовместимых шаров a a и двух ящиков 1 2:

1 2
a a

например для двух одинаковых несовместимых шаров a a и трех ящиков 1 2 3 :

1 2 3
a a -
a - a
- a a
binomial(3,2) = 3

например для двух одинаковых несовместимых шаров a a и четырех ящиков 1 2 3 4 :

1 2 3 3
a a - -
a - a -
a - - a
- a a -
- a - a
- - a a
binomial(4,2) = 6

упаковать количество одинаковых шаров большее, чем количество ящиков, по этой статистике нельзя - из-за несовместимости шаров


listing R
#! /home/user/.nix-profile/bin/Rscript 
#  main statistics
#  arg1 - boxes, arg2 - balls

args  = commandArgs (TRUE)
boxes = as.numeric (args[1])
balls = as.numeric (args[2])

printf <- function(...) print (sprintf(...))

printf ("boxes : %i, balls : %i", boxes, balls)

x = boxes ^ balls
printf ("maxwell-boltsman : %i", x) 

x = if (boxes > balls) choose (boxes + balls - 1, boxes - 1) else choose (boxes + balls - 1, balls)
printf ("bose-einshtain   : %i", x) 

x = choose (boxes, balls)
printf ("fermi-dirak      : %i", x) 

end of listing
пример

у отца имеется пять (неразличимых) апельсинов, которые он может раздать восьми своим сыновьям

если его задача состоит в том, чтобы раздать их максимальному количеству сыновей, то любой из его сыновей не должен получить более одного апельсина. в этом случае количество способов, которыми он может раздать своим сыновьям эти пять апельсинов считается по статистике Ферми и равно binomial(8,5)=56

если же он раздает их по каким-то заслугам, и может любому сыну отдать любое количество апельсинов (но раздав их все), то количество способов это сделать считается по статистике Бозе и равно binomial(8+5-1,5-1)=binomial(12,4)=495


счастливые билеты

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

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

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

итак, у нас есть 5 благоприятствующих исходов, причем вот в совершенно прямом смысле этого слова - благоприятные и хорошие билеты, и 25 исходов всего, они считаются равновероятными, потому что профессор хорошо перетасовал колоду из своих билетов. естественно, вероятность успеха для первого товарища - она просто 1/5. вот если мы говорим про второго товарища, то пусть A - это то событие, которое нас интересует, т.е. событие, состоящее в том, что второй товарищ вытянул хороший билет. и для подсчета этой вероятности рассмотрим два случая.
первый случай - это что первый студент вытянул хороший билет, и вот это как раз плохо для второго. тогда у второго вероятность вытянуть хороший билет, действительно, понижается.
но второй случай состоит в том, что первый студент вытянул плохой билет, и тогда плохих билетов подиссякло. тогда у второго вероятность вытянуть хороший билет, наоборот, повышается

значит: B1 - это первый вытащил хороший и B2 - это первый вытащил плохой. поэтому желая посчитать вероятность события A, мы просто можем воспользоваться формулой полной вероятности, которая нам говорит, что вероятность A - это

    p (A|B1) × p (B1) + p (A|B2) × p (B2)
- просто формула полной вероятности. p (B1) - это вероятность того, что первый студент вытаскивает хороший билет, но мы ее уже сосчитали. это вероятность 1/5. давайте посмотрим с какой вероятностью второй студент достанет хороший билет, коль скоро один хороший билет уплыл к первому

если один хороший билет уплыл к первому, значит осталось 4 хороших и 20 плохих. с какой же вероятностью тогда второй студент сможет вытащить хороший билет, коль скоро все по-прежнему хорошо растасовано? понятно, что он это сделает с вероятностью 4/24, ну или, что то же самое, 1/6

теперь, вероятность B2. B2 - это что первый товарищ вытащил неудачный билет, это 4/5. это означает, что второму товарищу, по-прежнему, предстоит выбор возможный из 5 хороших, и, соответственно, 19 плохих. итого, всего, по-прежнему, 24, как и в первом случае, но благоприятствующих исходов 5. получаем 5/24, ну и продолжаем это равенство. значит

    1/6 × 1/5 = 1/30, а 5/24 × 4/5 = 1/6
итого имеем 6/30, чт.е. 1/5

все. задача решена

подумайте над тем, почему этот ответ вообще не зависит от номера студента в очереди за билетами. т.е. это не просто совпадение, что вот первые два там взаимно переставляются, а третьи уже несчастны. нет, третий тоже не несчастен, у него вероятность вытянуть правильный билет тоже 1/5

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


listing bc
/* four students s1 s2 s3 and s4 take 1 ticket for each from initial pile in 25 tickets
   they suppose that 5 tickets are easy-cakes and they agree abt which ones are
   the students take tickets one after another (in turn)
   does probability to obtain the good ticket depend on turn?
*/

scale = 4

s1 = 5 / 25
print s1 , "\n"

s2 = ((1-s1)*5 + s1*4) / 24
print s2 , "\n"

s3 = ((1-s1)*(1-s2)*5 + s1*s2*3 + s1*(1-s2)*4 + (1-s1)*s2*4) / 23
print s3 , "\n"

s4 = ((1-s1)*(1-s2)*(1-s3)*5 + s1*s2*s3*2 + s1*s2*(1-s3)*3 + s1*(1-s2)*s3*3 + 
     (1-s1)*s2*s3*3 + s1*(1-s2)*(1-s3)*4 + (1-s1)*s2*(1-s3)*4 + (1-s1)*(1-s2)*s3*4) / 22
print s4 , "\n"

quit

вот прога, которая считает вероятность получить первой картой туза для четырех игроков (карты сдаются по одной из колоды в 52 листа):


listing bc
/* сдается колода в 52 листа четверым игрокам по одной карте
   какова вероятность у каждого игрока получить первой картой любого туза?
*/

scale = 4

/*  первый получил любого туза */ 
x1 = 4 / 52 
print x1 , "\n"

/* второй получил любого туза */
x2 = (x1*3 + (1-x1)*4) / 51
print x2 , "\n"

/* третий получил любого туза */
x3 = ((1-x1-x2)*4 + x1*x2*2 + (1-x1)*x2*3 + x1*(1-x2)*3) / 50 
print x3 , "\n"

/* четвертый получил любого туза */
x4 = ((1-x1-x2-x3)*4 + x1*x2*x3*1 + (1-x1)*x2*x3*2 + x1*(1-x2)*x3*2 +  x1*x2*(1-x3)*2 + 
       x1*(1-x2)*(1-x3)*3 + (1-x1)*x2*(1-x3)*3 + (1-x1)*(1-x2)*x3*3) / 49
print x4 , "\n"

halt

end of listing

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

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

можно действовать так: произвольно поступить по отношению к элементу a1, т.е. либо положить его в строящееся множество, либо не положить. точно так же поступить по отношению к элементу a2: положить или не положить. тоже два способа. и так далее.

мы так не можем дойти до элемента с номером N, потому что если мы будем наплевательски относиться к делу, то может получиться как множество четной мощности, так и множество нечетной мощности. давайте дойдем только до элемента с номером (N - 1). к нему применим два стандартных способа, - т.е. либо положим его в строящееся множество, либо не положим, - а затем переведем дыхание и посмотрим, что у нас получилось на выходе в результате вот этих вот альтернатив

на выходе могло получиться множество четной мощности. но тогда, очевидно, элемент a с индексом N в него добавлять уже никак нельзя

и наоборот, могло получиться множество нечетной мощности, т.е. это как бы нехорошо. но тогда, однозначно, надо к нему просто прибавить элемент a с индектом N, и уже вместе с ним, опять-таки, получится множество четной мощности. т.е. есть всего 2^(N-1) способов выбрать первые (N-1) элементов, и для каждого из таких способов есть однозначный путь добавления элемента a с индексом N так, чтобы в итоге получилось множество четной мощности

мы получаем в итоге 2^(N-1) поделить на 2^N, и это равняется ½

выбор вектора

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

    p (e • u ≥ 1/2) 
где • - скалярное произведение векторов ?

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

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

а если вектор определяется случайным выбором точки в единичном шаре, через которую потом проводится вектор, то тогда ответ для n=3 будет

    √ (1 - 0.5²)
        ∫  πr² dr / (4π * 1³ / 3) ≅ 0.866³/4 ≅ 0.162 
        0
  
а для n=2

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

    TODO

задача про два случайных подмножества

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

означает это что у нас есть куча всех возможных подмножеств нашего n-элементного множества. мы из этой кучи всех возможных подмножеств, которых 2ⁿ штук, сначала выбираем некоторое множество А и запоминаем его. после чего возвращаем его элементы обратно в кучу, снова тщательно кучу перемешиваем и оттуда наугад достаем множество В, которое, с какой-то вероятностью может даже совпасть. т.е. каждая пара множеств, которую мы могли бы извлечь, имеет одну и ту же вероятность. т.о., пространство элементарных исходов - это множество всех упорядоченных пар подмножеств А и В

ну раз подмножество А можно выбрать 2ⁿспособами, и мы его потом возвращаем, то множество В тоже можно выбрать 2ⁿ способами, откуда получаем, что мощность омега - это 4ⁿ - любая пара возможностей нас устраивает и в том числе - совпадающих. поэтому получается, что мощность омега равняется 4ⁿ

вспомним формулировку задачи: множество А имеет мощность l1 и множество В имеет мощность l2 при условии, что эти множества не пересекаются

нам хочется найти условную вероятность того, что случайно вытащенные подряд множества оказались вот такими, т.е. что они имеют заданные наперед мощности, но при этом они не пересекаются. эту вероятность надо считать по обычной формуле. в числителе мы пишем вероятность пересечения событий, одновременно и мощности такие, и множества не пересекаются. нас устраивают все возможные пары множеств А и В, первое из которых имеет такую мощность, второе - такую, и при этом оба не пересекаются. это - числитель искомой вероятности. а в знаменателе стоит вероятность условия. т.е. вероятность того, что А, пересеченное с В, - пусто. поскольку каждая из этих вероятностей классическая, мы количество благоприятствующих исходов делим на общее количество исходов, на мощность омега большого, то и сверху имеется 4ⁿ, и снизу стоит в знаменателе 4ⁿ и эти четверки в n степени сократятся

итак, мощность А равняется l1. мощность В равняется l2, и А, пересеченное с В - пусто. вот количество всех таких пар, для которых одновременно эти три условия выполняются, - это количество благоприятствующих исходов для события. ну а количество исходов, благоприятствующих событию, количество пар АВ, таких, что А, пересеченное с В, является пустым множеством

числитель считается легко. давайте сначала будем выбирать множество А. но как мы должны его выбрать? мы его должны выбрать так, чтобы его мощность равнялась l1, и выбирается оно, конечно, из n-элементов. т.е. мы просто берем С из n по l1, и это количество способов зафиксировать множество А. после того как множество А зафиксировано, мы будем выбрать множество В мощности l2, но при этом так, чтобы оно с А не пересекалось. но это очень легко. у нас осталось n−l1 элементов, которые множеству А не принадлежат. и вот из этих n−l1 элементов мы вольны выбрать произвольный l2 так, чтобы у нас на выходе получилось как раз l2-элементное множество В, которое с А не пересекается. т.е. числитель нашелся очень легко

а вот знаменатель вызывает некоторые трудности. ну действительно: как подсчитать количеств пар множеств, которые не пересекаются? давайте переберем случаи. давайте посмотрим, какой мощности может быть множество А. давайте ее k обозначим. теоретически она меняется от нуля до n. и вот при каждом таком k мы можем выбрать множество А (С из n по k) способами. у нас остается n−k элементов после того, как мы зафиксировали k элементов для множества А, и вот только из этих n−k элементов мы можем извлекать множество В. ну дальше - это просто бином Ньютона. и если раскрыть с помощью бинома Ньютона, то получится окончательный ответ:

    (С из n по l1) * (С из n−l1 по l2) / 3ⁿ  

с другой стороны, так долго и мучительно тройку в степени n совершенно необязательно было получать. смотрите, вот у нас есть два множества, А и В, которые не пересекаются. давайте каждой паре таких множеств однозначно сопоставим некую последовательность из ноликов, единиц и двоек, которая бы имела длину n. давайте делать так. смотрим на элементы множества 1, 2 и так далее n, из которого выбирались наши подмножества А и В. где-то здесь живет подмножество А. где-то живет подмножество В, и они не пересекаются. давайте каждому элементу множества А сопоставим единичку. каждому элементу множества В сопоставим сопоставим двоечку. а если, в свою очередь, элемент не попадает ни в множество А, ни в множество В, тогда нарисуем нолик. и вот у нас каждой паре множеств однозначно соответствует такая последовательность. где-нибудь вот здесь можем нарисовать нолик, где-то здесь, может, двоечка будет. последовательность из нулей, единиц и двоек. еще раз, нули стоят там, где нет вообще ни одного элемента: ни А, ни В. единицы стоят там, где есть элементы А, и двойки стоят там, где есть элементы В. при этом очевидно, что нули, единицы и двойки стоят на разных позициях, поскольку А и В не пересекаются. ну, в итоге получаем, что количество способов выбрать вот такую пару - это в точности количество способов построить такую вот последовательность из нулей, единиц и двоек. на каждую позицию ставим любое из трех чисел в позиции n. ответ - 3ⁿ. т.е., комбинаторно это можно получить гораздо короче, чем суммируя по биному


комбинаторика и группы

комбинаторная теория групп - это когда группа представляется образующими и отношениями между образующими:

       G = < X | R > 

такое представление групп имеет название "копредставлений"

например если группа имеет конечный алфавит и соотношение для любого своего элемента x²=1 тогда

     [a², b²] = (a * b)² 
и группа получилась абелевой - прямые суммы ℤ/2ℤ

иногда это же записывают так, что группа задана как < a | a² > (если соотношение не приравнивается числу, то считается, что оно приравнено к 1), откуда группа ℤ/2 выявляется рельефнее. получилась двумерная проективная плоскость ℝℙ², которая имеет π₂=ℤ

группа бутылки Клейна задается двумя образующими и одним соотношением :

    G = < a, b | a * b * a⁻ * b = 1 > 
это полупрямое произведение ℤ на ℤ

группа кос порядка 3:

     B₃ = < a, b | a² = b³ > 
называемая "группой трилистника". есть два 2-мерных комплекса, которые гомотопически неэквиваленты, но у которых фундаментальная группа π₁ одинакова и является группой B₃