چند گام را که امتحان کنید (آخرین دیدگاهم را بخوانید) به الگوی زیر میرسید:
$$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)$$
و در نتیجه حدس دیشب ثابت شد.
