Вопрос по перестановкам с повторениями

[Rubik]

Здравствуйте, форумчане! Есть следующий вопрос, хотел бы получить посильную помощь:

Имеется набор всех возможных перестановок с повторениями из чисел $\{a_i\}_{i=1}^n$ где число $a_i$ встречается $k_i$ раз. Число $a_i$ называется выигрышным по отношению к конкретной перестановке и натуральному числу $Q$ (кворуму), если оно входит в неё не менее $Q$ раз и его $Q$-е вхождение находится раньше $Q$-го вхождения любого другого числа. Для каждого числа необходимо найти вероятность того, что оно будет выигрышным в наугад взятой перестановке.

Мои рассуждения: если $Q > k_i $ для всех $i$, то выигрышных чисел не будет. Если только одно число встречается хотя бы $ Q$, то оно будет выигрышным во всех перестановках. Если несколько чисел встречаются одинаковое, не меньшее чем $Q$ количество раз, вероятности быть выигрышными для них равны.

Однако, я не могу придумать как в общем случае подсчитать вероятность выигрыша, если мы имеем несколько чисел, которые встречаются больше чем $Q$ раз но при этом не одинаково часто. Буду благодарен за любую подсказку. Спасибо.

[Yadryara]

Rubik в сообщении #1193523 писал(а):

Число $a_i$ называется выигрышным по отношению к конкретной перестановке и натуральному числу $Q$ (кворуму), если оно входит в неё не менее $Q$ раз и его $Q$-е вхождение находится раньше $Q$-го вхождения любого другого числа.

Уточните, пожалуйста, что значит "находится раньше".

[VAL]

Yadryara в сообщении #1193530 писал(а):

Уточните, пожалуйста, что значит "находится раньше".

Это значит, что Q-е вхождение данного числа встретится первым при просмотре перестановки слева направо.
Пусть, например $n=12, a_1=1, a_2=2, a_3=3, k_1=k_2=k_3=4, Q=3$.
Тогда $1$ явояется выгрышной для перестановки $(2,1,3,1,2,1,3,3,2,3,2,1)$ .
(По крайней мере, я так понял )

Rubik Вы не отметили еще один очевидный случай - $Q=1$.
Тогда искомая вероятность для $a_i$ равна $\frac{k_i}n$

[Yadryara]

VAL в сообщении #1193534 писал(а):

Это значит, что Q-е вхождение данного числа встретится первым при просмотре перестановки слева направо.
Пусть, например $n=12, a_1=1, a_2=2, a_3=3, k_1=k_2=k_3=4, Q=3$.
Тогда $2$ явояется выгрышной для перестановки $(2,1,3,1,2,1,3,3,2,3,2,1)$ .

Почему же? Если смотреть слева направо, то $1$ выигрышна. Ведь она раньше всех встретится в 3-й раз: (2, 1, 3, 1, 2, 1, 3, 3, 2, 3, 2, 1).

[VAL]

Yadryara в сообщении #1193535 писал(а):

VAL в сообщении #1193534 писал(а):

Это значит, что Q-е вхождение данного числа встретится первым при просмотре перестановки слева направо.
Пусть, например $n=12, a_1=1, a_2=2, a_3=3, k_1=k_2=k_3=4, Q=3$.
Тогда $2$ явояется выгрышной для перестановки $(2,1,3,1,2,1,3,3,2,3,2,1)$ .

Почему же? Если смотреть слева направо, то $1$ выигрышна. Ведь она раньше всех встретится в 3-й раз: (2, 1, 3, 1, 2, 1, 3, 3, 2, 3, 2, 1).

Писал практически ночью. Было темно. Очепятка.

[Rubik]

VAL в сообщении #1193534 писал(а):

Yadryara в сообщении #1193530 писал(а):

Уточните, пожалуйста, что значит "находится раньше".

Это значит, что Q-е вхождение данного числа встретится первым при просмотре перестановки слева направо.
Пусть, например $n=12, a_1=1, a_2=2, a_3=3, k_1=k_2=k_3=4, Q=3$.
Тогда $1$ явояется выгрышной для перестановки $(2,1,3,1,2,1,3,3,2,3,2,1)$ .
(По крайней мере, я так понял )

Да, именно это я и имел в виду под "раньше".

VAL в сообщении #1193534 писал(а):

Rubik Вы не отметили еще один очевидный случай - $Q=1$.
Тогда искомая вероятность для $a_i$ равна $\frac{k_i}n$

Спасибо, действительно не заметил.

[crazy_taxi_driver]

Предлагаю обозначить $M=\sum_1^n k_i$. Тогда

VAL в сообщении #1193534 писал(а):

$Q=1$. ...вероятность для $a_i$ равна $\frac{k_i}n$

$k_i/M$

свой набросок решения стёр - не верно, надо внимательнее..

[Yadryara]

crazy_taxi_driver в сообщении #1193601 писал(а):

Предлагаю обозначить $M=\sum_1^n k_i$

Лучше $s=\sum_1^n k_i$. Сумма всё-таки. Ещё предлагаю принять для определённости $a_1 \leqslant a_2 \leqslant a_3\; ...$

Ещё один частный случай. Все числа встречаются не меньше, чем $Q$ раз. $n=2; k_1=Q$. Тогда

$$P(a_1) =\frac{C_{2Q-1}^{k_1}}{C_s^{k_1}}$$

[crazy_taxi_driver]

Rubik
Не, а всё-таки я, кмк, могу записать громоздкий ответ (и да, задача не прямолинейная).. Другое дело что Вы, кроме анализа тривиальных случаев, не попытались (на мой взгляд) решить свою задачу. Как Ваши успехи?

Я рассматривал все равновозможные перестановки, их $M!$ (как длина перестановки, или число ячеек, и пр. - мне гораздо больше нравится $M$ чем $s$). Дальше я выделял первые $Q$ из чисел $a_1$, выбирал из всех оставшихся чисел сколько нужно, и рассовывал их в промежутки между первыми $Q$. Тут внимательно надо - порядок внутри промежутка (=ячейки) важен. Остальные - аналогично вправо, т.е. после тех $Q$ штук. Вам нужно понять, сколькими способами все эти шаги можно сделать, на что нужно домножить и пр..