2014 dxdy logo

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

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




 
 Нестандартная выборка шаров
Сообщение26.04.2015, 20:45 
На одном из форумов всретилась нестандарная задача, которую можно переформулировать так. В ящике лежат разные (пронумерованные) шары трех цветов (все количества известны). Катя, Женя и Света выбирают по одному шару, причем Катя выбирает красный, Женя желтый, а Света - синий. Сколько различных вариантов выбора существует? Вариант определяется по 3 парам: номер+хозяйка.
Это стандартная простая задача. А вот нестандартное расширение.
Цвета те же, но шары могут быть двух и трехцветными (их количества тоже известны). Катя выбирает шар, один из цветов которого - красный (1-2-3х цветный, неважно). Женя и Света поступают аналогично. Сколько теперь вариантов выбора шаров?
Задачу я просчитал но интересно, есть ли какие формулы, когда цветов/девушек больше 3х. Что-то типа включений-исключений.

 
 
 
 Re: Нестандартная выборка шаров
Сообщение26.04.2015, 22:06 
Пусть множество цветов — $C$, а распределение шаров задано функцией $f\colon 2^C\to\mathbb Z_{\geqslant0}$; $f(\varnothing)$ нам не важна, так что можно принять её равной чему угодно.

Дополнительные определения:
Скобка Айверсона $[\text{истина}] \equiv 1$, $[\text{ложь}] \equiv 0$.
Нисходящая степень $a^{\underline n} \equiv \prod_{i=0}^{n-1} (a-i)$, откуда $a^{\underline0} = 1$ и $a^{\underline n} = 0, n>a$.

Количество интересующих комбинаторных штучек равно$$\sum_{g\colon C\to2^C} \prod_{D\subset C} [d\subset D]\; f(D)^{\underline{\lvert d\rvert}},\quad d = g^{-1}(D).$$
Приземлять дальше лень.

-- Пн апр 27, 2015 00:14:05 --

Если нужны без учёта нумерации, $f(D)^{\underline{\lvert d\rvert}}$ заменяется на $\binom{f(D)}{\lvert d\rvert}$.

Надеюсь, какой-нибудь честный человек скажет, что я нигде не ошибся.

 
 
 
 Re: Нестандартная выборка шаров
Сообщение27.04.2015, 08:13 
Автор исходной задачи написал, что она была на контрольной. Не думаю, что имелось в виду это (см выше). Для меня это просто набор значков :-)
Я подумал - а вдруг есть "приземленная" или рекуррентная формула для расчета.
Кстати, на раз сталкивался с ситуацией, когда конкретный расчет в физике, в теории вероятностей или комбинаторике гораздо проще и быстрее запрограммировать, чем найти/вывести и посчитать точную формулу. Значит ли это, что программирование идет в массы? Физики, инженеры давно его осваивают. На очереди экономисты, финансисты, менеджеры?

 
 
 
 Re: Нестандартная выборка шаров
Сообщение27.04.2015, 18:57 
Спору нет, некоторые комбинаторные числа быстрее находить не ища и не используя «прямую» формулу. Моя, кстати, почти дословно переводится в код. Надо только вместо подмножеств $C$ использовать битовые шкалы, вместо функций $g$ перебирать всевозможные массивы длины $|C|$ и т. п..

zer0 в сообщении #1008407 писал(а):
Для меня это просто набор значков :-)
А какие ещё значки непонятны?
$2^M$ — это множество всех подмножеств $M$.
$f^{-1}(M)$ — прообраз множества $M$ — это $\{x : f(x)\in M\}$.

 
 
 [ Сообщений: 4 ] 


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