2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Нестандартная выборка шаров
Сообщение26.04.2015, 20:45 


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

 Профиль  
                  
 
 Re: Нестандартная выборка шаров
Сообщение26.04.2015, 22:06 
Заслуженный участник


27/04/09
28128
Пусть множество цветов — $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 


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

 Профиль  
                  
 
 Re: Нестандартная выборка шаров
Сообщение27.04.2015, 18:57 
Заслуженный участник


27/04/09
28128
Спору нет, некоторые комбинаторные числа быстрее находить не ища и не используя «прямую» формулу. Моя, кстати, почти дословно переводится в код. Надо только вместо подмножеств $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