Liczba par rozłącznych podzbiorów Driw: Ile różnych par rozłącznych podzbiorów ma zbiór 2011−elementowy? Nie wiem kompletnie jak to ruszyć

Bleee: Całkowita liczba podzbiorów podzielona przez 2

Bleee: Chociaż nie. Chwila. Hmmm

a7: z tego, co mi się znalazło w internecie, to wzór będzie n*2ⁿ⁻¹ 2011*2²⁰¹¹⁻¹=2011*2²⁰¹⁰ można to sprawdzić na prostszym przykładzie 3−elementowego zbioru X, n=3, |X|=3 3*2²=3*4=12 {1,2,3} {1−2} {1−3} {2−3} {12− 3} {13− 2} {23−1} {11−2} {11−3} {22−1} {22−3} {33−1} {33−2} zgadza się jeśli trzeba uwzględnić przypadek {∅,123} (?) to wtedy +1 czy mógłby ktoś potwierdzić ?

PW: Coś tych Twoich podziałów nie rozumiem. {1, 2, 3} można podzielić na dwa rozłączne podzbiory tylko na 4 sposoby: {∅}, {1, 2, 3} {1}, {2, 3} {2}, {1, 3} {3}, {1, 2} Sposób liczenia jest dosyć prosty. Potraktujmy zbiór 2011−elementowy jako zbiór kul oznaczonych numerami od 1 dp 2011. Dorzucamy jedną kulę z numerem '0' i dokonujemy losowania kolejnych kul − aż do momentu wyciągnięcia kuli z numerem '0'. Dostajemy w ten sposób podział zbioru na dwa rozłączne podzbiory − w jednym są kule wylosowane, w drugim pozostałe. W szczególności wyciągnięcie '0' za pierwszym razem daje podział na zbiór pusty i cały rozpatrywany zbiór. Losowań może być L,

	2011 1		2011 2		2011 3		2011 2011
L = 1 +		+		+		+ .... +		,

co odpowiada kolejno: − wyciągnięciu '0' za pierwszym razem: 1 sposób), podział na zbiór pusty i cały rozpatrywany

	2011 1
− wyciągnięciu '0' za drugim razem :		, podział na zbiór 1−elementowy i

(2011−1)−elementowy

	2011 2
− wyciągnięciu '0' za trzecim razem :		, podział na zbiór 2−elementowy i

(2011−2)−elementowy i tak dalej, aż do wyciągnięcia '0' na końcu − podział na zbiór 2011−elementowy i zbiór pusty. Przy takim sposobie liczenia każdy podział wystąpi 2 razy − raz jako podział na zbiór k−elementowy i (2011−k)−elementowy, a drugi raz jako podział na zbiór (2011−k) elementowy i zbiór k−elementowy. Wobec tego liczba podziałów jest równa

	L		1		2011 k
		=		∑		, sumowanie po k = 0 do 2011.
	2		2

Jak łatwo zauważyć (wzór na potęgę sumy)

	2011 k
∑		= (1 + 1)2011 = 22011,

a więc

	L
		= 22010.
	2

PW: Nie, jednak źle zrozumiałem trześć zadania. Nie idzie o podział na dwa rozłączne podzbiory, ale wyodrębnienie różnych możliwych par rozłącznych podzbiorów. Pewnie a7 podała dobry wzór.

a7: tak, zorientowałam się, że napisałam bzdurę już po fakcie, bo przecież elementy nie mogą się powtarzać, także źle mi się (tym razem ) znalazło w necie, musiałam opatrznie zrozumieć

a7: hmm, czy mam podać źródło?

a7: str. 13 (Metoda bijektywna, (2) "|Y|=n*2ⁿ⁻¹" http://www-users.mat.uni.torun.pl/~gregbob/old/matdyskII/Zbior.pdf ?

wredulus_pospolitus: a7 −−− Co to za podzbiór 33 1 − 23 1 − 2 1 − 3 2 − 13 2 − 3 3 − 12 i do tego jeszcze: ∅ − 'dowolny podzbiór' czyli w sumie 2³ takich 'par' dla podzbioru pustego i stąd mamy: 8 + 6 = 14 <−−− co nie pasuje do wzoru Jeżeli odrzucimy możliwość podzbioru pustego to byśmy mieli wartość (potencjalnie) pasującą do n*2ⁿ⁻²