Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI KOMBINATORIKA

Koliko ima funkcija f(x) koje zadovoljavaju f(f(x))=x

[inlmath]{n\choose k}=\frac{n!}{\left(n-k\right)!k!}[/inlmath]

Koliko ima funkcija f(x) koje zadovoljavaju f(f(x))=x

Postod sans » Četvrtak, 28. Mart 2019, 15:52

Neka je [inlmath]X=\{1,2,3,4\}[/inlmath]. Koliko ima funkcija [inlmath]f\colon X\to X[/inlmath] koje zadovoljavaju jednakost [inlmath](f\circ f)(x)=x[/inlmath] za svako [inlmath]x[/inlmath] iz [inlmath]X[/inlmath]?

Pokušao sam da uprostim zadatak razmatrajući prvo [inlmath]X_1=\{a,b\}[/inlmath], [inlmath]X_2=\{c,d\}[/inlmath] i broj načina da [inlmath]\{1,2,3,4\}[/inlmath] rasporedim u ta dva skupa i izbrojim sve mogućnosti pa da dobijeni zbir saberem sa slučajem [inlmath]X_1=\{a\}[/inlmath], [inlmath]X_2=\{b,c,d\}[/inlmath].
Ako je [inlmath]X_1=\{a,b\}[/inlmath] postoje dve mogućnosti [inlmath]f_1(a)=a[/inlmath], [inlmath]f_1(b)=b[/inlmath] i [inlmath]f_2(a)=b[/inlmath], [inlmath]f_2(b)=a[/inlmath]. Kada te dve mogućnosti pomnožimo sa brojem mogućnosti rasporeda [inlmath]\{c,d\}[/inlmath] (takođe [inlmath]2[/inlmath]) i brojem odabira [inlmath]\{a,b\}[/inlmath] iz [inlmath]\{1,2,3,4\}[/inlmath] dobijem [inlmath]n=2\cdot2\cdot6=24[/inlmath].
S obzirom da je ukupan broj permutacija od [inlmath]4[/inlmath] elementa [inlmath]4!=24[/inlmath] jasno mi je da ovo nije pravilan početak... a prostim prebrojavanjem mogućih funkcija dobije se da je ukupan broj mogućih funkcija [inlmath]10[/inlmath].

S druge strane postavljam sebi, a i vama opštije pitanje:

Šta ukoliko je [inlmath]X=\{1,2,3,\ldots,n\}[/inlmath]. Koliko ima funkcija [inlmath]f\colon X\to X[/inlmath] koje zadovoljavaju jednakost [inlmath](f\circ f)(x)=x[/inlmath] za svako [inlmath]x[/inlmath] iz [inlmath]X[/inlmath]?
Poslednji put menjao Daniel dana Četvrtak, 28. Mart 2019, 23:10, izmenjena samo jedanput
Razlog: Dodavanje Latexa – tačka 13. Pravilnika
sans  OFFLINE
 
Postovi: 3
Zahvalio se: 3 puta
Pohvaljen: 2 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +2

Re: Koliko ima funkcija f(x) koje zadovoljavaju f(f(x))=x

Postod ubavic » Petak, 29. Mart 2019, 02:02

Svaku funkciju [inlmath]f\colon X\rightarrow X[/inlmath] za koju važi [inlmath]x=f\left(f\left(x\right)\right)[/inlmath] za svako [inlmath]x\in X[/inlmath] nazivamo involucija. Lako se pokazuje da svaka involucija mora biti bijekcija. U algebri, svaku bijekciju skupa [inlmath]X[/inlmath] na njega samog nazivamo permutacija skupa [inlmath]X[/inlmath]. Ispostavlja se da skup svih permutacija skupa [inlmath]X[/inlmath] zajedno sa operacijom kompozicije funkcija [inlmath]\circ[/inlmath] čini jednu grupu, koju nazivamo simetrična grupa skupa [inlmath]X[/inlmath] i obeležavamo je sa [inlmath]\mathbb{S}_X[/inlmath] (ako je skup [inlmath]X[/inlmath] konačan i ima [inlmath]n[/inlmath] elemenata, tada koristimo oznaku [inlmath]\mathbb{S}_n[/inlmath], jer skupovi iste kardinalnosti imaju izomorfne simetrične grupe). Ciklus [inlmath]\zeta[/inlmath] je permutacija takva da postoji niz [inlmath]x_1,\dots x_k[/inlmath] od [inlmath]k[/inlmath] različitih elemenata, za koji važi:
  • [inlmath]\zeta\left(x_j\right)=x_{j+1}[/inlmath] za svako [inlmath]1\le j\le k-1[/inlmath],
  • [inlmath]\zeta\left(x_k\right)=x_1[/inlmath],
  • [inlmath]\zeta\left(x\right)=x[/inlmath] za sve [inlmath]x\notin\left\{x_1,\dots,x_k\right\}[/inlmath]
