Комбинаторика. Раскладки.

[oxid]

Разбираюсь с темой раскладки по Виленкину, непонятен такой вопрос, помогите разобраться.
Дается следующее - число способов распределения n различных предметов по m различным ящикам с учетом порядка в ящиках равно $A_{n+m-1}^n$

Но я никак не пойму почему не подходит такая формула - $n^m$ Вроде все возможные раскладки предметов в ней учтены?

[provincialka]

Ваша формула вообще непонятная. Обычно $n^m$ означает, что $m$ раз совершились события, у каждого из которых $n$ вариантов. И какое же событие имеет столько вариантов?

[oxid]

Ну как раз разложить 5 яблок по 3 пакетам ( пакет может быть пустым).. Т.е первое можно положить 3мя способами, второе тоже тремя и тд.
Это число способов забить все бильярдные шары. Т.е каждый шар может быть в любой из 6 луз. При этом все шары и лузы отличимы

[Otta]

oxid
Число размещений с повторениями:"число способов распределения n различных предметов по m различным ящикам с учетом порядка в ящиках равно $\bar A_{n+m-1}^n$" как раз и равно $n^m$.

oxid в сообщении #784258 писал(а):

Ну как раз разложить 5 яблок по 3 пакетам ( пакет может быть пустым).

В этой задаче считается число сочетаний с повторениями. Поскольку порядок внутри ящика не важен.

[oxid]

Извиняюсь, мой пример неверный. Да, яблоки и пакеты должны быть конечно перенумерованы.

Но тем не менее в учебнике Виленкина именно та формула что я написал - размещение без повторений. Если интересно - это 3 абзац, страница 106.

[Otta]

oxid в сообщении #784261 писал(а):

Но тем не менее в учебнике Виленкина именно та формула что я написал - размещение без повторений.

Размещение без повторений - это вообще третья штука. Воспроизведите полностью цитату, будьте добры.

[oxid]

Цитата:

Вообще, если имеется n различных предметов, то число способов распределения этих предметов по m различным ящикам с учетом порядка их расположения в ящиках равно $A_{n+m-1}^n$

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

[Otta]

oxid в сообщении #784263 писал(а):

Цитата:

Вообще, если имеется n различных предметов, то число способов распределения этих предметов по m различным ящикам с учетом порядка их расположения в ящиках равно $A_{n+m-1}^n$

Правильно. Нет, сорри, $n^m$ оно не равно, конечно.
provincialka права, совершенно дурацкая формула.

[oxid]

Что-то не похоже ;)

n=4, m=2

$n^m=16$

$\frac{n!}{(n+m-1-n)!} = 4! = 24$

[Whitaker]

Цитата:

Вообще, если имеется n различных предметов, то число способов распределения этих предметов по m различным ящикам с учетом порядка их расположения в ящиках равно $A_{n+m-1}^n$

А что тут непонятного?
Допустим, что предметы неразличимы, но ящики различимы. Тогда способов всего $C_{n+m-1}^{n}$. Но для каждой расстановки предметы можно переставлять $n!$ способами (здесь уже учитываем, что предметы различимы). По принципу произведения получаете то, что нужно.

[oxid]

Спасибо, такое рассуждение мне понятно ;)
Но остается вопрос про степенную формулу - почему она неверна?

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

До конца все ранво не понятно как из этой формулы плавно перейти к правильной. Ну и фиг с ним..

[Otta]

oxid в сообщении #784267 писал(а):

Но остается вопрос про степенную формулу - почему она неверна?

Да верна она, просто для другой задачи.
Еле выдумала под утро более-менее естественную,

(Оффтоп)

сапсем башка не варит уже. Так что если что - больно не бить и тапками не кидаться.

В магазине $n$ касс, $m$ покупателей, которые выбирают кассы совершенно наудачу.
(1) Сколькими способами они могут осуществить свой выбор?
(2) Сколькими способами они могут встать в очередь в эти кассы?

[provincialka]

Otta, по-моему, у вас обозначения перепутались. Я бы еще поняла, если бы ТС предложил формулу $m^n$. Для каждого из предметов есть $m$ вариантов, $m$ ящиков. Здесь только порядок не учитывается.
Но что может означать формула $n^m$? Что для каждого ящика выбирается любой предмет? Совсем уж странно.

[Otta]

provincialka в сообщении #784376 писал(а):

Но что может означать формула $n^m$?

Число размещений $m$ шаров по $n$ ящикам с повторениями. Все правильно, хотя я никогда не могу запомнить сама, кто в какой степени и каждый раз считаю заново.
Это именно упорядоченные наборы длины $m$ $(*,*,\ldots,*)$, где $i$-e место соответствует $i$-му шарику, и содержит информацию о ящике, в который он был положен. Таким образом, на каждом месте независимо друг от друга могут стоять числа от $1$ до $n$.

[provincialka]

oxid в сообщении #784252 писал(а):

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

Otta в сообщении #784502 писал(а):

Число размещений $m$ шаров по $n$ ящикам с повторениями.

Сравните! Обозначения разные.