2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Ширяев, Элементарная теория вероятностей. Задача I.1.6
Сообщение04.03.2022, 08:32 


04/03/22
4
Помогите разобраться с решением у Ширяева. Там такое решение задачи I.1.6(а) на стр. 11 в "Вероятность в теоремах и задачах", 2014, МЦНМО.

Цитата:
6. (Разные интерпретации биномиальных коэффициентов $C^n_{N +n-1}$.) Показать, что число неупорядоченных выборок $[. . .]$ размера n при «выборе с возвращением», составленных из элементов множества $A$ с $|A| = N$, равно $C^n_{N +n-1}$.

Решение. (a) Построим взаимно однозначное соответствие между интересующими нас выборками и упорядоченными последовательностями из n единиц и $N - 1$ нулей, которых в силу задачи I.1.3(b) ровно $C^n_{N +n-1}$. Для этого занумеруем элементы множества A числами от 1 до N и припишем к каждой последовательности перед первым элементом и после последнего элемента по нулю. Тогда выборке, в которой i-й элемент A встречается $a_i$ раз, $i = 1, \dots , N$, ставится в соответствиепоследовательность, в которой между i-м и (i + 1)-м нулем стоит $a_i$ единиц. Обратное отображение аналогично.


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

Сам я так решаю эту задачу. Возьмем выборку неупорядоченную, упорядочим ее элементы по неубыванию: $a_1 \le a_2 \le \dots \le a_n$. Прибавим кажому элементу по единице. Тогда максимальный элемент будет равен $N+n-1$ и число таких выборок будет $C^n_{N+n-1}$, т.е. будет равно числу сочетаний из $N+n-1$ по $n$ без повторов.

Но как у Ширяева доказано, я не понимаю. Берем множество A например 1 2 3 4. И как приписывать по нулю в каждой последовательности? 0 1 0, 0 1 2 0, 0 1 2 3 0, .. ?

 Профиль  
                  
 
 Posted automatically
Сообщение04.03.2022, 10:18 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- наберите не только решение, но и условие обсуждаемой задачи;
- предложите собственные содержательные попытки ответа на вопрос.

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

 Профиль  
                  
 
 Posted automatically
Сообщение04.03.2022, 11:01 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 Профиль  
                  
 
 Re: Ширяев, Элементарная теория вероятностей. Задача I.1.6
Сообщение04.03.2022, 11:28 
Заслуженный участник


12/08/10
1646
ArtemK в сообщении #1549839 писал(а):
Возьмем выборку неупорядоченную, упорядочим ее элементы по неубыванию: $a_1 \le a_2 \le \dots \le a_n$. Прибавим кажому элементу по единице. Тогда максимальный элемент будет равен $N+n-1$ и число таких выборок будет $C^n_{N+n-1}$, т.е. будет равно числу сочетаний из $N+n-1$ по $n$ без повторов.

1.Откуда взялось $N+n-1$?
2.В сочетаниях элементы не повторяются, а в выборке могут.
ArtemK в сообщении #1549839 писал(а):
Берем множество A например 1 2 3 4.
А сколько элементов выбираем? Ответ от этого зависит и пример привести невозможно.

 Профиль  
                  
 
 Re: Ширяев, Элементарная теория вероятностей. Задача I.1.6
Сообщение04.03.2022, 17:05 


04/03/22
4
Null в сообщении #1549851 писал(а):
1.Откуда взялось $N+n-1$?

Пронумерованные элементы множества $A$ будут дополненны таким образом ровно $n-1$ элеметами. Из этого нового множества число сочетаний из $N+n-1$ по $n$ без повторов будет $C^n_{N+n-1}$
Null в сообщении #1549851 писал(а):
2.В сочетаниях элементы не повторяются, а в выборке могут.

Можно договорится считать и так. В моем доказательстве я говорю о сочетаниях. Предлагаю читать вместо "таких выборок", "сочетаний".
Null в сообщении #1549851 писал(а):
А сколько элементов выбираем? Ответ от этого зависит и пример привести невозможно

Выбираем скажем 5 элементов (с повторами). Не суть. Как отображение построить согласно Ширяеву?

 Профиль  
                  
 
 Re: Ширяев, Элементарная теория вероятностей. Задача I.1.6
Сообщение04.03.2022, 18:00 
Заслуженный участник


12/08/10
1646
ArtemK в сообщении #1549863 писал(а):
Пронумерованные элементы множества $A$ будут дополненны таким образом ровно $n-1$ элеметами. Из этого нового множества число сочетаний из $N+n-1$ по $n$ без повторов будет $C^n_{N+n-1}$
Пишите еще раз и подробно, до этого было написанно совсем не это.
ArtemK в сообщении #1549863 писал(а):
Как отображение построить согласно Ширяеву?
$N=4$
$n=5$
Путь есть последовательность из $0$ и $1$ длинны 8 из 5 единиц и 3 нулей. Например, $11011010$. Дописываем нули в конец и в начало: $0110110100$.
Тогда у нас количества 1 между нулями:$2,2,1,0$. Это соответствует набору из двух 1, двух 2, одной 3 и нулю 4 - $11223$

 Профиль  
                  
 
 Re: Ширяев, Элементарная теория вероятностей. Задача I.1.6
Сообщение05.03.2022, 10:37 


04/03/22
4
:facepalm: Да, у себя в доказательстве ошибся (не 1 прибавляем). Еще раз пробую:

Возьмем неупорядоченную выборку, упорядочим ее элементы по неубыванию: $a_1 \le a_2 \le \dots \le a_i \le \dots \le a_n$, пусть это $A$. Прибавим к кажому элементу $i-1$ начиная со второго: $a_1 < a_2 + 1 < \dots < a_i + i - 1 < \dots < a_n + n - 1$, пусть это $B$. Тогда это будет взаимнооднозначное отображение, т.к. инъектвно: $ x \ne y \implies x' \ne y', x,y \in A, x',y' \in B$, и сюрьективно: если строго упорядочить выборку $x' \in B$ и вычесть $i-1$ начиная со второго. Но мощность $B$ равна $C^n_{N +n-1}$, тогда этому же и мощность A.

По Ширяеву, понял. Благодарю! Вот пример для $N = 3$ и $n = 4$. $ (0 1 1 1 1 0 0 0) \to [1 1 1 1], (0 1 1 0 1 1 0 0) \to [1 1 2 2], (0 1 1 0 1 0 1 0) \to [1 1 2 3], \dots $

 Профиль  
                  
 
 Re: Ширяев, Элементарная теория вероятностей. Задача I.1.6
Сообщение05.03.2022, 12:03 
Заслуженный участник


12/08/10
1646
ArtemK в сообщении #1549874 писал(а):
Возьмем неупорядоченную выборку, упорядочим ее элементы по неубыванию: $a_1 \le a_2 \le \dots \le a_i \le \dots \le a_n$, пусть это $A$. Прибавим к кажому элементу $i-1$ начиная со второго: $a_1 < a_2 + 1 < \dots < a_i + i - 1 < \dots < a_n + n - 1$, пусть это $B$. Тогда это будет взаимнооднозначное отображение, т.к. инъектвно: $ x \ne y \implies x' \ne y', x,y \in A, x',y' \in B$, и сюрьективно: если строго упорядочить выборку $x' \in B$ и вычесть $i-1$ начиная со второго. Но мощность $B$ равна $C^n_{N +n-1}$, тогда этому же и мощность A.
Да, это правда, но доказывать биективность, например на экзамене, надо бы более подробно.

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

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



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

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


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

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