Ciklus [inlmath]\zeta[/inlmath] u tom slučaju označavamo sa [inlmath]\left(x_1\,x_2\,\cdots\,x_k\right)[/inlmath]. Na primer, za ciklus [inlmath]\zeta=\left(2\,4\,3\right)\in\mathbb{S}_4[/inlmath] važi [inlmath]\zeta\left(1\right)=1[/inlmath], [inlmath]\zeta\left(2\right)=4[/inlmath], [inlmath]\zeta\left(3\right)=2[/inlmath] i [inlmath]\zeta\left(4\right)=3[/inlmath].
Jedan od osnovnih rezultata o simetričnoj grupi [inlmath]\mathbb{S}_n[/inlmath] kaže da se svaka permutacija [inlmath]n[/inlmath] elemenata može napisati kao proizvod disjunktnih ciklusa. Uz pomoć ovog stava lako dolazimo do rešenja tvog problema. Naime, ti tražiš permutaciju [inlmath]f[/inlmath] skupa od [inlmath]n[/inlmath] elemenata za koju važi [inlmath]x=f\left(f\left(x\right)\right)[/inlmath] za svako [inlmath]x\in X[/inlmath], odnosno za koju važi [inlmath]f^2=f\circ f=\varepsilon[/inlmath] (gde je [inlmath]\varepsilon[/inlmath] jedinični element grupe [inlmath]\mathbb{S}_n[/inlmath]). Drugim rečima, ti tražiš sve elemente reda dva u grupi [inlmath]\mathbb{S}_n[/inlmath]. Po pomenutom stavu, tražena permutacija se može napisati kao proizvod disjunktnih ciklusa tj. [inlmath]f=\zeta_1\circ\zeta_2\circ\dots\circ\zeta_l[/inlmath]. Kako su ciklusi disjunktni, oni komutiraju međusobno (sama grupa [inlmath]\mathbb{S}_n[/inlmath] nije komutativna!) pa je [inlmath]f^2=\zeta_1^2\circ\zeta_2^2\circ\dots\circ\zeta_l^2[/inlmath]. Opet, pošto su navedeni ciklusi disjunktni, važi [inlmath]\zeta_1^2=\varepsilon[/inlmath], [inlmath]\zeta_2^2=\varepsilon[/inlmath], ..., [inlmath]\zeta_l^2=\varepsilon[/inlmath]. Iz ovoga dalje sledi da je svaki navedeni ciklus reda jedan ili dva, odnosno da je oblika [inlmath](x_1)[/inlmath] ili [inlmath]\left(x_1\,x_2\right)[/inlmath]. Cikluse reda jedan možemo ignorisati (jer su oni zapravo jedna ista permutacija - [inlmath]\varepsilon[/inlmath]), pa je dovoljno posmatrati samo cikluse reda dva. Tražena permutacija je u potpunosti određena sa izborom ciklusa reda dva, i obrnuto, svaki izbor disjunktnih ciklusa reda dva određuje jednu jedinstvenu permutaciju sa traženom osobinom. Tačno [inlmath]k[/inlmath] disjunktnih ciklusa možemo izabrati na
[dispmath]{n\choose2k}\frac{\left(2k\right)!}{k!2^k}={n\choose2k}\left(2k-1\right)!![/dispmath] načina ([inlmath]2k[/inlmath] elemenata biramo na [inlmath]n\choose2k[/inlmath] načina, a tih [inlmath]2k[/inlmath] elemenata možemo zatim rasporediti u parove na [inlmath]\left(2k\right)!/\left(k!2^k\right)[/inlmath] načina). U dekompoziciji permutacije iz grupe [inlmath]\mathbb{S}_n[/inlmath] može biti najviše [inlmath]\lfloor n/2\rfloor[/inlmath], a najmanje [inlmath]0[/inlmath] ciklusa reda dva, pa sumiranjem prethodnog izraza dobijamo konačan rezultat
[dispmath]\sum_{k=0}^{\lfloor n/2\rfloor}{n\choose2k}\left(2k-1\right)!!.[/dispmath]
Inače, broj koji tražiš je poznat kao Telephone number. Na linkovanoj stranici možeš pročitati neke zanimljivosti o ovim brojevima (npr. In the mathematics of chess, the telephone numbers count the number of ways to place [inlmath]n[/inlmath] rooks on an [inlmath]n\times n[/inlmath] chessboard in such a way that no two rooks attack each other (the so-called eight rooks puzzle), and in such a way that the configuration of the rooks is symmetric under a diagonal reflection of the board.)

Rešenje koje sam naveo je elegantno ako se poznaje teorija grupa. Ovo mi je prvo palo na pamet. Nisam istraživao dalje, i ne znam da li postoji neko elementarnije rešenje.
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 385 puta
Pohvaljen: 641 puta

  • +1

Re: Koliko ima funkcija f(x) koje zadovoljavaju f(f(x))=x

Postod sans » Petak, 29. Mart 2019, 17:04

Zahvaljujem na brzom odgovoru koji mi je, bez obzira što mi nije u potpunosti jasan ipak proširio vidike.
Rešenje elementarnog zadatka se svodi na to da se od četiri elementa:
1) svi preslikavaju u sebe. Ovde imamo
[dispmath]{4\choose4}=1[/dispmath] 2) dva se preslikavaju u sebe a dva se preslikavaju u svoj par,
[dispmath]{4\choose2}=6[/dispmath] 3) dva para se preslikavaju u svoj par
[dispmath]\frac{4\choose2}{2!}=3[/dispmath]
Za opšti slučaj rešenje je
ako je [inlmath]n[/inlmath] parno:
[dispmath]{n\choose n}+{n\choose2}+\frac{{n\choose2}{n-2\choose2}}{2!}+\frac{{n\choose2}{n-2\choose2}{n-4\choose2}}{3!}+\cdots+\frac{{n\choose2}{n-2\choose2}\cdots{2\choose2}}{\left\lfloor\frac{n}{2}\right\rfloor!}[/dispmath]
ako je [inlmath]n[/inlmath] neparno:
[dispmath]{n\choose n}+{n\choose2}+\frac{{n\choose2}{n-2\choose2}}{2!}+\frac{{n\choose2}{n-2\choose2}{n-4\choose2}}{3!}+\cdots+\frac{{n\choose2}{n-2\choose2}\cdots{3\choose2}}{\left\lfloor\frac{n}{2}\right\rfloor!}[/dispmath]
sans  OFFLINE
 
Postovi: 3
Zahvalio se: 3 puta
Pohvaljen: 2 puta

  • +2

Re: Koliko ima funkcija f(x) koje zadovoljavaju f(f(x))=x

Postod Daniel » Subota, 30. Mart 2019, 01:53

Pokazao bih to i grafičkim putem, koristeći čistu kombinatoriku.
Kao što je već rečeno, trivijalan slučaj tražene funkcije je [inlmath]f(x)=x[/inlmath], tj. svaki element se slika u samog sebe (slika levo).

preslikavanje.png
preslikavanje.png (3.69 KiB) Pogledano 720 puta

