Тема ТЕОРИЯ ЧИСЕЛ

Делимость и делители (множители) → .07 Теоретико-числовые свойства биномиальных коэффициентов

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела теория чисел

Разделы подтемы Делимость и делители (множители)

Условия про НОД и НОК

Разложение на множители, основная теорема арифметики

Количество, сумма, произведение делителей

Степени вхождения простых

Оценки для доказательства делимости

Алгоритм Евклида

Теоретико-числовые свойства биномиальных коэффициентов

Теоретико-числовые свойства чисел Фибоначчи

Целые гауссовы числа

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#34950

Докажите, что

02 12 n2 n (C n)+ (Cn)+ ...+ (Cn) =C 2n

Подсказки к задаче

Подсказка 1

Решение будем строить комбинаторно, а, значит, пора определяться, для какого множества (из скольки элементов) и какие объекты будем считать.

Подсказка 2

Правая часть чётко говорит брать 2n элементов и считать число подмножеств из n элементов. Слева же в каждом слагаемом перемножают цешки из n. Что бы это могло значить?

Подсказка 3

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

Показать доказательство

Пусть имеется множество $N$ из $n$ элементов. Тогда справа $Cn 2n$ количество его подмножеств мощности $n.$

Посмотрим теперь, что будет слева. Разделим $N$ на два непересекающихся подмножества $A$ и $B$ по $n$ элементов в каждом. В силу $k n−k Cn = Cn$ верно $k2 k n−k (Cn) =(Cn)⋅(C n ).$ Тогда $k 2 (Cn)$ количество способов выбрать в $N$ подмножество мощности $n,$ что $k$ элементов лежат в $A,$ остальные $n − k$ в $B.$ Проходясь по всем $k$ получаем всевозможные подмножества $N$ мощности $n.$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#88062

На какое самое большое натуральное число будет гарантированно делиться произведение любых шести подряд идущих натуральных чисел?

Ответ обоснуйте.

Источники: Межвед - 2024, 11.1 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

Давайте сначала попробуем найти верхнюю границу (число больше которого искомое точно быть не может)

Подсказка 2

Теперь осталось доказать что (n + 1)(n + 2)...(n + 6) делится на 720 для любого натурального n. Давайте вспомним сочетания из комбинаторики

Подсказка 3

Действительно,

Показать ответ и решение

Поскольку произведение первых 6 натуральных чисел равно $6!= 720,$ то искомое число не больше $720.$

Осталось доказать, что произведение любых подряд идущих 6 натуральных чисел $n+ 1,n +2,...,n+ 6$ делится на $720$ . Поделим:

(n +1)(n +2)...(n+ 6) (n +6)! 6 --------6!--------= -6!n!--= Cn+6

и получим натуральное число способов выбрать шестёрку из $n+ 6$ элементов. Действительно, делится.

Ответ: 720

Ошибка.
Попробуйте повторить позже

Задача 3#89087

Докажите, что

0 2 4 2[n2] n−1 C n+ Cn+ Cn+ ...+ Cn = 2

Подсказки к задаче

Подсказка 1

Хотим построить комбинаторное решение. Надо определиться, из скольких элементов множество мы будем рассматривать и какие объекты считать.

Подсказка 2

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

Подсказка 3

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

Показать доказательство

Пусть имеется множество $N$ из $n$ элементов.

Поймём что слева слагаемое $2k Cn$ это количество подмножеств $N$ мощности $2k,$ а вся сумма тогда равна количеству подмножеств $N,$ содержащих чётное число элементов.

Теперь посчитаем число этих же объектов так: выделим в $N$ элемент $A,$ тогда для каждого подмножества $M$ из оставшегося числа элементов, либо $M$ содержит чётное число элементов, либо $M$ в объединении с $A$ содержит чётное число элементов. Причём таким образом рассмотрены всевозможные чётные подмножества, а значит их $n−1 2 .$

Ошибка.
Попробуйте повторить позже

Задача 4#89088

Докажите тождество

1 2 3 n n− 1 Cn+ 2Cn+ 3C n+ ...+nC n = n2

Подсказки к задаче

Подсказка 1

Нетрудно понять, какое множество хотим рассматривать (из скольки элементов). Вопрос в том, что за объекты будем считать.

Подсказка 2

Справа непонятно совсем, поэтому давайте думать что за цешка из n по k, умноженная на k.

Подсказка 3

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

