چنانچه محفل ریاضی را سودمند یافتید، لطفا برای حمایت از ما به کانال تلگرامی محفل ریاضی بپیوندید!
به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+3 امتیاز
57 بازدید
سوال شده در دانشگاه توسط مرادی
برچسب گذاری دوباره توسط AmirHosein

در یک گروهوار تعداد 3 ضربها، 2 تاست. تعداد 4 ضربها، 4 تاست. تعداد $n$ ضربها برای $n$ تا عضو از این گروهوار چند تاست؟

دارای دیدگاه توسط AmirHosein
+1
منظور از یک $n$-ضرب در یک گروهوار چیست و آیا گروهوار را ترجمهٔ groupoid برداشته‌اید؟
دارای دیدگاه توسط مرادی
ویرایش شده توسط مرادی
+1
AmirHosein@
در یک گروهوار دو $3$-ضرب  $x*(y*z)$ و $(x*y)*z$ وجود دارد؛  گروهوار ترجمه groupoid است.
دارای دیدگاه توسط AmirHosein
+1
چرا فکر می‌کنید ۴ عنصر کنار هم نوشته‌شده را تنها به ۴ روش می‌توان در هم ضرب کرد؟ اگر در منبعی این چنین خوانده‌اید، می‌شود آن‌را معرفی کنید؟

عبارت $a.b.c.d$ در یک ساختار جبری که از شرکت‌پذیر بودن عملش اطلاعی نداریم، در هر یک از ۵ ترتیب زیر ممکن است حاصل متفاوتی پیدا کند.

$((ab)c)d,\;(a(bc))d,\;(ab)(cd),\;a((bc)d),\;a(b(cd))$

بنابراین تعداد چیزی که شما ۴-ضرب می‌نامید ۵ خواهدبود نه ۴.

1 پاسخ

+3 امتیاز
پاسخ داده شده توسط AmirHosein
انتخاب شده توسط مرادی
 
بهترین پاسخ

چند گام را که امتحان کنید (آخرین دیدگاهم را بخوانید) به الگوی زیر می‌رسید: $$f(n)=\sum_{i=1}^{[\dfrac{n}{2}]}(-1)^{i-1}N_n(i)f(n-i)$$ که در آن $f(m)$ تعداد $m$-ضرب‌ها و $N_n(m)$ تعداد جفت‌هایی $m$-جفت‌هایی است که می‌توانید از یک صف $n$-تایی دربیاورید.

پرسش جبری‌ای که اینجا داریم در واقع هم‌ارز با پرسش شمارشی (ترکیبیاتی) زیر است.

«فرض کنید $n$ شیء به یک ترتیب خاص مانند $$x_1x_2\cdots x_n$$ داریم. می‌خواهیم دو تا شیء همسایه را انتخاب و سپس یک شیء در نظر بگیریم (هم‌ارز با اینکه آن دو در هم ضرب‌شده و به جای آن دو حاصل این ضرب که یک چیز است نه دو تا، قرار دهیم). سپس از بین $(n-1)$ شیء با ترتیبی که دارند، دوباره دو شیء همسایه انتخاب کنیم و همین روند را تا زمانیکه به یک شیء برسیم و دیگر انتخاب دو شیء ممکن نباشد ادامه دهیم.

نکتهٔ بسیار بسیار مهم در اینجا این است که پس از مرحلهٔ نخست به مسأله در حالت $(n-1)$ می‌رسیم یعنی حالت بازگشتی و استقرایی داریم! این یعنی اگر از تعداد حالت‌های ممکن در مرحله‌های پیشین اطلاعات داشته‌باشیم می‌توانیم تعداد حالت‌های مرحلهٔ جدید را نیز بدانیم.

تابع $f:\mathbb{N}\rightarrow\mathbb{I}$ را اینگونه تعریف کنید که $f(n)$ ، تعداد حالت‌های ممکن برای ضرب‌کردن $n$ عنصر مرتب باشد. بیایید چند مقدار نخست را محاسبه کنیم. $f(1)$ آشکارا صفر است (به همین دلیل هم‌دامنه را به جای $\mathbb{N}$ ، $\mathbb{I}$ گرفتیم). $x_1x_2$ تنها به یک حالت ضرب می‌شود پس $f(2)=1$ . $x_1x_2x_3$ به دو شکل ضرب می‌شود $(x_1x_2)x_3$ یا $x_1(x_2x_3)$ . پس $f(3)=2$ . توجه کنید که اگر $A$ یک مجموعه و $\cdot$ یک همل دوتایی روی $A$ باشد ولی هیچ ویژگی‌ای از $\cdot$ روی $A$ مانند شرکت‌پذیری فرض نشده‌باشد آنگاه تنها چیزی که می‌توانیم مطمئن باشیم این است که $x_1\cdot x_2$ یک حاصل یکتا دارد و آن نیز به این خاطر است که یک عمل دوتایی، تابع نیز است. اما بیاییم $x_1x_2x_3$ را ببینیم. $(x_1x_2)$ یک عضو یکتا از $A$ است، بفرض $y_1$ پس $(x_1x_2)x_3=y_1x_3$ و $y_1x_3$ یک عضو یکتا از $A$ است، بفرض $y_2$ . از طرف دیگر $x_2x_3$ یک عضو یکتا از $A$ است، بفرض $z_1$ . $x_1(x_2x_3)=x_1z_1$ و $x_1z_1$ یک عضو یکتا از $A$ است، بفرض $z_2$ . ولی آیا $y_2=z_2$ ؟ هیچ قانونی در ساختار جبری $(A,\cdot)$ نیامده‌است که از آن بتوانیم کمک بگیریم (و اتفاقا نمونه وجود دارد که $y_2\neq z_2$ روی دهد). برای همین اگر قانون شرکت‌پذیری یا موردهای همسان وجود نداشته‌باشند باید پرانتزگذاری کنید و عبارت $x_1x_2x_3$ بی‌معنا می‌شود.

اگر نگاه کنید، تعداد انتخاب‌های یک جفت همسایه در ۳ شیء مرتب برابر است با ۲و سپس با حالت $f(2)$ روبرو هستیم که یک است.

برویم سراغ $n=4$ . تعداد انتخاب جفت‌ها برابر با ۳ است و $f(4-1)=f(3)=2$ ولی آیا $f(4)=3\times 2=6$ است؟

