Содержание
- 2. Вопросы Проблемы комбинаторики Два правила комбинаторики Модельные задачи комбинаторики Функции, размещения, слова Задачи с ограничениями Перестановки
- 3. 2200 г. до н.э. китайский император ЮИ наблюдал магический узор волшебной черепахи… В современной интерпретации это
- 4. Существуют ли другие магические квадраты? Сколько существует магических квадратов? Существуют ли магические квадраты другой размерности? Если
- 5. Комбинаторика – раздел математики, в котором изучаются вопросы о количестве различных конфигураций (комбинаций), подчиненных тем или
- 6. Первая проблема – проблема пересчета подсчитать число комбинаций из заданных элементов, подчиненных условиям задачи Вторая проблема
- 7. Задачи, решающие проблемы комбинаторики Задача существования комбинаций Оценка числа комбинаций Подсчет числа комбинаций Перечисление комбинаций (реализация
- 8. Правило произведения: Если объект A может быть выбран m различными способами и после каждого из таких
- 9. Правило суммы: Если объект A может быть выбран m различными способами, а объект B может быть
- 10. Классическая задача комбинаторики: подсчитать число различных размещений n объектов по m ящикам так, чтобы были выполнены
- 11. Решение: Пусть X – множество объектов, |X| = n, Y – множество ящиков, |Y| = m.
- 12. Задача о числе функций: Пусть f : X → Y – функция, X , Y –
- 13. Утверждение: задачи I и II эквивалентны Доказательство: Любое размещение можно описать последовательностью. Пусть X – область
- 14. Задача о словах: Пусть Y = {y1, y2, …, ym} – конечный алфавит (множество различных символов),
- 15. Задача о словах: подсчитать число различных слов длины n в заданном алфавите Y (или удовлетворяющих заданным
- 16. Отображение f : X → Y инъективно ⇔ x1 ≠ x2 ⇒ f (x1) ≠ f
- 17. Утверждение 1’: Число размещений n различных объектов по m различным ящикам при условии, что в каждом
- 18. Перестановка – взаимно-однозначное отображение множества на само себя, т.е. f : X → X Обозначение: Краткая
- 19. Утверждение 2: Число перестановок из n различных элементов равно Pn = n!. Доказательство: Перестановка – инъективное
- 20. Двойным факториалом натурального числа n называется произведение числа n и всех меньших натуральных чисел той же
- 21. Упорядоченные размещения Пусть x ∈ ℝ Верхней n-ой степенью числа x называется [x]n = x⋅( x
- 22. Упорядоченнные размещения Упорядоченное размещение – размещение n объектов по m ящикам так, что каждый ящик содержит
- 23. Утверждение 3: Число упорядоченных размещений n различных объектов по m ящикам равно [m]n = m⋅( m
- 24. Пусть A = {a1, ... ,am } – упорядоченный алфавит, т.е. a1 Cлово x1x2... xn длины
- 25. Утверждение 4: Число монотонных слов длины n в алфавите из m символов равно [m]n / n!.
- 26. Задача Муавра: Чему равно число способов представления целого положительного числа m как упорядоченной суммы n неотрицательных
- 27. Задача 1: Небольшой фирме необходимо для работы приобрести 10 компьютеров. В магазине имеется в наличие 4
- 29. Скачать презентацию