Две теории из комбинаторики
Допустим, перед нами стоит задача:
В классе 30 учеников, среди них 2 друга. Для изучения иностранных языков класс разбили на 2 группы, в 1-ой 16 человек (английский язык), во 2-ой -14 (китайский язык). Спрашивается, какова вероятность того, что друзья окажутся в одной группе?
1-ое , что хочется сделать в данной ситуации – это попытаться выяснить, сколько же отличимых перестановок окажется в множестве перестановок множества, в котором 2 элемента неотличимы друг от друга? (так называемые перестановки с повторениями) И ответ на этот вопрос чрезвычайно прост: всякая пара перестановок исходного мноежства, отличающихся друг от друга только порядком идентичных элементов, является парой неотличимых перестановок. А поскольку количество перестановок из 2 равно 2 (то есть 2 – это значение фактора вырождения исходного множества перестановок вследствие идентичности элементов исходного множества), то отличимых перестановок окажется в 2 раза меньше, чем исходных. (при этом при решении задач по теории вероятности не следует забывать, что каждая неотличимая перестановка присутствует в множестве перестановок в количестве 2, в данном случае)
И вообще, количество отличимых перестановок:
P(n,k)=P(n)/P(k),
где k – количество идентичных элементов исходного множества.
Вот и вся теория перестановок с повторениями.
А, если в исходном множестве – несколько групп идентичных элементов, то вот так:
P(n,k1,k2)=P(n)/P(k1)/P(k2)
Вот теперь вся теория перестановок с повторениями.
Для решения же поставленной задачи нам потребуется
Теория разбиений множеств
Пусть множество разбивается на 2 подмножества.
Для построения теории в 1-ую очередь приходит идея обозначить элементы 1-го подмножества А, элементы 2-го подмножества – В.
Тогда получим, что множество ААВ разобьётся на подмножества 2+1 следующими 3-мя способами:
АА+В;
АВ+А
АВ+А
Последний случай как бы повторяет 2-ой, т.к. левый и правый А – разные. Поэтому разумно ввести нумерацию идентичных, вот так:
А1,А2+В;
А1,В+А2
А2,В+А1
Но как построить а таком случае разбиения 4-множества на 2+2?
Быть может, для начала построим эти разбиения, используя стандартные обозначения элементов множеств:
ab+cd
ac+bd
ad+bc
А потом, используя таблицу перекодировки:
A1=a, A2=b, B1=c, B2=d
построим то, что требуется:
A1A2+B1B2
A1B1+A2B2
A1B2+A2B1
Но и после этого (а тем более после разбиения 4-множества) задаёшься вопросом: а полно ли построенное тобой множество разбиений? Как это определить? Решение понятно: алгоритмизовать эту задачу. Но как это сделать?
В связи с этим возникает идея: а что если из множества разбиений 3 (и не только на 2+1) построить множество разбиений 5 на 3+2? Ведь они вполне родственны друг другу.
В итоге для основы получаем следующее множество разбиений:
B1B2B3+0
B1B2+B3
B1B3+B2
B2B3+B1
Присоединяемые же к ним подмножества таковы:
1)0+A1A2
2)[A1+A2,A2,A1,0+A1A2] (3 варианта)
3)[A1+A2,A2,A,0+A1A21]
4)[A1+A2,A2,A1,0+A1A2]
Итого получается 1+3*3=10 вариантов разбиений.
Но как же всё-таки алгоритмизовать этот расчёт?.
Во-первых, нужно понять, что обозначения элементов вида А1, В3 – это всего лишь иная система координат для создания обозначений, а поэтому для решения (поставленной) задачи она ровным счётом ничего не даёт.
Во-вторых, нужно понять, что на шаг более сложное разбиение я могу получить из текущего всего 2-ью способами. А именно, сделав с новым элементом такое:
1)добавив его в разбиение как новое подмножество
2)добавив его в одно из подмножеств разбиения.
Всё вышесказанное порождает следующий рекуррентный алгоритм расчёт количества разбиений множества. Для определённости пусть 5-множество разбивается по схеме 3+2, тогда нужно вычислить:
N(3,2)=N(2,2)*2+N(3,1)
(множитель 2 для 1-го слагаемого потому, что добавлять новый элемент можно в одну из 2-х позиций)
N(3,1)=N(2,1)+N(3)
(по народным поверьям сначала вычисляем более старшее число)
N(3)=1
(банальный случай: разбить 3-множество по 3 можно только 1 способом)
N(2,1)=N(1,1)*2+N(2)
N(2)=1
N(1,1)=1
(еще 1 банальный случай: разбиение всякого множества по 1-ому элементу – единственно. Так как нам неважен порядок раскладки по этим подмножествам.)
N(1,1)=N(1)
Так что, теория разбиений создана?
Да, создана, но расчёт по ней весьма трудоёмок.
Но нельзя ли в ней как-то использовать инструменты комбинаторики? Может, что-то более простое получится?
Казалось бы, задачу определения количества разбиений множества можно решить посредством инструмента сочетаний (который определяет количество подмножеств множества). Но не так-то всё просто оказывается.
Например, нужно найти число разбиений 5-множества по схеме 3+2. Тогда количество подмножеств из 5 по 3 равно
С(5,2) = 5!/(5-2)!/2! = 5*4/2 = 10
А количество подмножеств из 5 по 2 равно
С(5,3) = 5!/(5-3)!/3! = 5*4*3/(3*2) = 10
Чему же в итоге равно количество разбиений, 10*10? А ведь согласно найденной рекуррентной теории N(3,2)=10
Объясняется это так: каждому подмножеству из С(5,2) соответствует зеркальное ему подмножество из С(5,3), а порядок следования подмножеств в разбиении не важен. Таким образом, N(3,2)=10.
Займёмся другим примером. Пусть надо найти количество разбиений 4-множества по схеме 2+2.
Количество сочетаний в этом случае равно С(4,2)=4!/(4-2)!/2! = 4*3/2=6, а именно:
ab, ac, ad, bc, bd, cd
Но количество разбиений – это не количество сочетаний, а количество сочетаний из сочетаний. А оно таково:
ab+cd, ac+bd, ad+bc
Таким образом N(2,2)= С(4,2)/2
И такое деление будет иметь место для каждого разбиения, в котором мощности подмножеств совпадают. Но на 2 делим, когда мощности совпадают для 2 подмножеств.
А если для бОльшего количества? Оставим этот вопрос на потом.
А пока разовьём и далее применение сочетаний для решения данных задач.
Построим все разбиения N(2,1,1):
ab+c+d, ac+b+d, ad+b+c, bc+a+d, bd+a+c, cd+a,b
Итого 6 разбиений (скажу по секрету: для построения чего я использовал разбиение N(2,2))
Сделаем расчёт:
1)количество вариантов 1-го подмножества = С(4,2)=6 (выбираем из 4 исходных элементов 2)
2)при этом количество вариантов 2-го подмножества = С(4-2,1)=2 (из 2 оставшихся (=невыбранных) элементов выбираем 1)
3)при этом количество вариантов 3-го подмножества = С(2-1,1)=1 (из 1 оставшихся элементов выбираем 1)
Т.к. мощность 2-го и 3-го подмножества равны, то делим на 2. Итого:
N(2,1,1)= С(4,2)* С(4-2,1)* С(2-1,1)=6*2*1/2=6
Что совпадает в том числе и с построением.
Вычислим с помощью сочетаний количество разбиений N(3,2,1)
1)количество вариантов 1-го подмножества С(6,3)=6!/(6-3)!/3! = 6*5*4/(3*2)=20
2)количество вариантов 2-го подмножества С(6-3,2)=3!/(3-2)!/2! = 3*2/2=3
3)количество вариантов 3-го подмножества С(3-2,1)=1
Т.к. идентичности подмножеств в данном случае нет, то деления на фактор идентичности нет.
Итого: N(3,2,1) =20*3*1=60.
Всё, теория разбиения множеств создана!
**
Но возвратимся к исходной задаче.
В классе 30 учеников, среди них 2 друга. Для изучения иностранных языков класс разбили на 2 группы, в 1-ой 16 человек (английский язык), во 2-ой -14 (китайский язык). Спрашивается, какова вероятность того, что друзья окажутся в одной группе?
После чего становится понятно, что созданной только что теории разбиения множеств для решения её недостаточно. Как же подступиться к её решению?
Для этого пойдём на хитрость: пусть множество 2-х друзей, являющееся подножеством класса, уже разбито всеми возможными способами на подножества.
А именно, получится N(2)=1 (когда оба друга в одном подмножестве) и N(1,1)=1 (когда друзья в разных подмножествах)
Так почему бы теперь не «разбавить» это разбиение всеми остальными учениками данного класса, до получения реальной картины разбиения уже класса?
Вот и получится
Теория разбиения подмножества множества на фоне разбиения множества
Что, учитывая созданную ранее теорию выращивания разбиений из более простых разбиений, сделать совсем не сложно.
Продемонстрируем это на примере выращивания N(3,3) из N(1,1):
1)вариантов наращивания 1-го подмножества = С(6-2,2) = С(4,2) = 6
(из 4 оставшихся элементов (т.к. 2 уже задействовано в начальном множестве) выбираем 3-1=2 недостающих элемента)
2)вариантов наращивания 2-го подмножества = С(4-2,2) = С(2,2) = 1
(из 2 оставшихся элементов (т.к. 2 уже задействовано в начальном множестве, а потом выбрано еще 2) выбираем 3-1=2 недостающих элемента.
Итого количество вариантов наращивания N(1,1) –> N(3,3) = 6*1=6. => D(3,3)=6
С учётом же того, что N(3,3)=10, c точки же зрения теории вероятности это выглядит так: если класс из 6 человек, содержащий 2-х друзей, разбить на группы по 3 человека, то вероятность того, что друзья окажутся в разных группах, равна 6/10.
Но, раз так, то вероятность разделения друзей = 4/10. (ведь иных вариантов разбиения 2-множества нет, чего не скажешь о 3-множестве и т.д.) Докажем это.
Чтобы это сделать, возьмём за исходное разбиение не N(1,1), а N(2). Напомню, что конечное разбиение N(3,3).
Отсюда:
1)вариантов наращивания 1-го подмножества = С(6-2,1) = С(4,1) = 4
2)вариантов наращивания 2-го подмножества = С(4-1,3) = С(3,3) = 1
Итого количество вариантов наращивания N(2) –> N(3,3) =4 => A(3,3)=4
Следовательно, если класс из 6 человек, содержащий 2-х друзей, разбить на группы по 3 человека, то вероятность того, что друзья окажутся в одной группе, равна 4/10.
Что и требовалось доказать!
Аналогично решаются и все подобные задачи, и в том числе где «друзей» больше, чем 2.
Итак, теория разбиения подмножества множества на фоне разбиения множества
построена!
Стоп, еще чуть-чуть осталось. А именно, обещанный мною выше ответ на вопрос, каков фактор идентичности для разбиения, например, N(1,1,1)
Поскольку разбивается 3-множество, то:
1)количество вариантов выбора 1-го подмножества = С(3,1)=3
2)количество вариантов выбора 2-го подмножества = С(3-1,1)=2
3)количество вариантов выбора 3-го подмножества = С(2-1,1)=1
Итого количество разбиений … нет, не 3*2*1, а всего лишь N(1,1,1)=6/P(3), т.к. фактор идентичности здесь P(3), ведь по определению мощность множества разбиений не зависит от порядка элементов этого множества.