Сколько способов разложить n шаров по m ящикам
Перейти к содержимому

Сколько способов разложить n шаров по m ящикам

  • автор:

Сколько способов разложить n шаров по m ящикам

Шесть ящиков занумерованы числами от 1 до 6. Сколькими способами можно разложить по этим ящикам 20 одинаковых шаров
а) так, чтобы ни один ящик не оказался пустым?
б) если некоторые ящики могут оказаться пустыми)?

Решение

а) Выложим шары в ряд. Для определения расклада наших шаров по шести ящикам разделим ряд пятью перегородками на шесть групп: первая группа для первого ящика, вторая – для второго и так далее. Таким образом, число вариантов раскладки шаров по ящикам равно числу способов расположения пяти перегородок. Перегородки могут стоять на любом из 19 мест (между 20 шарами – 19 промежутков). Поэтому число их возможных расположений равно .
б) Рассмотрим ряд из 25 предметов: 20 шаров и 5 перегородок, расположенных в произвольном порядке. Каждый такой ряд однозначно соответствует некоторому способу раскладки шаров по ящикам: в первый ящик попадают шары, расположенные левее первой перегородки, во второй – расположенные между первой и второй перегородками и т. д. (между какими-то перегородками шаров может и не быть). Поэтому число способов раскладки шаров по ящикам равно числу различных рядов из 20 шаров и 5 перегородок, то есть равно .

Ответ

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

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 2
Название Комбинаторика
Тема Комбинаторика
параграф
Номер 3
Название Размещения, перестановки и сочетания
Тема Классическая комбинаторика
задача
Номер 2.70, 2.71
книга
Автор Генкин С.А., Итенберг И.В., Фомин Д.В.
Год издания 1994
Название Ленинградские математические кружки
Издательство Киров: «АСА»
Издание 1
глава
Номер 11
Название Комбинаторика-2
Тема Классическая комбинаторика
задача
Номер 31, 32

Проект осуществляется при поддержке и .

5.3. Размещения, перестановки, сочетания

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

элементов выборки может осуществляться последовательно , и порядок следования элементов в выборке считается существенным для различения выборок (даже, если они состоят из одинаковых элементов: например, при определении цифр в номере выигравшего лотерейного билета). С другой стороны, в «спортлото» порядок выпадения номеров шаров по условию не существенен, т.е. в принципе, шары можно было бы выбирать не последовательно, как это делается при розыгрыше, а сразу «комплектом» из 5 (или 6) штук. Результат от этого не изменился бы. Всюду ниже в этом пункте мы рассматриваем некоторую генеральную совокупность фиксированного объема n и фиксируем объем выборки ( m ≤ n элементов). При этом элементы выборки по условию «извлекаются» из генеральной совокупности без возвращения , т.е. выборка не может содержать одинаковые (повторяющиеся) элементы. Размещения . Размещением из n элементов по m называется упорядоченная выборка без возвращения объема m из генеральной совокупности, состоящей из n элементов. Это означает, что соответствующие выборки мы различаем как по элементному составу, так и по порядку следования элементов в выборке. Например, выборки объема 4: (1, 3, 7, 4) и (3, 7, 4, 1) из генеральной совокупности (1, 2, 3, 4, 5, 6, 7, 8, 9) объема 9 мы считаем по условию различными. Теорема 5.2. Обозначим через P n m число различных размещений из n элементов по m . Тогда P n m = n ( n − 1)( n − 2). ( n − m + 1) . Действительно , первый элемент размещения мы можем выбрать n способами, второй – ( n – 1) способом, третий – ( n – 2) способами, и так далее, m -й элемент мы можем выбрать ( n – m + 1) способами. Теперь осталось применить основное правило комбинаторики. Теорема доказана. 73

Замечание . Помимо обозначения P n m для числа размещений часто используется обозначение Перестановки . Перестановкой из n элементов называется упорядоченная выборка без возвращения объема n из генеральной совокупности, состоящей из n элементов. Из предыдущего пункта очевидно следует Теорема 5.3 . Число различных перестановок из n элементов равно n ( n − 1)( n − 2) . 2 1 = n ! Замечание . Для числа перестановок из n элементов чаще всего используется обозначение P n . Сочетания . Сочетанием из n элементов по m называется неупорядоченная выборка без возвращения объема m из генеральной совокупности, состоящей из n элементов. При фиксированном элементном составе размещения из n элементов по m мы имеем m ! различных (различаемых только по порядку следования элементов) выборок. Но поскольку в сочетании порядок элементов несущественен, то становится очевидной Теорема 5.4. Обозначим через C n m число различных сочетаний из n

