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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
 Заголовок сообщения: Задача на сочетания
СообщениеДобавлено: 30 май 2015, 21:12 
Не в сети
Начинающий
Зарегистрирован:
30 май 2015, 20:53
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на сочетания
СообщениеДобавлено: 13 июн 2015, 15:50 
Не в сети
Начинающий
Зарегистрирован:
30 май 2015, 20:53
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Честно говоря, совсем не ожидап, что данная задача будет настолько сложна для коллективного разума. :cry:
Попробую еще добавить информации.
Допустим у нас есть множество из 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 - количеству сочетаний с повторениями.
Вопрос - можно ли как то составить универсальную формулу расчета данного числа или задача нетривиальна по сути?

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задача сочетания

в форуме Теория вероятностей

fob2000

3

240

23 окт 2016, 17:25

Задача про сочетания

в форуме Теория вероятностей

pmu_1

6

578

15 дек 2018, 09:32

Сочетания или сочетания с повторениями? Вот в чем вопрос

в форуме Комбинаторика и Теория вероятностей

wyifhd

2

220

17 сен 2020, 04:20

Комбинаторная задача на сочетания

в форуме Дискретная математика, Теория множеств и Логика

Romaru

1

232

10 авг 2019, 22:27

8 шариков, 4 белых, 4 чёрных. Задача на сочетания (по идее)

в форуме Теория вероятностей

danil_vm

8

216

21 фев 2021, 19:58

Сочетания

в форуме Комбинаторика и Теория вероятностей

mumuag

3

158

17 авг 2023, 14:09

Сочетания

в форуме Комбинаторика и Теория вероятностей

New15

2

335

26 июл 2017, 17:20

Сочетания

в форуме Комбинаторика и Теория вероятностей

New15

1

301

28 июл 2017, 17:01

Сочетания

в форуме Комбинаторика и Теория вероятностей

Race

2

299

04 янв 2017, 11:32

Сочетания

в форуме Комбинаторика и Теория вероятностей

Ivan7776

2

525

01 окт 2014, 19:53


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



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

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


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

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

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

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