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

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

Сколько способов разложить N шаров по M ящикам ?
Задача такая: есть M ящиков с номерами от 1 до M (т.е. ящики различимы) и N неразличимых шаров.

Сколько способов разложить n шаров по n-2 ящикам по 1 шару?
Шары, естественно, различимые

Сколько способов разложить 9 шаров по 3 ящикам по 3 шара?
Шары различимы. Порядок шаров в каждом ящике, конечно, не важен. И немного объясните само.

Сколько способов разложить 5 нумерованных шаров по 5 нумерованным ящикам?
По одному шарику в ящик. При этом только один шарик с номером Х попадает в ящик с номером Х. .

Байт, а как мы получили такую формулу? Можно расписать подробнее?

Или кто другой может объяснить?

Оставить пустыми r ящиков из m можно C_m r способами.
Остается m-r ящиков(непустых) и n шаров. Задача известная C_n-1 m-r-1

Добавлено через 3 минуты
Решение «известной» задачи. Пусть есть k ящиков и n шаров. Разложим шары в ряд. Нам надо положить k-1 «разделителей» между ними. Мест для этих разделителей ровно n-1. Итого C_n-1 k-1

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

Добавлено через 18 минут
Соображения.
Для 2-х ящиков F(n,2) = n/2 (деление — нацело)
Для 3-х F(n,3) = (n — 3(n/3))/2 + (n — 3(n/3 — 1))/2 + .
и поймать индуктивную закономерность.
.
Но это, кажется, не в ту степь.

Сколькими способами можно разложить a одинаковых шаров по b различным ящикам?
Сколькими способами можно разложить a одинаковых шаров по b различным ящикам, так, чтобы в каждом.

Разложить шары по ящикам, чтобы число шаров в любых двух ящиках не различалось более чем на 1
Сколько существует способов разложить x одинаковых шаров в y различных ящиков, так чтобы число.

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

Размещение различимых шаров по ящикам
Здравствуйте,вопрос в следующем сколько способов разместить 3 различимых шара по двум ящикам из 3.

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

Раскладывание шаров по ящикам: найти ошибку в рассуждениях
Доброго времени суток! Есть такая задача: найти вероятность того, что 2 шара, равновероятно.

Источник

комбинаторика — Размещение n одинаковых шаров по m различным ящикам с условием

Сколькими способами можно разложить 20 одинаковых шаров по 8 различным ящикам так, чтобы не более 3-х ящиков остались пустыми?

Я знаю, как решить эту задачу, если бы в ней не было бы условия «чтобы не более 3-х ящиков остались пустыми», но вот это условие все путает.

Если вам не сложно — подскажите, пожалуйста, как решить эту задачку.

задан 16 Окт ’16 19:51

Ну эта задача на олимпиадную не тянет совсем.

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

Ну, набросились. уже и спросить нельзя. )))

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

1 ответ

Пусть мы разложили шары. Обозначим через $%x_i$% количество шаров в $%i$%-м ящике. Тогда $%x_1+\cdots+x_8=20$%, и слагаемые являются целыми неотрицательными числами. Если не накладывать ограничений, то будут сочетания с повторениями из 8 по 20, то есть $%C_<27>^<20>=C_<27>^7=888030$%.

Теперь пусть ровно $%k$% ящиков у нас пусты, где $%0\le k\le3$%. Для начала имеется $%C_8^k$% способов выбрать, какие именно $%k$% ящиков будут пустыми. После этого у нас возникает уравнение вида $%y_1+\cdots+y_<8-k>=20$%, где все «игреки» отличны от нуля. Вычитая из них по единице, мы имеем уравнение $%x_1+\cdots+x_<8-k>=12+k$%, где «иксы» целые неотрицательные. А это уже известное нам число сочетаний с повторениями из $%8-k$% по $%12+k$%, которое равно $%C_<19>^<12+k>=C_<19>^<7-k>$%.

Таким образом, суммируя по $%k$%, мы имеем ответ $%C_8^0C_<19>^7+C_8^1C_<19>^6+C_8^2C_<19>^5+C_8^3C_<19>^4=810084$%. Можно заметить, что это число лишь немногим меньше общего числа способов, и при случайном разложении шаров по ящикам, вероятность того, что пустых окажется не более трёх, составляет более 91 процента.

отвечен 16 Окт ’16 20:26

