Ширяев, Элементарная теория вероятностей. Задача I.1.6

[ArtemK]

Помогите разобраться с решением у Ширяева. Там такое решение задачи 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, .. ?

[Pphantom]

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

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

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

[Pphantom]

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

[Null]

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.

А сколько элементов выбираем? Ответ от этого зависит и пример привести невозможно.

[ArtemK]

Null в сообщении #1549851 писал(а):

1.Откуда взялось $N+n-1$?

Пронумерованные элементы множества $A$ будут дополненны таким образом ровно $n-1$ элеметами. Из этого нового множества число сочетаний из $N+n-1$ по $n$ без повторов будет $C^n_{N+n-1}$

Null в сообщении #1549851 писал(а):

2.В сочетаниях элементы не повторяются, а в выборке могут.

Можно договорится считать и так. В моем доказательстве я говорю о сочетаниях. Предлагаю читать вместо "таких выборок", "сочетаний".

Null в сообщении #1549851 писал(а):

А сколько элементов выбираем? Ответ от этого зависит и пример привести невозможно

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

[Null]

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$

[ArtemK]

Да, у себя в доказательстве ошибся (не 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 $

[Null]

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.

Да, это правда, но доказывать биективность, например на экзамене, надо бы более подробно.