bigpo.ru
добавить свой файл
1 2

-

Раздел IV. Дискретная математика

Автор: Мансур Муллагаянович Галламов
Страничка в ЖЖ



Содержание программы по разделу дискретная математика


  1. Преамбула

  2. Подраздел IV.1. Комбинаторика.

Темы:

IV.1.1. Теоремы существования: чередование, принцип Дирихле.

IV.1.2. Элементы комбинаторики.

Подтемы (основные понятия и методы комбинаторики):

Основные понятия и методы комбинаторики.

IV.1.2.1. Классические задачи комбинаторики.

IV.1.2.2. Применение арифметических операций в комбинаторике.

IV.1.2.3. Технический прием вычисление вариантов – “шары и перегородки”.

IV.1.2.4. Формула «включений и исключений».

IV.1.2.5. Применение формула «включений и исключений».

IV.1.2.6. Алгебраические методы в комбинаторике

IV.1.2.7. Комбинаторные тождества

IV.1.2.8. Геометрические методы в комбинаторике

IV.1.2.9. Примечательные числа комбинаторики


  1. Подраздел IV.2. Игры

Темы:

IV.1.1. Детерминированые игры. Игры на симметрию. Выигрышные позиции.

IV.1.2. Игры и система счиления.

IV.1.3. Логические игры.

IV.1.4. Математические головоломки

IV.1.5. Турниры.

IV.1.6. Элементы дифференцируемых игр.


  1. Подраздел IV.3. Логические этюды

Темы:

IV.3.1. Логические задачи.

IV.3.2. Переправы, взвешивание, переливание, дележ, конструкции.

IV.3.3. Занимательные задачи, ребусы, головоломки, логические игры.


  1. Подраздел IV.4. Графы

Темы:

IV.4.1. Основные понятия, свойства и операции над графами

IV.4.2. Связные, плоские графы

IV.4.3. Раскраски и графы

IV.4.4. Ориентированные графы

IV.4.5. Экстремальные графы

IV.4.6. Задачи, решаемые с помощью графов

IV.4.7. Группы и их графы


  1. Подраздел IV.5. Вычислительная математика и алгоритмы

  2. Подраздел IV.6. Математическая логика и нормальные дизъюнктивные формы


Преамбула


Дискретная математика область математики, занимающаяся изучением свойств структур конечного характера, которые возникают как в самой математике, так и в области ее приложений. К числу таких конечных структур могут быть отнесены, например, некоторые алгебраические системы, конечные группы, графы, комбинаторика, некоторые метаматематические модели преобразователей дискретной информации, такие как конечные автоматы, машины Тьюринга и др., а также некоторые виды вычислительных сред (например, однородные структуры) и т. п. К числу таких структур могут быть отнесены некоторые виды вычислительных сред.

В отличие от дискретной математики классическая математика в основном занимается изучением свойств объектов непрерывного характера. Использование классической или дискретной математики как аппаратов исследования связано с тем, какие задачи ставит перед собой исследователь, и, в связи с этим, какую модель изучаемого явления он рассматривает — дискретную или непрерывную. Само деление математики на классическую и дискретную в значительной мере условно, поскольку, с одной стороны, происходит активная циркуляция идей и методов между ними, а с другой часто возникает необходимость исследования моделей, обладающих одновременно как дискретными и, так и непрерывными свойствами. Кроме того, в математике существуют подразделы, использующие средства дискретной математики для изучения непрерывных моделей, и, наоборот, часто средства и постановки задач классического анализа используются при исследовании дискретных структур. Это указывает на известное слияние рассматриваемых областей.

Дискретная математика представляет собой важное направление в математике, имеющее характерные для неё предмет исследования, методы и задачи, специфика которых обусловлена, в первую очередь, необходимостью отказа от основополагающих понятий классической математики — предела и непрерывности — и (в связи с этим) тем, что для многих задач дискретной математики сильные средства классической математики оказываются, как правило, мало приемлемыми. Наряду с выделением дискретной математики путем указания его предмета, методов и задач можно также охарактеризовать дискретную математику посредством перечисления подразделов, составляющих её. К ним, в первую очередь, относятся комбинаторный анализ, теория графов, теория кодирования и декодирования, теория функциональных систем и некоторые другие.

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