Показать доказательство

Пусть имеется $n$ школьников, из которых требуется выбрать дежурного и группу помощников для уборки (в группе помимо дежурного как ни странно может никого не быть).

Слагаемое слева $k kCn$ означает число способов выбрать группу из $k$ школьников, а затем дежурного в ней. Сложив по всем $k$ получаем число всевозможных групп с дежурным.

Можно же сначала $n$ способами выбрать дежурного, затем оставшихся распределить в группу или нет. Получаем справа также посчитано число искомых объектов.

Ошибка.
Попробуйте повторить позже

Задача 5#89089

Для $n> 2$ докажите тождество

1 2 2 2 32 n−12 2 n− 2 1⋅(n− 1)⋅(Cn) +2 ⋅(n− 2)⋅(Cn) + 3⋅(n − 3)⋅(Cn)+ ...+ (n− 1)⋅1⋅(Cn ) =n ⋅C2n−2

Подсказки к задаче

Подсказка 1

Выглядит, конечно, мощно давайте разбираться, что у нас считается слева. Что могут значит квадраты цешек?

Подсказка 2

Действительно, квадраты намекают на деление на две группы по n, коэффициенты перед цешками на выбор одного из них. Давайте совмещать идеи.

Подсказка 3

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

Показать доказательство

Пусть имеются два класса $A$ и $B$ по $n$ школьников, из которых требуется выбрать по дежурному, а также включающую их группу из $n$ активистов.

В силу $k n−k Cn =C n$ верно $k 2 k n−k k⋅(n− k)⋅(Cn) = k⋅Cn⋅(n− k)⋅Cn .$

Слагаемое слева $k 2 k⋅(n− k)⋅(Cn)$ количество способов выбрать $n$ активистов из которых в $A$ классе $k$ школьников, один из которых дежурный, остальные в $B$ классе с одним дежурным в нём. Сложив по всем $k$ получаем число всевозможных групп из $n$ активистов, в которых по одному дежурному в каждом из классов.

Можно же сначала $2 n$ способами выбрать в группу активистов по дежурному с классов, а затем из остальных школьников добрать группу. Получаем справа также посчитано число искомых объектов.

Ошибка.
Попробуйте повторить позже

Задача 6#89090

Даны натуральные $n,m$ такие, что $m < n.$ Докажите, что

0 m 0 1 m 1 n m n (− 1) ⋅0 ⋅C n+(−1) ⋅1 ⋅Cn +...+ (−1) ⋅n ⋅Cn =0

Подсказки к задаче

Подсказка 1

Ищем комбинаторный смысл. Что первое приходит в голову? А вот над объектом, который будем подсчитывать стоит подумать, всё-таки плюсы/минусы весьма непонятно.

Подсказка 2

Ага, вполне логично рассмотреть множество из n элементов (пусть уж они будут детьми), и будем в слагаемых слева выбирать группу и раздавать её участникам m различных шариков. Может есть идеи для объекта?

Подсказка 3

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

Подсказка 4

Для этого можно зафиксировать детей, у которых окажутся шарики при данном распределении (это не все дети, поскольку m<n), и посмотреть на группы добираемые к ним.

Показать доказательство

Предположим, что у нас есть $n$ детей и $m$ разных шариков. И мы хотим эти шарики раздать детям (некоторые дети могут получить больше одного шарика). В левой части в слагаемом $m k k C n$ мы сначала выбираем $k$ детей, которым будем давать шарики, а затем считаем количество способов раздать выбранным $k$ детям эти шарики. То есть один способ раздачи шариков посчитан в нескольких слагаемых. Зафиксируем произвольный способ раздачи шариков. Пусть в нем ровно у $x$ детей есть хотя бы один шарик. Тогда в слагаемом $m k k Cn$ этот способ посчитан 0 раз, если $k <x$ и $k−x Cn−x$ раз, если $k ≥x$ (то есть мы к зафиксированным $x$ детям добавляем еще $k− x$ ). Таким образом, суммарно в левой части наш зафиксированный способ посчитан следующее число раз.

(− 1)xCxn−−xx+ (−1)x+1Cxn+−1x−x+ ...+ (− 1)nCnn−−xx =0

