ОКТЧ 7. Сочетания. Принцип Дирихле

• Преподаватель начинает лекцию, приветствует студентов и задает вопрос о настроении.  

• Он обещает много интересных и нетривиальных утверждений в области комбинаторики.  

• Преподаватель объясняет правила сложения и умножения в комбинаторике.  

• Он подчеркивает, что правила умножения не зависят от того, пересекаются ли множества.  

• Преподаватель объясняет принцип Дирихле, который утверждает, что в любом наборе из n ящиков и n+1 кролика, по крайней мере, два кролика окажутся в одном ящике.  

• Он также упоминает, что этот принцип может быть применен к различным задачам.  

• Преподаватель объясняет разницу между размещением и сочетанием в комбинаторике.  

• Он приводит примеры, чтобы объяснить, как эти понятия применяются в различных ситуациях.  

• Преподаватель подчеркивает важность умения считать комбинаторные числа для успешного изучения комбинаторики.  

• Он приводит пример из своей научной работы, где он столкнулся с трудностями в подсчете комбинаторных чисел.  

• В видео обсуждается понятие "Цейзен пока" - количество способов выбрать из n объектов k штук так, чтобы они образовывали размещение без повторений, где порядок важен, но объекты не могут повторяться.  

• Обозначение "Цейзен пока" используется для удобства, но в мировой литературе чаще используется альтернативное обозначение "Цейзен пока".  

• В видео объясняется, что "Цейзен пока" можно выразить через "Цейзен пока с чертой" и "Цейзен пока без черты".  

• В видео объясняется, что "Цейзен пока с чертой" - это "Цейзен пока" без одного объекта.  

• Утверждается, что "Цейзен пока с чертой" равно "Цейзен пока минус один" и "Цейзен пока минус к плюс один".  

• В видео также объясняется, что "Цейзен пока с чертой" можно выразить через "Цейзен пока" и "Цейзен пока без черты".  

• В видео объясняется, что "Цейзен пока без черты" - это "Цейзен пока" без одного объекта, который не возвращается на место после выбора.  

• Утверждается, что "Цейзен пока без черты" равно "Цейзен пока" минус один.  

• В видео также объясняется, что "Цейзен пока без черты" можно выразить через "Цейзен пока" и "Цейзен пока с чертой".  

• Пример кодирования сочетания с повторениями, где используется русский алфавит.  

• Вводится понятие кода - последовательности из нулей и единиц.  

• Объекция между множеством всех к-сочетаний с повторениями и множеством всех последовательностей.  

• Принцип Дирихле: если в н ящиках н+1 кролик, то в каком-то ящике обязательно будет два кролика.  

• Пример с квадратом и пятью точками, где принцип Дирихле очевиден.  

• Множество в, состоящее из последовательностей ноликов, единиц и минус единиц.  

• Мощность множества в равна ц из восьми по четыре.  

• Обсуждается подмножество дубль в, обладающее свойством отсутствия ортогональных векторов.  

• Вопрос: насколько большой может быть мощность множества дубль в?.  

• В видео обсуждается принцип Дирихле, который утверждает, что если n кроликов распределены по ящикам, то в каждом ящике будет не менее n/k кроликов, где k - количество ящиков.  

• В данном случае, принцип Дирихле применяется к последовательностям из единиц и минусов, которые распределены по ящикам.  

• Утверждается, что если мощность множества дублива больше или равна 70, то по принципу Дирихле, какие-то две последовательности попадут в один ящик и аннигилируют.  

• В видео также обсуждается нерешенная задача о том, можно ли рассадить 30 школьников по двум аудиториям так, чтобы в каждой аудитории был хотя бы один школьник из каждой пятерки сильнейших по каждому из 15 предметов.  

• Утверждается, что при любом раскладе, можно так рассадить школьников, чтобы в каждой аудитории были представители из всех пятерок.  

• В видео обсуждается проблема рассадок, при которых специалисты по комбинаторике сидят в одной аудитории.  

• Автор предлагает решение, которое заключается в том, чтобы разделить специалистов на две группы и рассадить их в разные аудитории.  

• Автор объясняет, что круги - это множество рассадок, которые вредят, то есть не соответствуют желаемым.  

• Он также объясняет, что мощность объединения этих кругов не больше, чем сумма их мощностей.  

• Автор утверждает, что общее число рассадок строго больше, чем число тех, которые вредят.  

• Он также объясняет, что есть рассадки, при которых все хорошо, и все сидят как надо.