StudyDocs.ru Logo

Максимльная найденная информация.docx


6. Комбинаторные задачи о покрытиях, укладках, разбиениях. Примеры. Теорема о числе разбиений элементов множества на 2, 3, …,k классов, без учета их порядка в классах и без ограничений на занятость класса. Доказательства. Следствия.
Задача о покрытииНайти такие множества Ti, i = 1, 2, …, r, чтобы <Object: word/embeddings/oleObject1.bin> (чтобы объединение этих множеств «покрыло» S). Например, застелить весь пол в комнате несколькими коврами. Ковры могут накладываться друг на друга (множества могут пересекаться), но незакрытых участков пола быть не должно.Во многих задачах покрытие должно быть наиболее экономичным (так называемое минимальное покрытие), когда число множеств Ti должно быть минимальным, сами они должны содержать минимально возможное число элементов.
Задача об укладкеНайти такие попарно непересекающиеся множества Ti, i = 1, 2, …, r, (Ti Tj = при ij) чтобы <Object: word/embeddings/oleObject2.bin> (чтобы объединение этих множеств вошло в S).Например, уложить несколько предметов в одну коробку. Между предметами могут быть пустые промежутки, но сами предметы друг с другом не пересекаются и укладываются в коробку.Во многих задачах укладка должна быть наиболее экономичной, когда укладывается максимально возможное количество предметов, а количество пустых промежутков должно быть как можно меньше.
Задача о разбиенииНайти такие попарно непересекающиеся множества Ti, i = 1, 2, …, r, (Ti Tj = при ij) чтобы <Object: word/embeddings/oleObject3.bin> (чтобы объединение этих непересекающихся множеств дало S). Например, группы в институте – это разбиение множества студентов института. Группы не пересекаются, а их объединение дает множество всех студентов института.
Теорема о числе разбиений элементов множества на 2, 3, …,k классов, без учета их порядка в классах и без ограничений на занятость класса.
Теорема заключается в том, что данное число равно: <Object: word/embeddings/oleObject4.bin>В лекции давалась задача о кольцах (сколькими способами можно одеть на пальцы одной руки 7 колец). Вот нечто подобное с доказательством:
Есть k ящиков и n>=k однаковых шаров. Сколькими способами можно разложить шары по ящикам, если могут быть пустые ящики?РешениеДавайте определять раскладку так: выложим шары в ряд и поставим между ними k-1 перегородку. То, что слева от первой перегородки, положим в первый ящик, между первой и второй - во второй... то, что справа от последней - в последний, k-й ящик. Ящик будет пустым, только если две перегородки стоят рядом не разделенные шарами, либо перегородка стоит с краю, левее или правее всех шаров. Шары и перегородки можно ставить в произвольном порядке. Давайте считать, что у нас расставлено в ряд n+k-1 объектов: n из них шары, а остальные - перегородки. Тогда раскладка будет определяться тем, на каких местах какие объекты стоят. Из n+k-1 мест можно выбрать n мест для шаров Cn+k-1n способами, или: k-1 место для перегородок Cn+k-1k-1 способами. Эти числа равны и оба являются ответом.










































7. Комбинаторные задачи о покрытиях, укладках, разбиениях. Примеры. Теорема о числе разбиений элементов множества на 2, 3, …, k классов, с учетом их порядка в классах и без ограничений на занятость класса. Доказательства. Следствия.
… смотри предыдущий вопрос Теорема (PS лекции Гусева)Пусть мы рассматриваем упорядоченные разбиения n-множества на k-подмножеств Ti. <Object: word/embeddings/oleObject5.bin> (R1, R2,…,Rk) полиноминальные коэффициенты
<Object: word/embeddings/oleObject6.bin>Доказательство <Object: word/embeddings/oleObject7.bin>Следствие R сочетаний без повторений из n множества можно интерпретировать как (R, n-R)Пример: разбиение «Комбинаторика»
К 2О 2М 1Б 1И 2Н 1А 2Т 1ОР 1ИКА
Р13 (221121121)=13!/2!2!1!...1!