Так как сумма $ℓ Cn−x$ по всем $ℓ$ равна $n− x 2 ,$ а сумма по всем четным $ℓ$ числа $ℓ Cn−x$ равна $n−x−1 2 .$ То есть сумма по всем нечетным $ℓ$ чисел $ℓ Cn−x$ также равна $n−x−1 2 .$ Тогда знакопеременная сумма $ℓ Cn−x$ по всем $ℓ$ равна $0.$ То есть любой зафиксированный способ посчитан в левой части $0$ раз. Значит, и все выражение в левой части равно $0.$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#89091

Для каждого натурального $n$ докажите, что

n 1 n 1- n 1- n n C n + 2Cn+1+ ...+ 2kCn+k+ ...+ 2nC2n = 2

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Вот после домножения выглядит уже приличнее. Первым делом, конечно, хочется построить соответствие с всевозможными подмножествами 2n-элементного множества, но тут закопаться можно, что с левой частью совсем непонятно. Давайте добавим ещё элементик и попробуем считать какие-то более необычные объекты.

Подсказка 3

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

Показать доказательство

Сразу домножим наше тождество на $2n.$ То есть будем доказывать, что

n n n−1 n n−k n 0 n 2n 2Cn + 2 Cn+1+ ...+ 2 Cn+k+...+2 C2n = 2

Предположим, что у нас в ряд стоят $2n +1$ человек. И мы хотим выбрать из них хотя бы $n +1$ человека. Понятно, что каждому такому выбору соответствует выбор, в котором меньше $n+ 1$ человека (просто выбрать тех, кого не выбрали в первом способе). Тогда всего таких вариантов ровно $2n+1 2n 2 ∕2= 2 .$ Посчитаем требуемое количество способов по-другому. Посмотрим, где может находиться $(n+ 1)$ -ый человек (считая слева направо). Пусть он находится на $n+ k+1$ месте, где $k≥ 0.$ Тогда среди первых $n +k$ человек у нас есть ровно $n Cn+k$ способов выбрать $n$ человек. А среди оставшихся $2n +1− n− k− 1= n− k$ человек мы можем выбирать любых людей, то есть $n−k 2$ способов. Итого, если $(n +1)$ -ый по счету человек стоит на $(n+ k+ 1)$ -ом месте, то всего вариантов $n−k n 2 Cn+k.$ Сложив способы по всем $k= 0,1,2,...,n,$ получаем требуемое равенство.

Ошибка.
Попробуйте повторить позже

Задача 8#104479

Докажите тождества

k k k− 1 m k k m −k (a) Cn = Cn−1+C n− 1; (b) Cn Cm = CnCn−k

Показать доказательство

(a) Левая часть — количество способов выбрать из $n$ человек ровно $k.$ Посчитаем это по-другому. Зафиксируем одного человека. Если он в нашей группе, то остается выбрать еще $k− 1$ человека из $n− 1.$ Если он не в нашей группе, то из оставшихся $n − 1$ людей надо выбрать $k.$ Поскольку рассмотренные случаи не пересекаются, а ответы для каждого из них соответственно равны $k−1 Cn−1$ и $k Cn−1,$ то общий ответ $k k−1 Cn−1+ Cn−1.$

(b) Рассмотрим задачу: найти количество способов выбрать $m$ человек из $n$ и составить из этих $m$ человек команду из $k$ человек. Можно сначала зафиксировать $k$ человек, после чего добавить к ним еще $m − k$ из оставшихся $n− k.$ Это соответствует правой части уравнения: $k m −k Cn⋅Cn−k .$ С другой стороны, можно делать ровно то, что написано в условии: сначала выбрать $m$ человек, а затем среди них выбрать $k$ человек. Это соответствует левой части уравнения: $m k Cn ⋅Cn.$

Ошибка.
Попробуйте повторить позже

Задача 9#104480

Тождество Вандермонда. Докажите, что

k 0 k 1 k−1 k 0 Cn+m = CnCm + CnCm + ...+ CnCm

Показать доказательство

Рассмотрим следующую задачу. Пусть у нас есть группа из $m$ девочек и $n$ мальчиков. Нужно найти количество способов выбрать среди них $k$ человек. С одной стороны, это количество равно $k Cm+n.$ С другой стороны, можно воспринимать ее так: сумма количеств способов выбрать $i$ мальчиков и $k− i$ девочек. Для данного $i$ это количество равно $i k−i CnCm ,$ где $0≤ i≤k.$ Суммируем эти выражения по всем $i$ и получаем выражение в правой части.

Ошибка.
Попробуйте повторить позже

Задача 10#104481

