2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Равносильность двух комбинаторных задач
Сообщение13.04.2019, 15:29 


07/08/16
328
Задача 1.
Пусть имеется $M$ шаров из которых мы извлекаем $n$ шаров ($ 0 \leqslant n \leqslant M$). Занумеруем шары от $1$ до $M$. Каждое извлечение мы можем представить числом $a_i$, где $a_i$ означает извлечённый шар, а $i$ означает номер шага извлечения. Значит, если мы извлекаем $n$ шаров, то имеем некоторую конечную последовательность $(a_1,...,a_n)$.
Нам требуется определить мощность множества $\Omega_1 = \left\lbrace(a_1,..., a_n) | \forall i \rightarrow 1 \leqslant a_i \leqslant M\right\rbrace$, состоящего из всевозможных конечных последовательностей такого типа.
Возможны 4 варианта -
1.Упорядоченная выбора с возвращением, тогда $card(\Omega_1) = M^n$
2.Неупорядоченная выборка с возвращением, тогда $card(\Omega_1) =$ C $(M+n-1,n)$.
3.Упорядоченная выборка без возвращением, тогда $card(\Omega_1) = A(M,n)$.
4.Неупорядоченная выборка без возвращением, тогда $card(\Omega_1) =$ C $ С(M,n)$.
Эти 4 факта доказывать я умею, значит эту задача считаем решенной.

Задача 2.
Пусть имеется $M$ ячеек (пронумерованных от $1$ до $M$) и $n$ дробинок, нам необходимо поместить эти дробинки в ячейки и подсчитать, сколькими способами это можно сделать.
Тут мы имеем $\Omega_2 = \left\lbrace(a_1,..., a_n) | \forall i \rightarrow 1 \leqslant a_i \leqslant M\right\rbrace$, где $a_i$ указывает номер ячейки, куда была помещена дробинка, а $i$ идентифицирует саму дробинку.
Под запретом далее понимаем тот факт, что в ячейке не может быть более 1 дробинки.
Имеем также 4 случая -
1.Различимые дробинки помещаются в ячейки без запрета.
2.Неразличимые дробинки помещаются в ячейки без запрета.
3.Различимые дробинки помещаются в ячейки с запретом.
4.Неразличимые дробинки помещаются в ячейки с запретом.
Установим биективное соотношение между этими задачами.

В первой мы имеем $M$ шаров, во второй - $M$ ячеек. Значит строим биекцию
1."номер извлеченного шара" $\leftrightarrow$ "ячейка, куда была помещена текущая дробинка".
2."номер шага извлечения шара" $\leftrightarrow$ "номер, идентифицирующий текущую дробинку".
Проверяем, что мы получили в обоих случаях биективное отображение. (Проверил ручками - правда биекция).
При этом неупорядоченные последовательности из первой задачи - неразличимые дробинки из второй, упорядоченные - различимые, наличие "возвращения" - отсутствие запрета, отсутствие "возвращения" - наличие запрета.
Значит каждой конечной последовательности из 2-й задачи отвечает конечная последовательность из 1-й задачи (ведь у нас есть соотвествие и между номером и между стоящим под этим номером элементом), значит, $card(\Omega_1) = card(\Omega_2)$, соответственно для всех случаев 1-4 второй задачи мы уже имеем решение.

Теперь пусть есть
Задача 3.
Сколько существует бинарных конечных последовательностей длины $n$?
Решение.
Я говорю о - так мы просто имеем $n$ нуликов (наша первая конечная последовательность), каждый из которых - ячейка для нашей единицы (дробинки). Значит для каждого количества единиц (дробинок) ($k = 1... k=n$) мы имеем просто задачу 2, случай с запретом и неразличимыми дробинками, тут же получаю ответ.
Вопросы:
1.Корректно ли определять равносильность между Задачами 2 и 1 так,как делаю это я? Есть ли здесь "махание руками"?
2.Корректно ли Задача 3 сведена к 2? Приняли бы вы такое решение? (У меня никто ничего принимать не будет, мне просто понять, правильное ли здесь применение данной конструкции).

P.S.Это всё - по мотивам книги Ширяев, Вероятность - 1, Глава 1, Параграф 1. Я не уверен, что верно понимаю те места, где он просто пишет "очевидно, что".

 Профиль  
                  
 
 Re: Равносильность двух комбинаторных задач
Сообщение13.04.2019, 20:24 
Заслуженный участник


23/07/08
10626
Crna Gora
Sdy в сообщении #1387476 писал(а):
Корректно ли определять равносильность между Задачами 2 и 1 так,как делаю это я?
Да, корректно.
Sdy в сообщении #1387476 писал(а):
Есть ли здесь "махание руками"?
Да, есть, вот тут:
Sdy в сообщении #1387476 писал(а):
Проверил ручками - правда биекция
:-)
Sdy в сообщении #1387476 писал(а):
Корректно ли Задача 3 сведена к 2? Приняли бы вы такое решение?
Мне кажется, тут Вы сильно усложнили. Конечной бинарной последовательности длины $n$ в терминах Вашей первой задачи соответствует упорядоченная последовательность $n$ извлечений двух шаров ($0$ и $1$) с возвращением. В терминах второй задачи — распределение $n$ различимых дробинок по двум ячейкам ($0$ и $1$) без запрета.

Ещё я бы не требовал $n\leqslant M$ изначально. Для вариантов с возвращением/без запрета это очевидно. Но и для вариантов без возвращения/с запретом тоже не требовал бы. Например: сколько существует различных способов разложить $7$ дробинок по $4$ ячейкам так, чтобы в каждой ячейке было не больше одной дробинки? Ответ: $0$. Формулы выдадут такой результат автоматически: $C^7_4=0$.

 Профиль  
                  
 
 Re: Равносильность двух комбинаторных задач
Сообщение14.04.2019, 19:04 
Заслуженный участник


23/07/08
10626
Crna Gora
Я понимаю, что именно требование $n\leqslant M$ (ничем, по-моему, не мотивированное) и увело Вас в сторону от самого естественного варианта сопоставления задач.

 Профиль  
                  
 
 Re: Равносильность двух комбинаторных задач
Сообщение24.04.2019, 12:39 


07/08/16
328
svv, спасибо за ответ.
На самом деле, я просто сам проделал то что делает в своей книге Ширяев, только в том виде, в каком я это понимаю и без всяких "очевидно, что". А у него как раз было ограничение $n \leqslant m$. (Я пока не понял мотивировку наличия данного ограничения, но оставил, как было в книге).
Спасибо за указание возможности различного подхода к задаче 3, в действительности, если бы меня спросили о том, как ее решать, я бы просто воспользовался правилом умножения и мгновенно получил $2^n$ (то есть, фактически воспользовался бы вашим первым предложением с 2мя шарами). Просто хотелось понять, корректно ли рассуждаю я именно при таком подходе.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Gg322


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group