Элементы дискретной математики возникли в глубокой древности и, развиваясь параллельно с другими разделами математики, в значительной мере являлись их составной частью. Типичными для того периода были задачи, связанные со свойствами целых чисел, приведшие затем к созданию теории чисел. Позже, в основном в связи с игровыми задачами, появились элементы комбинаторного анализа и дискретной теории вероятностей, а в связи с общими проблемами теории чисел, алгебры и геометрии возникли важнейшие понятия алгебры такие, как группа, поле, кольцо и др., определившие развитие и содержание алгебры на много лет вперед и имевшие по существу дискретную природу. Стремление к строгости математических рассуждений и анализ рабочего инструмента математики логики — привели к выделению еще одного важного раздела математики — метаматематической логики. Однако наибольшего развития дискретная математика достигла в связи с появлением кибернетики и ее теоретической части математической кибернетики. Математическая кибернетика, непосредственно изучающая с позиций математики самые разнообразные проблемы, которые ставит перед кибернетикой практика, является важным поставщиком идей и задач для дискретной математики вызывая в ней целые новые направления. Так, прикладные вопросы, требующие большой числовой обработки, стимулировали появление мощных численных методов решения задач, оформившихся затем в вычислительную математику, а анализ понятий вычислимости и алгоритма привел к появлению важного раздела математической логики – теории алгоритмов. Растущий поток информации и связанные с ним задачи хранения, обработки и передачи информации привели к возникновению теории кодирования; экономические задачи, задачи электротехники, равно как и внутренние задачи математики, потребовали разработки теории графов; задачи конструирования и описания работы сложных управляющих систем привели к теории функциональных систем и т. д. В то же время математическая кибернетика использует результаты дискретной математики при решении своих задач.