8.9 Интерпретация комбинаторных операций выборки и упорядочивания как отображения множеств. Примеры. Сформулировать и доказать теорему о числе различных отображений N в K. Условие существования взаимно-однозначных отображений.
Интерпретация комбинаторных операцийИнтерпретация и выборкаиз k множества является заполнение ящиков из совокупности n с учетом k.Надо формализовать:Вид элементов и их число Вид ящиков и их вместимостьПорядок элементов, помещенных в ящикПорядок ящиковОпределение. Пусть А и В – произвольные множества. Отображением множества А в множество В называют правило (соответствие), которое каждому элементу множества А ставится в соответствие единственный для этого элемента элемент множества В.Инъективные, сюръективные, биективные отображения

Отображение 
 называется:  инъективным, если разные элементы
 
 
 в разные 
 
. Инъективное отображение удобно представлять как раскладывание m помеченных шаров в n различных ящиков так, чтобы в каждом ящике было не более одного шара.


 сюръективным, если каждый элемент множества 
 имеет хотя бы один 
 во множестве 
 при отображении 
.сюръективное отображение удобно представлять как раскладывание m помеченных шаров в n различных ящиков так, чтобы в в каждом ящике был хотя бы 1элемент.



 биективным (взаимно-однозначным отображением), если  каждому элементу одного множества соответствует ровно один элемент другого множества, при этом, определено обратное отображение, которое обладает тем же свойством. 












































10. Принцип включения и исключения. Теорема о числе элементов, не обладающих ни одним из указанных свойств (вес каждого элемента равен единице). Доказательство.Пусть дано n-множество элементов S и N-множество свойств p1,…,pN. Элементы множества S могут как обладать, так и не обладать любым из свойств pi. Количество элементов, обладающих теми или иными свойствами и их комбинациями, известно.Требуется найти число элементов, не обладающих ни одним из свойств.Обозначим:через <Object: word/embeddings/oleObject8.bin> некоторую i выборку свойств, а через <Object: word/embeddings/oleObject9.bin> – число элементов, каждый из которых обладает всеми этими r выбранными свойствами.через <Object: word/embeddings/oleObject10.bin> – отсутствие у элемента свойства pi. Тогда, например, <Object: word/embeddings/oleObject11.bin> – число элементов, обладающих свойствами p1 и p3 и не обладающих свойствами p2 и p4.
Рассмотрим два частных случая.Имеется лишь одно свойство p. Тогда очевидно, что число элементов, не обладающих свойством p, равно общему числу элементов минус число элементов, обладающих свойством p. <Object: word/embeddings/oleObject12.bin>.Имеется конечное множество свойств p1,…,pN, но они не совместимы (т.е. ни один из элементов не может обладать более чем одним свойством). Тогда число элементов, не обладающих ни одним из свойств, равно общему числу элементов минус число элементов, обладающих свойством p1, минус число элементов, обладающих свойством p2 и т.д.<Object: word/embeddings/oleObject13.bin>.Общий случай – элементы могут обладать комбинацией совместимых свойств.
Теорема. Если даны n-множество элементов S и N свойств pi <Object: word/embeddings/oleObject14.bin>, то число элементов, не обладающих ни одним из свойств, равно (формула решета): <Object: word/embeddings/oleObject15.bin><Object: word/embeddings/oleObject16.bin> nn(p1) n(p2)

