Подмножества по k элементов конечного множества s из n элементов в которых каждый элемент

1.1. Основные понятия и определения

Любое понятие дискретной математики можно определить с помощью понятия множества. Для самого же множества не существует формального определения, считается, что это понятие первичное и не определяется. Говорят, что множество есть объединение различных объектов. Однако, понятие “объединение” и “объекты” остаются неопределяемыми.

Объекты, образующие множество, называются его элементами. Если элемент m принадлежит множеству S, то используют запись mS, в противном случае – запись mS.

Множество, содержащее конечное число элементов, называется конечным. Если же множество не содержит ни одного элемента, то оно называется пустым и обозначается .

Число элементов конечного множества S называется его мощностью и обозначается |S|. 1

Конечное множество S будем задавать списком его элементов 2 :

S=<s₁,s₂,…,s_n>, где s₁,s₂,…,s_n – элементы S (обязательно различные).

Введем понятие мультимножества. Мультимножество есть объединение не обязательно различных объектов. Его можно считать множеством, в котором каждому элементу поставлено в соответствие 3 положительное целое число, называемое кратностью.

Конечное мультимножество S будем записывать в следующем виде:

Здесь все s_i различны и k_i – кратность элемента s_i. Тогда мощность S равна .

Теперь рассмотрим некоторые из комбинаторных объектов.

Подмножества. Множество M называется подмножеством множества S (обозначение МS либо SМ; читается М входит в S, S содержит М) тогда и только тогда, когда любой элемент множества М принадлежит множеству S.

Теорема. Число подмножеств n-элементного множества S равно 2 n .

Доказательство. Поставим в соответствие каждому подмножеству M множества S двоичный набор длины n по следующему правилу: s_iМ, если и только если i-й разряд равен единице. Число двоичных наборов длины n, согласно правилу произведения, равно 22…2=2 n . Следовательно, число всех подмножеств n-элементного множества равно 2 n .

Перестановки. Перестановкой называется расположение элементов множества в определенном порядке.

Теорема. Число перестановок n-элементного множества S, т.е. число способов его упорядочивания выражается формулой P_n=n!.

Символом n! (читается n-факториал) обозначается произведение натуральных чисел от 1 до n: n!=12. n. Считается, что 0!=1.

Доказательство. Будем последовательно выбирать элементы множества S и располагать их в определенном порядке на n местах. На первое место можно поставить любой из n элементов. После того, как заполнено первое место, на второе место можно поставить любой из оставшихся n-1 элементов и т.д. Тогда по правилу произведения все n мест можно заполнить n(п-1)(п-2). 21=n! способами. Следо­вательно, n-элементное множество можно упорядочить n! способами.

Размещения. Упорядоченные k-элементные подмножества множества из n элементов называются размещениями из n элементов по k.

Теорема. Число размещений из n по k определяется формулой:

.

Доказательство. Будем последовательно выбирать k-элементов из n-элементного множества, и располагать их в определенном порядке на k местах. На первое место можно поставить любой из n элементов, затем на второе — любой из n-1 оставшихся и т.д. По правилу произ­ведения имеем

.

Сочетания. Сочетанием из n элементов по k называется k-элементное подмножество множества из n элементов.

Теорема. Число сочетаний из n элементов по k выражается следу­ющей формулой:

.

Доказательство. Изn-элементного множества можно образоватьразличных упорядоченныхk-элементных подмножеств. Каждоеk-элементное подмножество может быть упорядоченоР_kспособами. Тогда число сочетаний изnпоk -число неупорядоченныхk-элементных подмножествn-элементного множества будет равно

.

Для числа сочетания справедливы равенства

,

,

.

Последнее свойство вытекает из теоремы о числе подмножеств конечного множества (объясните почему).

Перестановки с повторениями. Перестановкой с повторениями называется расположение элементов мультимножества в определенном порядке.

Теорема. Число перестановок с повторениями для мультимножествавыражается формулой

,

где .

