Число комбинаций

[monst92]

Доброго времени суток.

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

Для примера, из множества {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}, не является комбинацией - ок, количество таких "некомбинаций" равно мощности исходного множества.)

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

[Yadryara]

monst92 в сообщении #1377812 писал(а):

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

Конечно.

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

[mihaild]

А что за дискриминация - почему $\{1, 2, 3\}$ в первом случае пропущено, а $\{1, 2, 3, 4\}$ во втором - нет?

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

[monst92]

Действительно, пропустил {1;2;3} - невнимательность (поправил). Это что-то похоже на сочетания переменной длины.

[Yadryara]

monst92 в сообщении #1377825 писал(а):

Действительно, пропустил {1;2;3} - невнимательность (поправил). Это что-то похоже на сочетания переменной длины.

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

-- 22.02.2019, 22:56 --

monst92 в сообщении #1377829 писал(а):

24, можно закрывать

Нет, не $24$.

[monst92]

31

[wrest]

monst92 в сообщении #1377812 писал(а):

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

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

[Yadryara]

monst92 в сообщении #1377831 писал(а):

31

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

[monst92]

Всем спасибо, кто реально помог

[--mS--]

Картинку на свалку. Множество $\{\varnothing\}$ не является подмножеством множества $C=\{1,\,2,\,3\}$.

[arseniiv]

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

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

[monst92]

Спасибо, проверять конечно же нужно.

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

[--mS--]

Пустое $\varnothing$ - является. А совершенно не пустое множество $\{\varnothing\}$ - нет.

[Lia]

monst92

(Оффтоп)

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