n(p3)Рассмотрим доказательство при N=3.Обозначим кругами подмножества элементов, обладающих хотя бы свойством p1, хотя бы свойством p2 и хотя бы свойством p3. Тогда пересечения двух кругов будут давать подмножество элементов, обладающих хотя бы двумя свойствами одновременно, а пересечение всех трех кругов дает подмножество элементов, обладающих всеми тремя свойствами. Прямоугольник, в котором расположены круги, обозначает все множество S, содержащее n элементов. Нужно найти количество элементов, не обладающие ни одним из трёх свойств (за пределами кругов).Чтобы найти это число, нужно из n-множества исключить элементы, обладающие свойством p1, затем обладающие свойством p2, затем – p3, т.е. вычесть <Object: word/embeddings/oleObject17.bin>. Однако при этом элементы, обладающие двумя свойствами (например, p1 и p2), окажутся исключёнными дважды (сначала как элементы, обладающие свойством p1, затем как обладающие p2). Следовательно, нужно возвратить по одному разу элементы, исключённые дважды, т.е. добавить <Object: word/embeddings/oleObject18.bin>. Но при этом элементы, обладающие сразу тремя свойствами (p1, p2, p3), сначала были трижды исключены как элементы, обладающие по отдельности свойствами p1, p2 или p3, а затем трижды включены как обладающие парами свойств. Поэтому их нужно один раз исключить, т.е. вычесть <Object: word/embeddings/oleObject19.bin>. Рассуждая подобным образом, получаем алгоритм, который состоит в попеременном включении и отбрасывании подмножеств, дающий приведенную выше формулу решета.
Следствие. Характер доказательства таков, что его можно применять к любой комбинации свойств. Например,<Object: word/embeddings/oleObject20.bin>.





















11. Принцип включения и исключения. Теорема о сумме весов элементов, не обладающих ни одним из заданных свойств. Доказательство.v(Si)- вес элемента S;выборка свойств из Р1 …РNV() – сумма весов элементов, обладающих всеми из заданных свойств. сумма весов для всех выборок
(ps последняя формула не точно, общий материал взят из леций Гусева)































12. Принцип включения и исключения. Теорема о числе элементов, обладающих в точности R-свойствами из N–множества свойств. Доказательство.
Теорема:
Доказательство. Пусть некоторый элемент i имеет вес v(Si) и удовлетворяет в точности t свойствам pi1 pit из R. Возможно 3 случаяt< R вес этого элемента в подсчете не участвуют, вносится 0t=R в правую часть вносит свой собственный весt> R вносит свой вес v(Si):
Так как: )
Тогда выражение в скобках равно 0, так как оно является частным случаем разложением бинома Ньютона.