Доказательство 1.Рассмотрим одну перестановку мультимножества и заменим в ней все одинаковые элементы разными. Тогда, число различных перестановок, которые можно составить из рассматриваемой перестановки, равно k₁!k₂!…k_m!. Проделав это для каждой перестановки, получимn! перестановок. Следовательно,

Число C_n(k₁,k₂,…,k_m) называется полиномиальным коэффициентом. Приведем еще одно доказательство данной теоремы.

Доказательство 2. Для упорядочивания мультимножества необходимо из n мест выбрать k₁ мест для элемента s₁, что можно сделать способами, затем изn—k₁ оставшиеся мест выбрать k₂ мест для элемента s₂, что можно сделать способами и т.д. Тогда число способов упорядочивания мультимножестваS по правилу произведения равно (напомнив, что 0!=1)

.

Сочетания с повторениями. Сочетаниями из m элементов по n элементов с повторениями называются группы, содержащие n элементов, причем каждая элемент принадлежит к одному из m типов.

Например, из трех элементов (m=3) a, b, c можно составить такие сочетания по два с повторениями: aа, ab, ас, bb, bc, cc.

Теорема. Число различных сочетаний из m элементов по n с повторениями равно

.

Доказательство. Каждое сочетание полностью определяется, если указать, сколько элементов каждого из m типов в него входит. Поставим в соответствие каждому сочетанию последовательность нулей и единиц, составленную по следующему правилу: ставим подряд столько единиц, сколько элементов первого типа входит в сочетание, далее ставим нуль, и после него пишем столько единиц, сколько элементов второго типа содержит это сочетание и т.д. Например, написанным выше сочетаниям из трех букв по две будут соответствовать такие последовательности:

Подмножества по k элементов конечного множества s из n элементов в которых каждый элемент

Статья появилась как результат слегка юмористического переосмысления результатов работы над задачами для олимпиад по программированию.

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

• включить ЭВМ;
• решить задачу;
• выключить ЭВМ.

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

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

Если второй случай порождает целый букет дисциплин и подходов, связанных с оптимизацией — от линейного математического программирования и численных методов до генетических самообучающихся алгоритмов и многокритериальной оценки релевантности текста запросу, то первый класс алгоритмов гораздо более компактен и изучен.

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

1. генерация k-элементных подмножеств множества, состоящего из n элементов, где n>k; сюда же относится задача получения различных сочетаний по k элементов из n;
2. если мощность k искомого подмножества неизвестна, требуется генерация всех подмножеств данного множества из n элементов;
3. наконец, если ищется не подможество, а лишь порядковая конфигурация элементов, возникает задача о различных перестановках элементов n-элементного множества.

Рассмотрим каждый из этих классов задач.

1. Генерация k-элементных подмножеств

В комбинаторике количество различных сочетаний из n элементов по k обозначается C_n k и считается по хорошо известной формуле

При этом для фиксированного n выполняется соотношение C_n 1 = C_n n-1 = n, а максимального значения число сочетаний достигает при k=n/2. Как правило, генерацию k-элементных подмножеств проводят в «естественном» лексикографическом порядке, что не приводит к усложнению или увеличению вычислительной трудоемкости.

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

Взяв пример с суммой чисел, рассмотренный выше, напишем соответствующее решение.

Дан целочисленный массив A размерностью N и число M. Найти такое множество элементов A[i1],A[i2]. A[ik], что 1<=i1<i2<i3<. <ik<=N и A[i1]+A[i2]+. +A[ik]=M.

В этом листинге существенно используется умение процессора быстро работать с двоичными числами. Так, операция A shl B, означающая сдвиг двоичного представления операнда A на B бит влево, соответствует B-кратному умножению числа A на 2, выполняемому с минимальными вычислительными затратами. Аналогично, операция A shr B сдвигает операнд A на B бит вправо, производя соответствующее число раз целочисленное деление на 2. Увы, платой за эффективность становится ограничение диапазона обрабатываемых чисел. Тип данных longint, на который отводится 4 байта или 32 бита оперативной памяти, позволяет вводить значение N, не превышающее 31 (2 31 — предельное значение для longint, т.к. один старший бит используется под знак). При этом, уже для n=30 и m=200 время решения становится заметным — несколько секунд. Но на самом деле, перебор всех подмножеств у множеств большей размерности едва ли актуален — независимо от вычислительной мощности процессора на это потребуется значительное время.

