Задача комівояжера

https://www.slideshare.net/OleksiiMolchanovskyi/12-graphs-slides

Комбінаторика пофарбованої площини

Нещодавно дізнався про такий дивовижний факт. 

Проблема розфарбування карт на двовимірній поверхні була вирішена ще в 19 ст. - для поверхонь "з дірками", тобто поверхня топологічного роду більше 0. Загальна формула така:

X(g)=[(7+(1+48g)^1/2)/2] - це мінімальна кількість кольорів, в яку можна розфарбувати карту на поверхні роду g.

 Рід поверхні, або Ейлерову характеристику, визначають за формулою Ейлера

 2-2g=V+C-E, де V - кількість вершин графа, C - кількість клітин, E - кількість ребер. 

Клітини мають бути гомеоморфними кругу, тоді g буде залежати лише від поверхні, а не від графа.

Доведення цієї формули зовсім елементарне, вміщується на одну сторінку, але - лише як нерівність при g>0. Рівність була доведена пізніше, у 1965 р.

 Найдивовижніше те, що для площини (або сфери, що те саме), тобто при g=0 ця формула теж вірна, але це було встановлено тільки у 1980-ті роки комп'ютерним перебором; "нормального" доведення досі не існує.

Але ця формула не дає можливості з'ясувати, у скільки кольорів фарбується заданий граф, тому що визначення мінімального роду графа - дуже складна задача (насправді, NP-повна).

https://www.lektorium.tv/lecture/24312

Задачі для математичного гуртка

Числова послідовність а(n) = 2(n-1)!-n+1

Числова послідовність:  а₁=2,  а₂=1,  а₃=2,   а₄=9, а₅=44,  … 

                                         а_n = 2(n-1)!-n+1.

У цій статті розглядається числова послідовність,яка використовується

для підрахунку властивостей перестановок.

Нехай є n місць, в яких розташовані натуральні числа від 1 до n.

Нехай є множина М, яка складається із n елементів: 1, 2, 3,…, n. Якщо переставляти ці елементи можливими способами, залишаючи незмінним їх загальне число, одержуємо декілька послідовностей: 

(а₁, а₂, а₃, … ,а_n);   (а₂, а₁,  а₃,…,а_n);   (а₃, а₂, а₁,  … ,а_n);   …      (а_n, а_n-1,а_n-2,…, а₂, а₁)   і т. д.

Кожна з таких послідовностей є перестановкою із даних n елементів.

Перестановкою (the permutation) із n елементів називається будь-яка скінченна послідовність (progression), яка одержується в результаті упорядкування деякої скінченної множини, складеної з n елементів. Число всіх перестановок із n елементів позначається Р_n. Це число дорівнює добутку всіх цілих чисел від 1 до n. Позначають:

.

Добуток n перших натуральних чисел прийнято позначати символом n!

Символ n! читають "eн факторіал". Це слово походить від латинського factor, що означає “множник”. При n=1 у виразі  залишається одне число 1. Тому приймається (як визначення), що 1!=1. При n=0 вираз  немає змісту, з числа 0 існує одне переміщення, тому приймається, що 0!=1. Значить, Р_n=n! правильна формула .

Приклад. Якою кількістю способів можна розсадити 8 студентів в ряд з 8 місць:

.

Класична задача на перестановках. Знайти формулу, яка знаходить кількість перестановок Р_n+1, що породжена множиною М, яка складається із n+1 елементів, тобто натуральних чисел: 1, 2, 3,…, n+1 і в яких хоча б один номер місця в перестановці дорівнює натуральному числу, яке стоїть на цьому місці.

Розв’язання.  Доведемо формулу, що задовольняє умову класичної задачі:

F(n+1)=n(n!-(n-1)!+1).

Формула виконується для n=1,  F(2)=1*(1!-(1-1)!+1)=1*(1-1+1)=1*1=1. Маємо дві перестановки з чисел: (1;2) та (2; 1). Номер першого місця і число 1 рівні між собою, і це виконується  тільки в одному варіанті: (1;2).