13. Задача о беспорядках. Теорема о числе беспорядков из элементов
n–множества. Доказательство. Следствия.Пусть имеется конечное упорядоченное множество элементов {1,…, n}. Из этих элементов могут быть образованы перестановки a1,…, an (ai{1,…,n}). Число всех возможных перестановок – n!. Среди этих n! перестановок есть такие, что ни один элемент не стоит на своём месте (aii, i=<Object: word/embeddings/oleObject21.bin>). Иначе говоря, элемент номер 1 не стоит на 1-ом месте, элемент номер 2 не стоит на 2-м месте, и т.д., элемент номер n не стоит на n-м месте. Такие перестановки называются беспорядками.Число беспорядков из n элементов обозначается Dn (ясно, что Dn<n!).
Теорема. Число беспорядков из n элементов равно:<Object: word/embeddings/oleObject22.bin>.Доказательство Обозначим через свойство pi – «i элемент стоит на i-м месте». Тогда по формуле решета <Object: word/embeddings/oleObject23.bin>.Общее число перестановок n элементов – n! Число перестановок, где i элемент стоит на i-м месте, равно (n-1)! (ставим i-й элемент на i-е место, а оставшиеся n-1 элементы переставляем (n-1)! способами). При этом сам i элемент можно выбрать <Object: word/embeddings/oleObject24.bin> способами. Таким образом, число перестановок, где хотя бы по одному элементу стоит на своём месте, равно <Object: word/embeddings/oleObject25.bin>.Число перестановок, где i элемент стоит на i-м месте, а j на j-м (ij), равно (n-2)!, при этом i и j элементы можно выбрать <Object: word/embeddings/oleObject26.bin> способами. Таким образом, число перестановок, где хотя бы два элемента стоят на своих местах – <Object: word/embeddings/oleObject27.bin>.Аналогично, число перестановок, где на своих местах стоят хотя бы три элемента<Object: word/embeddings/oleObject28.bin>. Число перестановок, где на своих местах стоят хотя бы r элементов<Object: word/embeddings/oleObject29.bin>. Число перестановок, где все элементы стоят на своих местах <Object: word/embeddings/oleObject30.bin>. Подставляем в формулу решета: <Object: word/embeddings/oleObject31.bin>Следствие 1.Так как <Object: word/embeddings/oleObject32.bin>,то <Object: word/embeddings/oleObject33.bin>.Следствие 2.Так как <Object: word/embeddings/oleObject34.bin>, то <Object: word/embeddings/oleObject35.bin>.
15 Функция ЭйлераФункция Эйлера φ(n), где n натуральное число, дает количество натуральных чисел, не превышающих n и взаимно простых с n. Иначе говоря, φ(n)=k, где 0<kn; (k,n)=1.
Теорема<Object: word/embeddings/oleObject36.bin>, где piвсе простые делители n. (<Object: word/embeddings/oleObject37.bin> - произведение по всем простым делителям числа n).# В теореме Лежандра заменим ai на pi, где piпростые делители n.Тогда <Object: word/embeddings/oleObject38.bin> (так как pi делят n нацело).По теореме Лежандра<Object: word/embeddings/oleObject39.bin><Object: word/embeddings/oleObject40.bin>. #
Пример. Определим, сколько чисел, не превышающих 100, взаимно простые с 100. Разложим число 100 на простые сомножители: 100=2·2·5·5=2252. Таким образом, у числа 100 два простых делителя – 2 и 5. По формуле Эйлера получаем<Object: word/embeddings/oleObject41.bin>.Таким образом, среди первой сотни есть 40 чисел, взаимно простых с 100.
Функция МебиусаФункция Мебиуса (n), где n натуральное число, принимает следующие значения:<Object: word/embeddings/oleObject42.bin>Функция Мебиуса позволяет записать функцию Эйлера в виде суммы:<Object: word/embeddings/oleObject43.bin>.Суммирование идет по всем делителям n (а не только по простым делителям).
Пример. Вычислим φ(100), используя функцию Мебиуса. Все делители 100 – {1, 2, 4, 5, 10, 20, 25, 50, 100}.(1) = 1,(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 делится и на 22, и на 55)(100) = 0 (100 делится и на 22, и на 55)Таким образом, <Object: word/embeddings/oleObject44.bin>
Свойство функции Мебиуса: <Object: word/embeddings/oleObject45.bin>.Например, n=100, {1, 2, 4, 5, 10, 20, 25, 50, 100}.<Object: word/embeddings/oleObject46.bin>.