Наряду с отмеченными, дискретная математика обладает рядом и других особенностей. Так, вместе с задачами типа существования, имеющими общематематический характер, важное место в дискретной математике занимают задачи, связанные с алгоритмической разрешимостью и построением конкретных решающих алгоритмов, что характерно именно для дискретной математики. Особенностью дискретной математики является и то, что она по существу первая столкнулась с необходимостью глубокого исследования так называемых дискретных многоэкстремальных задач, часто возникающих в математической кибернетике. Соответствующие методы классической математики для поиска экстремумов, существенно использующие гладкость функций, в этих случаях оказываются мало эффективными. Типичными задачами такого рода в дискретной математике являются, например, задачи об отыскании в некотором смысле оптимальных стратегий в шахматной партии при ограниченном числе ходов, поиск выигрышной стратегии (см. тему: «IV.1.1. Детерминированые игры. Игры на симметрию. Выигрышные позиции» подраздела «IV.2. Игры» данного раздела, а также важный вопрос математической кибернетики о построении минимальных дизъюнктивных нормальных форм для булевых функций, т. е. так называемая проблема минимизации булевых функций. Особенностью дискретной математики, связанной уже с задачами для конечных структур, является и то, что для многих из этих задач, как правило, существует алгоритм решения, в то время как в классической математике полное решение задачи часто возможно лишь при весьма жестких ограничениях. Примером такого алгоритма может служить алгоритм просмотра всех возможных вариантов, т. е. алгоритм типа «полного перебора». К числу задач указанного вида можно отнести, например, упомянутые задачи о стратегиях в шахматной партии, о минимизации булевых функций и др. Вместе с тем, решения типа «полного перебора» очень трудоемки и практически мало приемлемы, в связи с чем возникает ряд новых задач, связанных с условиями, ограничивающими перебор и приводящими к сведению индивидуальных задач, характеризующихся конкретными значениями параметров, к массовой проблеме, характеризующейся бесконечным множеством значений параметров; возникают задачи наложения ограничений на средства решения, естественных для этого класса задач, и др. IIостановка такого рода вопросов и разработка методик осуществляется на конкретных моделях, доставляемых различными разделами математики, например, на моделях минимизации булевых функций и синтеза управляющих систем из математической кибернетики.

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

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


Подраздел IV.1. Комбинаторика.


Темы:

IV.1.1. Теоремы существования:


Подтемы:

IV.1.1.1. Четность: чередование, разбиение на пары, четность и нечетность

Литература:

  1. Шарыгин И. Ф., Шевкин А. В. Задачи на смекалку. Учебное пособие для 5-6 классов общеобразовательных учреждений. М: Просвещение, 2003. – 95 с. (2. Четность. С.19-24)

  2. Генкин С. А., Итенберг И. В., Фомин Д. В. Ленинградские математические кружки. Киров: АСА, 1994. – 272 с. (Глава 2. Четность. С. 12 – 16. Задачи № 1 – 32).

  3. Мерзляков А. С. Факультативный курс по математике (первый год обучения). Ижевск Издательский дом «Удмуртский университет», 2002.318 с. (Занятие 6. Четность. С. 59 – 70; Занятие 7: Аналоги четности: чередование, разбиение на пары. С. 71 – 80. Задачи на стр.77 – 78)

  4. Спивак А. В. Тысяча и одна задача по математике. М.: Просвещение, 2002. – 207 с. [§45. Четность. Задачи № 434 – 450. §46. Чередование. Задачи № 452 – 460. §47. Разбиение на пары. Задачи № 461 – 469. С.68 – 75]

  5. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (§4.1. Четность. Задачи № 4.1 – 22. С. 62 – 65).

  6. Бахтина Т. П. Раз задачка, два задачка…Минск: Асар, 2001. – 224 с. [Задачи № 57 – 71. С. 41 – 46 ].

  7. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи. М:МЦНМО, 2001. – 96 с. [Задачи № 2 – 3, 6, 10. С.14 – 15 ]

  8. Рукшин С. Е. Математические соревнования в Ленинграде – Санкт-Петербурге. Первые 50 лет. Ростов н/Д,2000. – 320 с. (См. в предметном указателе термин “Четность”).

  9. Сайт: www.mccme.problems.ru  

  10. Сайт: www.mccme.ru


IV.1.1. 2. Принцип Дирихле. Принцип Дирихле для остатков. Принцип Дирихле для длин, углов и площадей

Литература:

  1. Генкин С. А.., Итенберг И. А., Фомин Д. В. Ленинградские математические кружки: пособие для внеклассной работы. Киров: АСА, 1994. 272 с. (Принцип Дирихле. Задачи № 1 – 34. С. 39 – 46).

  2. Бахтина Т. П. Раз задачка, два задачка…Минск: Асар, 2001. – 224 с. (Глава III. Принцип Дирихле. Задачи № 167 – 205. С.104 – 124).

  3. Мерзляков А. С. Факультативный курс по математике (первый год обучения). Ижевск Издательский дом «Удмуртский университет», 2002. – 318 с. (Принцип Дирихле. С.147-160)

  4. Бабинская И. Л.. Задачи математических олимпиад. М.: Наука, 1975. – 112 с. (Глава 1. §3. Принцип Дирихле (Задачи № 106 – 128. С.16-18).

  5. Леман А. А.. Сборник задач московских математических олимпиад. Под ред. В. Г. Болтянского. М.: Просвещение, 1965.

  6. Муштари Д. X.. Подготовка к математическим олимпиадам: задачи, темы, методы. Казанский ун-т, 1990. – 239 с. (Теоремы существования.§23. Принцип Дирихле. Задачи № 170 – 193. §24. Принцип Дирихле для остатков. Задачи № 185 – 189. §25. Принцип Дирихле для длин и площадей. Задачи № 190 – 193.)

  7. Андреев А.А., Горелов Г.Н., Люлев А.И., Савин А.И. "Принцип Дирихле", Самара "Пифагор", 1997

  8. Фоминых Ю. Ф.. Принцип Дирихле. // Ж-л «Математика в школе», 1996, No3.

  9. Шарыгин И. Ф., Шевкин А. В. Задачи на смекалку. М: Просвещение, 2003. – 95 с. (9. Принцип Дирихле. С. 51 – 5 2).

  10. Рукшин С. Е. Математические соревнования в Ленинграде – Санкт-Петербурге. Первые 50 лет. Ростов н/Д,2000. – 320 с. (См. в предметном указателе термин “Принцип Дирихле”)

  11. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (§2.2. Принцип Дирихле. Задачи № 2.17 – 38. С. 17 – 19)

  12. Энциклопедия для детей. Т11. Математика. М:Аванта+,2002. – 688 с. (Принцип Дирихле. С.564)


IV.1.1.3. Принцип максимума (минимума)

Литература:

  1. Муштари Д. X.. Подготовка к математическим олимпиадам: задачи, темы, методы. Казанский ун-т, 1990. – 239 с. (Теоремы существования. §26. Принцип максимума (минимума). Задачи № 194 – 205)

  2. Рукшин С. Е. Математические соревнования в Ленинграде – Санкт-Петербурге. Первые 50 лет. Ростов н/Д,2000. – 320 с. (См. в предметном указателе термин “Принцип крайнего”)

  3. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи. М:МЦНМО, 2001. – 96 с. [Метод крайнего. Примеры 1 – 5. С. 32 – 33. Задачи № 1 – 13. С. 33 – 34]


IV.1.1.4. Метод раскраски.

Литература:

  1. Дынкин Е. Б., Успенский В. А. Математические беседы. Москва · Ижевск: РХД, 2002. – 260 с. (Раздел I. Задачи о многоцветной раскраске. С. 9 – 42)

  2. Гантмахер Г., Теплиц О. Числа и фигуры. Ижевск: Ижевская республиканская типография, 200. – 254 с. 13. Проблема четырех красок. С. 92 – 102 (Излагается другой подход к этой проблеме, чем в [1])

  3. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с.

  4. Рукшин С. Е. Математические соревнования в Ленинграде – Санкт-Петербурге. Первые 50 лет. Ростов н/Д,2000. – 320 с. (См. в предметном указателе термин “Раскраски”)

  5. Спивак А. В. Тысяча и одна задача по математике. М: Просвещение, 2002. – 207 с.

  6. Бахтина Т. П. Раз задачка, два задачка…Минск: Асар, 2001. – 224 с.

  7. Канель-Белов А. Я., Ковальджи А. К. Как решают нестандартные задачи. М.: МЦНМО, 2001. – 96 с.

  8. Мительман И. М. Раскрасим клетчатую доску. Ижевск: Издательский дом «Удмуртский университет»,2002. – 56 с.


IV.1.2. Элементы комбинаторики: основные понятия и методы комбинаторики

Подтемы:

IV.1.2.1. Классические задачи комбинаторики.

Литература:

  1. Математическая энциклопедия: Гл.редактор И. М. Виноградов,т.2 Д – Коо – М.: «Советская энциклопедия»,1979. – 1104 стб.,ил. (ст.»Комбинаторные задачи». С.971 – 974).

  2. Риордан Дж. Введение в комбинаторный анализ. М.: Мир, 1963. – 256 с.(Из предисловия автора. С.5 – 8. Глава 1. Перестановки и сочетания. С.9 – 28. Глава 2. Производящие функции. С.29 – 62)


IV.1.2.2. Применение арифметических операций в комбинаторике.

Литература:

  1. Генкин С. А.., Итенберг И. А., Фомин Д. В. Ленинградские математические кружки: пособие для внеклассной работы. Киров: АСА, 1994. 272 с. (Комбиниторика-1. С. 17 – 25.Комбиниторика-2. С.123 – 139)

  2. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава I. Общие правила комбинаторики (16 задач). Глава II. Размещения , перестановки и сочетания (17 задачи))

  3. Шафаревич И. Р. Избранные главы алгебры: учебное пособие для школьников. М: Журнал «Математическое образование», 2000. – 380 с. (Глава 3. Конечные множества (Тема: Множество). §8. Комбинаторика. С. 103 – 120)

  4. Спивак А. В. Тысяча и одна задача по математике. М: Просвещение, 2002. – 207 с. (72. Комбинаторика. С. 117 – 129).

  5. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. [Задачи №2.2 – 11, 1.40. С.16 – 17. Задачи №2.42 – 2.52. С.20 – 21, Задачи №2.57 – 2.70. С.22 – 23].

  6. Яглом А. М., Яглом И. М. Неэлементарные задачи в элементарном изложении: Задачи по комбинаторике и теории вероятностей, задачи из разных областей математики. М.: КомКнига, 2006. – 544 с. (Раздел I: Задачи по комбинаторике и теории вероятностей. §I.1. Вводные задачи (1 – 10)).

  7. Холл М. Комбинаторика. М.: Мир, 1970. – 424 с. (Глава 1. Перестановки и сочетания. С.9 – 17).


IV.1.2.3. Технический прием вычисление вариантов – “шары и перегородки”.

Литература:

    1. Мерзляков А. С. Факультативный курс по математике (первый год обучения). Ижевск Издательский дом «Удмуртский университет», 2002. – 318 с. (Занятие 4. Комбинаторика. С. 33 – 48)

    2. Генкин С. А.., Итенберг И. А., Фомин Д. В. Ленинградские математические кружки: пособие для внеклассной работы. Киров: АСА, 1994. 272 с. [Глава комбинаторика-2. §3. Шары и перегородки. С. 134 – 136].

    3. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. [Задачи №2.13 – 14, 1.40. С.17. Задачи №2.2.71 – 2.75. С.23 – 24.].

    4. Яглом А. М., Яглом И. М.Неэлементарные задачи в элементарном изложении: Задачи по комбинаторике и теории вероятностей, задачи из разных областей математики. М.: КомКнига, 2006. – 544 с. (Раздел I: Задачи по комбинаторике и теории вероятностей. §I.2. Разложение чисел в произведение сомножителей и на сумму слагаемых (11 – 31)).

    5. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава IV. Комбинаторика разбиений (22 задачи)).

    6. Холл М. Комбинаторика. М.: Мир,1970. – 424 с. (Глава 3. Производящие функции и рекуррентные соотношения. С.33 – 44. Глава 4. Разбиения. С.45 – 64).

    7. Эндрюс Г. Теория разбиения. М.: Наука, 1982. – 256 с. (О методах разбиения натурального числа)


