Лемма.

Доказательство . Для утверждение очевидно. Пусть и − каноническое разложение числа . Тогда, учитывая, что делители имеют вид , где , ,…, ; , получаем

поскольку

Теорема. (Аддитивная формула обращения Мёбиуса .) Пусть и − функции натурального аргумента . Тогда, если

Доказательство . Имеем

Пусть . Тогда прификсированном пробегает все значения делителей числа . Это означает, что знаки суммирования в последней двойной сумме можно поменять местами, т.е.

Теперь, учитывая, что

получаем

Имеется другая форма доказанной теоремы:

Теорема . (Мультипликативная формула обращения Мёбиуса .) Пусть

где символ обозначает произведение, распространенное на все делители числа .

Доказательство :

Примеры использования формулы обращения Мёбиуса :

Задача о числе кольцевых последовательностей. См.: Холл М. Комбинаторика. М.: Мир, , § .

Число неприводимых многочленов заданной степени над конечным полем из элементов. См.: Берлекэмп Э. Алгебраическая теория кодирования. − М.: Мир, 1970, Гл. 3.

Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра. В -х т. М.: Гелиос, . Т. , § .

Для самостоятельного изучения :

Обращение Мёбиуса на частично упорядоченных множествах. Принцип включения-исключения как частный случай формулы обращения Мёбиуса. См.: Холл М. Комбинаторика. М.: Мир, , § ; Бендер Э., Гольдман Дж. О приложениях обращения Мёбиуса в комбинаторном анализе. В кн.: Перечислительные задачи комбинаторного анализа. М.: Мир, 1971. С. - .

Сравнения для чисел сочетаний

Пусть − простое число.

Лемма.

Доказательство . При числитель в формуле

Следствие.

Доказательство .

Лемма. Пусть , , , − неотрицательные целые числа, причем , . Тогда

Доказательство . Имеем

С другой стороны,

Сравнивая коэффициенты при одинаковых степенях , получаем требуемый результат. ∎

− представления неотрицательных целых чисел и по основанию . (Здесь любое целое, при котором , ). На множестве неотрицательных целых чисел определим отношение частичного порядка (отношение предшествования ) , полагая , тогда и только тогда, когда

Теорема Лукаса ( ).

Доказательство . Согласно предыдущей лемме,

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

Замечание. Теорема не верна для непростых . Например (см. Берлекэмп, с. ),

Следствие .

II. Алгебраические структуры

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 будет пробегать все делители d n ′ . Таким образом

∑ µ (d)g(

) = ∑ f(d′ ) ∑ µ (d′ )

d′

d′

d′

n > d′

Но согласно (1) имеем ∑

µ (d′ ) =

n = d′

d′

d′