элементов по m . Тогда:
m P m n ( n − 1)( n − 2). ( n − m + 1) n !
C n = n = = . (5.1)
m ! m ! m !( n − m )!

Замечание . Обратим внимание читателя на то, что число различных сочетаний из n элементов по m совпадает с соответствующим биномиальным коэффициентом в формуле бинома Ньютона: 74

( a + b ) n =
= C n 0 a n + C n 1 a n − 1 b + C n 2 a n − 2 b 2 + . + C n m a n − m b m + (5.2)
+ . + C n n − 1 ab n − 1 + C n n b n .

Отсюда, в частности, следует, что число всех подмножеств n -элементного множества равно 2 n . Действительно, поскольку в подмножества данного множества различаются только по составу элементов, то число различных k -элементных подмножеств данного множества совпадает с числом сочетаний из n элементов по k . Поэтому общее число всех подмножеств данного n -элементного множества (включая само это множество и пустое множество) равно C n 0 + C n 1 + C n 2 + . + C n k + . + C n n − 1 + C n n = (1 + 1) n = 2 n .

5.4. Примеры

1. У филателиста есть 8 разных марок на космическую тему и 10 разных марок на спортивную тему. Сколькими способами можно наклеить 3 марки первого вида и 3 марки второго вида в альбом на 6 пронумерованных мест? Решение. Филателист может выбрать 3 марки из 8 числом способов, равным C 8 3 = 3!5! 8! = 56 , и 3 марки из 10 числом способов, равным C 10 3 = 3!7! 10! = 120. При этом первую группу из 3-х марок он может разместить на 6-ти пронумерованных местах числом способов, равным P 6 3 = 120; при этом вторая группа из 3-х марок размещается на оставшихся трех местах числом способов, равным 3! = 6. Таким образом, общее число различных способов, которыми можно наклеить марки в альбом, равно 56 120 120 6 = 4 838 400. 2. Сколькими способами можно переставить буквы слова «Юпитер», чтобы гласные шли в алфавитном порядке? Решение. Число способов, которыми можно разместить в алфавитном 75

порядке 3 различные гласные буквы на 3 места из 6, равно C 6 3 = 20 . 34 На оставшиеся места остальные буквы (в любом порядке) можно разместить 3! = 6 способами. Таким образом, искомое число способов равно 20×6 = 120. 3. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево (например, таких, как 67876, 17071)? Решение. Очевидно, выбор первых двух цифр такого числа однозначно определяет последние две его цифры. На первом месте может стоять любая цифра, кроме нуля (т.е. девять цифр от 1 до 9). На втором и третьем месте может стоять любая из десяти цифр (от 1 до 9 и 0), поэтому искомое количество чисел будет равно 9×10×10 = 900. 4. Сколькими способами можно разложить 19 различных предметов по 5-ти различным ящикам так, чтобы в 4 ящика легли по 4 предмета, а в оставшийся ящик – 3 предмета? Решение. В первый ящик 4 предмета можно положить числом способов, равным C 19 4 = 3876. Во второй ящик 4 предмета можно положить, следовательно, числом способов, равным C 15 4 = 1365; в третий ящик – числом способов, равным C 11 4 = 330 , в четвертый – числом способов, равным C 7 4 = 35. Далее предметы для последнего ящика определяются однозначно. Наконец, мы должны учесть, что при распределении групп по 4 предмета используются 4 ящика из 5. Число различных комбинаций по 4 ящика из 5 равно C 5 4 = 5. Таким образом, искомое число способов равно C 19 4 C 15 4 C 11 4 C 7 4 C 5 4 = 305 540 235 000. Следующие несколько примеров более сложны, но имеют важное прикладное значение. 5. Распределение r шаров по n ящикам . Сколькими способами можно r неразличимых между собой шаров распределить по n различным ящикам? 34 То есть число способов, которыми можно выбрать три числа из шести без учета порядка, ибо каждой неупорядоченной тройке различных чисел соответствует один и только один упорядоченный набор, в котором эти числа идут по возрастанию. 76