Uslov [inlmath](f\circ f)(x)=x[/inlmath] zadovoljavaće i funkcija na slici u sredini, koja ima, da se slobodnije izrazim, jedan „ukršten par“, dok se svaki od preostalih elemenata slika u samog sebe.
Na slici desno imamo dva ukrštena para, takva funkcija takođe zadovoljava uslov.
Uslov će zadovoljavati svaka funkcija koja ima proizvoljan broj tako ukrštenih parova, pod uslovom da se svaki od onih elemenata koji ne pripadaju ukrštenim parovima slika u samog sebe.
Ukrštenih parova može biti najviše [inlmath]\frac{n}{2}[/inlmath] kada je [inlmath]n[/inlmath] parno, odnosno [inlmath]\frac{n-1}{2}[/inlmath] kada je [inlmath]n[/inlmath] neparno. Ili, u opštem slučaju (nezavisno od parnosti [inlmath]n[/inlmath]), može ih biti [inlmath]\left\lfloor\frac{n}{2}\right\rfloor[/inlmath], tj. celobrojni deo od [inlmath]\frac{n}{2}[/inlmath].

Nađimo sada broj funkcija kod kojih imamo [inlmath]k[/inlmath] ukrštenih parova (nakon toga ćemo pustiti sumu po [inlmath]k[/inlmath] da ide od [inlmath]0[/inlmath] do [inlmath]\left\lfloor\frac{n}{2}\right\rfloor[/inlmath], jer [inlmath]k[/inlmath] može uzeti sve ove vrednosti).
Prvi ukršteni par možemo odabrati na [inlmath]n\choose2[/inlmath] načina (kombinacije bez ponavljanja, jer od ukupno [inlmath]n[/inlmath] elemenata biramo neka [inlmath]2[/inlmath]). Nakon toga nam je ostalo [inlmath]n-2[/inlmath] elemenata od kojih biramo njih [inlmath]2[/inlmath] za drugi ukršteni par, prema tome, broj takvih načina je [inlmath]n-2\choose2[/inlmath]. Sledeći binomni koeficijent će biti [inlmath]n-4\choose2[/inlmath] itd..., a poslednji ([inlmath]k[/inlmath]-ti) binomni koeficijent biće [inlmath]n-2k+2\choose2[/inlmath]:
[dispmath]{n\choose2}{n-2\choose2}{n-4\choose2}\cdots{n-2k+2\choose2}[/dispmath] Množenjem ovih binomnih koeficijenata dobićemo [inlmath]k![/inlmath] puta veći rezultat od stvarnog broja odabira [inlmath]k[/inlmath] ukrštenih parova, jer smo za svaki od tih slučajeva računali sve njegove permutacije, kojih ima [inlmath]k![/inlmath]. Dakle, proizvod binomnih koeficijenata treba sada podeliti sa [inlmath]k![/inlmath] (slično odnosu varijacija bez ponavljanja i kombinacija bez ponavljanja):
[dispmath]\frac{{n\choose2}{n-2\choose2}{n-4\choose2}\cdots{n-2k+4\choose2}{n-2k+2\choose2}}{k!}[/dispmath] Binomne koeficijente sada napišimo preko njihove definicije:
[dispmath]\frac{\frac{n!}{\cancel{(n-2)!}2!}\frac{\cancel{(n-2)!}}{\cancel{(n-2-2)!}2!}\frac{\cancel{(n-4)!}}{\cancel{(n-4-2)!}2!}\cdots\frac{\cancel{(n-2k+4)!}}{\cancel{(n-2k+4-2)!}2!}\frac{\cancel{(n-2k+2)!}}{(n-2k+2-2)!2!}}{k!}=\frac{n!}{2^k(n-2k)!k!}[/dispmath] Prema tome, broj traženih funkcija iznosi
[dispmath]\enclose{box}{\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!}{2^k(n-2k)!k!}}[/dispmath] što je identično rezultatu koji je dobio ubavic, a što se može i pokazati ako izraz pod sumom malo transformišemo:
[dispmath]\frac{n!}{2^k(n-2k)!k!}=\frac{n!(2k)!}{2^k(n-2k)!(2k)!k!}={n\choose2k}\frac{(2k)!}{2^kk!}=[/dispmath][dispmath]={n\choose2k}\frac{\cancel{2k}(2k-1)\cancel{(2k-2)}(2k-3)\cancel{(2k-4)}\cdots\cancel6\cdot5\cdot\cancel4\cdot3\cdot\cancel2\cdot1}{\cancel{2k}\cdot\cancel{2(k-1)}\cdot\cancel{2(k-2)}\cdots\cancel{(2\cdot3)}\cdot\cancel{(2\cdot2)}\cdot\cancel{(2\cdot1)}}=[/dispmath][dispmath]={n\choose2k}(2k-1)(2k-3)\cdots5\cdot3\cdot1={n\choose2k}(2k-1)!![/dispmath]
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

  • +1