Значит, равенство (3) установлено. Пусть теперь (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. Рассмотрим приложение обращения Мебиуса.

Пусть дан алфавит А из s букв. Имеется 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 слов. Из предыдущего имеем

d n. Таким образом, справедлива формула ∑ 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(A B) = 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

Приложение

Введение

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

Слышали ли вы когда – нибудь о листе Мёбиуса? Как его можно изготовить, как он связан с математикой и где применяется в жизни.

Занимаясь этой работой, я пришла к выводу, что хотя лист Мёбиуса открыли ещё в XΙX веке, он был актуален и в 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.Теоремы о ленте Мебиуса

Теорема 1: λ ≥ π/2

Из-за сложности доказательства я не рассматриваю его в своей работе.

Теорема 2: λ ≤ √3

Эта теорема проще предыдущей: для её доказательства достаточно объяснить, как склеить ленту Мёбиуса из полоски, длина которой больше √3. Предположим сначала, что её длина в точности равна √3. Тогда на этой полоске можно расположить два правильных треугольника. Перегнём полоску по боковым сторонам этих треугольников, чередуя направления сгиба. Края AB и CD полоски совместятся, причём точка A совместится с точкой D, а точка B – с точкой C. Получится лента Мёбиуса, края которой располагаются встык.(см. приложение 1.2)

При этом построении было нарушено главное правило – не мять бумагу. Но легко понять, что если длина полоски хоть немного больше √3, то излом по образующей можно заменить изгибанием, производимым на узком участке. Короче говоря, излом вдоль прямолинейного отрезка нам не страшен: его можно заменить близким к нему изгибанием. (Непоправимое сминание бумаги происходит, когда две линии перегиба пересекаются, т.е. когда лист складывается наподобие носового платка – всё это известно нам из повседневного опыта.). Её устройство можно представить себе так: три одинаковых правильных треугольника ABC, A"B"C", A"B"C" лежат параллельно друг другу, соответствующие вершины над соответствующими вершинами; стороны AB и A"B", B"C" и B"C", C"A" и CA соединены перемычками. Линия склейки проходит по медиане одного из треугольников.

Почему не удаётся найти λ точнее?

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

Теорема 3. Ленту Мёбиуса с самопересечениями можно склеить из полоски любой длины, большей π/2.

Делается это так. Возьмём достаточно большое нечётное n и построим правильный n-угольник, вписанный в окружность диаметра 1. Рассмотрим, далее, n содержащих центр окружности треугольников, каждый из которых ограничен стороной и двумя диагоналями n-угольника (n=7). Эти треугольники покрывают наш n-угольник, некоторые его места – по нескольку раз. Приложим теперь эти n треугольников друг к другу, после чего отрежем по длинной медиане половину самого левого треугольника и приложим её к самому правому треугольнику. Получится прямоугольная полоска с отношением длины к ширине, бóльшим π/2 и стремящимся к π/2 при n, стремящимся к ∞ (ширина полоски стремится к 1, а длина – к π/2). Последовательно перегнем эту полоску по всем проведённым на ней линиям, чередуя направления сгиба. Отрезки AB и CD при этом почти совместятся – между ними окажется только несколько слоёв сложенной бумаги. При этом “почти совмещении” точка A совместится с D, а точка B – с C, так что если бы мы смогли “пропустить ленту сквозь себя” и склеить |AB| с |CD|, то получилась бы лента Мёбиуса. Если ленту взять чуть более длинной, можно избежать складок, подобно тому как мы это сделали в доказательстве теоремы 2. Получили ленту Мебиуса, края которой разделены несколькими слоями бумаги,смотрите в приложении 1.3. Но вернёмся к ленте Мёбиуса. Теорема 1, как мы видели, в действительности относится к самопересекающимся лентам. Маловероятно, чтобы условие отсутствия самопересечений не воздействовало на λ; однако учесть это воздействие не удаётся, поскольку математика не обладает достаточными техническими средствами для изучения самопересечений в трёхмерном пространстве. Напротив, вполне вероятно, что теорема 2 неулучшаема. Ведь улучшить её – значит придумать новую конструкцию ленты. Опыт показывает, что оптимальные конструкции бывают простыми и гармоничными, каковой и является конструкция из доказательства теоремы 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 году на ретроспективной выставке работ Рона Арада (Ron Arad ) в парижском Центре Помпиду. Именно этот художник и архитектор придумал космический дизайн флакона в виде ленты Мебиуса. Он разработан так, чтобы точь-в-точь поместиться в ладонь. Unidentified Fragrance Object , или «Неопознанный ароматический объект» существует в количестве всего 180 экземпляров и стоит $188.

МЕБЕЛЬ

Стол Мёбиуса

Смотри прил. 16

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

Книжная полка Infinity

Смотри прил. 17 .

Дизайнер Джоб Келевий сломал форму, когдаразрабатывал свой книжный шкаф Инфинити. Используяматематическую концепцию Лемниската, и что-то похожеена ленту Мебиуса, в полке Инфинити дизайнер воплотилфизическое представление о бесконечности. Это значит,что если вы прочитали все книги с этой полки, считайте, чтовы постигли всю бесконечность литературы.

Диван Мёбиуса

Смотри прил. 18.

Родившееся под девизом "Двойное кресло - двойное удовольствие", кресло-диван Moebius Double Armchair создано дизайнером Ga е tan Van de Wyer из Бельгии и несет в себе свежее видение мебели для влюбленных.

ЛОГОТИПЫ

Логотип компании Woolmark

Смотри прил. 19.

Логотип был создан в 1964 году в результате дизайнерского конкурса. Член жюри Franco Grignani не устоял и предложил свой вариант, спрятавшись под псевдонимом Francesco Seraglio . Данный логотип напоминает лист Мебиуса и является символом вечности и гибкости компании.

Символ переработки

Смотри прил. 20.

Международный символ переработки представляет собой Лист Мёбиуса. Перерабо́тка (другие термины: вторичная переработка,рециклинг отходов, рециклирование и утилизация отходов) - повторное использование или возвращение в оборот отходов производства или мусора. Наиболее распространена вторичная, третичная и т. д. переработка в том или ином масштабе таких материалов, как стекло, бумага, алюминий, асфальт, железо, ткани и различные виды пластика. Также с глубокой древности используются в сельском хозяйстве органические сельскохозяйственные и бытовые отходы.

Символ математики

Смотри прил. 21 .

Лист Мёбиуса считают символом современной математики, так как именно он дал толчок новым математическим исследованиям.

ОДЕЖДА И ОБУВЬ

Туфли

Смотри прил. 22.

Созданная в 2003 году архитектором Рэм Ди Колхаазом и обувщиком Галахадом Кларком компания United Nude специализируется на выпуске инновационной дизайнерской обуви. Одной из наиболее удачных разработок компании являются туфли Mobius , названные так в честь геометра Августа Мебиуса и его идеи односторонней поверхности. Идея туфель такова: кожаный верх туфель и подошва представляют собой единую ленту, закрученную определенным образом.

Шарф Мёбиуса

Смотри прил. 23 .

Инетресная вещь шарф Мёбиуса появивщаяся в гардеробах 21 века. Шарф Мёбиуса можно сделать самому связав концы шарфа на перекрутив на один оборорт.

ЖИВОПИСЬ

Граффити

Смотри прил. 24.

Современная лента Мёбиуса нарисована на одной из стен в Праге, Чехия. 

 По ленте двигаются два типа машин: танки и строительно-дорожная техника.Символ современной цивилизации: разрушаем-строим-разрушаем-строим..

АРХИТЕКТУРА

Здание библиотеки

Смотри прил. 25.

В настоящее время рассматривается проект постройки библиотеки в виде листа Мёбиуса в Казахстане.

Изгибы здания образуют лист Мёбиуса, таким образом внутреннее пространство переходит во внешнее и обратно; подобным образом стены переходят в крышу, а крыша трансформируется обратно в стены. Естественный свет проникает во внутренние коридоры сквозь геометрические отверстия во внешней оболочке, создавая прекрасно освещённые пространства, идеальные для чтения.

Аттракционы

Смотри прил. 26.

Аттракцион “Американские горки” напоминает форму листа Мебиуса. В Москве находятся самые большие в мире американские горки инвертированного типа, где человек сидит в подвешенном кресле, а его ноги находятся в воздухе. Скорость - 81 км/ч, высота 30 м. Высота, по сравнению с зарубежными аналогами, невелика, но это с лихвой окупается обилием спиралей, колец и мёртвых петель.

Кинолента

Смотри прил. 27.

В 1923 году выдан патент изобретателю Ли де Форсу, который предложил записывать звук на киноленте без смены катушек, сразу с двух сторон.

Кассета

Смотри прил. 28.

Придуманы кассеты для магнитофона, где лента перекручивается и склеивается в кольцо, при этом появляется возможность записывать или считывать информацию сразу с двух сторон, что увеличивает ёмкость кассеты и соответственно время звучания.

Автомобиль Toyota MOB

Смотри прил. 29.

Боллид Мёбиуса выполнен испанским дизайнером Хорхе Марти Видала и сочетает в себе красоту и загадку ленты Мёбиуса. Уникальная форма кузова обеспечивает гоночной машине хорошую аэродинамику

Матричный принтер

Смотри прил. 30.

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

Резистор Мёбиуса

Смотри прил. 31.

Это недавно изобретённый электронный элемент, который не имеет собственной индуктивности.

Шлифовальная лента

Смотри прил. 32.

В 1969 году советский изобретатель Губайдуллин предложил бесконечную шлифовальную ленту в виде листа Мёбиуса

Заключение

Лист Мёбиуса - первая односторонняя поверхность, которую открыл учёный. Позже математики открыли ещё целый ряд односторонних поверхностей. Но

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

Лист Мебиуса имеет один край, одну сторону

Лист Мёбиуса - топологический объект. Как и любая топологическая фигура, он не меняет своих свойств, пока его не разрезают, не разрывают или не склеивают его отдельные куски.

Один край и одна сторона листа Мебиуса не связаны с его положением в пространстве, не связаны с понятиями расстояния.

Лист Мёбиуса находит многочисленные применения в кулинарии, в технике, в физике, в живописи, в архитектуре, в оформлении ювелирных изделий и бижутерии и изучении свойств Вселенной. Вдохновлял он на творчество многих писателей и художников.

Практически все знают, как выглядит символ бесконечности, напоминающий перевернутую восьмерку. Этот знак называют еще «лемниската», что с древнегреческого означает лента. Представьте себе, что символ бесконечности очень похож на реально существующую математическую фигуру. Знакомьтесь, Лента Мебиуса!

Что такое Лента Мебиуса?

Лента Мебиуса (или ее еще называют петля Мебиуса, лист Мебиуса и даже кольцо Мебиуса) - одна из наиболее известных в математике поверхностей. Петля Мебиуса - это петля с одной поверхностью и одним краем.

Чтобы понять, о чем идет речь, и как такое может быть, возьмите лист бумаги , вырежьте полоску прямоугольной формы и в момент соединения ее концов перекрутите на 180 градусов один из них, после чего соедините. Разобраться в том, как сделать ленту Мебиуса поможет картинка ниже.

Что же такого примечательного в ленте Мебиуса?

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

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

Чтобы поверить в то, что у петли Мебиуса всего один край - проведите пальцем по одному из граней ленты не прерываясь, и Вы точно так же, как и в случае с раскрашиванием, упретесь в точку, с которой начали движение. Удивительно, не правда ли?

Изучением ленты Мёбиуса и множества других интересных объектов занимается - топология , раздел математики, который исследует неизменные свойства объекта при его непрерывной деформации - растяжении, сжатии, изгибе, без нарушения целостности.

Открытие Августа Мебиуса

«Отцом» открывателем этой необычной ленты признан немецкий математик Август Фердинанд Мебиус , ученик Гаусса, написавший не одну работу по геометрии, но прославившийся преимущественно открытием односторонней поверхности в 1858 году.

Удивительным является тот факт, что ленту с одной поверхностью в тот же самый 1858 год открыл другой ученик Гаусса - талантливый математик Иоганн Листинг , придумавший термин «топология» и написавший серию основополагающих трудов по этому разделу математики. Однако свое название необычная лента все же получила по фамилии Мебиуса.

Есть расхожее мнение, что прообразом модели «бесконечной петли» стала неверно сшитая лента служанкой профессора Августа Мебиуса.

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

«Магия» ленты Мебиуса

1. Несмотря на кажущееся наличие у листа Мебиуса двух сторон, на самом деле сторона всего одна, и раскрасить в два цвета ленту не получится.
2. Если ручкой или карандашом начертить по всей длине петли линию, не отрывая руку от листа, то грифель в конечном итоге остановится в точке, с которой Вы начали чертить линию;
3. Примечательные опыты получаются при разрезании ленты, способные удивить, как взрослого, так и ребенка в особенности.

• Для начала склеим ленту Мебиуса, как было рассказано ранее. Затем разрежем ее вдоль по всей длине ровно посередине, как показано ниже:

Вас порядком удивит результат, ведь вопреки ожиданиям в руках останется не два отрезка ленты, и даже не два отдельных круга, но другая, еще более длинная лента. Это уже будет не лента Мебиуса, перекрученная на 180 градусов, а лента с поворотом на 360 градусов.

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

У меньшей ленты Мёбиуса будет 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-элементов, среди которых нет двух соседних, из n элементов, расположенных в ряд. Доказать с помощью получения рекуррентной формулы.

17 Число сочетаний с повторениями

Число 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) =

На основе частных случаев можно предположить, что

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 } образуется данная последовательность коэффициентов {a r } …………*)

Данный ряд – формальный. Название формальный означает, что мы формулу *) трактуем как удобную запись нашей последовательности – в данном случае несущественно, для каких (действ и комплексных) значений он сходится. Роль t сводится к тому чтобы различать коэффициенты последовательности А0,А1,…Аr….поэтому в теории производящих функций никогда не вычисляют значения таого ряда для конкретного значения переменной t. Выполняются лишь только некоторые операции на таких рядах, а затем определяются только некоторые операции на таких рядах а затем определяются коэффициенты при отдельных степенях переменной 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,

Явная формула

Пример

Начальные значения чисел Стирлинга второго рода приведены в таблице:

Свойства

Биективным отображением называется отображение, обладающее признаками инъективности и сюръективности одновременно.