При этом предполагается, что число шаров в каждом ящике может принимать любое значение от 0 до r . Решение. Будем представлять ящики как промежутки между n + 1 черточками (черточки имитируют стенки ящиков), а шары условимся обозначать звездочками. Так, символ |***|*| | | |****| означает, что r = 8 шаров размещено по n = 6 ящикам, причем эти ящики содержат последовательно 3, 1, 0, 0, 0, 4 шаров. Такие символы всегда начинаются и кончаются черточками, но оставшиеся n − 1 черточку и r звездочек можно разместить в произвольном порядке. Число таких различимых размещений будет равно числу способов выбора r мест среди n + r − 1 мест (или, что то же, числу способов выбора n − 1 мест среди n + r − 1 мест), то есть будет равно числу сочетаний из n + r − 1 элементов по r (или, соответственно, по n − 1): C n r + r − 1 = C n n + − r 1 − 1 . Замечание . Если ящики считать неразличимыми, то число искомых размещений будет в n ! раз меньше (почему?). 5.1. В условиях предыдущей задачи указать число способов, которыми можно r неразличимых между собой шаров распределить по n различным ящикам с условием, что ни один ящик не будет пустым. Очевидно, что при этом должно быть r ≥ n . Решение. Условие отсутствия пустых ящиков приводит к следующему ограничению: каждая черточка (кроме крайних) должна быть заключена между двумя звездочками. Это соответствует числу способов, которыми можно разместить n − 1 черточку в r − 1 промежуток между звездочками. Это число равно, очевидно, C r n − − 1 1 . 5.2. Указать число различных целых неотрицательных решений r 1 , r 2 . r n уравнения 77

r 1 + r 2 + . + r n = r , r j ≥ 0 . (Порядок чисел r 1 , r 2 . r n здесь существенен: например, решения r 1 = 2, r 2 = 3 и r 1 = 3, r 2 = 2 считаются различными). Решение. Очевидно, эта задача эквивалентна задаче о числе размещений r шаров по n ящикам. Таким образом, число различных целых неотрицательных решений указанного уравнения будет равно C n r + r − 1 = C n n + − r 1 − 1 . 35 Аналогично, число различных натуральных решений этого уравнения

будет равно C r n − − 1 1 ( r ≥ n ).
Разбиение на группы
Теорема 5.5. Пусть r 1 , r 2 . r k целые неотрицательные числа, причем
r 1 + r 2 + . + r k = n , r j ≥ 0 .

Тогда число способов, посредством которых n различных элементов могут быть разделены на k групп, из которых первая группа содержит r 1 элементов, вторая r 2 элементов и т.д., равно 36 n ! . r 1 ! r 2 . r k ! Обращаем внимание читателя на то, что данная задача принципиально отличается от рассмотренной в предыдущем примере задачи о распределении шаров по ящикам: в примере 5 шары считаются неразличимыми, в то время каквнашемслучаеэлементы предполагаютсяразличными.Неимеет значения лишь порядок элементов в каждой группе, но элементный состав групп существенен. Кроме того, порядок групп остается также существенным в том смысле, что, например, разбиения ( r 1 = 2, r 2 = 3) и ( r 1 = 3, r 2 = 2) считаются 35 Для читателей, знакомых с анализом, отметим, что очевидным следствием этого результата является тот факт, что этойжевеличинеравно числоразличных частных производных порядка r аналитическойфункции n переменных: ∂ r f ( x 1 , x 2 . x n ) ∂ x 1 r 1 ∂ x 2 r 2 . ∂ x n r n . Действительно, частные производные порядка r от аналитической функции n переменных не зависят от порядка дифференцирования, а зависят лишь от того, сколько раз мы дифференцируем по каждому переменному. Каждое переменное здесь играет роль «ящика», а роль «шара» играет операция дифференцирования. 36 Случай r j = 0 также включается, если учесть формулу 0! = 1 . 78