Тем не менее, приведем для сравнения вариант программы, снимающей ограничение на размерность множества. Здесь в массиве B, длина которого соответствует количеству элементов N исходного множества, будет храниться двоичное представление текущего числа. Логическая переменная flag становится истинной тогда, когда прибавить единицу к текущему числу уже невозможно, то есть, достигнуто окончание перебора.

За некоторое время (не столь уж малое, несколько часов в фоновом режиме) эта программа нашла решение для N=40 и M=800. Для N=50 и M=1200, думаю, жизни компьютера бы не хватило 🙂

Из теории Вы наверняка помните, что глубокие рекурсии чреваты переполнением стека. Но подпрограмма plus1 и не обязана быть рекурсивной. Вот ее не-рекурсивный вариант:

Цифры двоичных чисел в программах subsets2 занумерованы слева направо, поэтому рассмотрение начинается не с первой цифры, а с последней. Ранее мы нумеровали цифры справа налево, что соответствовало обратному порядку рассмотрения подмножеств. Теоретически это различие несущественно, но оно может привести к тому, что что найденные решения будут различными. При желании можно устранить расхождение, поставив в соответствие последнему элементу массива B первый элемент массива A, предпоследнему — второй и т. д. Второй вариант — переписать процедуру plus1 так, чтобы нумерация цифр поменялась на противоположную.

3. Генерация всех перестановок множества из n элементов

Легко подсчитать, что n элементов могут быть переставлены между собой 1*2*. *n=n! способами. Действительно, на первом месте в перестановке может стоять любой из n элементов массива, после того, как на первом месте зафиксирован какой-либо элемент, на втором месте может стоять любой из n-1 оставшихся элементов и т.д.

1. Ищется такой элемент в массиве индексов P, который меньше стоящего за ним элемента, то есть, существует возможность увеличения данного индекса. Необходимо найти максимальный из таких элементов, что легко достигается при просмотре массива P справа налево — тогда первый найденный подходящий элемент и будет искомым.
2. Найденный элемент p[i] меняется местами с минимальным из элементов, больших p[i] и находящихся правее его.
3. элементы p[i+1], p[i+2], p[i+3], . p[n] переставляются в обратном порядке, то есть меняются местами p[i+1] и p[n], p[i+2] и p[n-1] и т.д.

Описанные шаги дают одну перестановку, а генерация перестановок заканчивается, когда на первом шаге искомая пара индексов p[i] и p[i+1] не будет найдена, что соответствует обратному порядку индексов n, n-1, . 2, 1. Теперь программа.

Для n=10 Вы увидите не так уж мало перестановок (10!=3 628 800) 🙂 Разумеется, львиная доля процессорного времени при этом уйдет на вывод. Но об этих проблемах мы еще поговорим далее, а сейчас рассмотрим рекурсивный вариант программы генерирования всех перестановок в лексикографическом порядке.

Параметром i процедуры Permutations («перестановки») служит то место в массиве p, начиная с которого должны быть получены все перестановки правой части этого массива. Идея рекурсии состоит в том, что на i-ом месте должны побывать все элементы массива p с i-го по n-ый включительно и для каждого из них должны быть получены все перестановки остальных элементов, начиная с (i+1)-го места в лексикографическом порядке. После получения последней из перестановок, начиная с (i+1)-го места, порядок элементов должен быть восстановлен (для этого используется процедура циклического сдвига Sdvig).

Конечно же, при решении реальных задач наибольшую сложность будет представлять как раз анализ каждой из перестановок (у нас он заменен ее выводом на экран), однако, умение правильно и быстро их генерировать (плюс навык их увидеть в условии задачи) также не будут лишними. Попробуйте, например, по прочтении статьи решить следующее:
Линейный кроссворд представляет собой цепочку слов, в которой несколько символов в конце одного слова могут являться началом следующего. Для заданного набора слов написать программу составления такой цепочки минимальной длины. Более двух слов одновременно пересекаться не могут.
Пример:
РАСИСТ МАТРАС НАПАЛМ ИСТИНА АЛМАЗ -> МАТРАСИСТИНАПАЛМАЗ