IV.1.2.4. Формула «включений и исключений».

Литература:

  1. Колосов В. А. Теоремы и задачи алгебры, теории чисел и комбинаторики. М: «Гелиос АРВ», 2001. – 256 с. (§2.4. Формула «включений и исключений». С.39 – 44.).

  2. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. [§2.4. Формула «включений и исключений». С.28 – 30.Задачи №2.109. С.29].

  3. Холл М. Комбинаторика. М.: Мир,1970. – 424 с. (§2.1. Принцип включения и исключения. Обращение Мёбиуса. С.10 – 26).

  4. Риордан Дж. Введение в комбинаторный анализ. М.: Мир, 1963. – 256 с. (Глава 3. Принцип включения и исключения. 1. Введение, с. 63. 2. Логическое тождество, с. 62 – 76. 3. Символическое обобщение. 66 – 70. 4. Ранг, с. 70 – 71)

  5. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с. (Глава третья. Логические методы. § 3.1. Метод включения и исключения, 77 – 85)


IV.1.2.5. Применение формула «включений и исключений».

Литература:

  1. Колосов В. А. Теоремы и задачи алгебры, теории чисел и комбинаторики. М: «Гелиос АРВ», 2001. – 256 с. (§2.4. Формула «включений и исключений». С.39 – 44)

  2. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. [§2.4. Формула «включений и исключений». С.28 – 30.Задачи №2.101 – 116. С.28 – 30].

  3. Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. М.: Наука, 1977. – 80 с. (§11. Метод включений и исключений. С.49 – 63).

  4. Риордан Дж. Введение в комбинаторный анализ. М.: Мир, 1963. – 256 с. (Глава 3. Принцип включения и исключения. 5. Задача о встречах, с. 71 – 76)

  5. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с. (Глава третья. Логические методы. § 3.1. Метод включения и исключения, 77 – 85. § 3.2. системы представлений множеств, с. 85 – 92. § 3.3. Теорема Рамсея, с. 92 – 97)