различными. Доказательство . Выберем сначала первую группу, состоящую из r 1 элементов. Такую группу можно выбрать числом способов, равным C n r 1 . Вторую группу объема r 2 можно, следовательно, выбрать числом способов,

равным C n r 2 − r , третью – числом способов, равным C n r 3 − r − r и т.д. После
1 1 2
образования ( k − 1) -й группы, остается n − r 1 − r 2 − . − r k − 1 = r k элементов,

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

групп, из которых первая содержит r 1 элементов, вторая r 2 элементов и т.д.,
будет равно
N = C n r 1 C n r 2 − r C n r 3 − r − r . C n r k − − r 1 − r − . − r .
1 1 2 1 2 k − 2
Преобразуем последнее выражение:
N = n ! ( n − r 1 )! ( n − r 1 − r 2 )! ( n − r 1 − r 2 − . − r k − 2 )!
= . =
r !( n − r )! r !( n − r − r )! r !( n − r − r − r )! r !( n − r − r − r − . − r )!
1 1 2 1 2 3 1 2 3 k − 1 1 2 3 k − 1
= n ! , так как n − r 1 − r 2 − . − r k − 1 = r k . Теорема доказана.
r 1 ! r 2 . r k − 1 ! r k !

В качестве примера применения последней теоремы рассмотрим следующую задачу. При игре в бридж между четырьмя игроками распределяют n = 52 карты по 13 карт каждому ( r 1 = r 2 = r 3 = r 4 = 13). Какова вероятность того, что каждый игрок получит ровно по одному тузу? Решение. Число вариантов распределения по 13 карт между четырьмя игроками соответствует числу способов, которыми можно 52 элемента разбить на 4 группы по 13 элементов в каждой, т.е., согласно теореме 5.5, равно (13!) 52! 4 . Четыре туза могут быть распределены между четырьмя игроками 4! = 24 способами. Оставшиеся 48 карт могут быть распределены 79

Сколькими способами можно разместить n шаров по n ящикам?

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

Смотри.
Пусть A и B — конечные множества с количествами элементов |A| = n, |B| = m.
Тогда из A в B существует m^n различных отображений.
Первый элемент A можно отобразить в любой из m элементов B
Второй элемент A можно (независимо от первого) отобразить в любой из m элементов B
Третий элемент A можно (независимо от первого и второго) отобразить в любой из m элементов B
И так далее.
У тебя A — множество шаров, B — множество ящиков, m = n.

ОлландУченик (70) 1 год назад

https://www.cyberforum.ru/combinatorics/thread2636719.html
вот тут посчитано только количество нужных событий

ОлландУченик (70) 1 год назад
ну хорошо конечно подгонять условие, когда ответ заранее не известен

Тадасана Просветленный (38344) Олланд, если бы ответ не был заранее известен, я бы счел шары одинаковыми, потому что учителя за последние несколько десятилетий стали жуткими неформалами и теперь могут всуе использовать слово «разместить», даже если речь не идет о размещениях с повторениями или без. 30 лет назад я счел бы шары различными и ответил n^n, потому что авторы задач раньше слов на ветер не бросали. Разместить — значит, разместить, а в урны просто чего-то там наложить.

ОлландУченик (70) 1 год назад
ну кстати это феллер 84 года, так что вы правильно поняли условие))
Рустам ИскендеровИскусственный Интеллект (138963) 1 год назад

«Сколькими способами можно разместить n туристов по n отелям?» Тогда да, ответ был бы по-другому. Но тут вопрос о несчастных шарах.

Остальные ответы

Вот:

ОлландУченик (70) 1 год назад

вот тут посчитано только количеств нужных событий

ответ из сборника C(n,2)*n!*n^-n

а ты сам эксперимент сделай с матрицей 2х2 или 3х3 возьми и посчитай число комбинаций
Как размещать-то надо? Обязательно по одному шару в ящик или как?
Рустам ИскендеровИскусственный Интеллект (138963) 1 год назад

Можно, например, все шары поместить в один какой-нибудь ящик. Нет никаких ограничений в способе размещения.

ОлландУченик (70) 1 год назад

https://www.cyberforum.ru/combinatorics/thread2636719.html
вот тут посчитано только количество нужных событий

