Лемма.
Доведення. Для твердження очевидно. Нехай і - канонічне розкладання числа. Тоді, враховуючи, що дільники мають вигляд , де , , …, ; , отримуємо
оскільки
Теорема. (Адитивна формула звернення Мебіуса.) Нехай і – функції натурального аргументу. Тоді, якщо 
Доведення. Маємо
Нехай. Тоді прифіксованому пробігає всі значення дільників числа. Це означає, що знаки підсумовування на останній подвійний сумі можна поміняти місцями, тобто.
Тепер, враховуючи, що
отримуємо
Є інша форма доведеної теореми:
Теорема.
(Мультиплікативна формула звернення Мебіуса.) Нехай 
де символ позначає твір, поширений попри всі дільники числа .
Доведення:
Приклади використання формули звернення Мебіуса:
Завдання про кількість кільцевих послідовностей. Див: Холл М. Комбінаторика. М.: Світ, , §.
Число ненаведених багаточленів заданого ступеня над кінцевим полем елементів. Див: Берлекемп Еге. Алгебраїчна теорія кодування. − М.: Мир, 1970, Гол. 3.
Глухов М. М., Єлізаров Ст П., Нечаєв А. А. Алгебра. У -х т. м.: Геліос, . Т., §.
Для самостійного вивчення:
Звернення Мёбіуса на частково впорядкованих множинах. Принцип включення-виключення як окремий випадок формули звернення Мебіуса. Див: Холл М. Комбінаторика. М.: Світ, , §; Бендер Е., Гольдман Дж. Про додатки звернення Мебіуса в комбінаторному аналізі. У кн.: Перечислювальні завдання комбінаторного аналізу. М.: Світ, 1971. З. - .
Порівняння для чисел поєднань
Нехай – просте число.
Лемма.
Доведення. При чисельник у формулі
Слідство.
Доведення.
Лемма.Нехай , , , − невід'ємні цілі числа, причому , . Тоді
Доведення. Маємо
З іншого боку,
Порівнюючи коефіцієнти при однакових ступенях, отримуємо необхідний результат. ∎
− подання невід'ємних цілих чисел і з основи. (Тут будь-яке ціле, при якому , ). На безлічі невід'ємних цілих чисел визначимо відношення часткового порядку (ставлення попередження) , вважаючи , тоді і лише тоді, коли
Теорема Лукаса ( ).
Доведення. Згідно з попередньою лемою,
де , . Застосовуючи лему повторно до належного числа разів, отримуємо необхідний результат. ∎
Зауваження.Теорема не вірна для непростих. Наприклад (див. Берлекемп, с. ),
Слідство.
II . Алгебраїчні структури
ІІ. 1. Безліч з бінарними операціями. Групоїди, напівгрупи, моноїди
Бінарною операцією алгебри(або законом композиції) на непорожній безлічі Sназивається відображення : , Порівняє парі , елементів , однозначно певний елемент , . На безлічі може бути задано багато операцій. (Якщо, наприклад, звичайно, то число способів дорівнює , де число елементів в .) Бажаючи виділити одну з них, наприклад, , пишуть , . Такий об'єкт називають бінарною алгеброю, або групоїдом. Замість , часто пишуть , а саму операцію позначають символом ( , , , і т.п.).
Зауваження.Поряд з бінарними операціями розглядають більш загальні -арні операції (унарні при, тернарні при і т.д.). Пов'язані із нею алгебраїчні структури (системи) становлять предмет дослідження т.зв. універсальний алгебр.
Бінарна операція на множині називається асоціативною, якщо
для будь-яких , , .
Группоїд з асоціативною операцією називають напівгрупою.
Приклад неасоціативного групоїду.На безлічі визначимо операцію як 
. Операція неасоціативна: , але .
Теорема.Якщо бінарна операція на безлічі асоціативна, то значення висловлювання залежить від розстановки у ньому дужок.
Доведення.При , або твердження очевидно. Для достатньо, застосовуючи індукцію, показати, що
для будь-яких . За припущенням індукції розміщення дужок у
Не суттєва; зокрема, .
Якщо то .
Якщо то
До такого ж виду наводиться і права частина рівності, що доводиться (1). ∎
Елемент називається нейтральнимщодо операції, якщо
для будь-якого.
Напівгрупу з елементом називають моноїдом(або напівгрупою з одиницею) і позначають , , .
У напівгрупі (групоїді) може бути не більше одного нейтрального елемента: якщо
, − нейтральні елементи, то 
Группоїд (напівгрупу) , називають підгрупоїдом (підполугрупою) групоїда (напівгрупи) , , якщо
І для будь-яких, .
У цьому випадку кажуть, що підмножина замкнуто щодо операції. Моноїд , , називають підмоноїдоммоноіда , , якщо виконується і .
Елемент моноїду , , називається оборотнимякщо знайдеться елемент такий, що 
(Очевидно, що тоді й обернемо). Якщо таку ж властивість має і елемент, тобто. 
, то з рівностей випливає, що елемент є насправді єдиним (стосовно ). Це дозволяє говорити про зворотномуелементі , до(оборотного) елементу , з властивостями: , .
Якщо , − оборотні елементи моноїду , , , то їх твір − також оборотний елемент, оскільки 
, 
. Очевидно, що оборотний елемент. Отже, має місце
Теорема.Безліч всіх оборотних елементів моноїду , , замкнено щодо операції ∗ і утворює підмоноїд в , , .
Групи
Визначення групи.Моноїд , , , всі елементи якого оборотні, називається групою.
Іншими словами, група – це безліч з бінарною операцією, для яких виконуються такі аксіоми:
. (Замкнутість операції.) , .
. (Асоціативність операції.) ,
. (Існування нейтрального елемента.) ∃ 
.
. (Існування зворотного елемента.) .
Зауваження.Повертаючись до введених вище структур алгебри, ми спостерігаємо серед них наступну ієрархію: пара , групоїдом, якщо виконується аксіома; напівгрупою, якщо виконуються аксіоми та ; моноїдом, якщо виконуються аксіоми та ; групою, якщо виконуються аксіоми , , та .
Природно визначаються ступеня елементів з очевидними властивостями:
(Раз),
; 
, (
, , .
Переставляти елементи у виразі взагалі кажучи, не можна (тобто. 
). Якщо 
, то елементи називаються перестановочними, або комутуючими. Якщо будь-які два елементи групи комутують, то група називається комутативної, або абельовий(На честь норвезького математика Ріль Хенріка Абеля (-)).
Операція групи найчастіше позначається або символом (складання), або символом (множення). При цьому група називається відповідно адитивнийабо мультиплікативної, її нейтральний елемент – відповідно нулем() або одиницею(). В адитивній групі елемент, елемент, зворотний до елемента, називається протилежнимі позначається, а замість пишуть. У мультиплікативній групі замість зазвичай пишуть , опускаючи символ операції.
Приклади адитивних груп. 1) , , , , , , , , – адитивні групи кільця та полів , , . Пишуть просто,,,,. 2) Будь-яке кільце по додаванню – абелева група. Зокрема, кільце багаточленів ,…, ] і кільце матриць, порядку над полем – абелеві групи. 3) Будь-який векторний простір над полем щодо складання – абелева група. 4) , 1,…, − повна система найменших неотрицательных відрахувань по модулю з операцією додавання по модулю .
Приклади мультиплікаційних груп. 1) , , − мультиплікативні групи полів , , . 2) − безліч оборотних елементів будь-якого кільця з одиницею щодо множення. Зокрема, =; , − безліч оборотних матриць з . 3) − всіх (речових та комплексних) коренів
, , 1,…, , − уявна одиниця,
рівняння – мультиплікативна абелева група. 4) − безліч обертань правильного -кутника у площині та у просторі − некомутативна група (при ).
Далі найчастіше використовується мультиплікативна форма запису операції. Група зазвичай позначається однією літерою без зазначення операції. Безліч всіх елементів групи називається основним безліччю групиі позначається тією ж літерою. Якщо основна множина звичайно, то група називається кінцевою; в іншому випадку вона називається нескінченною. Число елемент кінцевої групи називається її порядком. Група порядку 1 називається одиничною, або т ривіальної. Про нескінченну групу кажуть, що вона має нескінченний порядок. Для позначення порядку групи (потужності основної множини) використовуються рівноправні символи Card (кардинальне число) та ().
Якщо , − підмножини (основної множини) групи, то вважаємо
, 
, .
Підгрупоюгрупи називається підмножина в саме є групою щодо тієї ж операції, що і . Інакше кажучи, підмножина є підгрупою і тоді, коли ( одиниця в ) і замкнуто щодо множення і взяття зворотного, тобто. , (Насправді тут навіть рівності). Якщо - підгрупа в, то пишуть; якщо при цьому , то називається власноюпідгрупою і це позначається як .
1. Нагадаємо спочатку визначення важливої теоретико-числової функції Мебіу-
1, якщо n = 1
µ (n) = 0, якщо існує просте число p, p2 n (-1) k, якщо n = p1 … pk - добуток k різних простих множників.
Доведемо основну властивість функції Мебіуса:
Теорема 1.
♦ Якщо n = 1, то єдиний дільник d = 1 та (1) вірно, т.к. µ (1) = 1. Нехай тепер n > 1. Подаємо його у вигляді
n = p1 s 1 ps 2 2 K ps k k ,
де pi, i 1, k - прості числа, si - їх ступеня. Якщо d - дільник n, то d = p1 d 1 pd 2 2 K pd k k ,
де 0 ≤ di ≤ si, i 1, k. Якщо di > 1 для деякого i 1, k , то µ (d) = 0. Значить (1) потрібно розглянути тільки такі d, для яких di ≤ 1, i 1, k . Кожен такий дільник спів-
стоїть з добутку r різних простих чисел, де r 1, k , причому його внесок у суму
(1) дорівнює (-1)r і всього їх k. Таким чином, отримуємо
µ (d) = 1 − |
K + (−1) k |
0. ♦ |
||||||||
Теорема 2. (Формула звернення Мебіуса). Нехай f(n) і g(n) - функції нату- |
||||||||||
рального аргументу. Тоді рівність |
||||||||||
∑ f(d) |
||||||||||
справедливо тоді і лише тоді, коли справедлива рівність |
||||||||||
∑ µ (d)g( |
||||||||||
♦ Нехай (2) справедливо для будь-якого n. Тоді
g(d n ) = ∑ f(d′ )
d′ d n
Підставляючи в праву частину (3), отримуємо
∑ µ (d)g( |
) = ∑ µ (d) ∑ f(d′ ) |
||||||
d′ |
|||||||
Подвійне підсумовування праворуч проводиться по всіх парах d, d′, таким, що d d′n. Якщо вибрати d′, то d пробігатиме всі дільники dn′. Таким чином
∑ µ (d)g( |
) = ∑ f(d′ ) ∑ µ (d′ ) |
||||||||||||
d′ |
d′ |
||||||||||||
d′ |
n > d′ |
||||||||||||
Але згідно з (1) маємо ∑ |
|||||||||||||
µ (d′) = |
n = d′ |
||||||||||||
d′ |
|||||||||||||
d′ |
|||||||||||||
Отже, рівність (3) встановлена. Нехай тепер справедливо для будь-якого n. Тоді
∑ f(d) = |
∑ ∑ µ (d′ )g( |
) , d′′ = d d ′ - є дільником n та подвійна сума може |
||||||||||||
d′ |
||||||||||||||
n d′ |
||||||||||||||
бути переписана у вигляді |
||||||||||||||
∑ µ (d′ )g(d′′ ) = |
∑ g(d′′ ) |
∑ µ (d′ ) |
||||||||||||
d ′′ |
n d ′ |
d ′′ |
d ′′ |
d′ |
d ′′ |
|||||||||
Згідно з (1) остання сума перетворюється на одиницю у разі d′′ = n, в інших слу-
чаях вона є нуль. Це свідчить (2). ♦ 2. Розглянемо програму звернення Мебіуса.
Нехай дано алфавіт А з букв. Є sn слів довжини n у цьому алфавіті. Для кожного слова w0 = a1 a2 … an можна визначити n – 1 слів
w1 = a2 a3 … an a1 , w2 = a3 a4 … a1 a2 , … , wk-1 = an a1 … an-1 , одержуваних один з одного циклічними зрушеннями. На багатьох всіх sn слів введемо відношення еквівалентності: два слова оголосимо еквівалентними, якщо одне з іншого виходить циклічним зрушенням. Нас цікавитимуть кількість класів, які містять точно n слів. Таке завдання виникає у теорії синхронізуючих кодів.
Будемо називати слово w виродженим, якщо клас еквівалентності, що містить w, складається з менш ніж n слів. Назвемо w періодичним, якщо існує слово u та натуральне число m, таке, що w = u u … u (m разів).
Теорема 3. Слово w періодичне тоді і лише тоді, коли воно вироджене.
якості u можна взяти a 1 a 2 … a p , а як m =
♦ Зрозуміло, що якщо w періодичне, воно вироджене. Нехай w вироджено. Нехай p - мінімальне ціле, таке, що w = wp. Тоді якщо
w = a1 a2 … an , то wp = a1 + p a2 + p … an + p (індекси за модулем n). Звідси отримуємо, що n p . (Легко бачити, що p n). ♦ Обо-
значимо через M(d) - число квадратів, які містять слів d. З попереднього маємо
dn. Таким чином, справедлива формула∑ dM(d) = s n . d n
Застосуємо формулу звернення Мебіуса для випадку g(n) = sn, f(d) = dM(d). Тоді отримуємо
nM(n) = ∑ µ (d)s n d d n
∑ µ (d)sn d |
|||||||||||||
Таким чином, M(n) - цікаве для нас число. Якщо n = p – просте число, то |
|||||||||||||
− s) |
|||||||||||||
Є мультиплікативний варіант звернення Мебіуса. Справедлива |
|||||||||||||
Теорема 4. Нехай f(n) і g(n) - функції натурального аргументу, пов'язані соот- |
|||||||||||||
носінням |
|||||||||||||
f(n) = ∏ g(d) |
|||||||||||||
µ(n |
|||||||||||||
g(n) = ∏ f(d) |
|||||||||||||
і назад, з (5) випливає (4).
Використовуючи формулу звернення Мебіуса, можна вирішити важливе в практичному відношенні задачу про кількість багаточленів фіксованого ступеня, що не наводяться, над кінцевим полем. Нехай GF(q) - поле з елементів q і m - натуральне число. Тоді для числа
Φ m (q) ненаведених багаточленів над полем GF(q) справедлива формула
Наведемо таблицю перших кількох значень функції Φ m (2)
Φ m (2) |
§ 5. Перманенти та їх застосування до перелічувальних
1. Для вирішення багатьох комбінаторних завдань використовуються перманенти. Розглянемо числову матрицю
A = (ai, j), i = 1, n, j = 1, m, n ≤ m
Перманент матриці А (позначення – per А) визначається рівністю
per A = ∑ |
a 2 j L a nj |
||||
(j1, K, jn) |
|||||
де підсумовування проводиться за всіма n-перестановками з m елементів 1, 2, m. Іншими словами, перманент матриці дорівнює сумі творів елементів, взятих по одному з кожного рядка та різних стовпців.
З формули (1) випливають деякі очевидні властивості перманенту, аналогічні властивостям визначника квадратних матриць.
1. Якщо один із рядків(n× m)-матриці А (n ≤ m) складається з нулів, то per A = 0. При n = m те ж саме і для стовпців.
2. При множенні всіх елементів одного з рядків матриці на деяке число значення перманента А множиться на те ж число.
3. Перманент не змінюється при перестановці рядків і стовпців.
Позначимо через Aij - матрицю, отриману з А викресленням i-го рядка і j-го стовпця.
4. Справедлива формула розкладання перманенту по i-му рядку per A = ai1 per Ai1 + ai2 per Ai2 + ... + aim per Aim (2)
таким чином, багато властивостей перманентів аналогічні властивостям визначників.
Однак, основна властивість визначників det(AB) = detA detB не виконується для перманентів, і ця обставина сильно ускладнює їх обчислення.
Наприклад, |
|||||
2, per |
|||||||||
Однак, 4 = per |
≠ per |
||||||||
розглянемо одне з найважливіших застосувань поняття перманента в комбінаторних за-
дачах. Нехай X = (x1, xm) - кінцева множина, а X1, ..., Xn - система підмножин
При цьому кажуть, що елемент xi представляє множину Xi. Необхідність знаходження системи різних представників виникає під час вирішення багатьох прикладних завдань. Розглянемо таку задачу кодування. Нехай є деяке речення, тобто. впорядкований набір слів у певному алфавіті. Потрібно закодувати цю пропозицію так, щоб кожному слову ставилася у відповідність одна літера, причому ця літера повинна входити до складу цього слова, а різним словам повинні відповідати різні літери.
Приклад: Пропозиція a bc ab d abe c de cd e можна закодувати як abecd. У той же час пропозиція ab ab bc abc bcd не може бути закодована подібним чином, оскільки перші чотири слова в сукупності містять лише три літери.
Для системи множин X1, …, Xn визначимо матрицю інцидентності A = (aij), i = 1, n,
1, якщо xi |
||||||||
a ij = |
||||||||
0, інакше. |
||||||||
Справедлива |
||||||||
Теорема 1. Нехай A = (aij), i = |
(n ≤ m) матриця інцидентності |
|||||||
множин X1, …, Xn, де Xi X, i = 1, n, X = (x1, …, xm). Тоді для числа систем раз-
особистих представників R(X1, …, Xn) множин X1, …, Xn справедливо рівність
R(X1, …, Xn) = per A |
|||||||||||||||||
♦ Справді, оскільки в матриці А елемент aij = 1 якщо xj Xi і aij = 0 , |
|||||||||||||||||
якщо xj |
K , xi |
) елементів X є системою різних перед- |
|||||||||||||||
Xi , то набір (xi |
|||||||||||||||||
ставителів для X1, …, Xn |
в тому і тільки в тому випадку, коли a1i |
K ,a ni |
|||||||||||||||
менти a1i |
K ,a ni |
знаходяться в різних стовпцях матриці А. Підсумовуємо числа |
|||||||||||||||
a1i ,K ,a ni |
по всіх n-перестановок елементів 1, 2, … m. Тоді отримаємо з однієї сто- |
||||||||||||||||
рони число систем різних представників для X1, …, Xn, а з іншого - значення пер-
манента матриці А. ♦
a 1i 1 a 2i 2 L a ni n
Слідство. Система різних представників для X1, …, Xn існує тоді і тільки тоді, коли для відповідної матриці інцидент А виконано:
Оскільки у формулі (1) m(m – 1) … (m – n +1) членів, то обчислення перманента на основі визначення важко. Наведемо для цього загальну формулу.
2. Обмежимося розглядом квадратних числових матриць А = (aij), i, j = 1, n.
Тоді per A = ∑
(i1, K, in)
де сума поширюється по всіх перестановках i1, …, in елементів
1, 2, …, n. Застосуємо формулу включення-виключення для обчислення перманента матриці А. Кожному набору i1, …, in поставимо у відповідність вага, що дорівнює a1i 1, K, a ni n.
Значить перманент А - це сума терезів тих наборів, які відповідають перестановкам. Введемо n властивостей P1, …, Pn на множині всіх наборів i1, i2, …, in з 1, 2, …, n, де властивість Pi означає, що в наборі i1, …, in немає елемента i. Таким чином, перманент А - це сума ваг наборів i1, …, in, що не мають жодної з властивостей P1, …, Pn. Залишилося визначити суму ваг W(Pi 1 ,K , Pi k ) наборів, що володіють k властивостями
Pi 1, K, Pi k. Маємо для суми ваг W(0) всіх наборів i1, …, ik. |
|||||||||
W(0) = ∑ |
K, a ni |
= (a 11 + L + a 1n) (a 21 + L + a 2n) L (a n1 + L + a nn) |
|||||||
i1 ,K ,in |
|||||||||
W(N(Pi )) = |
a1i ,K , a ni |
= (a 11 + L + a 1i |
L + a1n) L (a n1 + L a ni + L + a nn) (9) |
||||||
≠i |
|||||||||
де знак над елементом матриці А означає, що цей елемент слід опустити. Аналогічно для sij (i< j) имеем
W(N(Pi , Pj )) = (a11 + L + a1i |
L+a 1j |
L + a1n) L (a n1 + L a ni + L + a nj + L + a nn) (10) |
|
Тепер, використовуючи формулу включення-виключення, отримуємо формулу Райзера для перманента А:
per A = ∏ i n = 1 (ai1 + L + ain ) − ∑∏ k n = 1 (a k1 + L + a ki + L + a kn )+ L + |
|||||
+ (− 1)s |
∑∏n |
||||
(a k1 + L + a ki1 |
L+a ki |
L + a kn) + L |
|||
1≤ i1< L < is ≤ k n= 1 |
|||||
Обчислення перманента за формулою Райзера можна організувати так, що потрібно
(2n - 1)(n - 4) множень та (2n - 2)(n + 1) додавань. Хоча ця величина росте швидко зі зростанням n, ця формула дає найбільш ефективний спосіб обчислення перманентів.
3. З'ясуємо тепер питання умов рівності нулю перманента (0, 1)-матрици. Обмежимося нагодою квадратної матриці.
Теорема 2. Нехай A = (aij), i, j = 1, n - (0, 1) - матриця порядку n. Тоді
per A= 0 в тому і тільки в тому випадку, коли А існує підматриця з нулів розміру s × t, де s + t = n + 1.
♦ Нехай така нульова підматриця А існує. Оскільки перманент не змінюється від перестановок рядків і шпальт, можна вважати, що ця підматриця розташована у лівому нижньому кутку, тобто.
де - (s × t) - матриця з нулів, підматриця B має розмір (n - s) × t. Будь-який член перманенту А повинен містити по одному елементу з перших стовпців t. Тому, якщо шукати позитивний член перманента, то елементи цих стовпців повинні належати попарно різним рядкам із номерами 1, 2, …, n - s. Однак n - s = t - 1< t и поэтому данное условие выполнить нельзя, т.е. per A = 0.
Нехай тепер per A = 0. Доказ теореми проводимо індукцією з n. При n = 1 твердження очевидне (А = (0)). Нехай воно справедливе всім порядків, менших n. Якщо А – нульова матриця порядку n, то твердження очевидне. Якщо А - не нульова матриця, то нехай aij = 1. Запишемо розкладання по рядку i:
per A = ai1 Ai1 + … + ain Ain
Оскільки per А = 0, то per Аij = 0. Але Аij має розмір (n - 1) × (n - 1) і припущення індукції для неї існує підматриця з нулів розміру
s1 × t1, причому s1 + t1 = n - 1 + 1 = n. Переставимо рядки та стовпці так, щоб ця нульова підматриця опинилась у нижньому лівому кутку:
A → B = |
|
де О - нульова підматриця розміру s1 × t1 , s1 + t1 = n, С - має розмір (n - s1 ) × t1 , D -
має розмір s1 × (n - t). Отже, матриці З і D - квадратні і мають порядок (t1 × t1) і (s1 × s1) відповідно. Згідно з визначенням перманента маємо per B = per A і,
per B = per C per D і тому з per А = 0 випливає, що або per C = 0, або per D = 0.
Нехай per C = 0. За припущенням індукції в Знайдеться нульова підматриця розміру
u × v, де u + v = t1 + 1. Нехай вона розташована в рядках з номерами i1, …, iu та стовпцями з номерами j1, …, jv. Розглянемо підматрицю B, що складається з рядків
i1, …, iu, t1 + 1, …, n і стовпців j1, …, jv. Це нульова підматриця розміру (u + n - t1) × v,
де u + n – t1 + v = n + +1. Отже, в матриці B вказано нульову підматрицю розміру s × t, де s + t = n + 1. Оскільки матриці А і B відрізняються перестановкою рядків і стовпців, теорема доведена. ♦
Розглянемо тепер важливий окремий випадок матриці А. Позначимо через А(k, n) - матрицю з елементів 0,1 розміру n × n з k одиницями до кожного рядка та кожного стовпця (k > 0).
Теорема 3. Для будь-якої матриці А(k, n) справедливо per А(k, n) > 0.
♦ Допустимо неприємне, що per А(k, n) = 0. Тоді за теоремою 2 існує нуль-
ма підматриця розміру s × t, де s + t = n + 1. Тоді, переставляючи рядки і стовпці матриці А(k, n) отримаємо матрицю
де - нульова (s × t)-матриця.
Підрахуємо число одиниць у матрицях B і D. Оскільки A(k, n) має k одиниць у кожному рядку та кожному стовпці, то в кожному стовпці B та кожному рядку D є точно k
одиниць. Усього А(k, n) є n k одиниць, тому nk ≥ tk + sk = (t + s)n. Таким чином
зом, n t + s, що неможливо, т.к. s + t = n + 1 З цього протиріччя слід спра-
Ведливість затвердження. ♦ Аналогічно доводиться
Теорема 3а. Нехай А - (0,1)-матриця розміру n m (n m). Тоді perА = 0 у тому і тільки в тому випадку, коли містить нульову підматрицю розміру s t, де s + t = m +1.
4. Розглянемо тепер додаток розглянутих питань до побудови ла-
тинських квадратів. Латинським (n × m)-прямокутникомнад безліччю X = (x1, ..., xm)
називається (n× m) -матриця з елементів X, в якій кожен рядок є n-перестановка X, а кожен стовпець є m-перестановка множини X. При n=m латинський прямокутник називається латинським квадратом.
Зрозуміло, що з n=1 число латинських 1× m прямокутників дорівнює m!. При n=2 після того, як обрано перший рядок, як другий можна взяти будь-яку переста-
новку, що суперечить обраній. Число таких перестановок Dm тому число 2× m -
латинських прямокутників дорівнює m! Dm.
Виникає природне питання у зв'язку з індуктивною побудовою латинських квадратів. Нехай ми збудували латинський (n×m)-прямокутник (n< m). Можно ли его расширить до ((n+1)× m) -прямоугольника добавлением (n+1)-й строки?
Справедлива
Теорема 4. Кожен латинський (n×m) -прямокутник n ♦ Нехай X=(x1 ,…,xm ) і L- латинський (n× m)-прямокутник з елементами з X. Розглянемо набір множин A1 ,… ,Am де Ai - елементи i-го стовпця латинського прямокутника L. Нехай А - матриця інцидентності системи множин A1, ..., Am. Вона має розмір m× m , і кожен рядок матриці містить точно n одиниць, оскільки Ai = n, i = 1, m . Кожен елемент xi X може з'явитися в стовпцях L не більше m разів, інакше знайшовся б рядок, в якому цей елемент зустрінеться двічі. Загальна кількість елементів L дорівнює m n, тому кожен елемент xi X з'являється у стовпцях точно n разів. Звідси випливає, що кожен стовпець матриці А містить точно n одиниць. Розглянемо тепер матрицю A отриману заміною кожної одиниці на нуль і кожного нуля на одиницю. Матриця A є матриця інцидентів системи множин X1 , … , Xn де Xi = X\Ai , i = 1, m. Вона містить по m - n одиниць у кожному рядку та у кожному стовпці. За теоремою > 0. Нехай ai1 … a mi ≠ 0 . Тоді маємо xi X1 ,K , xi Xm та всі елементи xi ,K , xi попарно різні. Рядок xi ,K , xi може бути взята як (n + 1)-ой для латинського (n × m)-прямокутника L. Продовжуючи цю процедуру, отримаємо латин- ський квадрат. ♦ Позначимо l n - число латинських квадратів порядку n, з елементами з множини X = (1, 2, ..., n), у яких елементи першого стовпця і першого рядка йдуть у природному порядку. Наведемо таблицю кількох відомих значень числа l n : 5. Матриця A = (aij ) розміру n × n із дійсними, невід'ємними елементами називається двічі стохастичної, якщо Муніципальна бюджетна загальноосвітня установа середня загальноосвітня школа з поглибленим вивченням окремих предметів с. Тербуни Стрічка Мебіуса
Виконала: Чепуріна Ганна Віталіївна, учениця 10-а класу Керівник: Кірікова М.А, вчитель математики першої кваліфікаційної категорії с.Тербуни 2015р. Вступ…………………………....................................... .................3 Історична довідка ……………………………………………4 Аркуш Мебіуса - початок нової науки топології.........................5 Виготовлення листа Мебіуса ………………………………........6 Досліди з листом Мебіуса.............................................. .................9 Топологічні властивості листа Мёбиуса ……………………..11 Теореми про стрічку Мебіуса…………………………………… .12 Фокуси зі стрічкою Мебіуса………………………………………15 Застосування листа Мёбиуса……………………………………..16 Висновок................................................. .........................................23 Список використаної литературы............................................... .25 додаток Вступ
В наш час актуальним є вивчення різних властивостей та нестандартних застосувань незвичайних фігур. Чи чули ви колись про листок Мебіуса? Як його можна зробити, як він пов'язаний з математикою і де застосовується в житті. Займаючись цією роботою, я дійшла висновку, що хоча лист Мебіуса відкрили ще в XX столітті, він був актуальний і в XX столітті, і в XX століття. Дивовижні властивості листа Мебіуса використовувалися і використовуються в кулінарії, техніці, фізиці, живопису, архітектурі, в оформленні ювелірних виробів і біжутерії. Надихав він на творчість багатьох письменників та художників. Інтерес до аркуша Мебіуса не згас і в наші дні. У Москві у вересні 2006 року відбувся Фестиваль художньої математики. З великим успіхом було прийнято виступ професора міста Токіо. Мене дуже зацікавила, зацікавила ця тема. Я вивчила літературу, потім сама виготовила аркуш Мебіуса, а потім проводила дослідження, роблячи досліди, вивчаючи його чарівні, незвичайні властивості. Стрічка Мёбіуса – паперова стрічка, повернена одним кінцем на півоберта (тобто 180 градусів) і склеєна з його іншим кінцем. Мільйони людей у всіх частинах світу навіть не підозрюють, що вони щодня використовують стрічку Мебіуса. Ціль
: розповісти і показати однокласникам, що на вигляд проста стрічка, повернена на півоберта зі склеєними кінцями, може містити в собі багато несподіванок. Об'єкт дослідження:
лист Мебіуса. Завдання:
виявити джерела та літературу з цієї теми та проаналізувати їх; ознайомитися з історією виникнення аркуша Мебіуса; навчитися виготовляти лист Мебіуса; вивчити різноманітні властивості аркуша Мебіуса; Працюючи над темою, використовувала такі
методи: аналіз, синтез, спостереження, експеримент, порівняння та соціологічне опитування. РОЗДІЛ
I
«Аркуш Мебіуса-початок нової науки»
1. 1. Історична довідка
Таємничий і знаменитий лист Мебіуса вигадав 1858 року німецький геометрСерпень Фердинанд Мебіус
. Розповідають, що відкрити свій “лист” Мебіусу допомогла служниця, яка зшила неправильно кінці довгої стрічки. Сім років він чекав на розгляд своєї роботи і, не дочекавшись, опублікував її результати. Одночасно з Мебіусом винайшов цей лист та інший учень К. Ф. Гаусса –Йоганн Бенедикт Лістинг,
професор Геттінгенського університету. Свою роботу він опублікував на три роки раніше, ніж Мебіус, – у 1862 році. А. Ф. Мебіус народився у місті Шульпфорті. Деякий час під керівництвом Гаусса вивчав астрономію. Почав вести самостійні астрономічні спостереження Плейсенбургской обсерваторії, в 1818г. став її директором. У ті часи заняття математикою не зустрічали підтримки, а астрономія давала достатньо грошей, щоб не думати про них, і залишала час для власних роздумів. Ставши професором Лейпцизького університету, з 1816 року Мебіус вперше запровадив проективну геометрію, систему координат та аналітичні методи дослідження; встановив існування односторонніх поверхонь (аркушів Мебіуса), багатогранників, для яких не застосовується «закон ребер» і які не мають об'єму. Мебіус – один із основоположників теорії геометричних перетворень, а також топології. Він отримав важливі результати теорії чисел (функція Мебіуса) і став одним з найбільших геометрів свого часу. 1.2. Стрічка Мебіуса – початок нової науки топології
З того моменту, як німецький математик А. Ф. Мебіус виявив існування дивовижного одностороннього аркуша паперу, почала розвиватися ціла нова галузь математики, яка називається топологією. Термін "топологія" може бути віднесений до двох розділів математики. Одну топологію, родоначальником якої був Пуанкаре, тривалий час називали комбінаторною. За іншою, біля витоків якої стояв німецький учений Георг Кантор, закріпилася назва загальної чи теоретико-множинної. Комбінаторна топологія – розділ геометрії. «Геометрія» - слово грецьке, у перекладі російською мовою означає «землемірство», («гео» - по – грецькою земля, а «метрео» - міряти) вивчає властивості фігур. Як і будь-яка наука, геометрія ділиться на розділи. 1. Планіметрія (лат. слово, "планум" - поверхня + метрія), розділ геометрії, що вивчає властивості фігур на площині (трикутник, квадрат, коло, коло і т.д.) 2. Стереометрія (греч, «стереос» - простір + метрія) - розділ геометрії, що вивчає властивості фігур у просторі (куля, куб, паралелепіпед тощо) З. Топологія (грецьк. «топос» - місце, місцевість + логія) є одним із «молодих» розділів сучасної геометрії, в якому вивчаються властивості таких фігур, які не змінюються, якщо їх гнути, розтягувати, стискати, але не склеювати і не рвати, тобто змінюються при деформаціях. Прикладом топологічних об'єктів є: літери І та Н, тонкі довгі повітряні кульки. Комбінаторна топологія вивчає властивості геометричних фігур, що залишаються незмінними при взаємно однозначних та безперервних відображеннях. Довгий час топологія сприймалася як наука, далека від життя, покликана лише прославляти людський розум. Але в наш час з'ясувалося, що вона має безпосереднє відношення до пояснення пристрою світобудови. Загальна топологія примикає до теорії множин і лежить в основі математики. Це аксіоматична теорія, покликана досліджувати такі поняття, як «межа», «збіжність», «безперервність» тощо. Основи аксіоматики топологічного простору було закладено Феліксом Хаусдорфом і завершено російським математиком Павлом Сергійовичем Александровым. 1.3. Як виготовляють лист Мебіуса
● Лист Мебіуса відноситься до числа (математичних несподіванок). Щоб виготовити лист Мебіуса, візьмемо прямокутну смужку АВCD, перекрутимо її на 180 градусів і склеїмо протилежні сторони АВ таCD, тобто. так що суміщаються точки А іCі крапки Dта Ст. Дивись дод. 1. 1. ● Форми та розміри паперової смужки
для аркуша Мебіуса. Смужка має бути вузькою та довгою, з можливо великим ставленням довжини до ширини. З квадратного аркуша стрічки Мебіуса не зробиш. Це правильно, але не можна недооцінювати те що, що обмеження розмір мають значення у разі, коли папір забороняється м'яти. Якщо ж м'яти папір не забороняється, то лист Мебіуса можна склеїти не тільки з квадрата, але з прямокутника будь-яких розмірів - сторони, що склеюються, можуть бути навіть у скільки завгодно разів довше не склеюваних. ● Розгортаюча поверхня.
Якщо вимога не м'яти папір важлива, подивимося, який його математичний зміст. Легко зрозуміти, що заборона м'яти папір значно обмежує можливість маніпулювати паперовим листом. Наприклад, лист паперу, не пом'явши, можна згорнути в трубку або скласти без складки навпіл, але не можна скласти вчетверо. З аркуша паперу, не зім'явши його, можна зробити конус, але не можна зробити сферу або навіть її шматочок: притисніть аркуш паперу до глобуса, і обов'язково з'являться складки. Як видно, аркуш паперу можна надати далеко не будь-яку форму. Дивись дод. 2 . Поверхні, які можна зробити з аркуша паперу, згинаючи, але, не змінюючи його, математики називають такими, що розгортаються. У математиці поверхні, що розгортаються, визначаються не так: у метаматематичній мові відсутні слова «папір», «зминати», «зробити». Існує ціла теорія поверхонь, що розгортаються, серед досягнень якої – задовільна відповідь на питання, якими вони можуть бути; математики називають це «класифікацією» (відповідь належить Леонардо Ейлер). Наведемо лише деякі властивості поверхонь, що розгортаються, як експериментальні факти. Дивись дод. 3 1.Через кожну точку А поверхні, що розгортаються, не лежать на її кордоні, проходить лежачий на поверхні відрізок, не закінчується в А. Інакше кажучи, кожній точці до поверхні, що розгортається (вигнутому, але не зім'ятому аркушу паперу) можна прикласти спицю так, щоб вона прилягала до поверхні на деякому протязі з обох боків від взятої точки. Такий відрізок називається утворює поверхні (умовимося, що ця назва відноситься тільки до відрізків максимальної довжини, що повністю лежить на поверхні, тобто до відрізків, що не містяться у великих відрізках з цією властивістю). 2.Якщо через точку А, що не лежить на межі поверхні, проходять дві різні утворюючі, причому А не є кінцем жодної з них, то досить маленький шматок поверхні, що оточує А, є плоским. У такому разі точку А ми називатимемо плоскою. 3.Якщо точка А, яка не лежить на межі поверхні, є кінцем якоїсь утворюючої, скажімо,а
, то околиця точки А влаштована так: через точку А проходить єдина не утворююча, що не закінчується в ній, допустимоb
. Ця утворювальна поділяє поверхню на дві частини. З того боку від твірноїb
, з якої знаходиться утворювальнаa
до утворюючої b
прилягає плоский шматок, з іншого бокуb
, скільки завгодно від точки А, є не плоскі точки. Точку А в цій ситуації ми називатимемо напівплоскою. Підкреслимо, що якщо точка поверхні не є ні граничною, ні плоскою, то через неї проходить єдина не утворююча, що не закінчується в ній, причому кінці цієї утворюючої лежать на межі поверхні. ●Приклади: Лист паперу, згорнутий у циліндр або конус, не має плоских (і напівплоських) точок. У циліндра утворюють складають сімейство паралельних відрізків, у конуса – сімейство відрізків, що віялом розходяться з однієї точки. Можливі складніші розташування утворюючих. Дивись дод. 4 . Наприклад, утворюють і плоскі точки поверхні, що розгортається, показані на малюнку (на ньому поверхня розгорнута в плоский аркуш паперу): тонкі лінії – утворюючі, а зафарбовані області складаються з плоских точок. Крапки, що лежать на межі області плоских точок, є або граничними для всієї поверхні, або напівплоськими. Якщо поверхня зроблена з паперового багатокутника (скажімо, з прямокутника), то плоскі точки складають один або кілька плоских багатокутників, причому у кожного з цих багатокутників вершини лежать на межі поверхні, а сторони або лежать на кордоні, або складаються з напівплоських точок. РОЗДІЛ 2
2.1. Досліди з листом Мебіуса
Кожен з нас має інтуїтивне уявлення про те, що таке «поверхня». Поверхня аркуша паперу, поверхня стін класу, поверхня земної кулі відомі всім. Чи може бути щось таємниче в такому звичайному понятті? Так, може, прикладом є лист Мебіуса. Щоб вивчити його властивості, я провела кілька дослідів (розділивши їх на дві групи) самостійно. I
група дослідів Досвід № 1. Ми звикли до того, що у будь-якої поверхні, з якої маємо справу (аркуш паперу, велосипедна або волейбольна камера) – дві сторони. Почала фарбувати листок Мебіуса, не перевертаючи його. Результат
. Аркуш Мебіуса зафарбувався повністю. « Якщо хтось надумає розфарбувати тільки один бік
поверхні мебіусової стрічки, нехай відразу занурить її у відро з фарбою»,
- пише Ріхард Курант і Герберт Робінс у чудовій книзі «Що таке математика?» Досвід №2. Виготовила з паперу павука та муху та відправила «гуляти» по
звичайному кільцю, але заборонила їм переповзати кордони. Результат.
Павук не зміг дістатися мухи. Досвід №3. Відправила цих павука та муху тільки вже по аркушу Мебіуса. І заборонила їм переповзати через кордон Результат.Бідолашна муха буде з'їдена, якщо, звичайно, павук бігає швидше! Досвід №4. Виготовила з паперу чоловічка і відправила його подорожувати стрічкою Мебіуса. Результат.
Людина повернеться до точки відправлення, в ній він зустрівся б при цьому зі своїм дзеркальним відображенням. IIгрупа дослідів пов'язана з розрізанням листа Мёбіуса, результати занесені до таблиці досвіду Опис досвіду Результат
Просте кільце розрізало посередині вздовж. Отримала два простих кільця, такої ж довжини, завширшки вдвічі вже, з двома межами. Лист Мебіуса розрізала посередині вздовж. Отримала 1 кільце, довжина якого вдвічі більша, ширина вдвічі вже, перекручена на 1 повний оборот, з одним кордоном. Лист Мебіуса шириною 5см розрізала вздовж на відстані 1см від краю. Отримала два зчеплені один з одним кільця: 1) лист Мебіуса - довжина = довжині вихідного, ширина 3см; 2) ширина 1см, довжина вдвічі більше вихідного перекручена на два повні обороти, з двома межами. Лист Мебіуса шириною 5см розрізала вздовж з відривом 2см від краю. Отримала два зчеплені один з одним кільця: 1) кільце – лист Мебіуса шириною 1см, довжина = довжина вихідного; 2) кільце - ширина 2см, вдвічі довше вихідного перекрученого на два повні обороти, з двома межами. Лист Мёбіуса шириною 5см, розрізала вздовж на відстані 3см, від краю. Отримала два зчеплені один з одним кільця:1) кільце – лист Мебіуса шириною 1см такої ж довжини; 2) кільце - шириною 2см довжина його вдвічі більше вихідного перекручена на два повні обороти. Результати проведеного соціологічного опитування з учнями 10 класу. Так Ні Чули 1. Чи знаєте ви, що таке топологія? 2. Чи знаєте ви, що таке стрічка Мебіуса? 3.Чи знаєте ви, властивості стрічки Мебіуса? Тільки 5% учнів 10-го класу знають, що таке топологія. 30% учнів знають, що таке стрічка Мебіуса. 20% чули про неї. 50% не мають уявлення про стрічку Мебіуса. 25% учнів знають властивості стрічки, 10% чули про них, 65% нічого не знають про властивості стрічки Мебіуса. 2.2.Топологічні властивості листа Мёбіуса
За результатами дослідів можна сформулювати такі топологічні властивості аркуша Мебіуса, які стосуються математичних несподіванок. Однобічність – топологічна властивість листа Мебіуса, характерне лише йому. Безперервність - на аркуші Мебіуса будь-яка точка може бути з'єднана з будь-якою іншою точкою. Розривів немає – безперервність повна. З топологічної точки зору коло не відрізняється від квадрата, тому що їх легко перетворити один на інший, не порушуючи безперервність. Зв'язність – щоб розполовинити кільце, знадобиться два розрізи. Що стосується листа Мебіуса, то кількість зв'язків замінюється в залежності від зміни кількості обертів стрічки: якщо один оборот - двозв'язковий, якщо два обороти - однозв'язковий, якщо три - двозв'язковий і т. д. А ось щоб розділити квадрат на дві частини, нам потрібно буде тільки один розріз. Зв'язок прийнято оцінювати числом Бетті, або іноді користуються ейлерової характеристики. 4.Орієнтованість - властивість, яка відсутня у листа Мебіуса. Так, якби людина змогла промандрувати по всіх вигинах аркуша Мебіуса, то тоді він повернувся б у вихідну точку, але перетворився б на своє дзеркальне відображення. 5.«Хроматичний номер» - це максимальна кількість областей, які можна намалювати на поверхні так, щоб кожна з них мала спільний кордон з усіма іншими. Хроматичний номер листа Мёбіуса дорівнює шести. 6.Теореми про стрічку Мебіуса
Через складність доказу я не розглядаю його у своїй роботі. Ця теорема простіша за попередню: для її доказу достатньо пояснити, як склеїти стрічку Мебіуса зі смужки, довжина якої більша за √3. Припустимо спочатку, що її довжина точно дорівнює √3. Тоді на цій смужці можна розташувати два правильні трикутники. Перегнемо смужку з боків цих трикутників, чергуючи напрямки згину. Краї AB і CD смужки суміщаться, причому точка A суміщається з точкою D, а точка B – з точкою C. Вийде стрічка Мебіуса, краї якої розташовуються встик.(Див. додаток 1.2) Поки задача не вирішена, важко сказати, чому вона не вирішена. Все ж таки іноді в різних невирішених завданнях вдається простежити загальні труднощі, відзначити, так би мовити, на математичній карті важкопрохідні місця, що дозволяє часом передбачити успіх або невдачу при вирішенні того чи іншого завдання Теорема 3. Стрічку Мебіуса із самоперетинами можна склеїти зі смужки будь-якої довжини, більшої π/2. Ось чому очікується, що λ = √3. Фокуси зі стрічкою Мебіуса
Проблема зав'язування вузлів
Як зав'язати на шарфі вузол, не випускаючи з його кінців? Це можна зробити так. Покладіть шарф на стіл. Схрестіть руки на грудях. Продовжуючи тримати їх у такому положенні, нагніть до столу і по черзі візьміть по одному кінці шарфа кожною рукою. Після того, як руки будуть розведені, в середині шарфа сам собою вийде вузол. Користуючись топологічною термінологією, можна сказати, що руки глядача, його корпус та шарф утворюють замкнуту криву у вигляді "трьохлистого" вузла. При розведенні рук вузол лише переміщається з рук на хустку. Зав'язати вузол на шарфі однією рукою, не випускаючи кінець шарфа із руки. Відповідь цієї головоломки можна знайти у книзі М.Гарднера "Математичні чудеса та таємниці". З погляду топології жилет можна як двосторонню поверхню з трьома не зчепленими краями, кожен із яких є звичайної замкнутої кривою. Застебнутий жилет є двосторонньою поверхнею із чотирма краями. Загадкова петля.
Глядачеві, що носить жилет, надягають на руку петлю, а потім просять закласти великий палець у нижню кишеню жилета. Тепер можна запропонувати присутнім зняти петлю з руки, не витягаючи пальця з жилетної кишені. Розгадка така: петлю потрібно протягнути в жилетний отвір для рукава, перекинути через голову глядача, витягнути через другий отвір для рукава та перенести під другу руку. В результаті цих дій петля опиниться під жилетом, оточуючи собою груди. Опускайте її до тих пір, поки вона не з'явиться з-під жилета, а потім дайте впасти на підлогу. Викручування жилета на виворот, не знімаючи з людини.
Власнику жилета необхідно зчепити пальці рук за спиною. Навколишні повинні вивернути жилет навиворіт, не рознімаючи рук власника. Для демонстрації цього досвіду необхідно розстебнути жилет і стягнути його руками за спину власника. Жилет бовтатиметься у повітрі, але, звичайно, не зніметься, бо руки зчеплені. Тепер потрібно взяти ліву підлогу жилета і, намагаючись не зім'яти жилет, просунути її якнайдалі в праву пройму. Потім взяти праву пройму і просунути в ту ж пройму і тому напрямі. Залишилося розправити жилет та натягнути його на власника. Жилет виявиться на виворот. Цей фокус ми провели та зняли на відео з однокласниками. Воно міститься у презентації «Стрічка Мебіуса». 2.3. Застосування аркуша Мебіуса
∞ Біля входу до Музею історії та техніки у Вашингтоні повільно обертається на п'єдесталі сталева стрічка, закручена на піввітка. У 1967 році, коли в Бразилії відбувся міжнародний математичний конгрес, його організатори випустили пам'ятну марку номіналом п'ять сентаво. На ній була зображена стрічка Мебіуса. І монумент заввишки більш ніж два метри, і крихітна марка – своєрідні пам'ятники німецькому математику та астроному Августу Фердинанду Мебіусу. Дивись додаток 5. Патентна служба зареєструвала чимало винаходів, в основі яких лежить все та ж одностороння поверхня. ∞ Лист Мёбиуса використовується в багатьох винаходах, навіяних ретельним вивченням властивостей односторонньої поверхні. Смуга стрічкового конвеєра, виконана у вигляді листа Мебіуса, дозволяє йому працювати довше вдвічі, тому що вся поверхня листа рівномірно зношується. В 1923 видано патент винахіднику Лі де Форсу, який запропонував записувати звук на кінострічці без зміни котушок відразу з двох сторін. Придумані касети для магнітофона, де стрічка перекручується і склеюється в кільце, при цьому з'являється можливість записувати або зчитувати інформацію відразу з двох сторін, що збільшує ємність касети в два рази і час звучання. У матричних принтерах барвна стрічка мала вигляд листа Мебіуса збільшення терміну придатності. Це дає відчутну економію. Лист Мёбіуса застосовують у велосипедній та волейбольній камері. ∞ Зовсім недавно їй знайшли інше застосування - вона стала грати роль пружини, ось тільки особливої пружини. Як відомо, зведена пружина спрацьовує в протилежному напрямку. Лист Мебіуса ж, всупереч усім законам, напрямок спрацьовування не змінює, подібно до механізмів з двома стійкими положеннями. Така пружина могла б стати безцінною у заводних іграшках – її не можна перекрутити, як звичайну – свого роду вічний двигун. Дивіться дод. 6. ∞ У 1971 році винахідник з Уралу Чесноков П.М. застосував фільтр у вигляді аркуша Мебіуса. ∞ Лист Мёбіуса використовується в кулінарії для того, щоб створити цікавий та апетитний вигляд для булочок, сушок, хмизу. А також при виготовленні інструментів для приготування та прикраси різних страв, силових конструкцій (мішалка). Дивись дод. 7. ∞ За допомогою стрічки Мёбіуса створюють цілі шедеври. Аркуш Мебіуса служив натхненням для скульптур та для графічного мистецтва. Ешер був одним із художників, хто особливо любив його і присвятив кілька своїх літографій цьому математичному об'єкту. Одна з відомих показує мурах, що повзають по поверхні аркуша Мебіуса. Дивись дод.9. ∞ Аркуш Мебіуса також постійно зустрічається у науковій фантастиці, наприклад, у оповіданні Артура Кларка «Стіна Темряви». Іноді науково-фантастичні розповіді припускають, що наш Всесвіт може бути деяким узагальненим листом Мебіуса. У оповіданні автора А.Дж. Дейча, бостонське метро будує нову лінію, маршрут якої стає настільки заплутаним, що перетворюється на лист Мебіуса, після чого на цій лінії починають зникати потяги. ∞ Є гіпотеза, що спіраль ДНК сама по собі теж є фрагментом стрічки Мебіуса, і тому генетичний код такий складний для розшифровки і сприйняття. Більше того – така структура цілком логічно пояснює причину настання біологічної смерті: спіраль замикається сама на себе і відбувається самознищення. Додаток 10. ∞ Мебіусовий лист сподобався не лише математикам, а й фокусникам Більше 100 років лист Мёбіуса використовується для показу різних фокусів та розваг. Дивовижні властивості аркуша демонструвалися навіть у цирку, де підвішувалися яскраві стрічки, склеєні у вигляді аркушів Мебіуса. Фокусник закурював сигарету і палаючим кінцем торкався середньої лінії кожної стрічки, яка була виконана з калійної селітри. Вогняна доріжка перетворювала першу стрічку на довшу, а другу - на дві стрічки, одягнена одна в іншу. (У цьому випадку фокусник розрізав лист Мебіуса не посередині, а на відстані одну третину його ширини). ∞ Фізики стверджують, що всі оптичні закони засновані на властивостях аркуша Мебіуса, зокрема, відображення в дзеркалі – це своєрідне перенесення у часі, короткострокове, що триває соті частки секунди, адже ми бачимо перед собою… правильно, дзеркального свого двійника. ∞Існує гіпотеза, що наш Всесвіт цілком імовірно замкнутий у той самий лист Мебіуса, згідно з теорією відносності, чим більше маса, тим більше кривизна простору. Ця теорія повністю підтверджує припущення, що космічний корабель, що весь час летить прямо, може повернутися до місця старту, це підтверджує необмеженість та кінцівку Всесвіту. Дивись дод. 11. ∞ Інтерес до аркуша Мебіуса не згас і в наші дні. У Москві у вересні 2006 року відбувся Фестиваль художньої математики. З великим успіхом було прийнято виступ професора з Токіо Джина Акіяма. Його вистава нагадувала шоу ілюзіоніста, де було місце і аркушу Мебіуса (робота з папером «Аркуш Мебіуса та його модифікації»). СПОРТ
Ручний еспандер "Робур"
Дивись дод. 12 . Одна зулюблених речей усіх шкільних вчителів фізкультури, яка за їхвласним виразом «тренує нетільки м'язи кисті, алеі м'яз мозку ". Кистьовий еспандер відстудії Артемія Лебедєва повторює форму стрічки Мёбіуса. Відмінний засіб для зняття стресу, роздумів пронескінченності тапросто корисний спосіб зайняти руки. ПАРФЮМ
Духи Bugatti
Дивись дод. 13 КомпаніяBugattiпочала випуск не лише наддорогих автомобілів (модельVeyronкоштує 1,3 млн. євро), але й… парфумів. кожен флакончик, зроблений з кришталю і покритий справжнім золотом, виконаний у вигляді незвичайного листа Мебіуса, який має лише одну сторону. Ціна парфумівBugattiскладає 3500 євро. Духи Loewe Quzas, Quizas, Quizas
Дивись дод. 14 . Восени 2011 року вийшла багряна версія аромату, флакон якої обернутий стрічкою Мебіуса – символом круговороту пристрастей у природі. Багатство композиції складається із свіжості азіатських апельсинів, бергамоту, червоних ягід, триває квітковим серцем з магнолії, фрезії та пелюсток апельсина, і завершується композицією із чуттєвого шлейфу кашмірового дерева, золотої амбри та ветівера. Духи UFO Limited Edition, Kenzo
Дивись дод. 15 . Презентація ароматуKenzoвідбулася у 2009 році на ретроспективній виставці робіт Рона Арада (RonArad) у паризькому Центрі Помпіду. Саме цей художник та архітектор вигадав космічний дизайн флакона у вигляді стрічки Мебіуса. Він розроблений так, щоб точнісінько поміститися в долоню.UnidentifiedFragranceObject, або «Невідомий ароматичний об'єкт» існує в кількості всього 180 екземплярів і коштує $188. МЕБЛІ
Стіл Мебіуса
Дивись дод. 16 Стіл із однією поверхнею, за яким можна стояти, сидіти і на якому можна зручно лежати. Книжкова полиця Infinity
Дивись дод. 17 . Дизайнер Джоб Келевій зламав форму, коли розробляв свою книжкову шафу Інфініті. Використовуючи математичну концепцію Лемніската, і щось схоже на стрічку Мебіуса, в полку Інфініті дизайнер втілив фізичне уявлення про нескінченність. Це означає, що якщо ви прочитали всі книги з цієї полиці, вважайте, що ви спіткали всю нескінченність літератури. Диван Мебіуса
Дивись дод. 18. "Подвійне крісло - подвійне задоволення", що народилося під девізом, крісло-диванMoebiusDoubleArmchairстворено дизайнеромGaеtanVandeWyerз Бельгії та несе у собі свіже бачення меблів для закоханих. ЛОГОТИПИ
Логотип компанії Woolmark
Дивись дод. 19. Логотип було створено у 1964 році в результаті дизайнерського конкурсу. Член журіFrancoGrignaniне встояв і запропонував свій варіант, сховавшись під псевдонімомFrancescoSeraglio. Цей логотип нагадує лист Мебіуса і є символом вічності та гнучкості компанії.
Символ переробки
Дивись дод. 20. Міжнародний символ переробки є Ліст Мебіуса.Переробка (інші терміни: вторинна переробка, рециклінг відходів,рециклювання та утилізація відходів)- повторне використання або повернення в обіг відходів виробництва чи сміття. Найбільш поширена вторинна, третинна тат. д. переробка у тому чи іншому масштабі таких матеріалів, як скло, папір, алюміній, асфальт, залізо, тканини та різні види пластику. Також з давніх-давен використовуються в сільському господарстві органічні сільськогосподарські та побутові відходи. Символ математики
Дивись дод. 21 . Лист Мёбиуса вважають символом сучасної математики, оскільки саме він дав поштовх новим математичним дослідженням. ОДЯГ І ВЗУТТЯ
Туфлі
Дивись дод. 22. Створена в 2003 році архітектором Рем Ді Колхаазом та взуттьовиком Галахадом Кларком компаніяUnitedNudeспеціалізується на випуску інноваційного дизайнерського взуття. Однією з найвдаліших розробок компанії є туфліMobius
названі так на честь геометра Августа Мебіуса та його ідеї односторонньої поверхні. Ідея туфель така: шкіряний верх туфель і підошва є єдиною стрічкою, закрученою певним чином.
Шарф Мебіуса
Дивись дод. 23 .
Інетресна річ шарф Мебіуса, що з'явилася в гардеробах 21 століття. Шарф Мёбиуса можна зробити самому зв'язавши кінці шарфа на перекрутивши на один оборорт. ЖИВОПИС
Графіті
Дивись дод. 24. Сучасна стрічка Мебіуса намальована на одній зі стін у Празі, Чехія.
По стрічці рухаються два типи машин: танки і будівельно-дорожня техніка. Символ сучасної цивілізації: руйнуємо-будуємо. АРХІТЕКТУРА
Будівля бібліотеки
Дивись дод. 25. В даний час розглядається проект будівництва бібліотеки у вигляді аркуша Мебіуса в Казахстані. Вигини будівлі утворюють лист Мебіуса, таким чином внутрішній простір переходить у зовнішній та назад; подібним чином стіни переходять у дах, а дах трансформується назад у стіни. Природне світло проникає у внутрішні коридори крізь геометричні отвори у зовнішній оболонці, створюючи чудово освітлені простори, ідеальні для читання. Атракціони
Дивись дод. 26. Атракціон "Американські гірки" нагадує форму аркуша Мебіуса. У Москві знаходяться найбільші у світі американські гірки інвертованого типу, де людина сидить у підвішеному кріслі, а її ноги перебувають у повітрі. Швидкість - 81 км/год, висота 30 м. Висота, порівняно із зарубіжними аналогами, невелика, але це з лишком окупається великою кількістю спіралей, кілець і мертвих петель. Кінострічка
Дивись дод. 27. В 1923 видано патент винахіднику Лі де Форсу, який запропонував записувати звук на кінострічці без зміни котушок, відразу з двох сторін. Касета
Дивись дод. 28. Придумані касети для магнітофона, де стрічка перекручується і склеюється в кільце, при цьому з'являється можливість записувати або зчитувати інформацію відразу з двох сторін, що збільшує ємність касети і час звучання. Автомобіль Toyota MOB
Дивись дод. 29. Болід Мебіуса виконаний іспанським дизайнером Хорхе Марті Відала і поєднує в собі красу та загадку стрічки Мебіуса. Унікальна форма кузова забезпечує гоночній машині гарну аеродинаміку. Матричний принтер
Дивись дод. 30. Багато матричних принтерах барвна стрічка також має вигляд листа Мёбиуса збільшення її ресурсу. Резистор Мебіуса
Дивись дод. 31. Це нещодавно винайдений електронний елемент, який не має власної індуктивності. Шліфувальна стрічка
Дивись дод. 32. У 1969 році радянський винахідник Губайдулін запропонував нескінченну шліфувальну стрічку у вигляді аркуша Мебіуса. Висновок
Аркуш Мебіуса – перша одностороння поверхня, яку відкрив учений. Пізніше математики відкрили цілу низку односторонніх поверхонь. Але ця - найперша, що започаткувала цілому напрямі в геометрії, як і раніше привертає до себе увагу вчених, винахідників, художників і учнів. Мені були дуже цікаві відкриті властивості листа Мебіуса: Лист Мебіуса має один край, один бік Аркуш Мебіуса – топологічний об'єкт. Як і будь-яка топологічна фігура, він не змінює своїх властивостей, поки його не розрізають, не розривають чи не склеюють окремі шматки. Один край і одна сторона аркуша Мебіуса не пов'язані з його положенням у просторі, не пов'язані з поняттями відстані. Лист Мёбиуса знаходить численні застосування у кулінарії, у техніці, у фізиці, в живописі, в архітектурі, в оформленні ювелірних виробів та біжутерії та вивченні властивостей Всесвіту. Надихав він на творчість багатьох письменників та художників. Практично всі знають, як виглядає символ нескінченності, що нагадує перевернуту вісімку. Цей знак називають ще «лемніската», що з давньогрецької означає стрічка. Уявіть собі, що символ нескінченності дуже схожий на реальну математичну фігуру. Знайомтесь, Стрічка Мебіуса! Стрічка Мебіуса(або її ще називають петля Мебіуса, лист Мебіуса і навіть кільце Мебіуса) – одна з найбільш відомих у математиці поверхонь. Петля Мебіуса – це петля з однією поверхнею та одним краєм. Щоб зрозуміти, про що йдеться, і як таке може бути, візьміть аркуш паперу, виріжте смужку прямокутної форми і в момент з'єднання її кінців перекрутіть на 180 градусів один з них, після чого з'єднайте. Розібратися в тому, як зробити стрічку Мебіуса допоможе малюнок нижче. Стрічка Мебіуса- приклад неорієнтованої односторонньої поверхні з одним краєм у звичайному тривимірному Евклідовому просторі. Більшість предметів є орієнтованими, що мають дві сторони, наприклад, аркуш паперу. Як тоді стрічка Мёбіуса може бути неорієнтованою, односторонньою поверхнею - скажете ви, адже папір, з якого вона зроблена має дві сторони. А ви спробуйте взяти маркер і заповнити кольором одну зі сторін стрічки, в кінцевому підсумку ви впертеся в початкову позицію, причому вся стрічка виявиться цілком зафарбованою, що підтверджує наявність у неї лише однієї сторони. Щоб повірити в те, що у петлі Мебіуса всього один край - проведіть пальцем по одному з граней стрічки не перериваючись, і Ви точно так само, як і у випадку з розфарбовуванням, упріться в точку, з якої почали рухатися. Дивно, чи не так? Вивченням стрічки Мебіуса та безлічі інших цікавих об'єктів займається топологія, розділ математики, який досліджує постійні характеристики об'єкта при його безперервній деформації - розтягуванні, стисканні, згинанні, без порушення цілісності. «Батьком» відкривачем цієї незвичайної стрічки визнано німецького математика Серпень Фердинанд Мебіус, учень Гаусса, який написав не одну роботу з геометрії, але прославився переважно відкриттям односторонньої поверхні у 1858 році. Дивним є той факт, що стрічку з однією поверхнею в той самий 1858 відкрив другий учень Гаусса - талановитий математик Йоганн Лістинг, що вигадав термін «топологія» і написав серію основних праць з цього розділу математики. Проте свою назву незвичайна стрічка все ж таки отримала на прізвище Мебіуса. Є поширена думка, що прообразом моделі «нескінченної петлі» стала неправильно пошита стрічка служницею професора Августа Мебіуса. Насправді, Стрічка була відкрита давним-давно ще у стародавньому світі. Одним із підтверджень служить давньоримська мозаїка, що знаходиться у Франції, в музеї міста Арль з такою самою перекрученою стрічкою. На ній намальований Орфей, який зачаровує звірів звуками арфи. На фоні неодноразово зображений орнамент із перекрученою стрічкою. Вас добряче здивує результат, адже всупереч очікуванням у руках залишиться не два відрізки стрічки, і навіть не два окремі кола, але інша, ще довша стрічка. Це вже не стрічка Мебіуса, перекручена на 180 градусів, а стрічка з поворотом на 360 градусів. У меншої стрічки Мебіуса буде 1/3 від початкової ширини стрічки, довжина L та поворот на 180 градусів. У другої довшої стрічки буде також ширина 1/3 від початкової, але довжина 2L, а поворот на 360 градусів. Стрічка Мебіуса - зовсім не абстрактна фігура, потрібна лише для цілей математики, вона знайшла застосування і в реальному повсякденному житті. За принципом цієї стрічки функціонує в аеропорту стрічка, яка пересуває валізи з багажного відділення. Така конструкція дозволяє їй служити довше у зв'язку з рівномірним зношуванням. Відкриття Августа Мебіуса повсюдно використовується в станкобудуванні. Конструкцію використовують для більшого часу запису на плівку, а також у принтерах, які використовують стрічку під час друку. Завдяки своїй наочності, петля Мебіуса дає можливість робити сучасним вченим все нові та нові відкриття. З моменту виявлення дивовижних властивостей петлі по всьому світу прокотилася хвиля запатентованих нових винаходів. Наприклад, значне поліпшення властивостей магнітних сердечників, виготовлених з феро-магнітної стрічки, намотаних за способом Мебіуса. Н. Тесла отримав патент на багатофазну систему змінного струму, використавши намотування котушок генератора на кшталт петлі Мебіуса. Американський вчений Річард Девіс сконструював нереактивний резистор Мебіуса - здатний гасити реактивний (ємнісний та індуктивний) опір, не викликаючи електромагнітних перешкод. Важко оцінити важливість значення відкриття петлі Мебіуса, яке надихнуло не лише безліч учених, а й письменників, художників. Найвідомішою роботою, присвяченою стрічці Мебіуса, вважається картина Moebius Strip II, Red Ants або Червоні Мурахи голландського художника-графіка Мауриця Ешера. На картині представлені мурахи, що дерються по петлі Мебіуса з обох боків, насправді одна сторона. Мурахи повзуть нескінченною петлею один за одним по одній і тій же поверхні. Художник черпав свої ідеї зі статей та праць з математики, він був глибоко захоплений геометрією. У зв'язку з чим на його літографіях і гравюрах часто є різні геометричні форми, фрактали, приголомшливі оптичні ілюзії. Досі інтерес до петлі Мебіуса перебуває на дуже високому рівні, навіть спортсмени запровадили однойменну фігуру найвищого лижного пілотажу. За твором «Стрічка Мебіуса» письменника фантаста Арміна Дейча знято не один фільм. У формі петлі Мебіуса створюється безліч прикрас, взуття, скульптур та багатьох інших предметів і форм. Аркуш Мебіуса наклав відбиток на виробництво, дизайн, мистецтво, науку, літературу, архітектуру. Розум багатьох людей хвилювала схожість форми молекули ДНК і петлі Мебіуса. Існувала гіпотеза, яку висунув радянський цитолог Навашин, що форма кільцевої хромосомиза будовою аналогічна стрічці Мебіуса. На цю думку вченого наштовхнув той факт, що кільцева хромосома, розмножуючись, перетворюється на більш довге кільце, ніж на самому початку, або в два невеликі кільця, але як у ланцюзі пройнятих одне в інше, що дуже нагадує вище описані досліди з листом Мебіуса. У 2015 році група вчених з Європи та США змогла закрутити світло в кільце Мебіуса. У науковому досвіді вчені використовували оптичні лінзи, і структуроване світло - сфокусований лазерний промінь з певною інтенсивністю та поляризацією в кожній точці свого руху. У результаті було отримано світлові стрічки Мебіуса. Є ще одна масштабніша теорія. Всесвіт - це величезна петля Мебіуса. Такої ідеї дотримувався Ейнштейн. Він припустив, що Всесвіт замкнутий, і космічний корабель, що стартував з певної її точки і що летить весь час прямо, повернеться в ту саму точку в просторі і часі, з якої і почався його рух. Поки що це лише гіпотези, які мають як прибічники, і противники. Хто знає, до якого відкриття підведе вчених, начебто, такий простий об'єкт, як Стрічка Мебіуса. Функція Мебіуса
(n), де n– натуральне число, що приймає такі значення: Функція Мебіуса дозволяє записати функцію Ейлера у вигляді суми: Підсумовування йде за всіма дільниками n(а не тільки за простими дільниками). приклад.Обчислимо φ
(100), використовуючи функцію Мебіуса. Усі дільники 100 – (1, 2, 4, 5, 10, 20, 25, 50, 100). (2) = (-1) 1 = -1 (у двійки один простий дільник – 2) (4) = 0 (4 ділиться на квадрат двійки) (5) = (-1) 1 = -1 (у 5 один простий дільник – 5) (10) = (-1) 2 = 1 (у 10 два простих дільника – 2 і 5) (20) = 0 (20 ділиться на квадрат двійки) (25) = 0 (25 ділиться на квадрат п'ятірки) (50) = 0 (50 ділиться і на 2 2 і на 5 5) (100) = 0 (100 ділиться і на 2 2 і на 5 5) Таким чином, Властивість функції Мебіуса:. Наприклад, n=100,
{1,
2, 4, 5, 10, 20, 25, 50, 100}. 16
Теорема про кількість способів вибору k-елементів, серед яких немає двох сусідніх, з елементів, розташованих у ряд. Довести за допомогою одержання рекурентної формули. Число r-поєднань з повтореннями з n-множини одно – доказ за допомогою рекурентної формули.
Метод базується на отриманні формули, що дозволяє обчислювати значення шуканої величини крок за кроком виходячи з відомих початкових значень і значень, обчислених на попередніх кроках. Рекурентна формулаr
-го порядку- Формула виду a n =
f(n,
a n- 1 ,
a n- 2 ,
… , a n-r). Формула виражає при n>rкожен член послідовності ( a i) через попередні rчленів. Побудова рекурентної формули складається з наступних кроків. 1. Вироблення початкових умоввиходячи з якихось очевидних співвідношень. Позначимо через f(n,r). Очевидно, що 2. Логічні міркування.Зафіксуємо якийсь елемент у безлічі S. Тоді щодо будь-якого r-поєднання з повтореннями з n-множини Sможна сказати, містить воно цей зафіксований елемент чи ні. Якщо містить, то інші ( r-1) елемент можна вибрати f(n,r-1) методами. Якщо не містить(у вибірці цього елемента немає), то r-поєднання складено з елементів ( n-1)-множини (множина Sза винятком цього зафіксованого елемента). Число таких поєднань f(n-1,r). Т.к. ці випадки взаємовиключні, то за правилом суми 3. Перевірка формули на деяких значеннях та виведення загальної закономірності. 1) Обчислимо f
(n
,0)
. З (2) випливає Тоді f(n,0)=f(n,1)-f(n-1,1). З (1) f(n,1)=n, f(n-1,1)=n-1. Отже, f(n,0)=n-(n-1)=1=. 2) f
(n
,1)
=f(n,0)+f(n-1,1)
= 1+n- 1 =n==. 3) f
(n
,2)
=f(n,1)+f(n-1,2)
=n+f(n-1,1)+f(n-2,2) =n+(n-1)+f(n-2,1)+f(n-3,2) =
… = = n+(n-1)+…+2+1 = (Сума арифметичної прогресії) 4) f
(n
,3)
=f(n,2)+f(n-1,3)
=+f(n-1,2)+f(n-2,3)
=++f(n-2,2)+f(n-3,3)
= … = (Сума геометричної прогресії) 5) f
(n
,4)
= На основі окремих випадків можна припустити, що що узгоджується з (1) # 19, 20) Число бінарних дерев з n вершинами дорівнює C (n), де C (n) - це n-е число Каталана. Кількість бінарних дерев з n вершин називається числом Каталана, яке має безліч цікавих властивостей. N-е число Каталана вважається за формулою (2n)! /(n+1)!n!, яка росте експоненційно. (У Вікіпедії запропоновано кілька доказів, що це форма числа Каталана.) Число бінарних дерев даного розміру 0 1 1 1 2 2 4 14 8 1430 12 208012 16 35357670 Підстановка Перейти до: навігація,
пошук Це стаття про підстановку як про синтаксичну операцію надтермами
. Можливо, вас цікавитьперестановка
.
У математикиі комп'ютерні науки
підстановка- це операція синтаксичноюзаміни підтермів даного термаіншими термами, згідно з певними правилами. Зазвичай йдеться про підстановку терму замість змінної. Визначення та позначення Для підстановки немає універсальної, узгодженої нотації, як і стандартного визначення. Поняття підстановки варіюється у межах розділів, а й у рівні окремих публікацій. Загалом можна виділити контекстну підстановкуі підстановку «замість». У першому випадку місце в термі, де відбувається заміна, задається контекстом, тобто частиною терму, що «оточує» це місце. Зокрема, таке поняття підстановки використовується в листуванні. Другий варіант найпоширеніший. У цьому випадку підстановка зазвичай задається деякою функцією з безлічі змінних безліч термів. Для позначення дії підстановки, як правило, використовують постфіксну нотацію. Наприклад, означає результат дії підстановки на терм. У переважній більшості випадків потрібно, щоб підстановка мала кінцевий носій, тобто, щоб безліч Останнє визначення підстановки є, мабуть, типовим і найчастіше використовуваним. Однак і для нього немає єдиної загальноприйнятої нотації. Найчастіше для позначення підстановки aзамість xв tвикористовується запис t[a/x],
t[x:=a] або t[x←a]. Підстановка змінної вλ-численні
У λ-обчисленні, підстановка визначається структурною індукцією. Для довільних об'єктів і довільної змінної результат заміщення довільного вільного входження вважається підстановкоюі визначається індукцією по побудові: (i) базис:: об'єкт збігається зі змінною. Тоді; (ii) базис:: об'єкт збігається з константою. Тоді для довільних атомарних; (iii) крок:
(iv) крок:: об'єкт неатомарний і є абстракцією. Тоді [; (v) крок:: об'єкт неатомарний і є абстракцією, причому. Тоді: для ілі; Підстановка змінної у програмуванні Підстановказмінної ( англ. substitution) в аплікативному програмуваннірозуміється так. Для обчислення значення функції fна аргументі vзастосовується запис f(v)), де fвизначена конструкцією f(x) = e. Запис f(v)у цьому випадку означає, що у виразі eвідбувається заміщення, або підстановка змінної xна v. Виконання заміщення відбувається відповідно до семантикою обчислень. Підстановказмінної ( англ. assignment) в програмуваннярозуміється як привласнення. Оператор присвоєння є проявом ефекту «пляшкового шийки» фон Нейманна для традиційних мов програмування
. Від цього вільні аплікативні обчислювальні системи. http://math.nsc.ru/LBRT/u3/bard/fails/Brenner_Evans.pdf 21
Виробляють функції.Виробна функція (нумератор) та перелічуюча функція для поєднань без повторень. Виробляючі функції: 1) Z-перетворення 2) генератриса 3) породжувальна функція 4) виробляюча функція послідовності (a r) на базисі (g r) – функція f при розкладанні якої в ряд за функціями фіксованого базису (g r) утворюється дана послідовність Цей ряд – формальний. Назва формальний означає, що формулу *) трактуємо як зручну запис нашої послідовності – у разі несуттєво, яких (дійств і комплексних) значень він сходиться. Роль t зводиться до того щоб розрізняти коефіцієнти послідовності А0,А1,…Аr…. Виконуються лише деякі операції на таких рядах, а потім визначаються тільки деякі операції на таких рядах, а потім визначаються коефіцієнти при окремих ступенях змінної t. Зазвичай як 22
Виробляюча функція. Виробна функція (нумератор) і перелічує функція, що виробляє, для поєднань з повтореннями. Виробляюча ф-я для : Правило побудови 1) Якщо ел-т типу i може входити в поєднання K 1 або K 2 або ... K i раз, то йому соотв множник 3) Залишається знайти коеф. при експоненційна виробляюча ф-я для розміщень правило побудови 25) До комбінаторних чисел також відносяться числа Стірлінгапершого та другого роду. Ці числа визначаються як коефіцієнти рівності і мають простий комбінаторний зміст - дорівнює числу елементів групи підстановок, що є творами рівно kциклів, що не перетинаються, а дорівнює числу розбиття n-елементної множини на kнепустих підмножин. Очевидно, що. Аналогічна сума чисел Стірлінга другого роду називається n-м числом Белла і дорівнює числу всіх розбиття n-Елементної множини. Для чисел Белла справедлива рекурентна формула. При вирішенні комбінаторних завдань часто виявляється корисною формула включень-виключень що дозволяє знаходити потужність об'єднання множин, якщо відомі потужності їх перетинів. Скористаємося формулою включень-виключень для отримання явної формули для чисел Стірлінга другого роду. Числа Стірлінга першого роду Матеріал з Вікіпедії – вільної енциклопедії Перейти до: навігація,
пошук Числа Стірлінга першого роду(без знака) – кількість перестановокпорядку nз k
циклами. Визначення Числами Стірлінга першого роду(зі знаком) s(n, k)називаються коефіцієнти багаточлена: де ( x) n
- символ Похгаммера
(спадний факторіал): Як видно з визначення, числа мають знак, що чергується. Їхні абсолютні значення задають кількість перестановокмножини, що складається з nелементів з k
циклами. Рекурентне співвідношення Числа Стірлінга першого роду задаються рекурентнимспіввідношенням: s(n,n) = 1, для n ≥ 0, s(n,0) = 0, для n> 0, для 0< k
< n. Доведення. Для n=1 ця рівність перевіряється безпосередньо. Нехай перестановка ( n-1)-го порядку розпадається на kциклів. Число nможна додати після будь-якого числа у відповідний цикл. Усі отримані перестановки - різні та містять k циклів, їх кількість ( n-1) · s(n-1,
k). З будь-якої перестановки ( n-1)-го порядку, що містить k-1 цикл, можна сформувати єдину перестановку nпорядку, що містить kциклів, додавши цикл утворений одниною n. Очевидно, що ця конструкція описує всі перестановки n-го порядку, що містять kциклів. Тим самим рівність доведено. приклад Перші ряди: У комбінаторики
числом Стірлінга другого родуз nпо k, що позначається або називається кількість невпорядкованих розбиття
n-елементного безлічіна kнепустих підмножин. Рекурентна формула Числа Стірлінга другого роду задовольняють рекурентномуспіввідношенню: Для n ≥ 0, Для n > 0 Явна формула приклад Початкові значення чисел Стірлінга другого роду наведені в таблиці: Властивості Бієктивнимвідображенням називається відображення, що має ознаки ін'єктивності та сюр'єктивності одночасно.
Теорема 1: λ ≥ π/2
Теорема 2: λ ≤ √3
У цьому побудові було порушено головне правило – не м'яти папір. Але легко зрозуміти, що якщо довжина смужки хоч трохи більше √3, то злам за твірною можна замінити згинанням, виробленим на вузькій ділянці. Коротше кажучи, злам уздовж прямолінійного відрізка нам не страшний: його можна замінити близьким до нього згинанням. (Непоправне зминання паперу відбувається, коли дві лінії перегину перетинаються, тобто коли лист складається на кшталт носовичка – все це відомо нам із повсякденного досвіду.). Її пристрій можна уявити так: три однакових правильних трикутника ABC, A"B"C", A"B"C" лежать паралельно один одному, відповідні вершини над відповідними вершинами; сторони AB та A"B", B"C" і B"C", C"A" і CA з'єднані перемичками. Лінія склеювання проходить по медіані одного із трикутників.Чому не вдається знайти λ точніше?
Робиться це так. Візьмемо досить велике непарне n і побудуємо правильний n-кутник, вписаний в коло діаметра 1. Розглянемо, далі, що містять центр кола трикутників, кожен з яких обмежений стороною і двома діагоналями n-кутника (n=7). Ці трикутники покривають наш n-кутник, деякі його місця – кілька разів. Прикладемо тепер ці n трикутників один до одного, після чого відріжемо по довгій медіані половину самого лівого трикутника і докладемо її до правого трикутника. Вийде прямокутна смужка зі ставленням довжини до ширини, більшим π/2 і які прагнуть π/2 при n, що прагнуть ∞ (ширина смужки прагне 1, а довжина – π/2). Послідовно перегнемо цю смужку по всіх проведених на ній лініях, чергуючи напрямки згину. Відрізки AB та CD при цьому майже суміщаться – між ними виявиться лише кілька шарів складеного паперу. У цьому “майже поєднанні” точка A сполучиться з D, а точка B – з C, отже якби ми змогли “пропустити стрічку крізь себе” і склеїти |AB| з |CD|, то вийшла б стрічка Мебіуса. Якщо стрічку взяти трохи довшою, можна уникнути складок, подібно до того, як ми це зробили в доказі теореми 2. Отримали стрічку Мебіуса, краї якої розділені кількома шарами паперу, дивіться в додатку 1.3. Але повернемося до стрічки Мебіуса. Теорема 1, як ми бачили, насправді відноситься до стрічок, що самоперетинаються. Малоймовірно, щоб умова відсутності самоперетинів не впливала на λ; проте врахувати цей вплив не вдається, оскільки математика не має достатніх технічних засобів для вивчення самоперетинів у тривимірному просторі. Навпаки, цілком імовірно, що теорема 2 не покращується. Адже поліпшити її означає придумати нову конструкцію стрічки. Досвід показує, що оптимальні конструкції бувають простими і гармонійними, якою є конструкція з доказу теореми 2. Природно припустити, що якби краща конструкція існувала, вона була знайдена - за стільки років! Що таке Стрічка Мебіуса?
Що ж такого примітного у стрічці Мебіуса?
Відкриття Серпня Мебіуса
"Магія" стрічки Мебіуса
Навіщо потрібна петля Мебіуса? Застосування
Стрічка Мебіуса – широке поле для Натхнення
17 Число поєднань із повтореннями
.
.4. Перевірка початкових умов за допомогою отриманої формули.
,
було кінцевим. У такому разі її можна задати простим перерахуванням пар «Змінна-значення». Оскільки кожну таку підстановку можна звести до послідовності підстановок, що замінюють всього по одній змінній кожна, не обмежуючи спільності, можна вважати, що підстановка задається однією парою «Змінна-значення»що зазвичай і робиться.
: об'єктнеатомарний та має вигляд аплікації. Тоді;
…………*)
