به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+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>


☑ راهنمایی بیشتر: راهنمای تایپ
تلگرام محفل ریاضی
24 نفر آنلاین
0 عضو و 24 مهمان در سایت حاضرند
بازدید امروز: 1192
بازدید دیروز: 5435
بازدید کل: 4834304
...