Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 51
Текст из файла (страница 51)
4.8. Пусть т = [1оя (2о((п+ 1)) и ~р: В" + В" отображение т-мерных векторов в и-мерные по методу Хэмминга (см, з 3). Пусть к = п — т и Н матрица размера й х п, составленная из наборов (взятых в качестве столбцов) с номерами от 1 до и, расположенных в порядке возрастания номеров. Доказать, что матрица Н является проверочной для кода С = ~р(В'"). Например, матрица Н из задачи 4.7, 1), д) является проверочной для кода С = ~р(Ве).
Пусть Я и Р матрицы размерности соответственно й х гл и к х п. Тогда через ЯР) будем обозначать матрицу размерности Й х (ел+ и), в которой 1-я строка (1 < 1 < Й) получена приписыванием справа к 1-й строке матрицы Ц матрицы Р. 4.9. Доказать, что кодовое расстояние линейного кода С равно минимальному весу ненулевого кодового слова. 4.10. Пусть Н = (1яР), где 1 — - единичная матрица размерности к х й, а Р произвольная двоичная матрица размерности й х х (и, — к), каждая строка которой содержит по меньшей мере две единицы и все строки попарно различны.
Доказать, что код С(Н), порожденный матрицсй Н, является кодом Хэмминга. 4.11. Выяснить, каково кодовое расстояние И(С(М)) кода С(М), порожденного матрицей М = (1эН), где 1; единичная матрица размерности 5 х 5, а Н .- матрица из задачи 4.7, 1), д). 4.12. Пусть Г С В" пространство, состоящее из линейных комбинаций матрицы Н = (1еР), где 1ь -- единичная матрица размерности Й х Й, а Р --" матрица из нулей и единиц размерности й х (и — Й). Доказатгн что 1' является нулевым пространством для матрицы С = (Рт1„ь), где 1„ь единичная матрица размерности (н — й) х (ц — й), а Рт матрица, транспонированная к матрице Р.
4.6. Найти число векторов, ортогональных к данному ненулевому вектору Н из В". 4.7. 1) По матрице Н найти кодовое расстояние д(С(Н)) кода С(Н), порожденного матрицей Н: 252 Гл. еВ. Элементов теории новирования 4.13. Показать, что кодовое расстояние (и, к)-кода не превосходит (и. 2" ~/(2в — 1)). 4.14. Показать, что при и = 2е( — 1 мощность линейного (и, Щ- кода не превосходит 2е(. 4.15.
1) Показать, что максимально возможная мощность д(п, е() линейного (и, е()-кода удовлетворяет неравенству д(п, е() ( 2д(п — 1, е(). 2) С использованием утверждения задачи 4.14 показать, что д(п, е() ( е( 2и г"+г 4.16. Пусть код С является нулевым пространством матрицы С. Показать, что кодовое расстояние кода С тогда и только тогда нс меньше е(, когда, любая совокупность из е( — 1 или меньшего числа столбцов матрицы Н является линейно независимой.
е — г т-»еп — 11 4.17. Показать, что если ~ ~ . ) ( 2 — 1, то существует 1 матрица из нулей и единиц размерности Й х т, в которой любые е( — 1 столбцов линейно независимы и, следовательно, существует (и, п — Й)-код с кодовым расстоянием не меныпе е(. 4.18. 1) Показать, что д(9, 5) = 4.
2) Показать, что т(9, 5) 3 5, 4.19. Показать, что число различных базисов в В" равно (2" — 1)(2" — 2)... (2' — 2" ') и! 4.20. Показать, что число различных (п, й)-кодов в В" равно (2" — 1)(2" — 2)...(2в — 2" ' ) (2ь — 1)(2е - 2) (2и - 2и-г) ' Глава ЪтШ ЭЛЕМЕНТЫ КОМБИНАТОРИКИ З 1. Перестановки и сочетания Свойства биномиальных коэффициентов Набор элементов а„, ..., а,„из множества Ьт = (ам ..., ав1 называется выборкой объема т из и элементов или (и, г)-выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан.
Пвс упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов не является существенным, то выборка называется неупорядоченной В выборках могут допускаться или не допускаться повторения элементов. Упорядоченная (и, г)-выборка, в которой элементы могут повторяться, называется перестпановкой с повторениями из п элементов по г или (и, т)-пересплаювкой с повторениями. Если элементы упорядоченной (и, т)-выборки попарно различны, то она называется (и, т)-перестановкой без повторений или просто (и, т)-перестановкой Число (п, т)-перестановок будет обозначаться символом Р(п, г), а число (п, г)-перестановок с повторениями символом Р(п., т). Неупорядоченная (и, г)-выборка, в которой элементы могут повторяться, называется сочетпанием с повторениями из п, элементное по т или, короче, (и, т)-сочетонием с повторениями.
Если элементы неупорядоченной выборки попарно различны, то она называется сочетанием (без повторений) из п элементов по т или (и, г)-сочетанием. Каждое такое сочетание представляет собой подмножество мощности т множества Ьт. Число сочетаний из и элементов по г будет обозначаться через С(п, г). Число сочетаний с повторениями из и элементов по т будет обозначаться через С(а, т). Пример 1.
Пусть Ьт = (а, 6, с), г = 2. Тогда имен~тел: девять перестановок с повторениями --. аа, а6, ас, Ьа, ЬЬ, Ьс, са, сЬ, сс; шесть перестановок без повторений аЬ, ас, Ьа, Ьс, са, сЬ; шесть сочетаний с повторениями аа, а6, ас, ЬЬ, Ьс, сс; три сочетания без повторений аЬ, ас, Ьс. 254 Гл. 7П1. Элементы комбинаторики Произведение п(п — 1)... 1т~ — т + 1), где п действительное, а т целое положительное, будет обозначаться через 1т1), По определению положим 1ие) = 1. Если п натуральное, то 1п)„обозначается символом и! и называется и-факториалом. При и = О полагаем О! = 1. Для любого действительного и и целого неотрицательного т величина — ' называется биномиальным коэффициентом и обознача1н),. ется символом ) ~ ~. Пусть тю тз, ..., тя -- целые неотрицательные ?и'1 ~т~' п! числа и т з + тз +...
+ ть = п. Величина называется па- тП тИ т„! линомиальным коэффициентом и обозначается через ( ~ть тм ..., тяу ' При подсчете числа различных комбинаций используются следующие два правила. Правило произведения. Если объект А может быть выбран п способами и после каждого из таких выборов объект В в свою очередь может быть выбран и способами, то выбор «А и В» в указанном порядке может быть осуществлен т . и способами. Правило суммы. Если объект А может быть выбран т способами, а объект В другими и способами при условии, что одновременный выбор А и В невозможен, то выбор «А или В» можно осуществить т + п, способами. Пример 2.
Бросают две игральные кости 1с шестью гранями каждая). Сколькими способами они могут упасть так, что либо на каждой грани выпадет четное число очков, либо на каждой грани выпадет нечетное число очков? Решение. Пусть А число способов выпадения на каждой кости четного числа очков,  — число способов выпадения на каждой кости нечетного числа очков. Тогда по правилу суммы искомое число равно А + В. Пусть С число способов выпадения четного числа очков на первой кости, а Р число способов выпадения четного числа очков на второй кости.
Ясно, что С = Р = 3, а по правилу произведения А = С Р = 9. Аналогично, В = 9, а искомое число равно 18. П р имер 3. Доказать,что число 1п, т)-перестановок без повторений равно (п~)„. Решение. Индукция по т. При т = 1 число способов выбора одного элемента из и равно и = (п)м Пусть для некоторого г > 1 выполнено равенство Р? п., т) = 1п) „.
Докажем аналогичное равенство для т + 1. Всякая совокупность, состоящая из т + 1 элементов, может быть составлена путем предварительного выбора элементов, составляющих 1п, т)-перестановку, и последующего присоединения к ней от+1)-го элемента. Если т элементов выбраны, то 1т+ 1)-й может быть *) В литературе встречаются также обозначения С,",, иС„, 1н, т). ? Д Переегаановни и сочетания 255 выбран и — г способами. В силу правила произведения получаем, что Р(п, г + 1) = Р(л, г) . (и — г). С использованием предположения инцукции получаем отсюда, что Р(и, г + 1) = (п)„(и — г) = (п)„~.ы Большое число комбинаторных задач сводится к подсчету числа двоичных векторов. Пример 4. Сколькими способами можно представить число и в видо суммы и неотрицатсльных слагаомых? (Представления, отличающиеся лишь порядком слагаемых, считаются различными.) Решение.
Каждому разбиению числа и на а. целых неотрицательных слагаемых сопоставим вектор длины п+ Й вЂ” 1 с п единицами и Й вЂ” 1 нулями, в котором число единиц, стоящих перед первым нулем, равно первому слагаемому, число единиц, расположенных между первым и вторым нулями, .равно второму слагаемому и т.д. Соответствие взаимно однозначно. Заметим, что каждому двоичному вектору с п+ Й вЂ” ! координатами и и единицами в свою очередь можно сопоставить и-алиментное подмножество А множества Г = (аы аз, ..., а„е е) следующим образом: 1-я координата вектора равна 1 тогда и только тогда, когда и, Е А (1 = 1, 2,..., и+ а — 1). Но число таких подмножеств ость С(п -1- й -~- 1, п).
1.1. Сколькими способами можно распределить три билета среди 20 студентов, если: 1) распределяются билеты в разные театры, а каждый студент может получить не более одного билета; 2) распределяются билеты в разные театры и на разные дни, а каждый студент может получить любое (не превышающее трех) число билотов; 3) распределяются равноценные билеты на вечер н каждый студент может получить не более одного билета? 1.2. Выяснить, сколькими способами можно выстроить девять че- ЛОВОК; 1) в колонну по одному; 2) в колонну по три, если в каждой шеренге люди выстраиваются по росту и нет людей одинакового роста? 1.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