Формула виконується для n=2,  F(3)=2*(2!-(2-1)!+1)=2*(2-1+1)=2*2=1. 

Маємо шість перестановок із трьох чисел:

 (1;2;3) , (1; 3; 2),

(2;1;3) , (2; 3; 1),  

(3;2;1) , (3; 1; 2).  

У деяких перестановках номер місця і числа рівні між собою, і це виконується  в чотирьох  перестановках, а саме: (1;2;3) , (1; 3; 2), (2;1;3) , (3;2;1). Звертаємо увагу на те, що маємо три перестановки, у яких співпадає тільки один номер і одне число та одна перестановка у якої всі номери співпали з числами. Звертаємо увагу на те, що маємо  2 перестановки(синій колір), у яких немає жодного співпадіння номера і числа.

Формула виконується для n=3,  F(4)=3*(3!-(3-1)!+1)=3*(6-2+1)=3*5=15. 

Маємо двадцять чотири перестановки із чотирьох чисел:

(1;2;3;4) , (1; 2; 4; 3), (1;3;2; 4) , (1; 3; 4;2), (1;4;2;3) , (1; 4; 3; 2).

(2;1;3;4) , (2; 1; 4; 3), (2;3;1; 4) , (2; 3; 4;1), (2;4;1;3) , (2; 4; 3; 1).

(3;1;2;4) , (3; 1; 4; 2), (3;2;1; 4) , (3; 2; 4;1), (3;4;2;1) , (3; 4; 1; 2).

(4;1;3;2) , (4; 1; 2; 3), (4;2;3; 1) , (4; 2; 1; 3), (4;3;2;1) , (4; 3; 1; 2).

 У деяких перестановках номер місця і числа рівні між собою, і це виконується  в п’ятнадцяти  перестановках, а саме в перестановках, що мають червоний колір. Звертаємо увагу на те, що маємо  8 перестановок, у яких співпадає тільки один номер і одне число.   Звертаємо увагу на те, що маємо 6 перестановок,  у яких  тільки два номери співпали з числами.  Звертаємо увагу на те, що маємо  1 перестановку, у яких співпадають чотири номери з числами.  Звертаємо увагу на те, що маємо  9 перестановок(синій колір), у яких немає жодного співпадіння номера і числа. ( Тільки три номери  співпадати з числами  не можуть, бо завжди  потрібно щонайменше  два місця , аби вони були заповнені  не тотожними числами.)

Формула виконується для n=4,  F(5)=4*(4!-(4-1)!+1)=4*(24-6+1)=4*19=76. 

Маємо 120 різних перестановок із п’яти чисел.  У деяких перестановках номер місця і числа рівні між собою, і це виконується  в 76  перестановках, а саме: (1;2;3;4;5) , (1; 2; 3; 5; 4), (1;2;4;3; 5) ,…  і так далі.

Звертаємо увагу на те, що маємо  45 перестановок, у яких співпадає тільки один номер і одне число.   Звертаємо увагу на те, що маємо 24 перестановки,  у яких  тільки два номери співпали з числами.  

Звертаємо увагу на те, що маємо 6 перестановок,  у яких  тільки три номери співпали з числами.  Звертаємо увагу на те, що маємо  1 перестановку, у яких співпадають п’ять номери з числами.( Тільки чотири номери  співпадати не можуть, бо два місця мають бути заповнені не тотожними числами.) Звертаємо увагу на те, що маємо  9 перестановок(синій колір), у яких немає жодного співпадіння номера і числа.

Звертаємо увагу на те, що маємо 120-76=44  перестановок(синій колір), у яких немає жодного рівності номера позиції і самого числа в перестановці. 

Доведення формули можна продовжити переходом з індуктивним  кроком від k  до k+1.

Формула, що обраховує кількість перестановок Р_n, у яких немає жодної рівності між номером позиції  у перестановці і самого числа перестановки:

