Доказать что сумма сочетаний равна 2 n

Наука собственными силами

Сочетания

Свойства сочетаний

Числа C k n обладают целым рядом замечательных свойств. Эти свойства можно доказать по-разному. Можно доказывать алгебраически – прямо воспользоваться формулой (8)

Но можно эти же свойства доказывать и чисто комбинаторными соображениями.

Свойствo 1

В формулу для C k n верхним индексом подставим (n-k). Получим

Однако намного изящнее комбинаторное доказательство:

Что значит «выбрать n-k предметов из n»? Это все равно что «указать k предметов, которые не будут выбраны». Т.е. выбрать n-k предметов из n можно столькими же способами, что и k предметов.

Этим свойством удобно пользоваться, когда верхний индекс ненамного меньше нижнего. Сравните, к примеру, два способа вычисления C 5 7:

напрямую используя формулу (8):

или применяя формулу (9):
Не правда ли, второй проще?

Свойство 2

Запишем правую часть, используя формулу (8) для числа сочетаний:

Приведем к общему знаменателю, равному n!∙(n-k)!:

Однако и здесь комбинаторное доказательство намного красивее:

Все сочетания из n по k (их количество равно C k n ) можно разбить на два класса: содержащие элемент под номером n и не содержащие его.

Выбрать из n элементов k штук, включая n-й – это все равно, что из оставшихся n-1 элементов выбрать k-1. Это можно сделать C k-1 n-1 способами.

Если же n-й элемент в сочетание не входит, то все k элементов нужно выбирать из оставшихся n-1 элементов. Это можно сделать C k n-1 способами.

Так как каждое сочетание из n по k входит или в один, или в другой класс, но не в оба сразу, можно применить правило суммы, и получить доказываемое равенство:

(10).

Свойство 3

В левой части равенства стоит количество всех сочетаний из n элементов (независимо от числа элементов в самих сочетаниях).

О каждом элементе мы можем принять решение: брать его в сочетание или не брать. Т.е. для каждого элемента есть два варианта решения: «да» и «нет». Будем для обозначения того или иного сочетания класть на каждый элемент монетку, причем «да» будем обозначать орлом, а «нет» – решкой. Таким образом, каждому сочетанию из n элементов будет соответствовать ряд из n монет. В разделе «Основные законы комбинаторики» мы доказали, что для n монет возможны 2n вариантов распределения орлов и решек. Поэтому количество всех сочетаний из n элементов равно 2n, что и требовалось доказать.
Перейти к следующей главе →

Источник

Доказать что сумма сочетаний равна 2 n

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

Для формулирования и решения задач по комбинаторике используют следующие конфигурации: перестановки, размещения, сочетания.

Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Перестановкой из n элементов называется такой набор элементов множества, которые отличаются от исходного лишь порядком элементов. Обычно перестановка обозначается как P n и рассчитывается по формуле:

Найти число перестановок множества, состоящего из трех элементов: A, B, C.

Согласно формуле, количество перестановок будет равно 3! = 6.

Действительно, это наборы (ABC),(ACB),(BAC),(BCA),(CAB),(CBA).

Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Размещением из n элементов по k будет называться упорядоченное подмножество из k не повторяющихся элементов выбранные из множества, состоящего изn элементов. Обычно перестановка обозначается как A n k и рассчитывается по формуле:

Найти число размещений множества, состоящего из четырех элементов: A, B, C, D по два, т.е. сколько различных размещений по два элемента можно составить из указанного множества.

Согласно формуле, количество размещений будет равно 4! / (4-2)! = 24 / 2 = 12.

Действительно, это наборы (AB),(BA),(AC),(CA),(AD),(DA),(BC),(CB),(BD),(DB),(CD),(DC).

Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Сочетанием из n элементов по k будет называться подмножество из k не повторяющихся элементов выбранные из множества, состоящего из n элементов. Подмножества, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. Обычно сочетание обозначается как С n k и рассчитывается по формуле:

Найти число сочетаний множества, состоящего из четырех элементов: A, B, C, D по два.

Согласно формуле, количество сочетаний будет равно 4! / 2!(4-2)! = 24 / 4 = 6.

Действительно, это наборы (AB),(AC),(AD),(BC),(BD),(CD).

Сочетание играет важную роль в математике. В частности, он используется в биноме Ньютона.

Источник

Доказательство формулы бинома Ньютона.

Формула бинома Ньютона для натуральных n имеет вид , где — биномиальные коэффициенты, представляющие из себя сочетания из n по k, k=0,1,2,…,n, а «!» – это знак факториала).

К примеру, известная формула сокращенного умножения «квадрат суммы» вида есть частный случай бинома Ньютона при n=2.

Треугольник Паскаля.

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

Треугольник Паскаля чаще встречается в виде значений коэффициентов бинома Ньютона для натуральных n:

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