16 Теорема о числе способов выбора k-элементов, среди которых нет двух соседних, из n элементов, расположенных в ряд. Доказать с помощью получения рекуррентной формулы.
17Число сочетаний с повторениямиЧисло r-сочетаний с повторениями из n-множества равно<Object: word/embeddings/oleObject47.bin>.– доказательство с помощью рекуррентной формулы.Метод базируется на получении формулы, позволяющей вычислять значения искомой величины шаг за шагом, исходя из известных начальных значений и значений, вычисленных на предыдущих шагах.Рекуррентная формула r-го порядка – формула видаan= f(n, an-1, an-2, … , an-r).Формула выражает при n>r каждый член последовательности {ai} через предыдущие r членов. Построение рекуррентной формулы состоит из следующих шагов.1. Выработка начальных условий исходя из каких-либо очевидных соотношений.Обозначим <Object: word/embeddings/oleObject48.bin> через f(n,r). Очевидно, что <Object: word/embeddings/oleObject49.bin> (1)2. Логические рассуждения. Зафиксируем какой-либо элемент во множестве S. Тогда относительно любого r-сочетания с повторениями из n-множества S можно сказать, содержит ли оно данный зафиксированный элемент или нет.Если содержит, то остальные (r-1) элемент можно выбрать f(n, r-1) способами.Если не содержит (в выборке этого элемента нет), то r-сочетание составлено из элементов (n-1)-множества (множество S за исключением данного зафиксированного элемента). Число таких сочетаний f(n-1, r).Т.к. эти случаи взаимоисключающие, то по правилу суммы<Object: word/embeddings/oleObject50.bin> (2)3. Проверка формулы на некоторых значениях и вывод общей закономерности. 1) Вычислим f(n,0). Из (2) следует <Object: word/embeddings/oleObject51.bin>. (3)Тогда 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=<Object: word/embeddings/oleObject52.bin>.2) f(n,1) = f(n,0)+f(n-1,1) = 1+n-1 = n = <Object: word/embeddings/oleObject53.bin> = <Object: word/embeddings/oleObject54.bin>.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 = <Object: word/embeddings/oleObject55.bin><Object: word/embeddings/oleObject56.bin>. (сумма арифметической прогрессии)4) f(n,3) = f(n,2)+f(n-1,3) = <Object: word/embeddings/oleObject57.bin>+f(n-1,2)+f(n-2,3) = <Object: word/embeddings/oleObject58.bin>+<Object: word/embeddings/oleObject59.bin>+f(n-2,2)+f(n-3,3) = … =<Object: word/embeddings/oleObject60.bin>.(сумма геометрической прогрессии)5) f(n,4) = <Object: word/embeddings/oleObject61.bin>На основе частных случаев можно предположить, что<Object: word/embeddings/oleObject62.bin> 4. Проверка начальных условий с помощью полученной формулы.<Object: word/embeddings/oleObject63.bin>,что согласуется с (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[xa].Подстановка переменной в
В λ-исчислении, подстановка определяется структурной индукцией. Для произвольных объектов
,
и произвольной переменной
результат замещения произвольного свободного вхождения
в
считается подстановкой и определяется индукцией по построению
:(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)производящая функция последовательности {ar} на базисе {gr} – функция f при разложении которой в ряд по функциям фиксированного базиса {gr} образуется данная последовательность коэффициентов {ar} …………*)
Данный ряд – формальный. Название формальный означает, что мы формулу *) трактуем как удобную запись нашей последовательности – в данном случае несущественно, для каких (действ и комплексных) значений он сходится. Роль t сводится к тому чтобы различать коэффициенты последовательности А0,А1,…Аr….поэтому в теории производящих функций никогда не вычисляют значения таого ряда для конкретного значения переменной t. Выполняются лишь только некоторые операции на таких рядах, а затем определяются только некоторые операции на таких рядах а затем определяются коэффициенты при отдельных степенях переменной t.Обычно в качестве

22Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний с повторениями.

Производящая ф-я для :Правило построения1)Если эл-т типа i может входить в сочетания K1 или K2 или… Ki раз, то ему соотв множитель 2)F(t)=3)Остается найти коэф. при экспоненциальная производящая ф-я для размещений правило построенияЕсли ai множитель входящий в размещения К1 или…или Кi раз, то ему соответствует множитель если надо найти число размещений , если надо найти сами размещенияE(t)=Остается найти коэф при
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\k0123456
01
101
20−11
302−31
40−611−61
5024−5035−101
60−120274−22585−151
В
числом Стирлинга второго рода из n по k, обозначаемым
или
, называется количество неупорядоченных
n-элементного
на k непустых подмножеств.
Рекуррентная формулаЧисла Стирлинга второго рода удовлетворяют
соотношению:
, для n ≥ 0,
, для n > 0,
для
Явная формула
ПримерНачальные значения чисел Стирлинга второго рода приведены в таблице:
n\k0123456
01000000
10100000
20110000
30131000
40176100
50115251010
601319065151
Свойствагде .
Биективным отображением называется отображение, обладающее признаками инъективности и сюръективности одновременно.Биекция Материал из Википедии — свободной энциклопедииТекущая версия страницы пока
опытными участниками и может значительно отличаться от
, проверенной 18 февраля 2012; проверки требуют
.

Текущая версия страницы пока
опытными участниками и может значительно отличаться от
, проверенной 18 февраля 2012; проверки требуют
.Перейти к:
,


Биективная функция.Биекция — это отображение, которое является одновременно и
, и
. При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества, при этом, определено обратное отображение, которое обладает тем же свойством. Поэтому биективное отображение называют ещё взаимно-однозначным отображением (соответствием), одно-однозначным отображением.Если между двумя множествами можно установить взаимно-однозначное соответствие (биекция), то такие множества называются
. С точки зрения
, равномощные множества неразличимы.Взаимно-однозначное отображение
в себя называется
(элементов этого множества).
Определение