falcao
268k ● 6 ● 37 ● 51

Благодарю вас за подробный ответ! Буду разбираться!

Не могли бы вы пояснить момент с «Вычитая из них по единице»? Не понимаю, как вы из первого (в этом абзаце) уравнения получили второе.

@Integer: имелось в виду, что $%x_i=y_i-1$%. Это стандартный приём. Он позволяет свести задачу к случаю целых неотрицательных слагаемых, то есть к сочетаниям с повторениями. Вместо $%y_i\ge1$% получается $%x_i\ge0$%.

А как в правой части из 20 получилось 12+k?

@Integer: это такой вопрос, на который Вы и сами могли бы ответить. Что будет, если в левой части вычесть по 1 из каждого слагаемого? В целом мы вычтем 8-k, по числу слагаемых. Тогда столько же надо будет вычесть и из правой части, то есть из 20. Сделаем это, и — о, чудо! — получится 20-(8-k)=20-8+k=12+k.

Источник

Разместить n шариков по n ящикам, оставив 1 пустой

Пусть n⩾3. Шарики занумерованы числами от 1 до n n. Найдите количество способов эти n шариков разместить в n разных ящиков так, чтобы ровно один ящик оказался пустым.

Мой ход решения:

1)Возьму произвольную последовательность 1 2 3 4 и «выкину» последнеию цифру (4)
2)Посчитаю число сочетаний из n-1 шариков по n-1 ящикам
3)Проделаю тоже самое, для
2 3 4 1 (1 выкинул)
1 3 4 2 (2 выкинул)
1 2 4 3 (3 выкинул)

Для всех троек число сочетаний будет одинаковое — (n-1)!
Каждое сочетание тройки 1 2 3 может быть масштабированы в n — 1 раз, если по очереди в каждый непустой ящик класть четвёрку.
Каждое сочетание тройки 2 3 4 может быть масштабированы в n — 2 раз, если по очереди в каждый непустой ящик класть единицу.
Каждое сочетание тройки 1 3 4 может быть масштабированы в n — 3 раз, если по очереди в каждый непустой ящик класть двойку.
Вынося комбинаторный множитель n!(точнее (n-1)!*n так как пустой ящик тоже переставляется) за скобку получаю — (n- 1 + (n — 2) + . +1)
Если упростить то получится n*(n-1)/2
В итоге: n!*n*(n-1)/2
С ответом сошлось, но првильный ли был у меня ход мыслей ?

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

Сколькими способами можно разместить шары по ящикам без ограничений
Добрый день. Есть две задачи: 1) Есть N разных шаров и M одинаковых ящиков. Сколькими способами.

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

Можно ли купить k шариков мороженого ,если его продают по 3 и по 5 шариков?
Задача : «В кафе мороженое продают по три шарика и по пять шариков. Можно ли купить ровно k шариков.

Байт, У Вас слишком коротко, я пока только учусь
Я попробую поподробнее.

Проведу экспиремент на 4х шариках, пронумерованных от 1 до 4.(n = 4)
Возьму произвольную последовательность шаироков 1 2 3 4 и «выкину» шарик с последнеий цифрой (4)
2)Посчитаю число сочетаний из n-1 шариков(1 2 3) по n-1 ящикам
3)Проделаю тоже самое(подсчёт числа сочетаний), для шариков с номерами:
2 3 4 (шарик 1 отложил в сторону)
1 3 4 (шарик 2 отложил в сторону)
1 2 4 (шарик 3 отложил в сторону)

Для всех троек число сочетаний будет одинаковое — (n-1)!
Каждое сочетание тройки 1 2 3 может быть масштабированы в n — 1 раз, если по очереди в каждый непустой ящик на каждое сочетание класть четвёрку.
Каждое сочетание тройки 2 3 4 может быть масштабированы в n — 2 раз, если по очереди в каждый непустой ящик на каждое сочетание класть единицу.
Каждое сочетание тройки 1 3 4 может быть масштабированы в n — 3 раз, если по очереди в каждый непустой ящик на каждое сочетание класть двойку.
Вынося комбинаторный множитель n!(точнее (n-1)!*n так как пустой ящик тоже переставляется) за скобку получаю — (n- 1 + (n — 2) + . +1)
Если упростить то получится n*(n-1)/2

Источник