$$\begin{array}{lll} (x_1x_2)x_3x_4 & \Longrightarrow & \left\{\begin{array}{l} ((x_1x_2)x_3)x_4\\ (x_1x_2)(x_3x_4) \end{array}\right.\\ X_1(x_2x_3)x_4 & \Longrightarrow & \left\{\begin{array}{l} (x_1(x_2x_3))x_4\\ x_1((x_2x_3)x_4) \end{array}\right.\\ X_1x_2(x_3x_4) & \Longrightarrow & \left\{\begin{array}{l} (x_1x_2)(x_3x_4)\\ x_1(x_2(x_3x_4)) \end{array}\right. \end{array}$$

وقتی $x_1x_2$ جفت شدند آن را $a$ در نظر بگیرید. ضرب کردن $ax_3x_4$ دقیقا به تعداد حالت‌های مرحلهٔ پیش صورت می‌گیرد $(ax_3)x_4=((x_1x_2)x_3)x_4$ یا $a(x_3x_4)=(x_1x_2)(x_3x_4)$ . پس در شمارش $2\times 3=6$ روی می‌دهد ولی عضو تکراری نیز ممکن است روی بدهد! $(x_1x_2)(x_3x_4)$ مانند حالت انتخاب دو جفت و رفتن یک‌ضرب به $f(n-2)$ می‌ماند! پس به غیر از دانستن تعداد یک جفت‌ها باید تعداد دوجفت‌ها و به بالا نیز مهم باشد. تابع $N_n:\mathbb{N}\rightarrow\mathbb{I}$ را این‌گونه تعریف کنید که $N_n(M)$ تعداد حالت‌های ممکن برای انتخاب $m$ تا دو شیء همسایه از $n$ شیء مرتب باشد که این دوتاهمسایه‌ای‌ها مجزا از هم باشند، برای نمونه $N_4(1)=3$ و $N_4(2)=1$ . اگر توجه کنید با کم کردن $N_4(2)f(4-2)$ از $N_4(1)f(4-1)$ یعنی $6-1=5$ ، تعداد دقیق $f(4)$ به‌دست می‌آید.

آیا این اتفاق شانسی بود؟ خیر، در واقع برای یک $n$ ثابت، $(n-1)$ مجموعهٔ $A_1$ تا $A_{n-1}$ تعریف می‌کنیم. توجه کنید که $N_n(1)=n-1$ . $A_i$ مجموعهٔ همهٔ ضرب‌های ممکن $n$ شیء مرتب پس از اینکه شی‌های $i$ و $i+1$ در هم ضرب و حاصلش جایگزین شده‌است. با توجه به توضیح‌های پیشینمان $$f(n)=|A_1\cup\cdots\cup A_{n-1}|$$ اما در این اجتماع اعضای تکراری نیز هستند که البته پس از اجتماع‌گیری به عنوان عنصر یک مجموعه یک‌بار شمرده خواهند شد. از ترکیبیات یا جبر و احتمال دوم دبیرستان به یاد آورید که $$|A_1\cup\cdots\cup A_{n-1}|=\sum_i|A_i|-\sum_{i,j}|A_i\cap A_j|+\sum_{i,j,k}|A_i\cap A_j\cap A_k|-+\cdots+(-1)^{n-1}|A_1\cap\cdots A_{n-1}|$$ چون همهٔ $|A_i|$ ها با هم برابر و برابر $f(n-1)$ هستند پس قسمت اول می‌شود $N_n(1)f(n-1)$ . $A_i\cap A_j$ نیز اگر جفت $i$ ام و جفت $j$ ام مجزا باشند (برای نمونه $x_1x_2$ و $x_2x_3$ پذیرفته نیست ولی $x_1x_2$ و $x_3x_4$ پذیرفته‌است) برابر با $f(n-2)$ عضو دارد ولی اگر مجزا نباشند صفر عضو دارد پس تعداد ناصفرها $N_n(2)$ است و چون ناصفرها تعداد عنصر یکسان دارند جمع دومی برابر با $N_n(2)f(n-2)$ می‌شود. و همین‌گونه تا آخر ولی توجه کنید که بیشترین تعداد جفت که می‌توانید انتخاب کنید $[\dfrac{n}{2}]$ است که از $n-1$ کمتر است پس بهتر است فرمولمان را بی‌دلیل با یک تعداد صفر بزرگ نکنیم و تا $[\dfrac{n}{2}]$ بنویسیم. $$f(n)=\sum_{i=1}^{[\dfrac{n}{2}]}(-1)^{i-1}N_n(i)f(n-i)$$ و در نتیجه حدس دیشب ثابت شد.

لطفا ما را در شبکه های اجتماعی دنبال کنید:
به محفل ریاضی ایرانیان خوش آمدید!
امروز : تاریخ شمسی اینجا نمایش داده می‌شود

♥ حمایت مالی

راهنمایی:

  • برای رفتن به سطر بعدی دو بار Enter بزنید.
  •  یک بار Enter یک فاصله محسوب می‌شود.
  •  _ایتالیک_ یا I و **پررنگ** یا B
  •  نقل‌قول با قراردادن > در ابتدای خط یا ❝
  • برای چپ به راست کردن متن کلیدهای Ctrl+Shift سمت چپ کیبورد را فشار دهید
  •  برای تایپ فرمول ابتدا روی ریاضی کلیک کرده و سپس به کمک آیکون‌های موجود فرمول را در بین دو علامت دلار

<math> $ $ </math>

بنویسید.

  •  برای اینکه فرمول در خط بعدی و وسط صفحه قرار گیرد دو علامت دلار اضافی بنویسید

<math> $$ $$ </math>


☑ راهنمایی بیشتر: راهنمای تایپ
113 نفر آنلاین
0 عضو و 113 مهمان در سایت حاضرند
بازدید امروز: 2416
بازدید دیروز: 12337
بازدید کل: 4533571
...