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

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

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

Решение

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

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

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

элементов выборки может осуществляться последовательно , и порядок следования элементов в выборке считается существенным для различения выборок (даже, если они состоят из одинаковых элементов: например, при определении цифр в номере выигравшего лотерейного билета). С другой стороны, в «спортлото» порядок выпадения номеров шаров по условию не существенен, т.е. в принципе, шары можно было бы выбирать не последовательно, как это делается при розыгрыше, а сразу «комплектом» из 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) способами. Теперь осталось

применить основное правило комбинаторики. Теорема доказана.

Замечание . Помимо обозначения 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 ! различных (различаемых только по порядку следования элементов) выборок. Но поскольку в сочетании порядок элементов несущественен, то становится очевидной

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

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

задан 10 Июл ’15 5:40

@sapere aude, Если вам дан исчерпывающий ответ, отметьте его как верный (нажмите на галку рядом с выбранным ответом).

1 ответ

Если все ящики непустые, то ответом будут числа Стирлинга второго рода. Если всего ящиков $%m$%, то непустыми могут оказаться от одного до $%m$% ящиков, поэтому ответ для общего случая даётся суммой $%S(n,1)+S(n,2)+\cdots+S(n,m)$%.

Для небольших значений $%m$% можно указать простые формулы: $%1$% (для $%m=1$%); $%2^$% (для $%m=2)$%; $%\frac<3^+1>2$% (для $%m=3$%); $%\frac<(2^+1)(2^+2)>6$% (для $%m=4$%). Далее всё постепенно усложняется.

отвечен 10 Июл ’15 6:30

@falcao А если допустить, что ящики могут быть пустыми?

@sapere aude: так я именно этот случай и рассматривал. Для непустых — это числа Стирлинга II рода, а если разрешить пустые, то будут их суммы. У меня именно этот ответ и указан. Сейчас я чуть подправлю начало текста, чтобы было яснее.

А я решил прочитать про числа Стирлинга в общем виде потом, думал, что ниже про них. Простите, мозг что-то перегрелся)

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

Правило умножения используется в том случае, если у нас есть два множества, и мы составляем всевозможные пары из элементов этих множеств. Например, если взять множество, состоящее из 5-ти яблок и множество, состоящее из 7-ми груш и составить всевозможные пары из этих фруктов, то мы получим всевозможных пар.

Действительно. Возьмем первое яблоко. Мы можем положить к нему любую из семи груш, то есть получаем 7 пар. Возьмем второе яблоко, и к нему мы также можем положить любую из 7-ми груш, получаем ещё 7 пар. И так далее. Всего получается пар.

Пусть двузначное чиcло имеет вид , где — число десятков, — число единиц. При этом цифра может принимать значения от 1 до 9 ( цифра 0 не может стоять на первом месте, так как в этом случаем мы получим однозначное число), цифра может принимать значения от 0 до 9.

Пусть , и у нас есть 10 вариантов цифр, которые могут стоять на втором месте. Тогда мы имеем 10 двузначных чисел, содержащих 1 десяток.

Затем мы берем и так же получаем 10 двузначных чисел, у которых теперь уже 2 десятка.

Так как цифра может принимать 9 различных значений, то получаем двузначных чисел.

Зная, что на первом месте может стоять 9 различных цифр, а на втором — 10, мы получаем комбинаций этих цифр, то есть все возможные двузначные числа. Здесь важно понимать, что любая цифра, стоящая на первом месте, может сочетаться с любой цифрой, стоящей на втором месте.

Если мы хотим ответить на вопрос, сколько существует трехзначных чисел, мы заметим, что в трехзначном числе первая цифра может принимать 9 значений, вторая — 10, и третья — 10 значений. И мы получаем трехзначных чисел.

Пусть множество А содержит n элементов, множество В содержит m элементов, и пересечение этих множеств содержит k элементов. То есть k элементов содержатся и в множестве А, и в множестве В. Тогда объединение множеств содержит m+n-k элементов.

# # # # # # # #

Найдем, сколько трехзначных чисел НЕ содержит цифру 3. В этом случае на первом, втором и третьем месте в записи числа может стоять любая цифра кроме 3. То есть первая цифра может принимать 8 значений, вторая — 9, и третья — 9 значений. Тогда мы получаем трехзначных чисел, которые НЕ содержит цифру 3. Следовательно, остальные числа содержат хотя бы одну цифру 3.

Мы знаем, что число делится на 5, если оно оканчивается на 0 или 5. Следовательно, в четырехзначном числе последняя цифра может принимать только два значения: 0 и 5.
Первая цифра может принимать 9 значений, вторая — 10, и третья — 10 значений, четвертая — 2 значения.

Тогда мы получаем четырехзначных чисел, которые делятся на 5.

Человека, стоящего первым в шеренге можно выбрать семью способами, второго можно выбрать из оставшихся шести человек, то есть шестью способами. Третьего, соответственно, пятью. И так далее. Последнего можно выбрать единственным способом. Всего получаем способов построить 7 человек в шеренгу.

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

Факториалом натурального числа называется произведение всех натуральных чисел от 1 до :

Перестановкой из предметов называется любой способ нумерации этих предметов (способ расположения их в ряд).

Число перестановок предметов равно .

в слове «МАТЕМАТИКА» 2 буквы «М»; 3 буквы «А»; 2 буквы «Т», следовательно по правилу произведения это дает нам способов перестановки этих букв с сохранением слова «МАТЕМАТИКА».

Таким образом, мы получаем вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны.

Если умножить и разделить это выражение на , то получим следующую формулу:

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

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

Число размещений из элементов по обозначается и находится по формуле:

При бросании кости первый раз мы получим 6 различных вариантов: 1 очко, 2, 3. или 6. Аналогично при бросании кости во второй и в третий раз мы получим также по 6 различных вариантов. По правилу умножения получим число различных комбинаций трех чисел, принимающих значения от 1 до 6:

Пусть у нас есть множество , состоящее из элементов.

Любой упорядоченный набор элементов множества, состоящего из элементов называется размещением с повторением из элементов по . Число различных размещений с повторениями равно

Действительно. Представим ящик с пронумерованными шарами. Мы вынимаем шар, записываем его номер и возвращаем обратно, и так раз. Сколько комбинаций из номеров мы можем получить?

Сочетаниями из n элементов по k элементов называются подмножества, состоящие из k элементов множества (множества, состоящего из n элементов).

Из 8 красных карандашей можно извлечь два карандаша способами.

Из 4 синих карандашей можно извлечь два карандаша способами.

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

Так как переменные могут принимать только целые неотрицательные значения, следовательно, у нас есть 10 переменных, и они могут принимать значения 0, 1, 2, 3 и 4. Представим, что у нас есть 10 коробок (это переменные), и мы должны разложить по этим коробкам 4 шара. Сколько шаров попадет в коробку, таково значение соответствующей переменной. Если у нас 10 коробок, следовательно, 10-1=9 внутренних перегородки. И 4 шара. Всего 13 мест. Нам надо расположить на этих 13 местах 4 шара. Число таких возможностей:

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

Сочетаниями из элементов по элементов с повторениями называются группы, содержащие элементов, причем каждый элемент принадлежит к одному из типов.

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