Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 2 ] |
|
Автор | Сообщение | |
---|---|---|
_MBK_ |
|
|
Предположим, есть некое множество N элементов {1,2,3,...N} Нужно определить количество всевозможных не повторяющихся наборов по M элементов. К примеру, для M=4 {{1,2,3,4},{2,4,5,6},{7,8,4,9}...} В этом случае задача решается просто - это классический случай, количество сочетаний без повторений. Немного усложним задачу - нужно определить количество всевозможных наборов по M элементов, в которых не повторяется K элементов. То есть, при K=M задача вырождается в предыдущую; при K=1 нам необходимо посчитать множества, состоящие из полностью различных элементов {{1,2,3,4},{5,6,7,8},{12,9,30,10},...}; при K=2 нам подходят все наборы, в которых повторяется не более одного элемента {{1,2,3,4},{1,5,6,7},{2,5,9,10},...} и т.д. В самом идеальном случае хотелось бы получить быстрый линейный алгоритм перебора таких множеств. Заранее огромное спасибо |
||
Вернуться к началу | ||
_MBK_ |
|
|
Честно говоря, совсем не ожидап, что данная задача будет настолько сложна для коллективного разума.
Попробую еще добавить информации. Допустим у нас есть множество из N элементов, из которого нужно выбирать 4 элементные выборки. Выборок, в которых ни один элемент не пересекается будет, по понятным причинам N/4 Выборки, в которых повторяется не более одного элемента можно посчитать эмпирически: N кол-во возможных выборок 5 1 6 1 7 2 8 2 9 3 10 5 11 5 12 6 13 8 ... Выборки, в которых повторяется не более двух элементов: N кол-во выборок 5 1 6 3 7 7 8 10 9 13 10 18 11 27 12 37 13 50 14 65 15 81 16 102 17 127 18 149 19 185 20 212 ... Для 3 повторяющихся элементов, по понятным причинам, количество будет равно количеству сочетаний из 10 по 4 без повторений а для 4 - количеству сочетаний с повторениями. Вопрос - можно ли как то составить универсальную формулу расчета данного числа или задача нетривиальна по сути? |
||
Вернуться к началу | ||
[ Сообщений: 2 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Задача сочетания
в форуме Теория вероятностей |
3 |
240 |
23 окт 2016, 17:25 |
|
Задача про сочетания
в форуме Теория вероятностей |
6 |
578 |
15 дек 2018, 09:32 |
|
Сочетания или сочетания с повторениями? Вот в чем вопрос
в форуме Комбинаторика и Теория вероятностей |
2 |
220 |
17 сен 2020, 04:20 |
|
Комбинаторная задача на сочетания | 1 |
232 |
10 авг 2019, 22:27 |
|
8 шариков, 4 белых, 4 чёрных. Задача на сочетания (по идее)
в форуме Теория вероятностей |
8 |
216 |
21 фев 2021, 19:58 |
|
Сочетания
в форуме Комбинаторика и Теория вероятностей |
3 |
158 |
17 авг 2023, 14:09 |
|
Сочетания
в форуме Комбинаторика и Теория вероятностей |
2 |
335 |
26 июл 2017, 17:20 |
|
Сочетания
в форуме Комбинаторика и Теория вероятностей |
1 |
301 |
28 июл 2017, 17:01 |
|
Сочетания
в форуме Комбинаторика и Теория вероятностей |
2 |
299 |
04 янв 2017, 11:32 |
|
Сочетания
в форуме Комбинаторика и Теория вероятностей |
2 |
525 |
01 окт 2014, 19:53 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |