|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[32] Биномиальные коэффициенты Для числа сочетаний из га по к используется обозначение Ск или (в английской литературе) (): Эта формула симметрична относительно замены к на га - к : Скп = Спп~к.(6.4) Числа Ск известны также как биномиальные коэффициенты (binomial coefficients), появляющиеся в биноме Ньютона (binomial expansion): п (x + y)n = J2Cknxkyn-k(6.5) к=0 (если раскрыть скобки в (ж + у)п, то количество членов, содержащих к множителей ж и га - к множителей у, равно количеству способов выбрать к мест из га, т.е. Ск). При ж = у = 1 бином Ньютона даёт к=0 Сп-(6-6) (Комбинаторный смысл: 2п двоичных строк длины га сгруппированы по числу единиц: имеется как раз Ск строк с к единицами.) Существует много тождеств с биномиальными коэффициентами (некоторые из них предлагаются в качестве упражнений в конце этого раздела). Оценки биномиальных коэффициентов В некоторых случаях нам понадобится оценить величину биномиальных коэффициентов. Для 1 к га имеем оценку снизу , га(га- 1) ..-(га - к+ 1) к{к-1)--Л га\ /га - 1\ /га - к А- 1 к) \к- 1) \ 1 raN Ь > (?) •(6-7) Используя неравенство kl (~)к, являющееся следствием формулы Стирлинга (2.12), получаем оценку сверху , га(га - 1) ---(га- к +1) к{к-1)--Л /еп\к < (т) •(6-9) Для всех 0 к га можно по индукции (см. упр. 6.1-12) доказать оценку где ради удобства записи полагаем 0° = 1. Для к = An, где 0 А 1, эта оценка может быть записана как Схпа < (Ап)А«((1-А)п)(!-А> 1-А\ где величина )(6-11) (6.12) Я(А) = -A lg А - (1 - A) lg(l - А)(6.13) называется (двоичной) шенноновской энтропией, по-английски (binary) entropy function. В этой записи мы полагаем 0 lg 0 = 0, так что Я(0) = Я(1) = 0. Упражнения 6.1-1 Сколько существует /г-подстрок строки длины га? (Подстроки, начинающиеся с различных позиций строки, считаются разными.) каково общее число подстрок строки длины га? 6.1-2 Булева функция (boolean function) с га входами и т выходами - это функция, определенная на множестве {true, false}™ со значениями в множестве {true, false}"1. Сколько существует различных булевых функций с га входами и одним выходом? А булевых функций с га входами и т выходами? 6.1-3 Сколькими способами га (различных) профессоров могут расположиться за круглым столом? Способы, отличающиеся поворотом, считаются одинаковыми. 6.1-4 Сколькими способами можно выбрать три различных числа из множества {1, 2,..., 100} так, чтобы их сумма была четной? (Порядок выбора существен.) 6.1-5 Докажите тождество Ckn = jCtX(6.14) для 0 < к га. 6.1-6 Докажите тождество Сп~ п-к-1 для 0 к < га. 6.1-7 Выбирая к предметов из га, можно отметить один из предметов и следить, выбран он или нет. Используя это обстоятельство, докажите, что s~ik s~ik I s~ik - 1 bn - un-l "I" un-l • 6.1-8 Используя результат упражнения 6.1-7, составьте таблицу для Ск при га = 0,1,2,..., 6 и при к от 0 до га в виде равнобедренного треугольника (Сд сверху, С° и С\ в следующей строке, и так далее). Этот треугольник называют треугольником Паскаля (Pascals triangle). 6.1-9 Докажите равенство п 8 = 1 6.1-10 Покажите, что для фиксированного га 0 величина Ск достигает наибольшего (среди всех к от 0 до га) значения при к = ra/2j и при к = [га/2] (так что для чётного га максимум один, а для нечётного - два стоящих рядом). 6.1-11* Покажите, что для любых га 0, J 0, к 0, j + /г га выполнено неравенство f<j + k / f<jf<k с помощью комбинаторных рассуждений, а также с использованием формулы (6.3). В каких случаях это неравенство обращается в равенство? 6.1-12* Докажите по индукции неравенство (6.10) для к п/2; затем, используя (6.4), докажите его для всех к га. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||