Свойства биномиальных коэффициентов.

Для коэффициентов бинома Ньютона справедливы следующие свойства:

· коэффициенты, равноудаленные от начала и конца разложения, равны между собой , p=0,1,2,…,n;

· ;

· сумма биномиальных коэффициентов равна числу 2, возведенному в степень, равную показателю степени бинома Ньютона: ;

· сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах.

Первые два свойства являются свойствами числа сочетаний.

Доказательство формулы бинома Ньютона.

Приведем доказательство формулы бинома Ньютона, то есть докажем справедливость равенства .

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

1. Проверим справедливость разложения для какого-нибудь n, допустим, для n = 3.

Получили верное равенство.

2. Предположим, что равенство верно для n-1, то есть, что справедливо равенство .

3. Докажем, что верно равенство , основываясь на предположении второго пункта.

Поехали!

Раскрываем скобки

Группируем слагаемые

Так как и , то ; так как и , то ; более того, используя свойство сочетаний , получим

Подставив эти результаты в полученное выше равенство

придем к формуле бинома Ньютона .

Этим доказана формула бинома Ньютона.

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

Их общее количество обозначается: и равно произведению:

Вот эти размещения: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.

Их общее количество обозначается и может быть вычислено по формуле:

Из этой формулы ясно, что

В соответствии с этим определением получим:

Общее число сочетаний можно вычислить, пользуясь и другим выражением:

Эти сочетания: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.

Бином Ньютона. Это формула, представляющая выражение ( a + b ) n при положительном целом n в виде многочлена:

Заметим, что сумма показателей степеней для a и b постоянна и равна n.

Числа называются биномиальными коэффициентами.

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

мы можем получить результат моментально, используя таблицу:

Свойства биномиальных коэффициентов.

Для доказательства достаточно положить a = b = 1. Тогда в правой части разложения бинома Ньютона мы будем иметь сумму биномиальных коэффициентов, а слева:

2. Коэффициенты членов, равноудалённых от концов разложения, равны.

Это свойство следует из соотношения:

3. Сумма коэффициентов чётных членов разложения равна сумме коэффициентов нечётных членов разложения; каждая из них равна

Источник

Доказать что сумма сочетаний равна 2 n

Решение 1

а) Пусть нам из r человек надо выбрать комиссию в составе m человек, а внутри неё – штаб из k человек. Если сначала выбрать членов комиссии, а из них выбирать штаб, то подсчёт числа способов это сделать приведёт по правилу произведения к левой части равенства. Но можно поступить по-другому: сначала выбрать штаб, а потом из оставшихся r – k человек выбрать m – k «простых» членов комиссии. Тогда подсчёт приведёт к правой части равенства.

б) Пусть есть n + 1 шар: один – чёрный, а остальные – белые. Тогда число способов выбрать m + 1 белый шар равно а число способов выбрать m белых и один чёрный шар равно В сумме получим общее число способов выбрать m + 1 шар из n + 1, то есть

в) Достаточно в г) взять k = m = n.

г) Пусть есть набор из m чёрных и n белых шаров. При каждом p от 0 до k число способов выбрать p белых и k – p чёрных шаров равно Складывая, получим общее число способов выбрать k шаров из m + n, то есть

Решение 2

б) В равенстве (1 + x) n+1 = (1 + x) n (1 + x) одночлен в левой части получается как сумма одночленов и

г) В равенстве (1 + x) m+n = (1 + x) n (1 + x) m одночлен в левой части получается как сумма одночленов

д) Перепишем формулу п. б) в виде Применяя её последовательно, получим На последнем шаге надо заметить, что

Решение 3

б) – количество путей, ведущих из вершины треугольника Паскаля к числу, стоящему на (m+1)-м месте в (n+1)-й строке. Каждый такой путь проходит либо через m-е, либо через (m+1)-е число m-й строки и в далее за один «ход» попадает в нужное место. Путей второго типа – а первого –

в) – количество путей, ведущих из вершины треугольника Паскаля к числу, стоящему на n-м месте в 2n-й строке. Каждый такой путь проходит ровно через одно число n-й строки. При этом количество путей, проходящих через число, стоящее на k-м месте, равно (к указанной точке ведут путей, а из неё до нужного места – столько же).

г) – количество путей, ведущих из вершины треугольника Паскаля к числу, стоящему на k-м месте в (m+n)-й строке. Каждый такой путь проходит ровно через одно число n-й строки. При этом количество путей, проходящих через число, стоящее на l-м месте, равно (к указанной точке ведут путей, а из неё до нужного места – путей).

Замечания

1. Пункт б) также следует из построения треугольника Паскаля.

3. В задаче 30 из главы 11 книги «Ленинградские математические кружки» предлагался только пункт в).

Источники и прецеденты использования