Впрочем, если внимательно поискать по сайту, решение этой и еще ряда олимпиадных задач Вы найдете 🙂 Я же в завершении статьи хочу обнародовать «совершенно секретную инструкцию для служебного пользования».

4. Порядок решения олимпиадных задач.

Во-первых, большая часть олимпиад проводится по-прежнему на DOS-овских компиляторах Borland C++ 3 и Turbo Pascal 7 и отказываться от этой традиции никто не собирается — ведь люди соревнуются именно в разработке быстрых и экономичных алгоритмов, а не в умении рисовать красивые окошечки. Поэтому приведенные ниже советы относятся к этим двум популярным на этапе обучения программированию оболочкам.

Кроме того, на олимпиадах по программированию обычно предполагается, что все входные данные корректны — уточните, так ли это! Ведь всевозможные проверки корректности и учёт вырожденных случаев могут «съесть» (и обычно съедают) львиную долю времени разработки.

1. Первым делом запаситесь «универсальной» заготовкой на Паскале или Си. Вероятнее всего, от Вас потребуется написать консольную программу, читающую исходные данные из файла input.txt и выдающую результат в файл output.txt. Тем более, что жюри почти наверняка пользуется автоматизированной системой тестов, предполагающей наличие именно этих файлов. На Паскале наша заготовка могла бы выглядеть так:

Обратите внимание на все директивы компилятора, установленные в образце. Для C++ подойдет следующая заготовка:

Для Си следует внимательно проверить настройки среды:

Скопируйте эту заготовку столько раз, сколько задач предложено на олимпиаде и сразу назовите каждый файл так, как это требуется по условиям (обычно 1.pas, 2.pas и т.д.).

2. Внимательно прочитайте условие задачи, постарайтесь правильно понять, в чем она заключается, если условие или форма вывода результатов в файл не до конца понятны, лучше сразу же задать вопрос, обычно это разрешено.

3. Если с входными и выходными данными все ясно, можно описать основные глобальные переменные, заполнить процедуру Input для ввода данных, сразу же сделать их формальную проверку на допустимость. Если в условии сказано, что данные корректны или ограничены четко определенным форматом, проверку корректности следует исключить. При чтении из файла на Паскале не нужно использовать readln для чтения чисел (только для строк), а при чтении на Си нужно помнить о поведении строковых шаблонов этого языка — например, шаблон %s для ввода строки считает ее окончанием любой разделитель, в том числе и пробел.

4. После того, как данные читаются, обнулите или присвойте другие нужные начальные значения всем без исключения глобальным переменным. На этом же этапе подготовьте процедуру Output для вывода результата в такой форме, которая требуется в условии задачи. Это как поможет тестированию, так и сэкономит время на переделке «простого» вывода в «правильный». Короче говоря, на этом этапе у Вас уже есть работающая программа, которая компилируется, считывает данные и выводит «нулевые» результаты в нужном формате.

• Как проверить данные на фактическую корректность и нужно ли это делать? Если в условии ничего не сказано о корректности данных, то есть ли решение для «правильного» набора данных (например, граф связан, нет деления на ноль, все элементы массива данных различны и т.п.);
• Относится ли задача к знакомому классу или решение нужно искать «с нуля»? Как и какие комбинаторные алгоритмы применимы к поиску решения?
• Можно ли найти точное решение «на бумаге», по крайней мере, для малых размерностей данных. Что произойдет в вырожденным случае, когда все данные «нулевые»?
• Есть ли условие существования решения, по крайней мере, только необходимое или только достаточное?
• Какие тесты помогут проверить решение? Система тестов должна состоять, по крайней мере, из нескольких наборов: «вырожденный» пустой набор, полностью допустимый и корректный набор, частично корректный набор, где недопустимы только некоторые значения данных теста, полностью некорректный набор. Во всех случаях поведение программы должно быть понятным и предсказуемым.

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

