ЮБ
Юля Борисенко
Найти число подмножеств n множества, если n натуральное число? ? Помогите
мне решение надо
мне решение надо
Два в степени n
http://ru.wikipedia.org/wiki/Булеан
Включая само множество и пустое, 2 в степени n. В самом деле:
берем подмножества по 1 элементу, таких всего n штук.
берем подмножества по 2 элемента, таких всего С (n,2) -
число сочетаний из n элементов по 2.
берем подмножества по 3 элемента, таких всего С (n,3) -
число сочетаний из n элементов по 3.
....
берем подмножества по (n-1) элементов, таких всего С (n,n-1) -
число сочетаний из n элементов по (n-1).
Итак, общее число подмножеств (кроме самого мн-ва и пустого)
C(n,1)+C(n,2)+C*(n,3)+...+C(n,n-1).
Добавим сюда C(n,0) и C(n,n), получится:
C(n,0)+C(n,1)+C(n,2)+C(n,3)+...+C(n,n-1)+C(n,n).
А известно (бином Ньютона) , что это равно (1+1)^n=2^n.