6243. Uvod u kombinatoriku

Binarna operacija $*$ na skupu $A$ svakom uređenom paru $(x,y)\in A\times A$ dodeljuje tačno jedan element $x*y\in A ,$ tj. to je preslikavanje $A\times A\to A .$ Operaciju možemo zadati tablicom (Kejlijevom tablicom) sa $n$ vrsta i $n$ kolona, u čije polje $(x,y)$ upisujemo $x*y .$

Pravilo proizvoda: $|A_1\times A_2\times\cdots\times A_n|=|A_1|\cdot|A_2|\cdots|A_n| .$ Elementi Dekartovog proizvoda su uređene $n$ -torke $(a_1,a_2,\ldots,a_n)$ sa $a_i\in A_i .$ Praktično: kada objekat biramo u nekoliko koraka, a broj mogućnosti u svakom koraku ne zavisi od toga šta smo ranije izabrali, ukupan broj objekata je proizvod brojeva mogućnosti po koracima. Broj polja tablice je broj uređenih parova:

|A\times A|=n\cdot n=n^2

Svako od $n^2$ polja popunjavamo nezavisno jednim od $n$ elemenata, a različita popunjavanja daju različite operacije. Po pravilu proizvoda:

\underbrace{n\cdot n\cdots n}_{n^2}=n^{n^2}

Primer: za $A=\{a,b\}$ tablica ima $4$ polja, svako sa $2$ mogućnosti, pa ima $2^4=16$ operacija; za $n=3$ ih je već $3^9=19683 .$

Dakle, skup od $n$ elemenata ima $n^{n^2}$ binarnih operacija.

Započni učenje

Privatni časovi

422

Beleške

Slični zadaci

Slični zadaci