"🎱 Разбор задачи с собесов на шары и перегородки Задачи на чистую комбинаторику на собеседованиях встречаются редко. Обычно комбинаторика это составная часть задачи на теорвер. Но есть один вид задач, которым любят подловить на собесе. Он выбивается из привычной схемы «сочетания / перестановки / размещения». И если сразу его не узнать, решить такую задачу крайне сложно. Классическая формулировка звучит так: Пусть имеется r одинаковых (неразличимых) предметов (шаров) и n различных (различимых) ящиков. Сколькими способами можно разложить все r шаров по n ящикам? Но бывают и более замаскированные формулировки: -> Бросаем 3 кубика. Сколько различных исходов без учета порядка? -> Сколько неотрицательных целых решений у x₁+x₂+x₃=10? Все это задачи на метод шаров и перегородок. Узнать такую задачу можно по следующей конструкции: есть r одинаковых объектов, которые нужно распределить по n различимым ""корзинкам"". При этом важен только результат, т. е. сколько объектов оказалось в каждой корзинке. У таких задач есть два подвида. 1️⃣ Пустых ящиков нет. Тогда ответ C(r-1, n-1). 2️⃣ Ящики могут быть пустыми: C(r+n-1, n-1). Формулы можно просто запомнить. Но лучше понять интуицию за ними: 1️⃣ Без пустых ящиков. Выкладываем r шаров в ряд. Между ними есть r-1 промежутков, в которые нужно поставить n-1 перегородок. Итого C(r-1, n-1). Причем не больше одной перегородки в промежуток, иначе появится пустой ящик. По той же причине нельзя ставить перегородки по краям. 2️⃣ С пустыми ящиками. Теперь перегородки могут стоять рядом и по краям. Можно представить ряд из r+(n-1) позиций. Т. е. что у нас заготовлены ячейки под нужное количество шаров и перегородок. В каждой позиции должен стоять либо шар, либо перегородка. Выбираем n-1 позиций под перегородки, остальные заполняем шарами. Получаем C(r+n-1, n-1). — Попадались вам задачи на шары и перегородки на собеседованиях? Поставьте 🐳, если да. А если видите такую задачу впервые – 🔥. И можете поделиться формулировками подобных задач в комментариях.)"