Для каждого натурального $n$ докажите равенство

02 12 22 n 2 n−1 0⋅(Cn) + 1⋅(C n)+ 2⋅(Cn)+ ...+ n⋅(Cn) = n⋅C2n− 1

Показать доказательство

Для удобства перепишем каждое слагаемое левой части в виде $(Ci)2 = Ci ⋅Cn− i. n n n$ Рассмотрим задачу: выбрать из двух групп суммарно $n$ человек, и затем из выбранных людей первой группы назначить одного капитаном. Тогда каждое слагаемое левой части во вновь представленном виде

0 n 1 n−1 n 0 0 ⋅C nCn + 1⋅Cn⋅Cn + ...+ nCn ⋅C n

соответствует решению нашей задачи, когда в первой группе выбирается $i$ человек, а во второй $n − i,$ а сумма в точности соответствует решению задачи. Теперь посчитаем это по-другому: сначала из первой группы выбираем $1$ человека — это можно сделать $n$ способами, после чего из двух групп ( $2n− 1$ человек) выберем еще $n − 1$ человека. Тогда общий ответ $n−1 nC2n−1.$ Таким образом, тождество доказано.

Ошибка.
Попробуйте повторить позже

Задача 11#104483

Для каждого натурального $n$ докажите равенство

2 0 2 1 2 2 2 n n−2 0 ⋅Cn+ 1 ⋅Cn+ 2 ⋅Cn+ ...+ n ⋅Cn = n(n+ 1)⋅2

Показать доказательство

Рассмотрим следующую задачу: найти количество способов выбрать нескольких среди $n$ человек, и затем отдать каким-то двум из них по шарику (возможно, два шарика одному человеку). Слева в точности написан ответ на эту задачу: сначала выбирается $k$ человек, а затем для каждого из двух шариков есть $k$ возможностей. С другой стороны, можно сначала отдать два шарика, а потом в группу к этим людям добавить некоторое количество людей. Если оба шарика отданы одному человеку, то выбирается человек и еще $n − 1$ человек, количество таких объектов равно $n−1 n2 .$ Если же оба шарика отданы разным людям, то всего есть способов отдать два шарика $n(n− 1)$ (шарики отличаются). После этого нужно выбрать подмножество из $n− 2$ людей. Число таких объектов равно $n−2 n(n− 1)⋅2 .$

n(n− 1)⋅2n−2+ n2n−1 =n(n+ 1)2n−2

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#75086

Для натурального числа $n$ оказалось, что каждое из чисел $C1,C2,...,Ck− 1 n n n$ делится на $n,$ а число $Ck n$ — нет. Докажите, что $k$ — простое число.

Показать доказательство

Докажем чуть больше: что $k$ – наименьший простой делитель $n.$ Для этого обозначим через $p$ наименьший простой делитель $n.$ Ясно, что $. Cpn = n(n−1)...p(n!−p+1)⁄.. n$ так как в противном случае было бы выполнено $. (n − 1)...(n− p+ 1)..p!,$ хотя ни один из сомножителей не делится на $p.$ Таким образом, $p ≥k,$ ведь $k$ – наименьшее такое, что $k .. Cn ⁄. n.$ Теперь предположим, что $k <p.$ Так как $k$ меньше, чем наименьший простой делитель $n$ , $НОД (n,l)= 1$ для любого $l≤k$ Поэтому $НОД(n,k!)= 1,$ откуда $k n(n−1)...(n−k+1).. Cn = -----k!-----.n,$ что противоречит условию задачи. Значит $p =k,$ и утверждение задачи доказано.

Ошибка.
Попробуйте повторить позже

Задача 13#75087

Докажите, что для любого простого $p> 2$ выполнено

(2p) 2 p ≡ 2 (mod p)

Показать доказательство

Используя тождество Вандермонда для $m= n =k =p,$ получаем

(2p) (p)(p) (p)( p ) ( p )(p) (p)(p) p = 0 p + 1 p− 1 +⋅⋅⋅+ p− 1 1 + p 0

Первый и последний члены в правой части равны $1.$ Поскольку $p$ простое число, оно делит каждый биномиальный коэффициент $( ) pk$ при $1 ≤k ≤p− 1.$ Таким образом, каждое из оставшихся слагаемых делится на $p2,$ поэтому выполнено сравнение $( ) 2pp ≡2 (mod p2).$

Ошибка.
Попробуйте повторить позже

Задача 14#75088

Докажите, что для любой пары натуральных чисел $m$ и $k$ существует единственное представление

(ak) (ak−1) (at) m = k + k− 1 +...+ t

где $ak >ak−1 > ...> at ≥ t≥1.$

Показать доказательство

Сначала докажем единственность. Предположим, что $m$ — минимальное число, представляемое двумя последовательностями $a ,...,a k t$ и $bk,...,br.$ Первая позиция, в которой они различаются — это позиция $k$ (иначе $m$ было бы не наименьшим). Пусть $ak > bk.$ Тогда с помощью тождества $(n) (n−1) (n−1) k = k−1 + k$ и замечания $bk− s≥ bk−s$ для любого $s$ такого, что $k− s≥ r,$ получаем неравенства

(bk) (bk− 1) (bk − k+ 1) (bk+1) (ak) m ≤ k + k− 1 + ...+ 1 < k ≤ k ≤ m

противоречие.

Чтобы доказать существование, применим жадный алгоритм: найдем наибольшее $ak$ такое, что $( ) akk ≤ m,$ и применим тот же алгоритм с заменой $(m,k)$ на $( ) (m− akk,k− 1).$ Нам осталось убедиться, что полученная последовательность действительно уменьшается, но это следует из предположения: $( ) m < ak+k1 ,$ а значит $( ) ( ) m− akk < akk−1.$

Ошибка.
Попробуйте повторить позже

Задача 15#75089

Даны натуральные числа $1≤ k≤ n.$ Докажите, что $k$ является делителем суммы

k−∑1 ( ) n (−1)i n i=0 i

Показать доказательство

Преобразуем выражение:

k∑−1 () k∑−1 (( ) ( )) n (−1)in = n (−1)i n− 1 + n − 1 = i=0 i i=0 i i− 1 k∑−1 i(n − 1) k∑−1 i(n− 1) = ni=0(−1) i + ni=1(− 1) i− 1 = k∑−1 ( ) k∑−2 ( ) = n (−1)in − 1 − n (− 1)i n− 1 = i=0 ( i) i=0 i = n(−1)k−1 n− 1 = (nk)− 1 = k(−1)k−1k

Теперь понятно, что сумма делится на $k.$

Ошибка.
Попробуйте повторить позже

Задача 16#75090

Пусть $n$ — натуральное число. Докажите, что

n 0 0 [n∕2] 1 1 [(n−1)∕2] k k [(n−k)∕2] n n 0 C2n+1 = 2CnC n + 2C nCn−1 + ⋅⋅⋅+ 2 CnCn−k + ⋅⋅⋅+ 2 CnC0

( $k --n!-- Cn = k!(n−k)!$ — число способов выбрать $k$ предметов из $n$ без учёта порядка; $[x]$ — наибольшее целое число, не превосходящее $x.$ )

Показать доказательство

Выражение слева по определению равно количеству способов выбрать из $2n +1$ человек $n$ без учета порядка. Покажем, что этому же числу равна правая часть. Зафиксируем разбиение всех $2n +1$ людей, кроме одного, на пары. Пусть ровно из $k$ пар мы выбрали по одному человеку. Выбрать эти $k$ пар мы можем ровно $k Cn$ способами, а в самих парах $k 2$ – способами выбрать по одному человеку из пары.

Далее, нам осталось выбрать еще $n− k$ человек. Из остальных пар, в силу рассматриваемого случая, мы выбираем либо обоих людей, либо ни одного. Поэтому из оставшихся пар надо выбрать $[(n − k)∕2],$ из которых мы выберем двух людей, а в случае нечетной разности $n − k$ еще одним выбранным человеком будет тот, что остался без пары. Выбрать эти $[(n− k)∕2]$ пар можно $[(n−k)∕2] Cn−k$ способами, и это завершает выбор $n$ человек в данном случае. Все найденные выше способы перемножаются и получается в точности слагаемое $k k [(n−k)∕2] 2 CnCn−k$ из суммы выше. Рассматривая все возможные $k$ от 0 до $n,$ мы получаем в точности сумму из правой части условия.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#91944

Найдите суммы:
а) $1⋅n +2(n− 1)+ 3(n − 2)+ ...+n⋅1$
б) $Sn,k = k!⋅(n(n − 1)...(n− k+ 1))+ (2⋅3⋅...⋅(k +1))⋅((n− 1)(n− 2)...(n− k))+...+$
$+((n − k +1)(n − k +2)...⋅n)⋅(k(k− 1)⋅...⋅1).$

