2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Число комбинаций
Сообщение22.02.2019, 22:14 
Доброго времени суток.

Умышленно не использовал слова "сочетаний", "размещений", "перестановок" в топике, т.к. формализовать и классифицировать задачу затрудняюсь.

Для примера, из множества {1;2;3} можно составить следующие "комбинации" (без повторений):
{1},{1;2}{1;3}, {1;2;3}
{2},{2;3}
{3}
Всего 6 комбинаций.

Для {1;2;3;4} соответственно:

{1},{1;2},{1;3},{1;4},{1;2;3},{1;2;4},{1;3;4},{1;2;3;4},
{2},{2;3},{2;4},{2;3;4},
{3},{3;4},
{4}

Всего 15 комбинаций.


Существует ли общая формула количества комбинаций для множества N ?

(На замечание, что единственный элемент в выборке, например {1}, не является комбинацией - ок, количество таких "некомбинаций" равно мощности исходного множества.)

Спасибо за отзывы.

 
 
 
 Re: Число комбинаций
Сообщение22.02.2019, 22:26 
Аватара пользователя
monst92 в сообщении #1377812 писал(а):
Существует ли общая формула количества комбинаций для множества N ?

Конечно.

В первом случае пропущены две, а во втором — одна. То есть не $6$ и $15$, а $8$ и $16$ соответственно.

 
 
 
 Re: Число комбинаций
Сообщение22.02.2019, 22:36 
Аватара пользователя
А что за дискриминация - почему $\{1, 2, 3\}$ в первом случае пропущено, а $\{1, 2, 3, 4\}$ во втором - нет?

Попробуйте написать определение или хотя бы перечислить свойства, которые вам нужны. Из одних примеров понять нельзя - существует бесконечно много функций из натуральных чисел, которые для $3$ и $4$ принимают указанные вами значения.

 
 
 
 Re: Число комбинаций
Сообщение22.02.2019, 22:43 
Действительно, пропустил {1;2;3} - невнимательность (поправил). Это что-то похоже на сочетания переменной длины.

 
 
 
 Re: Число комбинаций
Сообщение22.02.2019, 22:52 
Аватара пользователя
monst92 в сообщении #1377825 писал(а):
Действительно, пропустил {1;2;3} - невнимательность (поправил). Это что-то похоже на сочетания переменной длины.

Это и есть сочетания переменной длины. Просто длина ещё бывает равна нулю. Теперь догадываетесь, сколько будет комбинаций для $N=5$ и какова формула?

-- 22.02.2019, 22:56 --

monst92 в сообщении #1377829 писал(а):
24, можно закрывать

Нет, не $24$.

 
 
 
 Re: Число комбинаций
Сообщение22.02.2019, 22:56 
31 :shock:

 
 
 
 Re: Число комбинаций
Сообщение22.02.2019, 22:57 
monst92 в сообщении #1377812 писал(а):
Умышленно не использовал слова "сочетаний", "размещений", "перестановок" в топике, т.к. формализовать и классифицировать задачу затрудняюсь.

Вы спрашиваете о количестве различных подмножеств (множества из $n$ элементов).
А это количество равно... :mrgreen: чему?

 
 
 
 Re: Число комбинаций
Сообщение22.02.2019, 23:00 
Аватара пользователя
monst92 в сообщении #1377831 писал(а):
31 :shock:

А что вас так удивляет? Вы же нулевую длину(пустое множество) не хотите считать.

 
 
 
 Re: Число комбинаций
Сообщение22.02.2019, 23:02 
Всем спасибо, кто реально помог :D
Изображение

 
 
 
 Re: Число комбинаций
Сообщение23.02.2019, 06:13 
Аватара пользователя
Картинку на свалку. Множество $\{\varnothing\}$ не является подмножеством множества $C=\{1,\,2,\,3\}$.

 
 
 
 Re: Число комбинаций
Сообщение23.02.2019, 12:23 
monst92
Картинки картинками, а разве не хотелось бы вам самому вывести формулу? (Или проверить, что приведённая действительно правильная. Вдруг она совпадает для нескольких первых натуральных чисел, а потом внезапно расходится.) Получается она очень просто, индукцией: пусть мы знаем сколько подмножеств у $1..n$, посмотрим на подмножества $1..(n+1)$ в свете предыдущих, а когда с этими будет всё ясно, останется посмотреть только на подмножества $\varnothing$. Получается рекуррентное соотношение, которое моментально решается.

Формулы для многих комбинаторных чисел можно узнать вот таким образом, сравнивая перечисляемые объекты разных размеров. Даже если пользоваться OEIS для угадывания последовательности по её началу (трудно переоценить пользу OEIS), важно уметь проверять, та ли нашлась.

 
 
 
 Re: Число комбинаций
Сообщение23.02.2019, 19:51 
Спасибо, проверять конечно же нужно.

А еще вопрос про пустое множество, почему оно не является подмножеством множества $\{1;2;3\}$ ? (Или любого другого).

 
 
 
 Re: Число комбинаций
Сообщение23.02.2019, 19:54 
Аватара пользователя
Пустое $\varnothing$ - является. А совершенно не пустое множество $\{\varnothing\}$ - нет.

 
 
 
 Re: Число комбинаций
Сообщение23.02.2019, 20:03 
monst92

(Оффтоп)

Есть много способов писать фигурные скобки правильно. Используйте хотя бы один из них. Пока исправлю в последнем посте.

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group