IV.1.2.6. Алгебраические методы в комбинаторике: методы рекуррентных соотношений, многочленов, производящих функций

Литература:

    1. Шафаревич И. Р. Избранные главы алгебры: учебное пособие для школьников. М: Журнал «Математическое образование», 2000. – 380 с. (Глава 7.Степенные ряды (Тема: Многочлен). §21. Многочлены как производящие функции. §22. Степенные ряды. §23. Partitio numerous (разбиение чисел). Приложение 1. Пентагональная теорема Эйлера. Приложение 2. Производящие функции для чисел Бернулли. С. 311 – 385)

    2. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (11. Последовательности и ряды. 11.2. Рекуррентные последовательности. С. 185 – 192. 11.3. Ароизводящие функции. С. 192 – 198)

    3. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава I. Общие правила комбинаторики (Глава VI. Рекуррентные соотношения.С. 154 – 181. Глава VII. Комбинаторика и ряды. С. 182 – 218).

    4. Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. М.: Наука, 1977. – 80 с. (§9. Метод рекуррентных соотношений. С. 46 – 47. §10. Метод производящих функций. С. 47 – 59).

    5. Кохась К. П. Ладейные числа и многочлены. М.: МЦНМО, 2003. – 20 с. (Биб-ка «Математическое просвещение». Вып. 26)

    6. Ландо С. К. Лекции о производящих функциях. М.: МЦНМО, 2002. – 144 с.

    7. Холл М. Комбинаторика. М.: Мир,1970. – 424 с. (Глава 3. Производящие функции и рекуррентные соотношения. С. 33 – 44).

    8. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с.

    9. Риордан Дж. Введение в комбинаторный анализ. М.: Мир, 1963. – 256 с.

    10. Грэхем Р., Кнут Д., Паташник О. Конкретная математика: основания информатики. М.: Мир, 1998. – 708 с. (1 Возвратные задачи. С. 17 – 386 Специальные числа. 7 Производящие функции. 7.3 Решение рекуррентных сотношений. С. 287 – 517. )