Подсказки к задаче

Подсказка 1, пункт а

Заметим, что нашу сумму можно записать в виде (n * n - (n-1)n) + (n(n-1) - (n-2)(n-1)) + (n(n-2) - (n-3)(n-2)) + ... + n * 1. Можно ли разбить ее на две суммы, которые удобно считать?

Подсказка 2, пункт а

Верно! Сумму положительных слагаемых найти просто: вынесем n и появится арифметическая прогрессия. У остальных выносим минус. Тогда надо найти сумму внутри скобок. Можно ли ее телескопировать?

Подсказка 3, пункт а

Заметим, что 3k(k+1) = k(k+1)(k+2) - (k-1)k(k+1). Как теперь найти нужную сумму?

Подсказка 1, пункт б

В таком виде, задачу решать неудобно. Но можно заметить, что если вынести за скобки k!, то каждое слагаемое можно выразить через числа сочетания. А как можно найти такую сумму?

Подсказка 2, пункт б

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

Подсказка 3, пункт б

Каждое слагаемое в скобке выражает ответ на задачу: выбрать k шаров среди первых k + i в ряде из n + k шаров, а затем еще k из последних n - i. А какую задачу тогда решает вся сумма в скобке?

Подсказка 4, пункт б

Конечно, эта скобка отвечает на вопрос: сколько есть способов вставить перегородку в ряд из n + k шаров так, чтобы слева и справа от нее было хотя бы по k шаров. Как можно посчитать это по-другому?

Подсказка 5, пункт б

Верно! Увеличим наш ряд до n + k + 1 шара. Тогда надо выбрать из него 2k + 1 шар и центральный заменить перегородкой. Каково это число способов?

Показать ответ и решение

(a) Заметим, что $3k(k+ 1)= k(k+ 1)(k+ 2)− (k− 1)k(k+ 1).$ Тогда

n∑−1 n∑−1 3k(k+1)= (k(k+ 1)(k+ 2)− (k− 1)k(k+1))= (n − 1)n(n +1) k=1 k=1

Теперь заметим, что

1 ⋅n +2 ⋅(n− 1)+3 ⋅(n− 2)+...+n ⋅1 =(n⋅n − (n− 1)n)+ (n(n− 1)− (n− 2)(n− 1))+ (n(n − 2)− (n − 3)(n − 2))+...n ⋅1

Раскроем скобки и перегруппируем слагаемые с плюсом и с минусом. Тогда сумма слагаемых с плюсом равна

n⋅n +n ⋅(n− 1)+...+n ⋅1 =n n(n-+1)- 2

Сумма слагаемых с минусом равна

n∑−1 k(k +1)= 13(n− 1)n(n+ 1) k=1

Тогда исходная сумма равна:

n2(n+-1) (n-− 1)n(n-+1) n(n+-1)(n+-2) 2 − 3 = 6

(b) Заметим, что

Sn,k = (k!)2(Ckk ⋅Ckn+ Ckk+1⋅Ckn−1+ Ckk+2⋅Ckn−2+ ...+ Ckn⋅Ckk)

Поймем, какую комбинаторную задачу решает выражение в скобке. Для этого расположим в ряд $n+ k$ шаров. $k k Ck+i⋅Cn−i$ — число способов выбрать $2k$ шаров из этого ряда так, что сначала выбраны $k$ шаров из первых $k +i,$ а затем еще $k$ из оставшихся $n− i.$ Таким образом, сумма в скобке — это число способов вставить перегородку в наш ряд так, что слева и справа от нее не менее $k$ шаров, а затем выбрать по $k$ шаров с каждой стороны.

Эта задача эквивалентна тому, чтобы найти число способов в ряде из $n +k+ 1$ шара выбрать $2k+ 1,$ а затем средний заменить перегородкой. Тогда сумма из скобки равна $C2nk++1k+1.$ Таким образом, $Sn,k =(k!)2C2nk++1k+1.$

Ответ:

а) $n(n+1)(n+2) 6$ б) $(k!)2⋅C2k+1 n+k+1$

Ошибка.
Попробуйте повторить позже

Задача 18#83303

Доказать следующие свойства биномиальных коэффициентов ( для любых $n$ и $k$ таких, что $1 ≤ k ≤ n$ ):

