rozdzielne podzbiory

v · Post autor: v » 16 gru 2004, o 19:27

Takie zadanie pojawiło się w testach wejściowych na AGH.

Z n-elementowego zbioru losujemy 2 dowolne podzbiory. Jakie jest prawdopodobieństwo, że wylosowane podzbiory będą rozłączne?

Doszedłem do sumy, jednak w odpowiedzi jest konkretna liczba:
P = (3/4)^n

Arek · Post autor: **Arek** » 16 gru 2004, o 21:08

Przeniosłem...

Hmmm.... dość podobny problem pojawił się w tym roku na OM, choć to jest prostsze... Może tak - jeżeli nikt nie poda jakiegoś krótkiego rozwiązania, to ja to się postaram jakoś wyjaśnić ok ?

Hydroksozbiory · Post autor: **Hydroksozbiory** » 17 gru 2004, o 19:20

no to może tak, z sumą rzeczywiście jest ciężko ale chyba da sie to zrobić inaczej, zakaładam , jeśli mam zb A taki że IAI=n to ilość sposobów na jaki mogę wybrac 2 rozłaczne podzbiory jest k, teraz dodajmy do zb A jeszcze jeden element, nowy zb nazwijmy A`, IA`I=n+1, i pytamy na ile sposobów można wybrac z niego dwa rozłaczne podzbiory, można powybierać to co mieliśmy dla zb A, można tez jeśi z A wybralismy np B i B`, wrzucić nowy dodany elenent to B lub B`, widac że mamy 3 razy więcej możliwości wyboru dwóch rozłącznych podzb. zb a~niż mieliśmy przy zb A czyli zdarzeń sprzyjających jest 3 razy więcej, a jak zmieni sie ilość zd elementarnych, proste, w przypadku zb A mamy 2^n*2^n, mozliwości, a dla zb A` mamy 2^(n+1) * 2^(n+1) czyli 4 razy wiecej, łatwo znaleźć warunki poczatkowe, i zad chyba zrobione,

btw, jak się rozpisze z sumy fajna tożsamośc wychodzi,

Arek a jakie było na OM?

v · Post autor: v » 18 gru 2004, o 23:22

Do rozwiązania już doszedłem, znowu ze wzoru na n-tą potęgę sumy (dzięki jeszcze raz).
Jakby kogoś to interesowało to będzie tak:
A = (n PO 0) * 2^n + (n PO 1) * 2^(n-1) + ... + (n PO (n - 1)) * 2^1 + (n PO n) * 2^0
A = Suma((n PO i) * 2^(n-i)) = (2 + 1)^n = 3^n

do każdego zbioru pierwszego wylosowanego dobieramy wszystkie możliwe inne podzbiory bez tych już wylosowanych.
BTW. jak zamiast tego równania wstawić obrazek ze sformatowanymi danymi? sam się wstawi?

Yavien · Post autor: **Yavien** » 19 gru 2004, o 01:27

BTW. jak zamiast tego równania wstawić obrazek ze sformatowanymi danymi? sam się wstawi?

v, popatrz na link do latexa w moim podpisie. Chyba o to chodzi?

Hydroksozbiory · Post autor: **Hydroksozbiory** » 19 gru 2004, o 10:03

a skąd jest ta równość:
Suma((n PO i) * 2^(n-i)) = (2 + 1)^n ??

liu · Post autor: **liu** » 23 gru 2004, o 15:36

Z dwumianu Newtona:

(a+b)^n = (n PO 0)a^n + (n PO 1)a^{n-1}b^1 + ... + (n PO n-1)a*b^{n-1} + (n PO n)b^n