Hányféle csoport alkotható a Földön élő összes emberből?

Ha megnézed, összeszámolod, mivel az üres halmazt, amikor egy ember sincs köztük, nem számoltad bele, ez összesen 2^4-1 = 15.

Ugyanígy n embernél 2^n-1. A kérdésed tehát általánosságban az, hogy n elemszámú halmaznak hány részhalmaza van, az üres halmazt nem számítva, amire 2^n-1 a válasz.

Hm… Az első két válaszadó se lát messzire, mondjuk az első válasz annyiból jogos, hogy a főkérdés el van írva. Helyesen:

„Hányféleképpen rendeződhet csoportokba a Földön élő összes ember?”

És a válasz:

[link]

[link]

Szóval azért nem olyan könnyű kérdés, na; jó hogy elgondolkoztunk rajta az eredeti kérdésnél (ha érdekel valakit, akkor ott adtam sokkal egyszerűbb felső és alsó becslést is). De a linkeken van az általános képlet, ha valakinek van kedve kiszámolni n = 7*10^9-re.

Durva alsó becslés:

Ha az embereket sorba rakjuk és a csoportok is csak sorban képezhetőek, akkor n-1 lehetséges szeparáló hely lehet a csoportok között. Az n-1 helyből bármelyik be vagy ki lehet kapcsolva, így a csoportok száma 2^(n-1).

Durva felső becslés:

Ha a csoportok sorrendje és azokon belül az emberek sorrendje is számít, akkor mondjuk először permutáljuk az embereket, aztán az előző módszerrel csoportokat alkotunk, vagyis n!·2^(n-1) a válasz.

Ezekkel a becslésekkel a példádnál minimum 2³ = 8, maximum 4!·2³ = 192 adódik a valós 15 helyett.

(Nagy n-eknél n! sokkal több, mint 2^n, úgyhogy n! szinte ugyanolyan jó felső becslés.)

n = 7·10⁹

n! · 2^(n-1) ≈ 5.5788 · 10^67982834881 < 10^10^11

Ez sokkal kevesebb, mint 10^10^100 (ami a googolplex)