تالار گفتمان مانشت

تعداد عمل دودویی روی یک مجموعه

(01 فروردین 1396 11:45 ب.ظ)peace2013 نوشته شده توسط: [ -> ]تعداد عمل دودویی روی یک مجموعه

اینجا نوشته که یه binary operation روی مجموعه‌ی S، در واقع یک نگاشتی هست که هر یک از اعضای [tex]S\times S[/tex] رو به اعضای [tex]S[/tex] مپ می‌کنه. در اینجا که [tex]S=\{a,b,c,d,x\}[/tex] هست اعضای [tex]S\times S[/tex] میشه [tex]\{(a,a),\: (a,\: b),\: ...,\: (x,d),\: (x,\: x)\}[/tex] که میشه 25 عضو. در حالت عادی هر کدوم از این 25 عضو رو می‌تونیم به هر یک از 5 عضو S نگاشت کنیم پس [tex]5^{25}[/tex] تابع مختلف می‌تونیم داشته باشیم یا به عبارتی، [tex]n^{n^2}[/tex]. ولی نکته‌ای که هست اینه که نگاشت جابجاپذیر هست، در نتیجه [tex](a,\: b)[/tex] با [tex](b,\: a)[/tex] یکی هست، پس [tex](a,\: b)[/tex] به هر چی مپ بشه، [tex](b,\: a)[/tex] هم به همون مپ میشه. پس به ازای هر [tex](w,\: z)[/tex] در [tex]S\: \times S[/tex] باید [tex](z,\: w)[/tex] ها رو به نوعی حذف کنیم یعنی اونا فقط به 1 جا می‌تونند مپ بشن (نه n جا). در نتیجه تعداد اعضایی که می‌مونه (و میتونن به n جا مپ بشند) میشه [tex]\frac{n(n+1)}{2}[/tex] که برای n=5 میشه 15.

اما میمونه عضو خنثای x. ما چون از operationمون خبر نداشتیم میگفتیم که هر زوج مثلاً [tex](a,\: b)[/tex] ممکن هست به هر چیزی مپ بشه یعنی a*b نمیدونیم که a میشه، b میشه، c یا ... ولی وقتی یکی از a یا b ها، عضو خنثی باشه، اونوقت میدونیم که a*b میشه a چون تعریف عضو خنثی این هست. در نتیجه میدونیم که [tex](a,\: x)[/tex] به a مپ خواهد شد، [tex](b,\: x)[/tex] به b و ... و [tex](x,\: x)[/tex] هم به x. پس برای اینا هم دیگه 5 حالت نداریم و در واقع 1 حالت هست. در نتیجه از اون [tex]\frac{n(n+1)}{2}[/tex] حالت باید n حالت هم کم کنیم و جواب میشه [tex]n^{\frac{n(n-1)}{2}}[/tex] که میشه [tex]5^{10}[/tex]

با تشکر فراوان از توضیحات جامع شما
موفق و پیروز باشید