Öt, egymástól távol eső tanya között kábeleket feszítenek ki, bármely két tanya között legfeljebb egyet.

a) Elvileg összesen hány különböző hálózatot lehetséges létrehozni a tanyák között? (A hálózatban a kifeszített kábelek száma 0-tól 10-ig bármennyi lehet. Két hálózatot akkor tekintünk különbözőnek, ha van olyan összeköttetés, amely az egyikben létezik, de a másikban nem.)

b) Takarékossági okokból csak 4 kábelt feszítenek ki úgy, hogy a hálózat azért összefüggő legyen. (Összefüggőnek tekintünk egy hálózatot, ha a kábelek mentén bármely tanyáról bármely másikba el lehet jutni, esetleg más tanyák közbeiktatásával.) Hány különböző módon tehetik ezt meg, ha az egyes tanyákat megkülönböztetjük egymástól?

Megoldás:

a) 1024

b) 125