называется биекцией (и обозначается
), если она:..
Примеры  на множестве биективно. — биективные функции из в себя. Вообще, любой одной является биекцией из в себя. — биективная функция из в .не является биективной функцией, если считать её определённой на всём .Свойства

Композиция
и
, дающая биекцию.Функция является биективной тогда и только тогда, когда существует такая, что
и
Если функции и биективны, то и композиция функций биективна, в этом случае . Коротко: композиция биекций является биекцией. Обратное, однако, неверно: если биективна, то мы можем утверждать лишь, что инъективна, а сюръективна.ПримененияВ информатикеОрганизация связи «один к одному» между

на основе
.
27) Числа Каталана Материал из Википедии — свободной энциклопедииПерейти к:
,
Числа Катала́на — числовая
, встречающаяся во многих задачах
. Последовательность названа в честь бельгийского математика
, хотя была известна ещё
.Первые несколько чисел Каталана:
,
,
,
,
,
,
, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … (последовательность
в
)
Содержание
Определенияn-е число Каталана
можно определить одним из следующих способов:Количество разбиений выпуклого (n+2)- на непересекающимися .Количество длины 2n, то есть таких последовательностей из n левых и n правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её открывающих скобок не меньше, чем закрывающих.Например, для n=3 существует 5 таких последовательностей: ((())), ()(()), ()()(), (())(), (()())то есть
.Количество способов соединения 2n точек на окружности n непересекающимися .Количество упорядоченных с корнем и n+1 листьями.СвойстваЧисла Каталана удовлетворяют :
и
для
Это соотношение легко получается из того, что любая непустая правильная скобочная последовательность однозначно представима в виде w=(w1)w2, где w1, w2 — правильные скобочные последовательности. чисел Каталана равна:
Числа Каталана можно выразить через :
Другими словами, число Каталана
равно разности
и соседнего с ним в той же строке
.
Чтобы не ограничиваться одной только ссылкой, напишу приведенный в "Конкретной математике" вывод формулы для чисел Каталана. Красивое и очень простое рассуждение.

Определение (одно из многих). Числом Каталана Cn называется количество последовательностей длины (2n+1) a0, a1, ..., a2n, составленных из +1 и -1, таких что сумма чисел равна +1, а все частичные суммы
a0, a0+a1, ..., a0+...+a2n
положительны.

Лемма Рени. Если x1, x2, ..., xm - любая последовательность целых чисел, сумма которых равна +1, то ровно у одного из её циклических сдвигов
x1, x2, ..., xm
x2, ..., xm, x1
xm, x1, ..., xm-1
частичные суммы все положительны.
Доказательство. Продолжим последовательность периодически до бесконечной последовательности: xm+k=xk, для всех k>0. Если для этой бесконечной последовательности нарисовать график частичных сумм sn=x1+...+xn, то он будет иметь "средний наклон" 1/m, поскольку sn+m=sn+1. Весь график может быть заключён между двумя прямыми наклона 1/m. Эти прямые касаются графика ровно один раз на каждом периоде из m точек, поскольку прямые с наклоном 1/m могут проходить через точки с целыми координатами только один раз на m единиц. Единственная нижняя точка касания -- это то единственное место в цикле, начиная с которого все частные суммы будут положительны.

Подсчёт последовательностей из +1 и -1 с общей суммой +1.
Всего есть C2n+1n последовательностей, содержащих n элементов -1 и (n+1) элементов +1. Построим все C2n+1n последовательностей и все (2n+1) их циклических сдвигов в виде таблицы из C2n+1n строк и (2n+1) столбцов. Очевидно, что каждая последовательность встречается в таблице (2n+1) раз, по одному разу в каждом столбце. По лемме Рени в каждой строке содержится ровно одна последовательность с положительными частичными суммами. Таким образом, всего в таблице искомые последовательности встречается C2n+1n раз. Каждая встречается (2n+1) раз. Следовательно
Cn = C2n+1n/(2n+1) = C2nn/(n+1).
28) Биномиальный коэффициент Материал из Википедии — свободной энциклопедииПерейти к:
,
В математике биномиальные коэффициенты — это коэффициенты в