G(n)=n! -(n-1)((n-1)!-(n-2)!+1)=

=n(n-1)! -(n-1)(n-1)!+(n-1)(n-2)!-n+1=2(n-1)!-n+1

G(n)= 2(n-1)!-n+1.

n	G(n)=2(n-1)!-n+1
1	2
2	1
3	2
4	9
5	44
6	235
7	1434
8	10073
9	80632
10	725751
11	7257590
12	79833589
13	958003188
14	12454041587

Кількість перестановок, де рівність номера позиції в перестановці  і числа в перестановці
хоча б один  номер позиції  в перестановці Р(n) дорівнює  числу G(n)=(n-1)((n-1)!-(n-2)!+1)	n	1 номер позиції  в перестановці Р(n) дорівнює  числу	2 номери позиції  в перестановці Р(n) дорівнює  числу	3 номери позиції  в перестановці Р(n) дорівнює  числу	4 номери позиції  в перестановці Р(n) дорівнює  числу	Пять номерів позиції  в перестановці Р(n) дорівнють   числу	Шість номерів позиції  в перестановці Р(n) дорівнють   числу
1	1	1	0	0	0	0	0
1	2	0	1	0	0	0	0
4	3	3	0	1	0	0	0
15	4	8	6	0	1	0	0
76	5	45	20	10	0	1	0
490	6	авось?	авось?	22	15	0	1

Трикутник Ейлера.
У комбінаториці число ейлера A ( n , m ) - це число перестановок чисел від 1 до n, в яких точніше m елементи більші, ніж попередній елемент (перестановки з m "підйому"). 

Основні властивості [ редагувати ]

Для заданого значення n  > 0 індекс m в A ( n , m ) може приймати значення від 0 до n  - 1. Для фіксованого nіснує одна перестановка, яка має 0 підйому; це падаюча перестановка ( n , n  - 1, n  - 2, ..., 1). Існує також одна перестановка, яка має n  - 1 підйому; це підйомна перестановка (1, 2, 3, ..., n ). Тому A ( n , 0) та A ( n , n - 1) мають значення 1 для всіх значень n .

Зміна перестановки з м піднімається створює іншу підстановку, в якій існують n  -  m  - 1 підйому. Тому A ( n , m ) = A ( n , n  -  m  - 1).

Значення A ( n , m ) можна обчислити "вручну" для малих значень n та m . Наприклад

н	м	Перестановки	A ( n , m )
1	0	(1)	A (1,0) = 1
2	0	(2, 1)	A (2,0) = 1
	1	(1, 2 )	A (2,1) = 1
3	0	(3, 2, 1)	A (3,0) = 1
	1	(1, 3 , 2) (2, 1, 3 ) (2, 3 , 1) (3, 1, 2 )	A (3,1) = 4
	2	(1, 2 , 3 )	A (3,2) = 1

Для більших значень n , A ( n , m ) можна обчислити, використовуючи рекурсивну формулу

$${\ displaystyle A (n, m) = (nm) A (n-1, m-1) + (m + 1) A (n-1, m).}

Наприклад

$${\ displaystyle A (4,1) = (4-1) A (3,0) + (1 + 1) A (3,1) = 3 \ times 1 + 2 \ times 4 = 11.}

Значення A ( n , m ) (послідовність A008292 в OEIS ) для 0 ≤ n ≤ 9 є:

n  \ m	0	1	2	3	4	5	6	7	8
1	1
2	1	1
3	1	4	1
4	1	11	11	1
5	1	26	66	26	1
6	1	57	302	302	57	1
7	1	120	1191	2416	1191	120	1
8	1	247	4293	15619	15619	4293	247	1
9	1	502	14608	88234	156190	88234	14608	502	1

Вище трикутний масив називається трикутником Ейлера або трикутником Ейлера , і він має деякі спільні характеристики з трикутником Паскаля . Сума рядка n є факторіалом n !.