Найти число способов раскладки n различных шаров по m различным корзинам

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

Найти число способов разложить 20 белых и 30 черных шаров по 5 пронумерованным урнам
Найти число способов разложить 20 белых и 30 черных шаров по 5 пронумерованным урнам так, чтобы в.

Поиск количества размещений n шаров по m корзинам, с условиями
Задача 3. Сколькими способами можно разместить n одинаковых шаров по m различным корзинам при.

Реализовать алгоритм разложения по двум корзинам пронумерованных шаров
Приветствую всех. Необходимо реализовать алгоритм разложения по двум корзинам пронумерованных.

Решение

ToxabullY, формула весьма банальна!

Сколько способов разложить 12 одинаковых монет по 4 различным карманам
Здравствуйте! Можете помочь решить задачу по комбинаторике? А то я то — то не могу сообразить. .

Сколькими способами можно разложить a одинаковых шаров по b различным ящикам?
Сколькими способами можно разложить a одинаковых шаров по b различным ящикам, так, чтобы в каждом.

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

Какое наименьшее число можно записать в виде суммы простых чисел по крайней мере 5000 различных способов?
Число 10 можно записать в виде суммы простых чисел ровно пятью различными способами: 7 + 3 5 + 5.

Источник

Сколькими способами можно разместить шары по ящикам без ограничений

Добрый день. Есть две задачи:
1) Есть N разных шаров и M одинаковых ящиков. Сколькими способами можно разместить шары по ящикам без ограничений, т.е. в одном ящике может быть от 0 до N шаров.
2) Есть N одинаковых шаров и M разных ящиков. Сколькими способами можно разместить шары по ящикам без ограничений, т.е. в одном ящике может быть от 0 до N шаров.

Я правильно понимаю, что для 2 задачи подойдет формула , т.е. это количество способов разместить M-1 перегородку по N+M-1 возможным местам?
Подскажите, как решать первую задачу, пожалуйста.

Сколькими способами можно разложить шары по ящикам?
Сколькими способами можно разложить 8 одинаковых шаров по 3 одинаковым ящикам?

Сколькими способами можно разложить все шары по ящикам?
Имеется 6 различных ящиков и 10 неразличимых шаров. Сколькими способами можно разложить все шары.

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

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

Спасибо большое за ответ.
Не могли бы вы чуть более детально объяснить решение и формулу? В чем именно заключается фишка «одинаковых» ящиков и «разных» шаров, и как это всё влияет на количество возможных вариантов?
И, например, как подсчитать ответ для 10 шаров и 4 ящиков? Не могу понять как именно всё подставить в формулу.
Возможно, у вас есть какие-то ссылки для меня, чтобы я мог ознакомиться. Искал в интернете задачи с «одинаковыми» ящиками и не нашел, к сожалению.

Вот ответ ваш достаточно понятен для меня. Но всё же сижу не могу сообразить как мне с помощью вашей формулы решить свою задачу с 10 шарами и 4 ящиками.
Шары различимы, т.е. важно какие именно попадают в ящики. Т.е. нужно для каждого варианта «вместимости» ящика подобрать разнообразные варианты выбора шаров из N (10) штук.
Получается, что нужно перебирать разнообразные варианты вместимости ящиков (0-10), и для каждого такого варианта перебирать выбор шаров для этих ящиков, начиная с первого ящика, где точно должно быть >1 шара. Я правильно мыслю?
Но вот всё никак не понимаю, как это решить с вашей формулой, эх.
Особенно предложение «Две части формулы связаны с тем, превышает ли количество групп шаров количество ящиков или не превышает.» вводит меня в ступор. Правильно я понимаю, что для каждой левой итерации от k до M мы умножаем всю эту часть на сумму ? Или это у нас идет умножение одной суммы на другую?

Добавлено через 57 минут

Сколькими способами можно разложить a одинаковых шаров по b различным ящикам?
Сколькими способами можно разложить a одинаковых шаров по b различным ящикам, так, чтобы в каждом.

Сколькими способами можно разложить красные и синие шары по урнам?
Имеется 5 урн. Сколькими способами можно разложить 50 красных и 30 синих шаров по 5 занумерованным.

Сколькими способами можно разместить
Сколькими способами можно разместить _ <1>красных, _ <2>желтых и _ <3>зеленых слоев по m.

Источник