IV.1.2.7. Комбинаторные тождества

Литература:

  1. Генкин С. А.., Итенберг И. А., Фомин Д. В. Ленинградские математические кружки: пособие для внеклассной работы. Киров: АСА, 1994. – 2 72 с.

  2. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с.

  3. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава I. Общие правила комбинаторики

  4. Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. М.: Наука, 1977. – 80 с. (Метод траекторий)

  5. Яглом А. М., Яглом И. М. Неэлементарные задачи в элементарном изложении: Задачи по комбинаторике и теории вероятностей, задачи из разных областей математики. М.: КомКнига, 2006. – 544 с. (Раздел I. Задачи по комбинаторике и теории вероятностей.5. Задачи на биномиальные коэффициенты. Задачи № 55 – 61)

  6. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с.

  7. Грэхем Р., Кнут Д., Паташник О. Конкретная математика: основания информатики. М.: Мир, 1998. – 708 с. (5 Биномиальные коэффициенты. С. 178 – 286)

  8. Риордан Дж. Комбинаторные тождества. М.: Наука,1982. – 226 с.


IV.1.2.8. Геометрические методы в комбинаторике

Литература:

  1. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с.

  2. Веленкин Н. Я. Комбинаторика. М.: Наука, 1969. – 328 с. (Глава I. Общие правила комбинаторики

  3. Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. М.: Наука, 1977. – 80 с. (Метод траекторий)

  4. Рыбников К. А. Введение в комбинаторный анализ. М.: МГУ, 1972. – 256 с. (Геометрические методы в комбинаторике)


IV.1.2.9. Примечательные числа комбинаторики. Биномиальные коэффициенты. Числа Фибоначчи, Бернулли, Каталана, Люка, Стирлинга.

Литература:

  1. Алфутова Н. В., Устинов А. В. Алгебра и теория чисел. Сборник задач. М: МЦНМО, 2005. – 320 с. (см. предметный указатель)

  2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика: основания информатики. М.: Мир, 1998. – 708 с.

  3. Доценко В. Числа Каталана и естественные отображения. С.180 – 212. // Задачи Санкт-Петербургской олимпиады по математике. Спб: Санкт-Петербургский государственный университет. – 2003.




следующая страница >>