Valaki segítene 2 kombinatorikai feladatban?

1)

Azt biztos tudod, hogy ha van N darab dolog, akkor abból K darabot (N alatt K) féleképpen lehet kiválasztani. (Az N alatt a K-t valójában függőlegesen kellene a zárójellel írni, de azt itt nem lehet.)

Az első barát kaphat (32 alatt 4) féleképpen lapot, a következő már csak a maradék 28 lapból (28 alatt 4) féleképpen, stb. Vagyis az összes lehetőség:

(32 alatt 4)·(28 alatt 4)·(24 alatt 4)·(20 alatt 4)·(16 alatt 4)

2)

Valószínű van egyszerűbb megoldás is, de most érd be ezzel:

Legyen kicsit általánosabb: Nem 10, hanem N darab ember van az asztalnál.

Én vagyok az egyik. Nézzük az én kézfogásaimat. Kezet fogok veled, aki valahol szemben vagy velem. A kör mentén egyik oldalon kettőnk között van k ember, a másik oldalon pedig N-2-k ember (azért minusz kettő, mert mi nem vagyunk benne).

Az egyik oldalon lévő k ember egymás között ha kezet fog, akkor nem keresztez minket. A másik oldaliak szintén, mindaddig, amíg egymás között fognak kezet. De ha az egyik oldalról valaki kezet fog egy másik oldalival, máris keresztezik a kettőnk kézfogását.

Vagyis ezt a kézfogásomat k·(N-2-k) kézfogás keresztezi.

Az én összes kézfogásomat ennyi keresztezi:

k=0 .. N-2 Σ k·(N-2-k)

Mindenki összes keresztező kézfogása ennek N/4-szerese. Osztani kell 4-gyel, mert:

- egyrészt amikor én fogok veled kezet illetve te fogsz velem kezet, az ugyanaz

- másrészt amikor A kezet fog B-vel, és ezt keresztezi C-D, az ugyanaz, mint amikor C kezet fog D-vel, és ezt keresztezi A-B

Szóval a végeredmény: A szumma k=0 és N-2 között megy:

1/4·N·Σ k·(N-2-k)

Megjegyzés: A szummát ki lehet fejezni zárt képlettel is, ebből ez a szebb végeredmény jön ki:

N·(N-1)·(N-2)·(N-3)/24

Ez egyébként éppen (N alatt 4). Biztos van valami sokkal egyszerűbb megoldás is, ami rögtön ezt adja, de most már késő van ahhoz, hogy rájöjjek, hogyan :)

N=10 esetén mindez 210

Megvan az egyszerű megoldás:

Bármelyik 4 ember között van 6 kézfogás, és ezek között egyetlen egy pár olyan, amik keresztezik egymást: azok, amik a négyszög átlóit alkotják. Vagyis mindegyik 4 emberhez tartozik 1 keresztező kézfogáspár. 4 embert pedig (N alatt 4) féleképpen lehet kiválasztani.