Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 48 ]  На страницу Пред.  1, 2, 3, 4, 5
Автор Сообщение
 Заголовок сообщения: Re: Kopзины и шapы
СообщениеДобавлено: 07 июл 2015, 23:01 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3194
Cпасибо сказано: 220
Спасибо получено:
199 раз в 189 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
Теоретически, я могу найти значение для любых чисел m,n,k и придумал для этого формулу, которую Вы видимо называете триномиальными, четыренормальными и.т.д. коэфицентами, о которой говорил ранее. Да, Ваш метод в предыдущем посте полностью совпадает с моим. Задача в принципе сводится к отысканию разложений числа n на k слагаемых, таких, что каждое не превосходит m и хотя бы одно из слагаемых равно m .
Например для 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.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Kopзины и шapы
СообщениеДобавлено: 07 июл 2015, 23:37 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3194
Cпасибо сказано: 220
Спасибо получено:
199 раз в 189 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
agua писал(а):
Спасибо за интерес к задаче – я уже собирался подводить итоги и закрывать тему в преддверии летних каникул. В финале я предполагал показать несколько способов вывода формул, некоторые из которых уже были рассмотрены. Меня прежде всего интересует применимость здесь метода производящих функций, но я на данный момент не владею им настолько, чтобы самостоятельно провести полноценное исследование.


agua
Не поздновато ли для преддверия летних каникул? Это в каком ВУЗе так издеваются над студентами?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Kopзины и шapы
СообщениеДобавлено: 08 июл 2015, 00:12 
Не в сети
Одарённый
Аватара пользователя
Зарегистрирован:
25 июн 2015, 20:58
Сообщений: 142
Cпасибо сказано: 23
Спасибо получено:
40 раз в 33 сообщениях
Очков репутации: 12

Добавить очки репутацииУменьшить очки репутации
Я могу показать, как получить явную формулу для любых [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
ivashenko писал(а):
Не поздновато ли для преддверия летних каникул? Это в каком ВУЗе так издеваются над студентами?
Я имел в виду каникулы на форуме – думаю, летом здесь немноголюдно.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю agua "Спасибо" сказали:
ivashenko
 Заголовок сообщения: Re: Kopзины и шapы
СообщениеДобавлено: 08 июл 2015, 00:32 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3194
Cпасибо сказано: 220
Спасибо получено:
199 раз в 189 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
Данным методом можно получить бесконечное множество решений, о чем я предполагал в самом начале, но не одно общее решение.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Kopзины и шapы
СообщениеДобавлено: 08 июл 2015, 04:00 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3194
Cпасибо сказано: 220
Спасибо получено:
199 раз в 189 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
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
ivashenko писал(а):
Не поздновато ли для преддверия летних каникул? Это в каком ВУЗе так издеваются над студентами?
Я имел в виду каникулы на форуме – думаю, летом здесь немноголюдно.


Либо я туплю, либо мы решаем несколько иную задачу, отличную от начальной и более простую?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Kopзины и шapы
СообщениеДобавлено: 08 июл 2015, 11:33 
Не в сети
Одарённый
Аватара пользователя
Зарегистрирован:
25 июн 2015, 20:58
Сообщений: 142
Cпасибо сказано: 23
Спасибо получено:
40 раз в 33 сообщениях
Очков репутации: 12

Добавить очки репутацииУменьшить очки репутации
Это та же задача, но переформулированная для 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, и именно количество элементарных исходов опыта для каждого возможного разбиения мы и учитываем в приведённых выше таблицах (и в конечной формуле вероятности).

Меня некоторое (возможно, довольно долгое) время не будет на форуме, так что можем подвести итоги уже с началом новой активной фазы. Впрочем, картина и так уже достаточно подробно описана. Но если будут какие-то новые идеи – обязательно сообщайте. Всем хорошего лета.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Kopзины и шapы
СообщениеДобавлено: 08 июл 2015, 12:24 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3194
Cпасибо сказано: 220
Спасибо получено:
199 раз в 189 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
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
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].

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Kopзины и шapы
СообщениеДобавлено: 08 июл 2015, 12:39 
Не в сети
Light & Truth
Зарегистрирован:
29 мар 2014, 00:59
Сообщений: 3194
Cпасибо сказано: 220
Спасибо получено:
199 раз в 189 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
Теперь у меня возникает вопрос: А как учитываются в данном решении комбинации, в которых ни в одной корзине не оказывается m шаров, т.е. ни одно из чисел k не выпадает m раз?

Получается, что мы решили следующую задачу: Определить вероятность того, что из n брошенных в k корзин шаров, в каждую из корзин попадёт не больше m шаров и хотя бы в одной из корзин будет ровно m шаров??? Или я что- то не понимаю???

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 48 ]  На страницу Пред.  1, 2, 3, 4, 5

Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved