2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 00:52 
oxid
Число размещений с повторениями:"число способов распределения n различных предметов по m различным ящикам с учетом порядка в ящиках равно $\bar A_{n+m-1}^n$" как раз и равно $n^m$.
oxid в сообщении #784258 писал(а):
Ну как раз разложить 5 яблок по 3 пакетам ( пакет может быть пустым).

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 00:57 
Извиняюсь, мой пример неверный. Да, яблоки и пакеты должны быть конечно перенумерованы.

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 01:01 
oxid в сообщении #784261 писал(а):
Но тем не менее в учебнике Виленкина именно та формула что я написал - размещение без повторений.

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 01:03 
Цитата:
Вообще, если имеется n различных предметов, то число способов распределения этих предметов по m различным ящикам с учетом порядка их расположения в ящиках равно $A_{n+m-1}^n$

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 01:04 
oxid в сообщении #784263 писал(а):
Цитата:
Вообще, если имеется n различных предметов, то число способов распределения этих предметов по m различным ящикам с учетом порядка их расположения в ящиках равно $A_{n+m-1}^n$

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 01:06 
Что-то не похоже ;)

n=4, m=2

$n^m=16$

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 01:09 
Аватара пользователя
Цитата:
Вообще, если имеется n различных предметов, то число способов распределения этих предметов по m различным ящикам с учетом порядка их расположения в ящиках равно $A_{n+m-1}^n$
А что тут непонятного?
Допустим, что предметы неразличимы, но ящики различимы. Тогда способов всего $C_{n+m-1}^{n}$. Но для каждой расстановки предметы можно переставлять $n!$ способами (здесь уже учитываем, что предметы различимы). По принципу произведения получаете то, что нужно.

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 01:12 
Спасибо, такое рассуждение мне понятно ;)
Но остается вопрос про степенную формулу - почему она неверна?

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

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 01:54 
oxid в сообщении #784267 писал(а):
Но остается вопрос про степенную формулу - почему она неверна?

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

(Оффтоп)

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

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

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 13:44 
provincialka в сообщении #784376 писал(а):
Но что может означать формула $n^m$?

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

 
 
 
 Re: Комбинаторика. Раскладки.
Сообщение04.11.2013, 14:16 
Аватара пользователя
oxid в сообщении #784252 писал(а):
число способов распределения n различных предметов по m различным ящикам

Otta в сообщении #784502 писал(а):
Число размещений $m$ шаров по $n$ ящикам с повторениями.
Сравните! Обозначения разные.

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group