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

@_Kate_ · Регистрация: 12.09.2012

Author24 — интернет-сервис помощи студентам

Сколькими способами можно разместить 10 одинаковых открыток в 4 почтовых ящиках так, чтобы: а) не было пустых ящиков б) во втором ящике было 3 открытки.
предполагаю что на первый вариант : 10*9*8*7=5040 вариантов.
над вторым вариантом затрудняюсь, прошу помощи )

zer0mail · 08.09.2013, 19:27

А если есть только 4 открытки, какой будет ответ для а) ?

@_Kate_ · 08.09.2013, 19:31 **[ТС]**

C из 4 по 4 = 1. Верно?
1 по тому что в условии написано чтобы не было пустых ячеек следовательно 1 вариант.

@Heidegger · 08.09.2013, 19:34

Сообщение от _Kate_

предполагаю что на первый вариант : 10*9*8*7=5040 вариантов.

Не совсем: метод шаров и перегородок для n = 10 открыток и k = 4 ящиков даёт ответ:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{n-1}^{k-1} = {C}_{9}^{3} = \frac{9!}{3!\cdot 6!} = \frac{7\cdot 8\cdot 9}{1\cdot 2\cdot 3} = 7\cdot 4\cdot 3 = 84$

метод шаров и перегородок

Задача. Есть k ящиков и n >= k однаковых шаров. Сколькими способами можно разложить шары по ящикам так, чтобы ни один ящик не оказался пустым?

Решение: Давайте определять раскладку так: выложим шары в ряд и поставим между ними k–1 перегородку. То, что слева от первой перегородки, положим в первый ящик, между первой и второй – во второй, ..., то, что справа от последней – в последний, k-й ящик. Ящик будет пустым, только если две перегородки стоят рядом не разделенные шарами, либо перегородка стоит с краю, левее или правее всех шаров. Так давайте это запретим! Пусть на каждое из n-1 мест между n шарами можно поставить не более одной из k–1 перегородок. То есть, из n–1 мест надо будет выбрать k–1, куда мы ставим перегородки. Отсюда получаем ответ: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{n-1}^{k-1}$ .

Задача. А сколько способов разложить шары, если могут быть пустые ящики?

Решение: Если определять раскладку так же, ставя между шарами k–1 перегородку, то ограничений уже не будет: шары и перегородки можно ставить в произвольном порядке. Давайте считать, что у нас расставлено в ряд n+k–1 объектов: n из них шары, а остальные – перегородки. Тогда раскладка будет определяться тем, на каких местах какие объекты стоят. Из n+k–1 мест можно выбрать n мест для шаров $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{n+k-1}^{n}$ способами, или: k–1 место для перегородок $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{n+k-1}^{k-1}$ способами. Эти числа равны и оба являются ответом.

@_Kate_ · 08.09.2013, 19:39 **[ТС]**

так это диофантовое уравнение получаеться что x1+x2+x3+x4=10 тоесть решение уравнения и есть ответ?
следовательно форма приведеная выше верна?

@Heidegger · 08.09.2013, 20:10

Сообщение от _Kate_

так это диофантовое уравнение получаеться что x1+x2+x3+x4=10 тоесть решение уравнения и есть ответ?

Да, количество вариантов равно числу различных решений уравнения x₁ + x₂ + x₃ + x₄ = 10 в целых числах (при условии x₁, x₂, x₃, x₄ > 0).

проверка в Mathematica

Matlab M

s = FindInstance[{x1 + x2 + x3 + x4 == 10, x1 > 0, x2 > 0, x3 > 0, x4 > 0},
                 {x1, x2, x3, x4}, Integers, 100];
 
Length[s]
 
> 84
 
{x1, x2, x3, x4} /. s
 
