Давайте посмотрим сколько минтермов различных рангов существует. Если нам надо взять k предметов из N - то количество перестановок равно: Сочетания из n объектов по k: n! С(n,k) = --------------- (n-k)! * k! где n! - факториал n! = n * (n-1) * (n-2) * ... * 2 * 1 1! = 1 0! = 1 Другая форма записи, практикуемая в американской литературе: n ( ) = C(n,k) k Свойства: С(n,k) = C(n, n-k) C(n,k) = C(n-1, k-1) + C(n-1, k) C(n,0) + C(1,0) + ... + C(n,n) = 2^n n n-1 n-1 ( ) = ( ) + ( ) r r-1 r r --- m+n \ m n ( ) = / ( ) ( ) r --- k r-k k=0 n --- 2n \ n 2 ( ) = / ( ) n --- k k=0
Биномальные коэффициенты
Треугольник Паскаля: n 1 0 1 1 1 1 2 1 2 1 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6 1 7 21 35 35 21 7 1 7 1 8 28 56 70 56 28 8 1 8
Для трех переменных: Мультиномиальные коэффициенты:
[1,0,0] = 1
[2,0,0] = 1 [1,1,0] = 2
[3,0,0] = 1 [2,1,0] = 3 [1,1,1] = 6
[4,0,0] = 1 [3,1,0] = 4 [2,2,0] = 6 [2,1,1] = 12
[5,0,0] = 1 [4,1,0] = 5 [3,2,0] = 10 [3,1,1] = 20 [2,2,1] = 30
[6,0,0] = 1 [5,1,0] = 6 [4,2,0] = 15 [4,1,1] = 30 [3,3,0] = 20 [3,2,1] = 60 [2,2,2] = 90
[7,0,0] = 1 [6,1,0] = 7 [5,2,0] = 21 [5,1,1] = 42 [4,3,0] = 35 [4,2,1] = 105 [3,3,1] = 140
Для четырех переменных:
[1,0,0,0] = 1
[2,0,0,0] = 1 [1,1,0,0] = 2
[3,0,0,0] = 1 [2,1,0,0] = 3 [1,1,1,0] = 6
[4,0,0,0] = 1 [3,1,0,0] = 4 [2,2,0,0] = 6 [2,1,1,0] = 12 [1,1,1,1] = 24
[5,0,0,0] = 1 [4,1,0,0] = 5 [3,2,0,0] = 10 [3,1,1,0] = 20 [2,2,1,0] = 30 [2,1,1,1] = 60
[6,0,0,0] = 1 [5,1,0,0] = 6 [4,2,0,0] = 15 [4,1,1,0] = 30 [3,3,0,0] = 20 [3,2,1,0] = 60 [3,1,1,1] = 120 [2,2,2,0] = 90 [2,2,1,1] = 180
Сочетания
Пример сочетаний: для числа переменных N=2: --------------------- 1 2 1 --------------------- XX X- -- -X --------------------- 2
для числа переменных N=3: -------------------------- 1 3 3 1 -------------------------- XXX XX- X-- --- X-X -X- -XX --X -------------------------- 3
для числа переменных N=4: ------------------------------------ 1 4 6 4 1 ------------------------------------ XXXX XXX- XX-- X--- ---- XX-X X-X- -X-- X-XX -XX- --X- -XXX X--X ---X -X-X --XX ------------------------------------ 4
для числа переменных N=5: --------------------------------------------- 1 5 10 10 5 1 --------------------------------------------- XXXXX XXXX- XXX-- ---XX ----X ----- XXX-X XX-X- --X-X ---X- XX-XX X-XX- -X--X --X-- X-XXX -XXX- X---X -X--- -XXXX XX--X --XX- X---- X-X-X -X-X- -XX-X X--X- X--XX -XX-- -X-XX X-X-- --XXX XX--- --------------------------------------------- 5
для числа переменных N=6: ------------------------------------------------------ 1 6 15 20 15 6 1 ------------------------------------------------------ XXXXXX XXXXX- XXXX-- XXX--- ----XX -----X ------ XXXX-X XXX-X- XX-X-- ---X-X ----X- XXX-XX XX-XX- X-XX-- --X--X ---X-- XX-XXX X-XXX- -XXX-- -X---X --X--- X-XXXX -XXXX- XX--X- X----X -X---- -XXXXX XXX--X X-X-X- ---XX- X----- XX-X-X -XX-X- --X-X- X-XX-X X--XX- -X--X- -XXX-X -X-XX- X---X- XX--XX --XXX- --XX-- X-X-XX XX---X -X-X-- -XX-XX X-X--X X--X-- X--XXX -XX--X -XX--- -X-XXX X--X-X X-X--- --XXXX -X-X-X XX---- --XX-X X---XX -X--XX --X-XX ---XXX ------------------------------------------------------ 6
для числа переменных N=7: ----------------------------------------------------------------- 1 7 21 35 35 21 7 1 ----------------------------------------------------------------- XXXXXXX XXXXXX- XXXXX-- XXXX--- XXXXX-X XXXX-X- XXX-X-- XXXX-XX XXX-XX- XX-XX-- XXX-XXX XX-XXX- X-XXX-- XX-XXXX X-XXXX- -XXXX-- X-XXXXX -XXXXX- XXX--X- -XXXXXX XXXX--X XX-X-X- XXX-X-X X-XX-X- XX-XX-X -XXX-X- X-XXX-X XX--XX- -XXXX-X X-X-XX- XXX--XX -XX-XX- XX-X-XX X--XXX- X-XX-XX -X-XXX- -XXX-XX --XXXX- XX--XXX XXX---X X-X-XXX XX-X--X -XX-XXX X-XX--X X--XXXX -XXX--X -X-XXXX XX--X-X --XXXXX X-X-X-X -XX-X-X X--XX-X -X-XX-X --XXX-X XX---XX X-X--XX -XX--XX X--X-XX -X-X-XX --XX-XX X---XXX -X--XXX --X-XXX ---XXXX ----------------------------------------------------------------- 7
8
Каким образом считать двойные сочетания.
Но для каждой уникальной перестановки возможно 2^R вариантов Минтермов. примеры: ------------------------------------------------------ 2 3 2 3 ранг минтерма XX- X-XX X--X X--X-X- перестановка ------------------------------------------------------ 00- 0-00 0--0 0--0-0- варианты 01- 0-01 0--1 0--0-1- 10- 0-10 1--0 0--1-0- 11- 0-11 1--1 0--1-1- 1-00 1--0-0- 1-01 1--0-1- 1-10 1--1-0- 1-11 1--1-1- ------------------------------------------------------ Таким образом: Количество переменных = N Количество минтермов ранга R = С(N,R) * 2^R Пример для N=3 ранга 3: 1 * 2^3 = 1 * 8 = 8 ранга 2: 3 * 2^2 = 3 * 4 = 12 ранга 1: 3 * 2^1 = 3 * 2 = 6 ранга 0: 1 * 2^0 = 1 * 1 = 1 Например для N=4: ранга 4: 1 * 2^4 = 1 * 16 = 16 ранга 3: 4 * 2^3 = 4 * 8 = 32 ранга 2: 6 * 2^2 = 6 * 4 = 24 ранга 1: 4 * 2^1 = 4 * 2 = 8 ранга 0: 1 * 2^0 = 1 * 1 = 1 Пример для N=5 ранга 5: 1 * 2^5 = 1 * 32 = 32 ранга 4: 5 * 2^4 = 5 * 16 = 80 ранга 3: 10 * 2^3 = 10 * 8 = 80 ранга 2: 10 * 2^2 = 10 * 4 = 40 ранга 1: 5 * 2^1 = 5 * 2 = 10 ранга 0: 1 * 2^0 = 1 * 1 = 1 Для N=6: ранга 6: 1 * 2^6 = 1 * 64 = 64 ранга 5: 6 * 2^5 = 6 * 32 = 192 ранга 4: 15 * 2^4 = 15 * 16 = 240 ранга 3: 20 * 2^3 = 20 * 8 = 160 ранга 2: 15 * 2^2 = 15 * 4 = 60 ранга 1: 6 * 2^1 = 6 * 2 = 12 ранга 0: 1 * 2^0 = 1 * 1 = 1
Собственно говоря строки треугольника Паскаля - это еще и коэффициенты при членах разложения (x + 1)^N (x + 1)^0 = 1 (x + 1)^1 = x + 1 (x + 1)^2 = x^2 + 2*x + 1 (x + 1)^3 = x^3 + 3*x^2 + 3*x + 1 Геометрический смысл: Геометрический смысл биномальных коэффициентов
Перестановки из n объектов по r: n! P(n,r) = -------------- (n-r)! Перестановки
1
----- 1 1 -----
2
e: --------- 1 2 1 2 ---------
--------- 1 2 2 1 ---------
2 из 3: Сочетания Перестановки порядок порядок неважен важен (12) [12] [21] (13) [13] [31] (23) [23] [32] 3
---------- 1 2 3 1 2 3 ---------
---------- 1 2 3 3 1 2 ----------
---------- 1 2 3 2 3 1 ----------
---------- 1 2 3 1 3 2 ----------
---------- 1 2 3 2 1 3 ----------
---------- 1 2 3 3 2 1 ----------
2 из 4: Сочетания Перестановки порядок порядок неважен важен (12) [12] [21] (13) (23) [13] [31] [23] [32] (14) (24) (34) [14] [41] [24] [42] [34] [43] 3 из 4: класс 0-0-1 (123) (234) (341) = (134) (412) = (124) все упорядоченно: Сочетания Перестановки порядок порядок неважен важен 123 [123] [132] [213] [231] [312] [321] 124 [124] [142] [214] [241] [412] [421] 134 [134] [143] [314] [341] [413] [431] 234 [234] [243] [324] [342] [423] [432] 4 из 4: 4
Тождество --------- 1 2 3 4 1 2 3 4 ---------
Вращение -90 --------- 1 2 3 4 4 1 2 3 ---------
Вращение -180 --------- 1 2 3 4 3 4 1 2 ---------
Вращение -270 --------- 1 2 3 4 2 3 4 1 ---------
Отражение через вертикаль --------- 1 2 3 4 2 1 4 3 ---------
Отражение через горизонталь --------- 1 2 3 4 4 3 2 1 ---------
Отражение LD-RU диоганаль --------- 1 2 3 4 3 2 1 4 ---------
Отражение LU-RD диагональ --------- 1 2 3 4 1 4 3 2 ---------
Отражение через центр --------- 1 2 3 4 3 4 1 2 --------- оно в данном случае экивалентно повороту на 180'
Вырожденный случай - обмен пары Таких случаев 6 - потому что 6 пар. --------- 1 2 3 4 (1 - 2) 2 1 3 4 --------- --------- 1 2 3 4 (1 - 3) 3 2 1 4 --------- --------- 1 2 3 4 (1 - 4) 4 2 3 1 --------- --------- 1 2 3 4 (2 - 3) 1 3 2 4 --------- --------- 1 2 3 4 (2 - 4) 1 4 3 2 --------- --------- 1 2 3 4 (3 - 4) 1 2 4 3 ---------
Вырожденный случай - вращение трешки вправо Таких случаев 4, потому что 4 трешки --------- 1 2 3 4 [123] 3 1 2 4 --------- --------- 1 2 3 4 [124] 4 1 3 2 --------- --------- 1 2 3 4 [134] 4 2 1 3 --------- --------- 1 2 3 4 [234] 1 4 2 3 ---------
Вырожденный случай - вращение трешки влево Таких случаев 4, потому что 4 трешки --------- 1 2 3 4 [123] 2 3 1 4 --------- --------- 1 2 3 4 [124] 2 4 3 1 --------- --------- 1 2 3 4 [134] 3 2 4 1 --------- --------- 1 2 3 4 [234] 1 3 4 2 ---------
Вращение (только по другим переменным) ---------- 1 2 3 4 2 4 1 3 ----------
тоже но в обратную сторону ---------- 1 2 3 4 3 1 4 2 ----------
Еще одно вращение по другим переменным ---------- 1 2 3 4 4 3 1 2 ----------
тоже но в обратную стророну ---------- 1 2 3 4 3 4 2 1 ---------- Всего перестановок 24 (мы их все описали базируясь на геометрическом смысле). Теперь полный список: ------------------------------------------- 1 2 3 4 e 1 2 4 3 обмен 3-4 1 3 2 4 обмен 2-3 1 3 4 2 вращение [234] влево 1 4 2 3 вращение [234] вправо 1 4 3 2 отражение по оси 1-3, обмен 2-4 2 1 3 4 обмен 1-2 2 1 4 3 отражение вертикаль 2 3 1 4 вращение [123] влево 2 3 4 1 поворот -270/+90 2 4 1 3 вращение вправо 2 4 3 1 вращение [124] влево 3 1 2 4 вращение [123] вправо 3 1 4 2 вращение 3 2 1 4 отражение по оси 2-4, обмен 1-3 3 2 4 1 вращение [134] влево 3 4 1 2 поворот -180/+180, отражение через центр 3 4 2 1 вращение 4 1 2 3 поворот -90/+270 4 1 3 2 вращение [124] вправо 4 2 1 3 вращение [134] вправо 4 2 3 1 обмен 1-4 4 3 1 2 вращение 4 3 2 1 отражение горизонталь -------------------------------------------
5
И 4 других аналогичных
6
-------------------------- Число Число разбиений -------------------------- 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 42 -------------------------- Диаграммы Юнга. Разбиения
[1]
[2] [1,1]
[3] [2,1] [1,1,1]
[4] [3,1] [2,2] [2,1,1] [1,1,1,1]
[5] [4,1] [3,2] [3,1,1] [2,2,1] [2,1,1,1] [1,1,1,1,1]
[6] [5,1] [4,2] [4,1,1] [3,3] [3,2,1] [3,1,1,1] [2,2,2] [2,2,1,1] [2,1,1,1,1] [1,1,1,1,1,1]
[7] [6,1] [5,2] [5,1,1] [4,3] [4,2,1] [4,1,1,1] [3,3,1] [3,2,2] [3,2,1,1] [3,1,1,1,1] [2,2,2,1] [2,2,1,1,1] [2,1,1,1,1,1] [1,1,1,1,1,1,1]
[8] [7,1] [6,2] [6,1,1] [5,3] [5,2,1] [5,1,1,1] [4,4] [4,3,1] [4,2,2] [4,2,1,1] [4,1,1,1,1] [3,3,2] [3,3,1,1] [3,2,2,1] [3,2,1,1,1] [3,1,1,1,1,1] [2,2,2,2] [2,2,2,1,1] [2,2,1,1,1,1] [2,1,1,1,1,1,1] [1,1,1,1,1,1,1,1]
Мультиномальные коэфициенты: Предположим что у нас 4 переменных, и 7 степень, нам подходят только те разбиения в которых число партиций не превышает 4. то есть число партиций [7] 1 - OK [6,1] 2 - OK [5,2] 2 - OK [5,1,1] 3 - OK [4,3] 2 - OK [4,2,1] 3 - OK [4,1,1,1] 4 - OK [3,3,1] 3 - OK [3,2,2] 3 - OK [3,2,1,1] 4 - OK [3,1,1,1,1] 5 - NONE [2,2,2,1] 4 - OK [2,2,1,1,1] 5 - NONE [2,1,1,1,1,1] 6 - NONE [1,1,1,1,1,1,1] 7 - NONE
Диаграммы Юнга и перестановки
столбик из двух - это обмен
В принципе столбик это поворот (тройки или четверки). Ниже будут указаны результатирующие индексы для таких столбиков.
Тождество - оно одно 1234 ---------- 1 2 3 4 1 2 3 4 ----------
Обмен пары. Всего существует 6 вариантов: 123 123 4 4 ---------- ---------- 1 2 3 4 1 2 3 4 4 2 3 1 1 4 3 2 ---------- ---------- 124 124 3 3 ---------- ---------- 1 2 3 4 1 2 3 4 3 2 1 4 1 3 2 4 ---------- ---------- 134 123 2 4 ---------- ---------- 1 2 3 4 1 2 3 4 2 1 3 4 1 2 4 3 ---------- ----------
Обмен двух пар: 12 13 12 34 24 43 ---------- ---------- ---------- 1 2 3 4 1 2 3 4 1 2 3 4 3 4 1 2 2 1 4 3 4 3 2 1 ---------- ---------- ---------- Всего есть 3 варианта - двух пар.
Вращение троек: Всего есть 4 тройки, каждая может быть повернута вправо или влево. 41 31 23 43 2 4 4 1 3 2 1 2 ---------- ---------- ---------- ---------- 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 4 2 3 1 3 4 2 2 4 3 1 4 1 3 2 ---------- ---------- ---------- ---------- 32 42 24 34 4 1 3 1 1 3 1 2 ---------- ---------- ---------- ---------- 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 3 2 4 1 4 2 1 3 2 3 1 4 3 1 2 4 ---------- ---------- ---------- ----------
Вращения 2 4 3 1 4 2 1 3 ---------- ---------- 1 2 3 4 1 2 3 4 2 3 4 1 4 1 2 3 ---------- ---------- (1234)~> <~(1234)
2 3 3 4 4 1 4 3 1 4 2 1 3 2 1 2 ---------- ---------- ---------- ---------- 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 2 4 1 3 3 1 4 2 3 4 2 1 4 3 1 2 ---------- ---------- ---------- ---------- (1243)~> <~(1243) (1324)~> <~(1324)
Почему вращений всего 6? 1 фиксируем на 1й позиции тогда возможные варианты: 1.234 1.243 1.324 1.342 = - 1.243 тоже но вращение в другую сторону 1.423 = - 1.324 тоже но вращение в другую сторону 1.432 = - 1.234 тоже но вращение в другую сторону 1234 left = 2341 = 3412 right 1234 right = 4123 = 3412 left 1243 left = 2431 = 4312 right 1243 right = 3124 = 4312 left 1324 left = 3241 = 2413 right 1324 right = 4132 = 2413 left
Композиция - это как разбиенее, но порядок слагаемых учитывается. Поэтому композиций получается больше чем разбиений. [1] Композиции
[2,0] [1,1] [0,2] 2
3
[3,0,0] [2,1,0] [2,0,1] [1,2,0] [1,1,1] [1,0,2] [0,3,0] [0,2,1] [0,1,2] [0,0,3]
[3,0,0]
[2,1,0]
[2,0,1]
[1,2,0]
[1,1,1]
[1,0,2]
[0,3,0]
[0,2,1]
[0,1,2]
[0,0,3]
[4,0,0,0] [3,1,0,0] [3,0,1,0] [3,0,0,1] [2,2,0,0] [2,0,2,0] [2,0,0,2] [2,1,1,0] [2,1,0,1] [2,0,1,1] [1,3,0,0] [1,2,1,0] [1,2,0,1] [1,1,1,1] [1,0,3,0] [1,0,2,1] [1,0,1,2] [0,4,0,0] [0,3,1,0] [0,3,0,1] [0,2,2,0] [0,2,1,1] [0,2,0,2] [0,1,3,0] [0,1,2,1] [0,1,1,2] [0,1,0,3] [0,0,4,0] [0,0,3,1] [0,0,2,2] [0,0,1,3] [0,0,0,4] 4