Задачи по комбинаторике

SiO2 · Сообщение **SiO2** » 22 окт 2009, 11:55

alexy.74 писал(а):Source of the post
Сколькими комбинациями можно числа образующие число 7 разложить по 4 ящикам.Ответ

B книге B.Феллера это называется числом различимых размещений или числом различных решений уравнения:
r₁+r₂+...+r_n=r
обозначается A_r,n= $C^{n-1}_{n+r-1}$
Даже специально ради этой задачи туда заглянул.)

alexy.74 · Сообщение **alexy.74** » 22 окт 2009, 12:10

SiO2 писал(а):Source of the post
alexy.74 писал(а):Source of the post
Сколькими комбинациями можно числа образующие число 7 разложить по 4 ящикам.Ответ

B книге B.Феллера это называется числом различимых размещений или числом различных решений уравнения:
r₁+r₂+...+r_n=r
обозначается A_r,n= $C^{n-1}_{n+r-1}$
Даже специально ради этой задачи туда заглянул.)

если ответ получается 10!/3!/7!=120 , то не верно так как я вручную перещитал комбинации для верности.

jarik · Сообщение **jarik** » 22 окт 2009, 12:19

120 получится.
Вручную пересчитал? :blink:

Вспомнил ситуацию, устроился к нам новый начальник БОТиЗа, молодой ещё такой сосунок, только только окончил универ, два месяца стажировки и его родственник дал ему руководящую должность. Всё бы ничего, но человека не научили в школе считать. Дык вот, сейчас приняли новый закон o начислении дополнительного отпуска тем, кто работает во вредных условиях труда. To есть платить за фактически отработанное время. Люди стали подмечать, что как-то странно мало становился отпуск. Пошли разбираться, на вопрос почему, он отвечал так, у меня посчитал компьютер. Один нашёлся и говорит, a мой компьютер посчитал 90 дней, и чо? Подняли ведомости за год, посчитали, ать, оказался не прав новый служащий...

Самоед

alexy.74 писал(а):Source of the post
SiO2 писал(а):Source of the post
alexy.74 писал(а):Source of the post
Сколькими комбинациями можно числа образующие число 7 разложить по 4 ящикам.Ответ

B книге B.Феллера это называется числом различимых размещений или числом различных решений уравнения:
r₁+r₂+...+r_n=r
обозначается A_r,n= $C^{n-1}_{n+r-1}$
Даже специально ради этой задачи туда заглянул.)

если ответ получается 10!/3!/7!=120 , то не верно так как я вручную перещитал комбинации для верности.

Нукося, вручную:
4111 - 4 комб.
3211 - 12 комб.
2221 - 4 комб.
Итого -20 комбинаций.
Ведь нужно разложить по всем 4 ящикам, a не по 1или 2 или 3 или 4 ящикам.
Про числа, образующие число 7 тоже неопределенно сказано (то ли сложением, то ли умножением, то ли логарифмированием), то ли натуральными, то ли действительными. Проще и понятнее - разложить 7 шаров по 4 ящикам. B каждый ящик класть не менее 1 шара ( иначе не разложение будет, a произвол : этому дали, a тому - не дали.).

alexy.74 · Сообщение **alexy.74** » 22 окт 2009, 16:48

Самоед писал(а):Source of the post B каждый ящик класть не менее 1 шара ( иначе не разложение будет, a произвол : этому дали, a тому - не дали.).

вот где ошибка

SiO2 · Сообщение **SiO2** » 22 окт 2009, 17:20

alexy.74 писал(а):Source of the post
вот где ошибка

Ошибка у кого? Алгоритм перебора в студию, a так же границы применимости вашего выражения, ибо, например, для (1,1) или (1,2) оно точно не работает.

alexy.74 · Сообщение **alexy.74** » 22 окт 2009, 17:22

Пример .Купили 7 шт пирожных одного сорта.Это означает -все 7 шаров в один ящик. У вас это не получается.Условиями это не запрещено.

SiO2 · Сообщение **SiO2** » 23 окт 2009, 20:19

alexy.74 писал(а):Source of the post
Пример .Купили 7 шт пирожных одного сорта.Это означает -все 7 шаров в один ящик. У вас это не получается.Условиями это не запрещено.

Почему?
n=1
r=7
$C^{n-1}_{n+r-1}$ = $C^{r}_{n+r-1}$ = $C^{7}_{7}$ =1
Я почему спрашиваю алгоритм пересчета -- перебрать все комбинации не так просто (численно).

alexy.74 · Сообщение **alexy.74** » 24 окт 2009, 08:13

комбинации
0007-4
0016-12
0025-12
0034-12
0124-24
0115-12
0133-12
0223-12
1222-4
1123-12
1114-4
Да, я не прав .Ответ 120.

СергейП

alexy.74 писал(а):Source of the post комбинации
0007-4
0016-12
0025-12
0034-12
0124-24
0115-12
0133-12
0223-12
1222-4
1123-12
1114-4
Да, я не прав .Ответ 120.

Считать вручную - неплохая тренировка, но мало похоже на решение.
Можно решать прямо по формуле $C^{n-1}_{n+r-1}$ , но лучше понять, как эта формула выводится. Вот схема (для этой задачи):
Имеем 7 предметов (неразличимых) и 4 ящика (различимых). Рассмотрим 7+4-1=10 битный двоичный код из 7 единичек и 3 нулей. Нули - разделители между ящиками, a 1 - предметы. Каждому способу распределения 7 предметов по 4 ящикам соответствует уникальный двоичный код и наоборот.
Например, 3 предмета в 1-ом ящике и по 2 в 3-ем и 4-ом - это 1110011011, a код 0110111011 - это 3 предмета в 3-ем ящике и по 2 во 2-ом и 4-ом.
Тогда понятно, что искомое число равно количеству способов выбора 3-х мест (для 0) из 10, т.e.
$C^{3}_{10}=C^{4-1}_{7+4-1}=120$
Методика легко обобщается на любое число предметов и ящиков.

yourdomain.com