در این بلاگ هدف یافتن تعداد گرنبندها با مهرههای رنگی تحت شرایطی خاص است.
تعریف: هر تابع $f:N \longrightarrow N$ را حسابی مینامند. و تابع حسابی $f$ را ضربی مینامند هرگاه:
$$ \forall m,n \in N , (m,n)=1:f(mn)=f(m)f(n)$$
به سادگی میتوان نشان داد که اگر $k$ عددی طبیعی باشد، توابع
$$\tau:N \longrightarrow N, \tau (m)= \sum_{d|m}1 , \sigma_k:N \longrightarrow N, \sigma_k (m)=\sum_{d|m}d^k$$
$$, \mu:N \longrightarrow N, \mu (1)=1, \mu (m)=\begin{cases}0 & \exists p :p^2|m\\(-1)^r & m=p_1p_2...p_k\end{cases} $$
که در آن $p$ اول و $p_i$ها اعداد اول متمایزند.
(این تابع منسوب به موبیوس $August Ferdinand
Möbius
17 Nov 1790 - 26 Sept 1868$ است).
و داریم:
$$\sum_{d|m} \mu (d)=\begin{cases}1 & m=1\\0 & m \neq 1\end{cases},\sum_{d|m} \phi (d)=m$$
که در آن $ \phi $ تابع اویلر (تمام اعداد طبیعی نابیشتر از $m$ که نسبت به $m$ اولند).
اگر $f$ تابعی ضربی باشد آنگاه $F(m)=\sum_{d|m}f(d) $ نیز ضربی است.
دستور عکس موبیوس ($Möbius Inversion Formula (MIF)$):اگر $f$ تابعی حسابی باشد (لزومی نیست ضربی باشد) و
$$F:N \longrightarrow N,F(m)=\sum_{d|m}f(d)$$
در اینصورت $f$ را می توان چنین به دست آورد:
$$f(m)=\sum_{d|m} \mu (d)F( \frac{m}{d} )=\sum_{d|m} \mu ( \frac{m}{d} )F(d)$$
واضح است که $f$ ضربی است اگر و تنها اگر $F$ ضربی باشد.
اثبات در نبوغ و کوشش موبیوس است که:
{$(d,c),d|m,c|\frac{m}{d}$}$=${$(d,c),c|m,d|\frac{m}{c}$}
از این فرمول به راحتی میتوان نشان داد که:
$$\sum_{d|m} \frac{ \mu (d)}{d}= \frac{ \phi (m)}{m} $$
کاربرد: به اندازه کافی مهر مشکی و سفید داریم. چند تا گردنبد می توان ساخت که از $m$ مهره تشکیل شده باشند؟ (دو گردنبند را یکسان میگیریم که با چرخاندن روی مرکز (نه با برگرداندن) یکی شوند.)
حل:تعداد را با $A_m$ نشان میدهیم. فرض کنید $M(d)$ تعداد گردنبندهای $d$ مهرهای (بدون یکی کردن تحت چرخاندن حول مرکز) باشند که متناوب نیستند. حالا اگر $C$ گردنبندی دلخواه باشد آنگاه یا متناوب نیست که تعدادشان $M(m)$ است و یا متناوب با کوچکترین دوره تناوب $d$ است که تعدادشان $M(d)$ است. با این توضیحات و اینکه حتمن $d|m$ (چرا؟) باید : $a_m=\sum_{d|m}dM(d)$. از طرفی دیگر داریم: $A_m=2^m,$ پس داریم: $2^m=\sum_{d|m}dM(d)$. حالا اگر دستور عکس موبیوس را بکار بگیریم داریم:
$$mM(m)=\sum_{d|m} \mu ( \frac{m}{d})2^d$$
$$ \Rightarrow A_m=\sum_{d|m}M(d)=\sum_{d|m} \frac{1}{d}\sum_{c|d} \mu ( \frac{d}{c})2^c$$
$$=\sum_{c|m} \frac{2^c}{c}\sum_{k| \frac{m}{c}} \frac{ \mu (k)}{k}$$
$$=\sum_{c|m}\frac{2^c}{c}\frac{ \phi(\frac{m}{c})}{\frac{m}{c}}$$
$$= \frac{1}{m}\sum_{c|m}\ \phi ( \frac{m}{c})2^c$$
برای مثال:
$$A_4= \frac{1}{4}( \phi (4)2^1+ \phi (2)2^2+ \phi (4)2^4)= \frac{1}{4}(4+4+2^4)=6$$
اگر مهرههای مشکی را با $0$ و مهرههای سفید را با $1$ نشان دهیم گردنبنها اینها هستند:
$$(0,0,0,0),(1,1,1,1),(1,0,1,0),(1,1,0,0),(1,1,1,0),(0,0,0,1)$$
سوال: آیا می توان تعداد گردنبنها را طوری به دست آورد که علاوه بر شرایط بالا اگر گردنبندی با برگرداندن روی گردنبد دیگری بیفتد آنها را یکی حساب کرد؟
این سوال را ریاضیدان بزرگ مجار جورج پولیا حین مطالعه عمل گروه حل کرد. ایشان نشان داد که تعداد گردنبندهای $m$ مهرهای از $c$ رنگ مهره به اندازه کافی موجود برابر است با $T_m$ که:
$$T_m=\frac{1}{2m}(\sum_{d|m} \phi (d)c^ \frac{m}{d})+ \frac{1}{4}(c^{[ \frac{m+1}{2} ]} +c^{[ \frac{m+2}{2} ]})$$
[] تابع کف ( جزء صحیح) است.
موبیوس بیشتر با نوار معروفش شناخته شده است که از وصل کردن دو سر یک نوار مستطیل شکل با نیم دور چرخاندن به دست میآید که با توپولوژی خارج قسمتی با نوار اصلی همومورف است.
جورج پولیا را ما بیشتر از آموزش ریاضی و با کتابهای "چگونه مساله را حل کنیم" ترجمه احمد آرام و "خلاقیت ریاضی" ترجمه پرویز شهریاری میشناسیم. ایشان معلم ریاضیدان بزرگ "جان فون نویمان" بود. مدتی هم در پرینستون همکار "هاردی" و "لیتل وود" بود که سه نفری کتابی عظیم و قابل ستایش "نامساویها" را نوشتند.
یاد همۀ بزرگانی که نامشان به این بلاگ گره خورده گرامی و زنده باد.
منابع:
1) 104 مسأله در نظریه اعداد تیتو آندرسکو/باقر نشوادیان.
2) مقدمهای بر جبر مجرد درک جی اس رابینسون / علی سرباز جانفدا.
3) شمردنیها را بشمار مجید میرزا وزیری نشر اینترنتی.
$\Box$