7. По одной пишем и отлаживаем подготовленные подпрограммы, добиваясь, чтобы каждая из них правильно выполняла свое действие при любых входных данных — например, подпрограммы поиска максимума или сортировки не должны смутить массивы, состоящие из всех одинаковых элементов, хотя и выполнять над ними полный цикл обработки — плохое решение. Словом, следует обратить особое внимание на вырожденные случаи (может ли эта операция деления в программе стать делением на ноль? И что делать, если так?) и возможность досрочного поиска решения. При программировании циклов они не должны зацикливаться ни при каких входных данных.

8. Если эффективногo решения задачи у Вас нет, как это часто и бывает, применяйте полный перебор или простую эвристику. Если и это сложно, упростите себе задачу, отбросив мешающие условия или добейтесь, чтобы программа работала на простейших тестах (точка, отрезок, треугольник и прямоугольник вместо произвольного многоугольника, вычисление выражений только для одного действия вместо всех и т.п.) Для остальных случаев программа может выдавать любимую фразу программистов «нет решения» или генерировать нечто правдоподобное с помощью датчика случайных чисел 🙂 Особенно это срабатывает, если существует всего два варианта ответа. Часто жюри начисляет ненулевые баллы за программы, прошедшие хотя бы часть тестов, а до внимательного анализа исходника, как правило, ни у кого не доходят руки.

9. Так же поступайте с задачами, на которые не хватает времени. За последние 15-20 минут можно сделать так, чтобы они работали хотя бы для вырожденных (входные параметры — нули или единицы) и частных случаев. Например, программа вида

иногда производит на жюри лучшее впечатление, чем мог бы произвести ее исходник 🙂

10. Перед сдачей подумайте о быстродействии. Если Вы использовали отладочную печать, закомментарьте ее — львиная доля времени прогона может уйти именно на ненужный вывод на экран средствами высокого уровня! Я лично в условиях нехватки времени на комментирование решал эту проблему тем, что стазу же ставил в заготовке отладочный флаг

и всю отладочную печать писал сразу в виде

Перед сдачей мне оставалось сбросить флаг в ноль.

С другой стороны, никому не понравится, если программа долго работает «молча», создавая впечатление зависшей. Для решения проблемы можно, например, выводить через каждые 100 или 1000 шагов цикла перебора одну точку на экран.

10. Запустите исполняемый файл *.exe из среды хотя бы для одного теста, чтобы убедиться в его работоспособности. Еще раз перечитайте условие. Отправьте программу жюри. Убедитесь, что запрограммировано совсем не то, что требовалось, и, получив свои 0 баллов, спокойно идите домой 🙂

Разработать программу, которая генерирует все k-элементные подмножества множества

Разработать программу, которая генерирует все k-элементные подмножества множества из n элементов таким образом, что каждое последующее подмножество образуется из предыдущего удалением одного элемента и добавлением другого.

Если поможет, вот похожая задача:

Разработать программу, которая генерирует все k-элементные подмножества множества из n элементов в лексикографическом порядке.

Разработать программу, которая генерирует все k-элементные подмножества множества n
Разработать алгоритм генерации всех k-элементов подмножества n-элементного множества в.

Разработать программу, которая генерирует все разбиения множества 1,2. n
Помогите с последней задачей. Пожалуйста. Надо разработать программу, которая генерирует все.

Надо составить программу в Паскале, которая будет выводить на экран все подмножества множества
надо составить программу в Паскале, которая будет выводить на экран все подмножества множества <1.

Перечислить все K элементные подмножества n элементарного множества
Перечислить все K элементные подмножества n элементарного множества пример с вводом выводом

Перечислить все K элементные подмножества n элементного множества
Например: есть множество 1, 2, 3 N=3, k=2, на выводе должны получить: 1 2 1 3 2 3

Задача, сгенерировать все k-элементные подмножества множества
Нужна помощь с задачей, нужно решить с циклами или как то по другом, но не каких рекурсий тд. тп.