> {{1, 1, 1, 7}, {1, 1, 2, 6}, {1, 1, 3, 5}, {1, 1, 4, 4}, {1, 1, 5, 3}, {1, 1, 6, 2}, {1, 1, 7, 1},
   {1, 2, 1, 6}, {1, 2, 2, 5}, {1, 2, 3, 4}, {1, 2, 4, 3}, {1, 2, 5, 2}, {1, 2, 6, 1}, {1, 3, 1, 5},
   {1, 3, 2, 4}, {1, 3, 3, 3}, {1, 3, 4, 2}, {1, 3, 5, 1}, {1, 4, 1, 4}, {1, 4, 2, 3}, {1, 4, 3, 2},
   {1, 4, 4, 1}, {1, 5, 1, 3}, {1, 5, 2, 2}, {1, 5, 3, 1}, {1, 6, 1, 2}, {1, 6, 2, 1}, {1, 7, 1, 1},
   {2, 1, 1, 6}, {2, 1, 2, 5}, {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 1, 5, 2}, {2, 1, 6, 1}, {2, 2, 1, 5},
   {2, 2, 2, 4}, {2, 2, 3, 3}, {2, 2, 4, 2}, {2, 2, 5, 1}, {2, 3, 1, 4}, {2, 3, 2, 3}, {2, 3, 3, 2},
   {2, 3, 4, 1}, {2, 4, 1, 3}, {2, 4, 2, 2}, {2, 4, 3, 1}, {2, 5, 1, 2}, {2, 5, 2, 1}, {2, 6, 1, 1},
   {3, 1, 1, 5}, {3, 1, 2, 4}, {3, 1, 3, 3}, {3, 1, 4, 2}, {3, 1, 5, 1}, {3, 2, 1, 4}, {3, 2, 2, 3},
   {3, 2, 3, 2}, {3, 2, 4, 1}, {3, 3, 1, 3}, {3, 3, 2, 2}, {3, 3, 3, 1}, {3, 4, 1, 2}, {3, 4, 2, 1},
   {3, 5, 1, 1}, {4, 1, 1, 4}, {4, 1, 2, 3}, {4, 1, 3, 2}, {4, 1, 4, 1}, {4, 2, 1, 3}, {4, 2, 2, 2},
   {4, 2, 3, 1}, {4, 3, 1, 2}, {4, 3, 2, 1}, {4, 4, 1, 1}, {5, 1, 1, 3}, {5, 1, 2, 2}, {5, 1, 3, 1},
   {5, 2, 1, 2}, {5, 2, 2, 1}, {5, 3, 1, 1}, {6, 1, 1, 2}, {6, 1, 2, 1}, {6, 2, 1, 1}, {7, 1, 1, 1}}

Сообщение от _Kate_

следовательно форма приведеная выше верна?

Какая форма?

@_Kate_ · 08.09.2013, 20:17 **[ТС]**

а если во второй ячейке 3 письма то получаеться, что нужно зафиксировать 3 письма 10-3=7 осталось розложить по 3 ячейкам и получим формулу С из 2 по 6; 6!/(2!4!)= 15. Верно?

@Heidegger · 08.09.2013, 20:38

Сообщение от _Kate_

нужно зафиксировать 3 письма 10-3=7 осталось розложить по 3 ячейкам и получим формулу С из 2 по 6; 6!/(2!4!)= 15. Верно?

Да, верно. Если не должно быть пустых.

Байт · 09.09.2013, 11:20

Если пустые допускаются, то есть такой любопытный прием
Вводим новые переменные y_i = x_i + 1
Получаем уравнение y₁+ ... y₄ = 10 + 4 =14, где y_i > 0,
т.е. сводим к непустому варианту

@_Kate_ 0 / 0 / 0 Регистрация: 12.09.2012 Сообщений: 92 Записей в блоге: 1
		1
	Задача с комбинаторики 08.09.2013, 16:57. Показов 6091. Ответов 8 Метки нет (Все метки) Сколькими способами можно разместить 10 одинаковых открыток в 4 почтовых ящиках так, чтобы: а) не было пустых ящиков б) во втором ящике было 3 открытки. предполагаю что на первый вариант : 1098*7=5040 вариантов. над вторым вариантом затрудняюсь, прошу помощи ) 0

zer0mail 2662 / 2237 / 240 Регистрация: 03.07.2012 Сообщений: 8,138 Записей в блоге: 1
	08.09.2013, 19:27	2
	А если есть только 4 открытки, какой будет ответ для а) ? 1

@_Kate_ 0 / 0 / 0 Регистрация: 12.09.2012 Сообщений: 92 Записей в блоге: 1
	08.09.2013, 19:31 [ТС]	3
	C из 4 по 4 = 1. Верно? 1 по тому что в условии написано чтобы не было пустых ячеек следовательно 1 вариант. 0

@Heidegger 617 / 242 / 16 Регистрация: 31.07.2013 Сообщений: 376
	08.09.2013, 19:34	4
	Сообщение от _Kate_ предполагаю что на первый вариант : 10987=5040 вариантов. Не совсем: метод шаров и перегородок для n = 10 открыток и k = 4 ящиков даёт ответ: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{n-1}^{k-1} = {C}_{9}^{3} = \frac{9!}{3!\cdot 6!} = \frac{7\cdot 8\cdot 9}{1\cdot 2\cdot 3} = 7\cdot 4\cdot 3 = 84$ метод шаров и перегородок Задача. Есть k ящиков и n >= k однаковых шаров. Сколькими способами можно разложить шары по ящикам так, чтобы ни один ящик не оказался пустым? Решение: Давайте определять раскладку так: выложим шары в ряд и поставим между ними k–1 перегородку. То, что слева от первой перегородки, положим в первый ящик, между первой и второй – во второй, ..., то, что справа от последней – в последний, k-й ящик. Ящик будет пустым, только если две перегородки стоят рядом не разделенные шарами, либо перегородка стоит с краю, левее или правее всех шаров. Так давайте это запретим! Пусть на каждое из n-1 мест между n шарами можно поставить не более одной из k–1 перегородок. То есть, из n–1 мест надо будет выбрать k–1, куда мы ставим перегородки. Отсюда получаем ответ: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{n-1}^{k-1}$ . Задача. А сколько способов разложить шары, если могут быть пустые ящики? Решение*: Если определять раскладку так же, ставя между шарами k–1 перегородку, то ограничений уже не будет: шары и перегородки можно ставить в произвольном порядке. Давайте считать, что у нас расставлено в ряд n+k–1 объектов: n из них шары, а остальные – перегородки. Тогда раскладка будет определяться тем, на каких местах какие объекты стоят. Из n+k–1 мест можно выбрать n мест для шаров $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{n+k-1}^{n}$ способами, или: k–1 место для перегородок $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{n+k-1}^{k-1}$ способами. Эти числа равны и оба являются ответом. 1

@_Kate_ 0 / 0 / 0 Регистрация: 12.09.2012 Сообщений: 92 Записей в блоге: 1
	08.09.2013, 19:39 [ТС]	5
	так это диофантовое уравнение получаеться что x1+x2+x3+x4=10 тоесть решение уравнения и есть ответ? следовательно форма приведеная выше верна? 0

@_Kate_ 0 / 0 / 0 Регистрация: 12.09.2012 Сообщений: 92 Записей в блоге: 1
	08.09.2013, 20:17 [ТС]	7
	а если во второй ячейке 3 письма то получаеться, что нужно зафиксировать 3 письма 10-3=7 осталось розложить по 3 ячейкам и получим формулу С из 2 по 6; 6!/(2!4!)= 15. Верно? 0

@Heidegger 617 / 242 / 16 Регистрация: 31.07.2013 Сообщений: 376
	08.09.2013, 20:38	8
	Сообщение от _Kate_ нужно зафиксировать 3 письма 10-3=7 осталось розложить по 3 ячейкам и получим формулу С из 2 по 6; 6!/(2!4!)= 15. Верно? Да, верно. Если не должно быть пустых. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	09.09.2013, 11:20	9
	Сообщение было отмечено как решение Решение Если пустые допускаются, то есть такой любопытный прием Вводим новые переменные y_i = x_i + 1 Получаем уравнение y₁+ ... y₄ = 10 + 4 =14, где y_i > 0, т.е. сводим к непустому варианту 3

Опции темы