Ф-ла n^n в корне неверна. Я проверил для n= 4. Число вариантов получилось 35. Тут выступает «треуг-к Паскаля». Свои соображения напишу позже.

Рустам ИскендеровИскусственный Интеллект (138963) 1 год назад

Берём треуг-к Паскаля:
****************01
**************01 01
************01 02 01
**********01 03 03 01
********01 04 06 04 01
******01 05 10 10 05 01
****01 06 15 20 15 06 01
**01 07 21 35 35 21 07 01
01 08 28 56 70 56 28 08 01
Пусть n= 1. Число вариантов — единица на вершине треуг-ка: N= 1. Пусть n= 2. Начиная с вершины, читаем 2+1= 3 числа вниз-вправо и суммируем их: N= 1+1+1= 3. Пусть n= 3. Берём параллельно первой «косую строку» на ступень ниже и суммируем 3+1= 4 числа: N= 1+2+3+4= 10. Пусть n= 4. Спускаемся ещё ниже и суммируем 5 чисел: N= 1+3+6+10+15= 35.
Все эти варианты (n от 1 по 4) проверил и все верны. Поэтому уверен, что данная процедура пригодна для любых n.
Например, для n= 5 ожидается: N= 1+4+10+20+35+56= 126.
Но каково общее выражение зависимости N от n — не знаю.

Рустам ИскендеровИскусственный Интеллект (138963) 1 год назад

Постой, вот что обнаруживается:
n= 1. N= С(0 из 1)= 1
n= 2. N= С(1 из 3)= 3
n= 3. N= С(2 из 5)= 10
n= 4. N= С(3 из 7)= 35
n= 5. N= С(4 из 9)= 126.
Сейчас обобщу.

Рустам Искендеров Искусственный Интеллект (138963) Рустам Искендеров,
Рустам ИскендеровИскусственный Интеллект (138963) 1 год назад
N= C(n-1 из 2n-1)= (2n-1)!/[n!*(n-1)!].
Это и есть ответ.

Олланд Ученик (70) Рустам Искендеров, https://www.cyberforum.ru/combinatorics/thread2636719.html вот тут посчитано только количество нужных событий

Сколько способов разложить n шаров по m ящикам

Руководители А. В. Антропов, М. А. Лимонов и А. Ю. Шапцев
2010/2011 учебный год

Ликвидация безграмотности!

Комбинаторика. 16 октября 2010 года

Великое напоминание: Через C n k —> обозначается количество способов выбрать из множества, содержащем n элементов, подмножество, содержащее k элементов. Или, по-простецки, количество способов выбрать из n предметов k без учета порядка.

1. Вспомните комбинаторные доказательства следующих тождеств: a) C n + 1 k = C n k − 1 + C n k ;—> b) C n 0 + C n 1 + … + C n n = 2 n ;—> c) n · C n − 1 k − 1 = k · C n k .—> 2. Докажите комбинаторно, что C n k · C n − k m = C n m · C n − m k .—>

Еще одно великое напоминание: (бином Ньютона)

a + b ) n = C n 0 a n + C n 1 a n − 1 b + C n 2 a n − 2 b 2 + … + C n n b n $—>

3. Вспомните доказательства через бином Ньютона следующих тождеств: a) C n 0 + C n 1 + … + C n n = 2 n ;—> b) C n 0 − C n 1 + … + ( − 1) n C n n = 0;—> 4. Сколько существует способов добраться из легого нижнего до правого верхнего угла в прямоугольнике n × k , если за каждый ход можно идти только вверх или вправо?

Указание. А когда мы можем сходить наверх?

5. Для проведения вступительной олимпиады преподаватели разбивают 65 школьников следующим образом: список в алфавитном порядке разбивается на 4 части, первая идет в первую аудиторию, вторая — во вторую и т.д. При этом в каждую аудиторию отправляется хотя бы один школьник. Сколькими способами можно произвести распределение?

Указание. По сути разбить список значит провести три черты где-то между детьми.

  • ЗАДАЧИ
  • 9-11 классы
  • Индукция
  • Алгоритм Евклида
  • Комбинаторика
  • Векторы
  • Геометрия масс
  • Дискретная непрерывность
  • Принцип Дирихле
  • Количество информации
  • Рекуррентные соотношения
  • Графы

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!


Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *