مجموعه تمامی مقسوم علیه های عدد ۲۱۰ که با d210 نمایش داده می شود همراه با رابطه عاد کردن (شمردن) یک جبر بول است تعداد زیر جبرهای حداقل دو عنصری ان کدام است؟(مهندسی کامپیوتر-۸۸)
و اما سوال من اول اینکه تعداد مقسوم علیه ها را چگونه حساب می کنند همچنین تعداد عناصر و تعداد زیر جبر؟
(۰۱ تیر ۱۳۹۴ ۱۱:۵۲ ق.ظ)sherlock990 نوشته شده توسط: مجموعه تمامی مقسوم علیه های عدد ۲۱۰ که با d210 نمایش داده می شود همراه با رابطه عاد کردن (شمردن) یک جبر بول است تعداد زیر جبرهای حداقل دو عنصری ان کدام است؟(مهندسی کامپیوتر-۸۸)
و اما سوال من اول اینکه تعداد مقسوم علیه ها را چگونه حساب می کنند همچنین تعداد عناصر و تعداد زیر جبر؟
- تعداد مقسوم علیه های یک عدد
من اول با یک مثال توضیحاتم رو میدم و بعد حالت کلی میگم:
مثلاً فرض کنید می خواهیم مقسوم علیه های ۳۶۰ را حساب کنیم. می دانید که هر عدد را می توانید به صورت حاصلضرب تعدادی عدد اول نوشت و [tex]360=2^33^25[/tex]. واضح هست که هر عدد به صورت [tex]2^{\alpha}3^{\beta}5^{\gamma}[/tex] که [tex]0\le\alpha\le3[/tex]، [tex]0\le\beta\le2[/tex] و [tex]0\le\gamma\le1[/tex] یک مقسوم علیه عدد ۳۶۰ خواهد بود و بنابراین برای بدست آوردن تعداد مقسوم علیه ها کافی است که تعداد این نوع اعداد را بشماریم. طبق اصل ضرب تعداد این اعداد برابر [tex]4\times3\times2=24[/tex] خواهد بود (عدد الفا چهار حالت دارد، عدد بتا سه حالت و عدد گاما دو حالت) یعنی عدد ۳۶۰ دارای ۲۴ مقسوم علیه (۱، ۲، ۳، ۴، ۵، ۶، ۸، ۹، ۱۰، ۱۲، ۱۵، ۱۸، ۲۰، ۲۴، ۳۰، ۳۶، ۴۰، ۴۵، ۶۰، ۷۲، ۹۰، ۱۲۰، ۱۸۰ و ۳۶۰) است.
در حالت کلی، برای محاسبه تعداد مقسوم علیه های هر عدد [tex]n\in Z^ [/tex] که [tex]n>1[/tex] است می نویسیم [tex]n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}[/tex] که در آن به ازای هر [tex]1\le i\le k[/tex] اعداد [tex]p_i[/tex] اعداد اول هستند و [tex]e_i>0[/tex] است. هرگاه [tex]m\mid n[/tex] باشد (یعنی m مقسوم علیه n باشد) آنگاه [tex]m=p_1^{f_1}p_2^{f_2}...p_k^{f_k}[/tex] که در آن [tex]0\le f_i\le e_i[/tex] است. در نتیجه، طبق اصل ضرب، تعداد مقسوم علیه های مثبت n برابر با [tex](e_1 1)(e_2 1)...(e_k 1)[/tex] خواهد بود.
- شمارش تعداد زیرجبرها
من برای توضیح این مطلب، همین تستی که گفتید رو به سه روش پاسخ می دهم تا متوجه شوید:
روش اول)
قبل از هر چیز، یادآوری می کنم که جبر بول جبر است که دارای خواص جابجایی، شرکت پذیری، توزیع پذیری، عضو خنثی و مکمل باشد، بنابراین این خواص باید در زیرجبرهای آن جبربول نیز برقرار باشد.
همانطور که صورت سوال گفته یک جبر بول هست (تجزیه عدد به عامل های اول [tex]210\: =\: 2\times3\times5\times7[/tex]) و نمودار Hasse آن به صورت زیر است:
که هر راس این نمودار از حاصلضرب عامل های اول مقسوم علیه های عدد ۲۱۰ تشکیل شده است، مثلاً عدد ۳۰ از حاصلضرب عامل های اول [tex]2\times3\times5[/tex] به دست آمده است. پس یعنی نمودار Hasse رابطه [tex]( D_{210} , \mid\: )[/tex] دارای یک ریختی (isomorphism) با رابطه [tex](P(\{2,3,5,7\})\: ,\: \subseteq)[/tex] است (که مجموعه [tex]\{2,3,5,7\}[/tex] مجموعه عامل های اول عدد ۲۱۰ می باشد و [tex]P(\{2,3,5,7\})[/tex] مجموعه توانی آن می باشد). می توان با شمردن تعداد زیرجبرهای رابطه ی یکریخت پاسخ مسئله را به دست آورد. دقت کنید که تنها رابطه ای [tex]( D_{n} , \mid\: )[/tex] که دارای زیرجبر یک عضوی است وقتی است که n=1 باشد و [tex]n>1[/tex] زیرجبر یک عضوی نخواهیم داشت، پس شرط حداقل دوعضوی اضافه می باشد. حال با توجه به اینکه به ازای هر دسته از اعضای [tex]\{2,3,5,7\}[/tex] به یک زیرجبر می رسیم (برای درک بهتر نمودار Hasse زیرجبر [tex](\: P(\{ \{ 2,3 \} , \{ 5,7 \} \}) \: , \: \subseteq )[/tex] و [tex](\: P(\{ \{ 2 \} , \{ 3 \} , \{ 5,7 \} \}) \: , \: \subseteq )[/tex] رسم کنید که می بینید دو نموادر Hasse متفاوت می دهند)، پس برای اینکه ببینیم چند زیرجبر با حداقل دو عضو داریم باید ببینیم که مجموعه [tex]\{2,3,5,7\}[/tex] را به چند طریق می توان به دسته های مختلف دسته بندی کرد که این مسئله دسته بندی اعضای مجموعه همان مسئله افراز اعضای مجموعه می باشد و می دانیم که تعداد حالت هایی که می توان یک مجموعه n عضوی را به r دسته (زیرمجموعه) غیرتهی افراز نمود برابر با عدد استرلینگ نوع دوم [tex]S(n,r)=\frac{1}{n!}\: Sigma_{i=0}^r\: \binom{r}{i}(-1)^i(r-i)^n[/tex] است. چون مجموعه ی [tex]\{2,3,5,7\}[/tex] چهار عضو دارد، در دسته بندی چهار حالت خواهیم داشت:
الف) هر چهار عضو در یک دسته باشند که تعداد آن برابر [tex]S(4,1)=1[/tex] است.
ب) هر چهار عضو در دو دسته افراز شوند که تعداد آن برابر [tex]S(4,2)=7[/tex] است.
پ) هر چهار عضو در سه دسته افراز شوند که تعداد آن برابر [tex]S(4,3)=6[/tex] است.
ت) هر چهار عضو در چهار دسته افراز شوند که تعداد آن برابر [tex]S(4,4)=1[/tex] است.
پس در مجموع تعداد زیرجبرهای حداقل دو عنصری برابر [tex]S(4,1) S(4,2) S(4,3) S(4,4)=1 7 6 1=15[/tex] می باشد.
(به این مجموع اعداد استرلینگ [tex]B(4)=S(n,1) S(n,2) S(n,3) S(n,4)[/tex]، عدد Bell نیز می گویند.)
روش دوم)
زیرجبرهای [tex]D_{210}[/tex] می بایست شامل دو (حداقل دو عضوی)، چهار، هشت و شانزده عضو باشند (چون تعداد اعضای نمودار Hasse یک جبر بول توانی از ۲ می باشد)، بنابراین چهار حالت خواهیم داشت:
الف) فقط یک زیرجبر دو عضوی داریم [tex](\{1,210\})[/tex] که شامل بزرگترین عضو یعنی ۲۱۰ و کوچکترین عضو یعنی ۱ می باشد.
ب) هر زیرجبر چهارعضوی به فرم [tex]\{\: 1\: ,\: x\: ,\: x'\: ,\: 210\: \}[/tex] می باشد که شامل بزرگترین عضو یعنی ۲۱۰، کوچکترین عضو یعنی ۱ و یک عضو غیرکران و مکملش می باشد. در [tex]D_{210}[/tex] چهارده عضو غیرکران ۲، ۳، ۵، ۶، ۷، ۱۰، ۱۴، ۱۵، ۲۱، ۳۰، ۳۵، ۴۲، ۷۰ و ۱۰۵ می باشد که در نتیجه [tex]\frac{14}{2}=7[/tex] جفت عضو غیرکران و مکملش [tex]( \: x\: , \: x'\: )[/tex] وجود دارد و بنابراین ۷ زیرجبر چهارعضوی داریم.
پ) هر زیرجبر ۸ عضوی به فرم [tex]\{1, s_1, s_2, s_3, s_1 \times s_2, s_1 \times s_3, s_2 \times s_3, 210 \}[/tex] که [tex]s_1[/tex] و [tex]s_2[/tex] از عامل های اول عدد ۲۱۰ انتخاب می شوند و [tex]s_3[/tex] از حاصلضرب دو عامل دیگر به دست می آید. مثلا [tex]s_1=2[/tex]، [tex]s_2=3[/tex] و [tex]s_3=5\times7=35[/tex]. برای انتخاب [tex]s_1[/tex] و [tex]s_2[/tex] از بین عامل های اول عدد ۲۱۰ دارای [tex]\binom{4}{2}=6[/tex] حالت خواهیم بود و بنابراین ۶ زیرجبر هشت عضوی داریم.
ت) تنها زیرجبر ۱۶ عضوی نیز خود [tex]D_{210}[/tex] می باشد.
بنابراین تعداد زیرجبرها برابر [tex]1 7 6 1=15[/tex] خواهد بود.
روش سوم)
می توان اثبات کرد متناظر هر زیرجبر [tex]( D_{210} , \mid\: )[/tex] یک جبربول [tex]( D_{n} , \mid\: )[/tex] وجود دارد که n یک مقسوم علیه عدد ۲۱۰ می باشد. عدد ۲۱۰ دارای ۱۶ مقسوم علیه است که یکی از آنها عدد یک می باشد که جبر یک عضوی نتیجه می دهد و بنابراین ۱۵ مقسوم علیه غیر یک خواهیم داشت و بنابراین ۱۵ زیرجبر حداقل دوعضوی برای رابطه [tex]( D_{210} , \mid\: )[/tex] خواهیم داشت.
(۰۱ تیر ۱۳۹۴ ۰۸:۴۸ ب.ظ)sherlock990 نوشته شده توسط: ممنون دوست عزیز عالی بود امکان داره بگید جواب رو ازکجا پیدا کردید منظورم جزوه یا کتاب؟
از جایی پیدا نکردم / تعداد مقسوم علیه ها رو که تو پیش دانشگاهی خوندیم / البته این مطلب هم تو گریمالدی هست هم تو روزن / زیرجبرها هم قبلاً این سوال رو خودم حل کردم بودم / البته روش اولش رو هم از دکتر اجلالی یاد گرفته بودم (تو جلد اول کتاب بانک سوالات ارشد نصیر هم این روش به صورت کامل اومده)