по степеням x. Коэффициент при
обозначается
(иногда
) и читается «биномиальный коэффициент из n по k» (или «це из n по k»):
В
биномиальный коэффициент
интерпретируется как количество
из n по k, то есть количество всех подмножеств (
) размера k в n-элементном
.Биномиальные коэффициенты часто возникают в задачах
и
. Обобщением биномиальных коэффициентов являются

.
Явные формулыЗначение биномиального коэффициента
определено для всех целых чисел n и k. Явные формулы для вычисления биномиальных коэффициентов:
для

для
или

для
где
 обозначает
числа m.Треугольник ПаскаляТождество
позволяет расположить биномиальные коэффициенты для неотрицательных целых чисел n, k в виде треугольника Паскаля, в котором каждое число равно сумме двух вышестоящих:
Треугольная таблица, предложенная
в «Трактате об арифметическом треугольнике» (1654), отличается от выписанной здесь поворотом на 45°. Таблицы для изображения биномиальных коэффициентов были известны и ранее (
,
и др.).Строки в треугольнике Паскаля в пределе стремятся к функции
.Если взять квадратную матрицу, отсчитав N элементов по катетам треугольника и повернув квадрат на любой из четырёх углов, то детерминант этих четырёх матриц по модулю равен 1 при любом N. Если поставить уголом из 1 в верхний левый угол, то детерминант матрицы будет равен 1.В матрице
числа на диагонали i+j = const повторяют числа строк треугольника Паскаля. (i,j = 0...∞)Матрицу
где i, j = 0…p можно разложить в произведение двух строго диагональных матриц. Первая нижнетреугольная, а вторая получается из первой путем транcпонирования. Элементы такой матрицы

где i,j = 0...p Далее обратная матрица к U
таким образом можно разложить обратную матрицу к
в произведение двух строго диагональных матриц и дать явное выражение для обратных элементов. Первая верхнетреугольная, а вторая получается из первой путем транспонирования.
i,j,m,n = 0...p, если выражение в кваратных скобках ложно, то элемент суммы равен 0. Элементы обратной матрицы меняются при изменение её размера и в отличие от матрицы
недостаточно приписать новую строку и столбец.СвойстваПроизводящие функцииДля фиксированного значения n
последовательности биномиальных коэффициентов
является:
Для фиксированного значения k производящей функцией последовательности биномиальных коэффициентов
является:
Двумерной производящей функцией биномиальных коэффициентов является:
ДелимостьИз
следует, что:нечётен в числа k единицы не стоят в тех разрядах, где в числе n стоят нули.некратен простому p в числа k все разряды не превосходят соответствующих разрядов числа n.В последовательности биномиальных коэффициентов : все числа не кратны заданному простому p , где натуральное число m < p;все числа, кроме первого и последнего, кратны заданному простому p ;количество нечётных чисел равно степени двойки (степень двойки равна количеству единиц в двоичной записи числа n);не может быть поровну чётных и нечётных чисел;количество не кратных простому p чисел равно , где числа  — разряды p-ичной записи числа n; а число — её длина.Тождества(правило симметрии).Следствия тождества : для .Это тождество можно усилить0<a<na>=nесли — более общий вид тождества выше.(свёртка Вандермонда).m-ое . даёт тождество, выражающее сумму биномиальных коэффициентов с произвольным шагом s и смещением t в виде замкнутой суммы из s слагаемых:
Асимптотика и оценкипри , при где
 Алгоритмы вычисленияБиномиальные коэффициенты могут быть вычислены с помощью формулы
, если на каждом шаге хранить значения
при
. Этот алгоритм особенно эффективен, если нужно получить все значения
при фиксированном
. Алгоритм требует
памяти (
при вычислении всей таблицы биномиальных коэффициентов) и
времени (в предположении, что каждое число занимает единицу памяти и операции с числами выполняются за единицу времени).При фиксированном значении k биномиальные коэффициенты могут быть вычислены по рекуррентной формуле
с начальным значением
. Для вычисления значения
этот метод требует
памяти и
времени.