Question

Wszystkich podzbiorów zbioru A, które mają co najwyżej dwa elementy, jest 37? Ile jest wszystkich podzbiorów zbioru A?

Answer 1

Liczbę podzbiorów z n elementów po k (n po k) oblicza się ze wzoru Newtona:
(n)       n!
(  ) = ---------
(k)   (n-k)! k!

U nas jest dane:
(n po 0) + (n po 1) + (n po 2) = 37
Podstawiając kolejno za n liczby naturalne, stwierdzimy, że równanie jest prawdziwe dla n = 8, bo:
(8 po 0) = 1 (zbiór pusty)
(8 po 1) = 8
(8 po 2) = 8!/[(8-2)!2!] = 8!/(6!2!) = 7*8/2 = 28
Razem: 1+8+28=37
Teraz należy więc policzyć jeszcze:
(8 po 3) + (8 po 4) + (8 po 5) + (8 po 6) + (8 po 7) + (8 po 8)
Dobrze jest jednak wiedzieć, że:
(n po k) = (n po (n-k)), co łatwo wykazać.
Więc
(8 po 6) + (8 po 7) + (8 po 8) = (8 po 2) + (8 po 1) + (8 po 0) = 37
Zostaje tylko policzyć:
(8 po 3) = (8 po 5) oraz
(8 po 4)
(8 po 3) = 8!/(5!3!) = 6*7*8/6 = 56 = (8 po 5)
(8 po 4) = 8!/(4!4!) = 5*6*7*8/24 = 70
Razem podzbiorów:
37 + 56 + 70 + 56 + 37 = 256
A więc dokładnie 2⁸, co nie jest przypadkiem, ale właściwością tzw. trójkąta Pascala.