Метод шаров и перегородок
Ошибка.
Попробуйте повторить позже
депутатов Городского Собрания выбирают Председателя из 
кандидатов. Каждый голосует ровно за одного из них. После
голосования составляется протокол заседания, в котором указывается лишь количество голосов за каждого кандидата (без указания, кто за
кого проголосовал). Сколько различных протоколов может получиться?
Источники:
Подсказка 1
Попробуем перевести задачу на язык шаров и перегородок. В конце концов в протоколе у нас будет пять значений – количество голосов за каждого кандидата. И нам нужно найти количество таких протоколов. Хм... Какое тогда уравнение можно составить, чтобы в дальнейшем применить идею шаров и перегородок?
Подсказка 2
Верно, если за 1, 2, 3, 4 и 5 кандидата проголосуют соответственно a, b, c, d и e депутатов, то их сумма будет равна 19. И того, учитывая ограничения на количество голосов(проголосовавших депутатов) нам нужно найти количество таких пятёрок. Тогда с точки зрения шаров и перегородок, что нам нужно сделать?
Подсказка 3
Да, нам нужно расставить 4 перегородки в какое-то количество мест. Поймём теперь в какое. Надо не забыть, что перегородки могут стоять в начале и в конце(когда за кандидата никто не проголосовал, например) и рядом между собой(тогда за кандидата между ними 0 голосов). Итого у нас получается всего элементов 23 – это 20 мест для одной перегородки между шарами и по краям, но у нас ещё есть 3 перегородки, которые могут стоять рядом с нашими позициями, то есть ещё дополнительных 3 места.
Количество различных протоколов соответствует количеству различных упорядоченных пятёрок 
, таких что
с учётом того, что у нас есть ограничения 
Такая задача эквивалентна тому, чтобы расставить 
перегородки между 
шариками, причем перегородки могут стоять в начале, в
конце или на одной и той же позиции (так как голосов каждого вида может быть любое количество от 
до 
, то есть ограничения на
количество голосов, кроме уравнения - связки, у нас нет). Количество элементов в каждой из получившихся пяти группах между
перегородками (возможно, каких-то пустых) это и будут значения 
Итак, у нас есть 
элемента - 
шариков и 
перегородки. Количество различных (!) их перестановок равно 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