Источник

Доказательство формулы (7)

Некоторые сведения из комбинаторики

1. Размещения. Пусть рассматривается совокупность из n упорядоченных, т.е. пронумерованных, элементов (a₁; a₂;…a_n). Будет составлять из этих n элементов всевозможные упорядоченные группы по m элементов в каждой группе, где m – любое натуральное число, не превосходящее n. Эти группы будем считать различными, если они отличаются друг от друга хотя бы одним элементом или даже только порядком следования элементов в группе (у каждого элемента в упорядоченной группе есть свое учитываемое место). Такие группы называются размещениями из n элементов по m элементов в каждом размещении. Их общее число обозначается символом , и находится оно по формуле:

= (7)

Напомним, что выражение n! называется эн–факториал, и определяется оно так:

1) Составим сначала все возможные размещения из n элементов (a₁; a₂;…a_n) по одному элементу в каждом размещении и подсчитаем их число . Эти размещения – просто отдельно взятые элементы a₁; a₂;…a_n. Их количество равно n. То есть

=n (9)

2) Составим теперь все возможные размещения из n элементов по два элемента в каждом размещении и подсчитаем их число . Эти размещения тоже очевидны:

=n(n-1) (11)

3) Составим все возможные размещения из n элементов по три элемента в каждом размещении и подсчитаем их число . Эти размещения получим, если возьмем за основу все возможные размещения (10) по два элемента и добавим по очереди справа к каждому из них любой из оставшихся n-2 элементов. Таким образом, из каждого размещения (10) по два элемента можно образовать n-2 размещения по три элемента. Например, из одного размещение a₁ a_{2 ,} содержащего два элемента, можно образовать следующее n-2 размещений по три элемента:

=· (n-2)=n(n-1)(n-2) (13)

= · (n-3)=n(n-1)(n-2)(n-3) (14)

= · (n-4)=n(n-1)(n-2)(n-3)(n-4)

= n(n-1)(n-2)(n-3)…..(n-m+1) (15)

Итак, мы получили формулу для при произвольном m (m=1,2,…n).

Преобразуем ее к более удобному виду. Для этого домножим и разделим выражение (15) на убывающие недостающие множители (n-m)(n-m-1)····3·2·1 так, чтобы последний множитель в (15) стал 1:

==

==

Формула (7) доказана.

Для примера подсчитаем общее количество всех возможныхразмещений из трех элементов (a₁; a₂; a₃) по одному, по два и по три элемента. Причем сделаем это и непосредственно, составив все эти размещения и пересчитав их, и по формуле (1):

=3; =6; =6 (17)

Эти же результаты дает и формула (7):

==; =; = (18)

2. Перестановки. Перестановками из данной совокупности n элементов (a₁; a₂;…a_n) называются различным образом упорядоченные (по разному переставленные) комбинации всех этих элементов. Их общее количество обозначается символом . Так как перестановки – это по сути размещения из n элементов по n элементов в каждом размещении, то

(19)

= (20)

Доказательство формулы (20)

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

, и значит (21)

Для примера подсчитаем общее количество всех возможных сочетаний из трех элементов (a₁; a₂; a₃) по одному, по два и по три элемента. Причем сделаем это и непосредственно, составив все эти сочетания и пересчитав их, и по формуле (20):

(22)

Эти же результаты дает и формула (20):

; (23)

Кстати, комбинации в (17) и в (22) наглядно демонстрируют разницу между размещениями и сочетаниями.

Выводя формулы (7), (19) и (20) для общего числа размещений, перестановок и сочетаний, мы полагали, что в каждом из указанных соединений любой из элементов совокупности (а_1; а_{2; …..}а_n) может встретиться только один раз. То есть повторять в них элементы нельзя. Если же повторять их всё же можно, то мы придём к размещениям, перестановкам и сочетаниям с повторениями.

Впрочем, мы могли подсчитать это число и иначе. Составляя любое размещение из двух элементов, на первое место в таком размещении можно поставить любой из данных трёх элементов (три варианта). На второе место – тоже любой из трёх элементов (тоже три варианта). Комбинируя каждый элемент, стоящий на первом месте, с каждым элементом, стоящим на втором месте, получим 3 2 =9 всех возможных комбинаций. То есть =3 2 =9.

А теперь легко понять, что если всех элементов не три, а n, и из них составляются все возможные размещения с повторениями по m элементов в каждом размещении, то их общее число найдётся по формуле:

=n m (24)

5. Сочетания с повторениями. Опять начнём с частного случая. А именно, подсчитаем – общее число всех возможных сочетаний с повторениями из трёх элементов (а_1; а_2; а₃) по два элемента в каждом сочетании. Этих сочетаний, очевидно, будет 6 – те 3, которые представлены в (22) и в которых оба элемента разные, и ещё три сочетания а₁а_1; а₂а_2; а₃а₃ с повторяющимися элементами. То есть =6=. И вообще, можно доказать, что