a) $(n) (n ) k = n− k$

b) $(n)+ (n ) = (n+1) k k+1 k+1$

c) $n∑ ( ) ( ) ( ) ( ) ( ) ( ) ( ) nk = nn + nn−1 + nn−2 + ⋅⋅⋅+ nk + ⋅⋅⋅+ n1 + n0 = 2n k=0$ (пользуясь исключительно комбинаторным определением! т.е. без бинома Ньютона)

d) $(n) k$ возрастает по $n$ при фиксированном $k$

e)* Фиксируем $n.$ Найти такое $k,$ при котором $( ) nk$ максимально.

Показать ответ и решение

a) Как мы помним, $(n) k$ равно числу подмножеств размера $k$ у $n$ -элементного множества $S.$ Но любому $k$ -элементному подмножеству $A ⊂ S$ можно однозначно сопоставить $(n − k)$ -элементное подмножество $¯A$ в $S.$ Другими словами, выбрать $k$ элементов из $n$ возможных – это то же самое, что из $n$ -элементного множества ”выкинуть” $\text{[math]}$ $n − k$ элементов.

По формуле для $(n) k$ всё совсем очевидно.
Поскольку $( ) nk = k!(nn!−k)!,$ то $( ) nn−k = (n−nk!)!(k)! = k!(nn−!k)!,$ так как наша формула $--n!-- k!(n−k)!$ очевидно симметрична относительно замены $k$ на $n− k.$

b) Это легко доказать просто поигравшись с формулой $( ) nk = k!(nn−!k)!.$
Действительно: $(n) (n ) --n!-- -----n!---- приведём к общ. знам. n!(k+1)+n!(n−k) k + k+1 = k!(n− k)! + (k+1)!(n−k−1)! = (k+1)!(n−k)! =$
$( ) = n!(((kk++11))!+(n(−n−k)k!)) = (k+n1!()n!(+n1)−k)! = (k+(1n)+!(1n)!−k)! = n+k+11$

c)В левой стороне равенства мы суммируем количество способов выбрать:

$n$ -элементное подмножество из n-элементного множества
$(n− 1)$ -элементное подмножество из n-элементного множества
...
$1$ -элементное подмножество из n-элементного множества
$0$ -элементное подмножество из n-элементного множества

То есть мы суммируем количество способов выбрать все возможные подмножества из $n$ -элементного множества. Но таких подмножеств будет ровно $n 2 ,$ поскольку подмножество множества $X$ можно задать так: сопоставить 0 тем элементам, которые в подмножество не входят, и 1 - тем элементам, которые в подмножество входят. Тогда различных подмножеств множества $X$ всего столько же, сколько строк длины $|X |,$ составленных из нулей и единиц, то есть $2n$

d) $(nk)$ при фиксированном $k$ - это количество способов выбрать $k$ объектов из всё бОльших и бОльших множеств ( $n$ растёт по условию, а $n$ - это и есть "размер" $\text{[math]}$ множества, из которого мы выбираем). Таким образом, очевидно, что т.к. растёт количество элементов в множестве, из которого мы выбираем элементы, то и вариантов выбрать какие-то $k$ у нас будет становиться всё больше и больше.

e)* Заметим такое очевидное соотношение:

$(n ) = ----n!-----= ---n!- ⋅--k-- = (n)⋅--k-- k−1 (k−1)!(n−k+1)! k!(n−k)! n−k+1 k n−k+1$

Что же оно нам даёт? А даёт оно нам условие, при котором при фиксированном $n$ предыдущий по $k$ биномиальный коэффициент не больше следующего. А именно, если присмотреться, то из нашей формулы следует, что:

( ) ( ) n ≤ n если и только если---k---- ≤ 1 k− 1 k n − k+ 1

Но это последнее условие уже, в свою очередь, эквивалентно тому, что $k ≤ n− k + 1,$ то есть $2k ≤ n + 1,$ то есть $k ≤ n+1. 2$

Отсюда делаем вывод, что биномиальные коэффициенты растут при фиксированном $n$ до тех пор, пока $k ≤ n+21.$ То есть, наибольшее значение $( ) nk$ будет при максимальном $k$ таком, что $k ≤ n+1. 2$ А это есть просто $k = ⌊n+1⌋ 2$ ( $⌊...⌋$ означает округление вниз до ближайшего целого.)

Ответ:

Предыдущая подтема

Следующая подтема