Перечислить все K элементные подмножества n элементарного множества
Перечислить все K элементные подмножества n элементарного множества пример и объяснение по этой.

теория-множеств — Каково максимальное количество выделенных подмножеств множества, состоящего из 2n элементов?

«Множество U содержит 2n элементов. В нём выделено k подмножеств, причём ни одно из них не является подмножеством другого. Каково может быть максимальное значение числа k? (Указание. Максимум достигается, когда все подмножества имеют по n элементов. В самом деле, представим себе, что мы начинаем с пустого множества и добавляем по одному элементу, пока не получится множество U. В ходе такого процесса может появиться не более одного выделенного множества; с другой стороны, можно подсчитать математическое ожидание числа выделенных множеств по линейности; вероятность пройти через данное множество Z ⊂ U минимальна, когда Z содержит n элементов, поскольку все множества данного размера равновероятны.)»

Может кто-нибудь помочь понять, что здесь написано?

Почему максимум достигается, когда все подмножества имеют по n элементов? Почему k не равно 2n, можно ведь просто взять все подмножества, состоящие из одного элемента?

задан 16 Апр ’16 2:36

Я пока отвечу только на последний вопрос, а потом постараюсь прокомментировать и остальное.

В Вашем примере получается k=2n, но это не максимальное значение, потому что в тексте рассматриваются все n-элементные подмножества (2n)-элементного множества, а их существенно больше, то есть $%k=C_<2n>^n$%.

@falcao точно, совсем забыл про это. Спасибо большое!

1 ответ

Думаю, что имеет смысл немного прокомментировать то решение, которое здесь было изложено. Пусть выделено $%k$% подмножеств из условия. Мы выбираем случайную перестановку $%2n$% элементов, одну из $%(2n)!$% (равновероятно). Она считается «успешной», если множество элементов некоторого её начального отрезка представляет собой одно из выделенных множеств. Ясно, что таких отрезков либо нет, либо он всего один. Тем самым, мы имеем случайную величину, принимающую значения 0 и 1. Очевидно, что её математическое ожидание не превосходит 1. Вместо этого мы можем также говорить о вероятности успеха, так как это то же самое для бернуллиевских случайных величин.

Легко понять, что если мы выделим в точности все $%n$%-элементные подмножества, то успех будет иметь место всегда, потому что набор из первых $%n$% элементов любой случайной перестановки выделен. И здесь матожидание, как и вероятность, будут равны 1. Теперь надо доказать, что это оптимальный вариант, то есть нельзя выделить более чем $%k=C_<2n>^n$% подмножеств.

Основное рассуждение такое: пусть имеется некоторое $%m$%-элементное подмножество $%Z$%. Какова вероятность, что мы через него пройдём, то есть первые $%m$% элементов случайной перестановки дадут именно $%Z$%? Можно сразу сказать, что элементами такого множества с равной вероятностью может оказаться любой из $%C_<2n>^m$% наборов, поэтому такая вероятность равна $%1/C_<2n>^m$%. К этому же выводу можно прийти и по-другому, рассматривая факториалы.

Из простейших свойств сочетаний следует, что максимум величины $%C_<2n>^m$% имеет место при $%m=n$%, то есть вероятность пройти через данное подмножество $%Z$% будет минимальна при $%m=n$%. В любом случае, она не меньше $%1/C_<2n>^n$%. И тогда, если выделено $%k$% подмножеств, то вероятность пройти через одно из них не меньше $%k/C_<2n>^n$%. Действительно, мы не можем пройти через два выделенных подмножества ни при каком испытании, то есть эти события попарно не пересекаются, и их вероятности мы суммируем.

Ввиду того, что вероятность итогового события (пройти через какое-нибудь выделенное подмножество) не превосходит единицы, мы отсюда имеем неравенство $%k\le C_<2n>^n$%, что и требовалось. Попутно это объясняет, почему мы интересовались минимальными вероятностями: чем они меньше, тем больше слагаемых мы себе можем позволить, чтобы сумма не вышла за пределы единицы.