(25)

6. Перестановки с повторениями.Пусть среди элементов (а_1; а_{2; …..}а_n) содержится лишь k различных элементов (k 2 =900.

Аналогично различных троек цифр будет:

=10 3 =1000.

(впрочем, это и так очевидно). Комбинируя (соединяя) теперь каждую пару букв с каждой тройкой цифр, получим искомое общее число N различных автомобильных номеров:

N= 900 · 1000 = 900000.

Пример 6. Имеются две колоды по 36 карт. Из каждой колоды вынимаются по одной карте. Сколько различных пар карт может быть при этом образовано?

Решение.В образовываемых парах карт порядок их следования, очевидно, не важен. Поэтому эти пары – различные сочетания из 36 карт. По условию, среди этих пар могут оказаться n пары с одинаковыми картами. То есть образованные пары карт – это сочетания с повторениями. А значит, их общее число:

Пример 7. Сколько всех возможных перестановок букв можно сделать в слове «математика»?

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

Решение. – число всех возможных способов выбора пяти различных мест из имеющихся восьми. На этих местах 5 человек можно рассадить числом способов = 5! В итоге искомое число способов

Пример 9. Из колоды в 36 карт наудачу вынимаются две карты. Какова вероятность того, что ими окажется два туза (любых)?

Решение. В данной задаче испытание – это вынимание из колоды наудачу двух карт, а событие А – вынимание двух тузов. Возможных исходов в испытании столько, сколько всего пар карт можно составить. Таких пар будет, очевидно, n = = 630. Все эти 630 возможных исходов испытания, очевидно, равновозможны. А число m исходов, благоприятствующих событию А – это, очевидно, число всех пар из четырёх тузов, то есть m = = 6. Поэтому по классической формуле (3) получаем:

Пример 10. Ребёнок играет двумя карточками с буквой «М» и двумя карточками с буквой «А», выкладывая их в линию. Какова вероятность того, что у него получится слово «МАМА»?

Это – число n всех возможных исходов испытания, причём исходов равновозможных. А число m исходов, благоприятствующих событию А, равно 1: m=1 (перестановка «МАМА»). В итоге по классической формуле (3) получаем:

Пример 11. Из десяти билетов выигрышными являются два. Определить вероятность того, что среди наудачу взятых пяти билетов: а) только один выигрышный; б) оба выигрышные.

Решение. Здесь испытание – выбор пяти билетов из десяти. Всего существует способов выбрать 5 билетов из 10. Следовательно, число n всех возможных исходов испытания и в задаче а), и в задаче б) одинаково и равно . Причём все эти исходы равновозможны.

В задаче а) благоприятный исход испытания состоит в том, что из двух выигрышных билетов будет выбран один (это можно сделать двумя способами), а из восьми невыигрышных будут выбраны четыре (это можно сделать способами). Таким образом, общее число всех благоприятных исходов равно 2·, а значит, вероятность события А, состоящего в том, что среди пяти отобранных билетов окажется лишь один выигрышный, по классической формуле (3) равна:

В задаче б) благоприятный исход испытания состоит в том, что из двух выигрышных билетов будут взяты оба (их можно взять одним способом) и ещё три билета будут взяты невыигрышных (их можно взять способами). Число благоприятных исходов, таким образом равно , а вероятность события В, состоящего в том, что среди пяти отобранных билетов окажется два выигрышных, по классической формуле равна

Пример 12. На книжную полку в произвольном порядке выставлены 5 книг. Какова вероятность того, что некоторые две из них, составляющие двухтомник, окажутся на полке рядом?

Решение. В данной задаче испытание – это установка на полку в произвольном порядке пяти книг. А событие А – то, что книги двухтомника окажутся рядом.

Всех возможных исходов испытания, очевидно, столько, сколько существует перестановок из пяти книг. То есть их = 5! = 120. Благоприятствующими событию А будут те из них, когда книги двухтомника стоят рядом.

Для начала подсчитаем число тех благоприятствующих исходов, когда книги двухтомника стоят на первых двух местах, причём первый том стоит на первом месте, а второй на втором. Так как последние три книги могут быть установлены произвольно, то таких исходов будет =3! = 6. Меняя местами книги двухтомника, получим ещё 6 благоприятствующих исходов. Таким образом, если книги двухтомника занимают на полке первые два места, то всего соответствующих благоприятствующих исходов (перестановок книг) оказывается 2·= 12. Но благоприятствующими событию А исходами будут и те, при которых книги двухтомника стоят на 2-3, 3-4, 4-5 местах. Итого всех таких исходов оказывается 12·4=48. А тогда по классической формуле (3) получаем:

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Источник