Re: Koliko ima funkcija f(x) koje zadovoljavaju f(f(x))=x

Postod sans » Subota, 30. Mart 2019, 10:17

Daniel je napisao: Prema tome, broj traženih funkcija iznosi
[dispmath]\enclose{box}{\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!}{2^k(n-2k)!k!}}[/dispmath] što je identično rezultatu koji je dobio ubavic, a što se može i pokazati ako izraz pod sumom malo transformišemo:
[dispmath]\frac{n!}{2^k(n-2k)!k!}=\frac{n!(2k)!}{2^k(n-2k)!(2k)!k!}={n\choose2k}\frac{(2k)!}{2^kk!}=[/dispmath][dispmath]={n\choose2k}\frac{\cancel{2k}(2k-1)\cancel{(2k-2)}(2k-3)\cancel{(2k-4)}\cdots\cancel6\cdot5\cdot\cancel4\cdot3\cdot\cancel2\cdot1}{\cancel{2k}\cdot\cancel{2(k-1)}\cdot\cancel{2(k-2)}\cdots\cancel{(2\cdot3)}\cdot\cancel{(2\cdot2)}\cdot\cancel{(2\cdot1)}}=[/dispmath][dispmath]={n\choose2k}(2k-1)(2k-3)\cdots5\cdot3\cdot1={n\choose2k}(2k-1)!![/dispmath]

Kada je [inlmath]k=0[/inlmath], tada je [inlmath]2k-1[/inlmath] negativno pa bih ga radije izbacio iz sume napisane u obliku koji je dao ubavic, dok je u obliku koji si ti uokvirio sasvim regularno da [inlmath]k[/inlmath] uzima sve vrednosti od [inlmath]0[/inlmath] do [inlmath]\left\lfloor\frac{n}{2}\right\rfloor[/inlmath]
[dispmath]\enclose{box}{1+\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}{n\choose2k}(2k-1)!!}[/dispmath]
sans  OFFLINE
 
Postovi: 3
Zahvalio se: 3 puta
Pohvaljen: 2 puta

  • +2

Re: Koliko ima funkcija f(x) koje zadovoljavaju f(f(x))=x

Postod Daniel » Subota, 30. Mart 2019, 14:30

Može i tako, ali je dvostruki faktorijel negativnih neparnih brojeva sasvim regularan.
Ako pođemo od rekurentne veze
[dispmath](n+2)!!=(n+2)n!![/dispmath] prebacivanjem [inlmath](n+2)[/inlmath] na levu stranu dolazimo do takođe rekurentne veze
[dispmath]n!!=\frac{(n+2)!!}{n+2}[/dispmath] i, uvrštavajući [inlmath]n=-1[/inlmath], dobijamo
[dispmath](-1)!!=1[/dispmath] Možemo uočiti da ovo nismo mogli primeniti na običan faktorijel negativnih celih brojeva, jer bismo već za [inlmath](-1)![/inlmath] u rekurentnoj vezi [inlmath]n!=\frac{(n+1)!}{n+1}[/inlmath] dobili nulu u imeniocu – što znači da faktorijel negativnih celih brojeva nije definisan.
Nulu u imeniocu bismo takođe dobili i da smo u [inlmath]n!!=\frac{(n+2)!!}{n+2}[/inlmath] uvrstili [inlmath]n=-2[/inlmath], što znači da ne postoje dvostruki faktorijeli parnih negativnih brojeva.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta


Povratak na KOMBINATORIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 45 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 13:22 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs