Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 5 из 5 |
[ Сообщений: 48 ] | На страницу Пред. 1, 2, 3, 4, 5 |
|
Автор | Сообщение | |
---|---|---|
ivashenko |
|
|
Например для n=7,m=6,k=5 имеем разложение числа 7 как 6+1+0+0+0. Всего может быть 5!=120 перестановок. 3 нуля дают 3!=6 перестановок. 120/6=20 . теперь перемножим 20*7!/(6!1!0!0!0!), получим результат 140. Естественно, разложение на слагаемые может быть неоднозначным. Данный алгоритм наверное удобен для компьютера. Хотя он и дает правильные результаты, но все же это не решение задачи и не формула. |
||
Вернуться к началу | ||
ivashenko |
|
|
agua писал(а): agua |
||
Вернуться к началу | ||
agua |
|
|
Я могу показать, как получить явную формулу для любых [math]k[/math] и [math]n,[/math] при условии, что [math]m > {n}\!{\not{\;}} {2},[/math] используя только биномиальные коэффициенты.
Определим количество [math]n[/math]– разрядных чисел, содержащих ровно [math]m[/math] одинаковых [math]k[/math]– ичных цифр. Т.к. [math]m > {n}\!{\not{\;}} {2},[/math] только одна из цифр может повторяться [math]m[/math] раз. Тогда для произвольно взятой цифры необходимо выбрать [math]m[/math] из имеющихся [math]n[/math] разрядов, что дает нам [math]C_n^m[/math] различных вариантов положения цифры, при этом оставшиеся [math]n-m[/math] разрядов занимают любые из оставшихся [math]k-1[/math] цифр (всего [math](k-1)^{n-m}[/math] вариантов), что для произвольно выбранной цифры дает [math]C_n^m (k-1)^{n-m}[/math] вариантов, а для всех [math]k[/math] цифр – [math]C_n^m k (k-1)^{n-m}[/math] вариантов. Для [math]k = 5, n = 7, m = 6[/math] получаем: [math]C_n^m k (k-1)^{n-m} = C_7^6 \cdot 5 \cdot (5-1)^{7-6} = 7 \cdot 5 \cdot 4 = 140.[/math] Формулу можно уточнить для [math]m > {n}\!{\not{\;}} {3},[/math], но затем количество вариантов уже сложно поддаётся анализу. Очевидно, эта формула не совпадает по форме с выражением через мультиномиальные коэффициенты, т.е. мы имеем уже два принципиально различных подхода к выводу общей формулы. Думаю, их существует значительно больше. ivashenko |
||
Вернуться к началу | ||
За это сообщение пользователю agua "Спасибо" сказали: ivashenko |
||
ivashenko |
|
|
Данным методом можно получить бесконечное множество решений, о чем я предполагал в самом начале, но не одно общее решение.
|
||
Вернуться к началу | ||
ivashenko |
|
|
agua писал(а): Я могу показать, как получить явную формулу для любых [math]k[/math] и [math]n,[/math] при условии, что [math]m > {n}\!{\not{\;}} {2},[/math] используя только биномиальные коэффициенты. Определим количество [math]n[/math]– разрядных чисел, содержащих ровно [math]m[/math] одинаковых [math]k[/math]– ичных цифр. Т.к. [math]m > {n}\!{\not{\;}} {2},[/math] только одна из цифр может повторяться [math]m[/math] раз. Тогда для произвольно взятой цифры необходимо выбрать [math]m[/math] из имеющихся [math]n[/math] разрядов, что дает нам [math]C_n^m[/math] различных вариантов положения цифры, при этом оставшиеся [math]n-m[/math] разрядов занимают любые из оставшихся [math]k-1[/math] цифр (всего [math](k-1)^{n-m}[/math] вариантов), что для произвольно выбранной цифры дает [math]C_n^m (k-1)^{n-m}[/math] вариантов, а для всех [math]k[/math] цифр – [math]C_n^m k (k-1)^{n-m}[/math] вариантов. Для [math]k = 5, n = 7, m = 6[/math] получаем: [math]C_n^m k (k-1)^{n-m} = C_7^6 \cdot 5 \cdot (5-1)^{7-6} = 7 \cdot 5 \cdot 4 = 140.[/math] Формулу можно уточнить для [math]m > {n}\!{\not{\;}} {3},[/math], но затем количество вариантов уже сложно поддаётся анализу. Очевидно, эта формула не совпадает по форме с выражением через мультиномиальные коэффициенты, т.е. мы имеем уже два принципиально различных подхода к выводу общей формулы. Думаю, их существует значительно больше. ivashenko Либо я туплю, либо мы решаем несколько иную задачу, отличную от начальной и более простую? |
||
Вернуться к началу | ||
agua |
|
|
Это та же задача, но переформулированная для n-разрядных чисел в k-ичной системе счисления. Пусть например, у нас имеется k = 2 корзины и n = 3 шара. Будем записывать исходы опыта в виде цепочек длины n = 3, каждый элемент которых может принимать значение 1 или 2 (номер корзины).
Всего получаем [math]N = {k^n} = {2^3} = 8[/math] различных исходов опыта: 111, 112, 121, 122, 211, 212, 221, 222, – т.е. 8 трёхбуквенных слов в двухбуквенном алфавите {1, 2}. Теперь рассмотрим события вида "..., i-я корзина содержит ровно j шаров, ...". В терминах цепочек это означает: "..., слово содержит ровно j букв i, ...". Получаем следующие композиции числа n = 3 (с учётом порядка слагаемых): (3, 0) – цепочка 111; (2, 1) – цепочки 112, 121, 211; (1, 2) – цепочки 122, 212, 221; (0, 3) – цепочка 222. В результате для количества цепочек в каждой композиции получаем строку треугольника Паскаля (1 3 3 1). Теперь перейдём от композиций к разбиениям (без учёта порядка слагаемых, т.е. без учёта номера корзин): {3, 0} – 3 шара в одной корзине и ни одного шара в другой корзине возможны в двух случаях (соответствует композициям (3, 0) и (0, 3)); {2, 1} – 2 шара в одной корзине и 1 шар в другой корзине возможны в шести случаях (композиции (2, 1) и (1, 2) вносят по три варианта). В результате получаем "сложенный пополам" треугольник Паскаля. Записать это можно следующими способами: [math]2 \cdot C_3^3 = C_2^1 \cdot C_3^3 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} 3 \\ 3 \end{pmatrix} = \begin{pmatrix} 2 \\ 1\; 1 \end{pmatrix} \cdot \begin{pmatrix} 3 \\ 3\; 0 \end{pmatrix}[/math] [math]2 \cdot C_3^2 = C_2^1 \cdot C_3^2 = \begin{pmatrix} 2 \\ 1 \end{pmatrix} \cdot \begin{pmatrix} 3 \\ 2 \end{pmatrix} = \begin{pmatrix} 2 \\ 1\; 1 \end{pmatrix} \cdot \begin{pmatrix} 3 \\ 2\; 1 \end{pmatrix}[/math] Запись через мультиномиальные коэффициенты будет полезна при записи формулы в общем виде. Итак, мы вначале перешли от элементарных исходов опыта к n-буквенным словам в k-буквенном алфавите, затем к композициям числа n, и, наконец, к разбиениям числа n, и именно количество элементарных исходов опыта для каждого возможного разбиения мы и учитываем в приведённых выше таблицах (и в конечной формуле вероятности). |
||
Вернуться к началу | ||
ivashenko |
|
|
ivashenko писал(а): agua писал(а): Я могу показать, как повсегоь явную формулу для любых [math]k[/math] и [math]n,[/math] при условии, что [math]m > {n}\!{\not{\;}} {2},[/math] используя только биномиальные коэффициенты. Определим количество [math]n[/math]– разрядных чисел, содержащих ровно [math]m[/math] одинаковых [math]k[/math]– ичных цифр. Т.к. [math]m > {n}\!{\not{\;}} {2},[/math] только одна из цифр может повторяться [math]m[/math] раз. Тогда для произвольно взятой цифры необходимо выбрать [math]m[/math] из имеющихся [math]n[/math] разрядов, что дает нам [math]C_n^m[/math] различных вариантов положения цифры, при этом оставшиеся [math]n-m[/math] разрядов занимают любые из оставшихся [math]k-1[/math] цифр (всего [math](k-1)^{n-m}[/math] вариантов), что для произвольно выбранной цифры дает [math]C_n^m (k-1)^{n-m}[/math] вариантов, а для всех [math]k[/math] цифр – [math]C_n^m k (k-1)^{n-m}[/math] вариантов. Для [math]k = 5, n = 7, m = 6[/math] получаем: [math]C_n^m k (k-1)^{n-m} = C_7^6 \cdot 5 \cdot (5-1)^{7-6} = 7 \cdot 5 \cdot 4 = 140.[/math] Формулу можно уточнить для [math]m > {n}\!{\not{\;}} {3},[/math], но затем количество вариантов уже сложно поддаётся анализу. Очевидно, эта формула не совпадает по форме с выражением через мультиномиальные коэффициенты, т.е. мы имеем уже два принципиально различных подхода к выводу общей формулы. Думаю, их существует значительно больше. ivashenko Либо я туплю, либо мы решаем несколько иную задачу, отличную от начальной и более простую? В предложенном Вами решении и его трактовке мы рассматриваем n шаров, каждый шар содержит внутри себя k цифр, одна из которых может выпадать при его подбрасывании. Положительным исходами будут такие, когда подброшены все шары, но с одинаковыми цифрами не больше m. Т.к. m>n/2, то в каждом испытании может быть только одно число из k, содержащихся в каждом шаре, которое выпадет m раз.Т.е. m шаров могут выпасть одной из цифр k.(попасть в одну из k) корзин. А всего эти m шаров можно выбрать из всех n шаров [math]C_n^k[/math] способами. Оставшиеся (n-m) шаров можно распределить по оставшимся (k-1) корзинам [math](k-1)^{(n-m)}[/math] способами. Т.к. первую заполнившуюся корзину мы можем выбрать произвольно из k вариантов, то всего получим [math]C_n^k(k-1)^{(n-m)}k[/math]. |
||
Вернуться к началу | ||
ivashenko |
|
|
Теперь у меня возникает вопрос: А как учитываются в данном решении комбинации, в которых ни в одной корзине не оказывается m шаров, т.е. ни одно из чисел k не выпадает m раз?
Получается, что мы решили следующую задачу: Определить вероятность того, что из n брошенных в k корзин шаров, в каждую из корзин попадёт не больше m шаров и хотя бы в одной из корзин будет ровно m шаров??? Или я что- то не понимаю??? |
||
Вернуться к началу | ||
На страницу Пред. 1, 2, 3, 4, 5 | [ Сообщений: 48 ] |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |