تالار گفتمان مانشت
ساختمان گسسته ، آیتی ۸۴(فصل آنالیز ترکیبی) - نسخه‌ی قابل چاپ

ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی) - reyhaneh64 - 26 آذر ۱۳۹۰ ۰۸:۰۴ ب.ظ

به چند طریق میتوان ۲۱ مهره غیر همانند را در ۳ جعبه غیر همانند توزیع کرد به طوریکه در جعبه اول تعداد زوجی از مهر‌ها و در جعبه دوم تعداد فردی از مهره‌ها قرار گیرند؟
ج:
۴/(۲۱^۳+۱)

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی) - مازیار صفایی - ۲۷ آذر ۱۳۹۰ ۰۲:۰۵ ق.ظ

راه حل تون غلطه.
توی ظرف اول می تونه هیچ مهره ای قرار نگیره چون صفر زوجه. ولی در ظرف دوم حداقل باید یک مهره باشه.
در ظرف سوم هم حتما تعدا زوجی مهره داریم.
چون تعداد ۲۱ است هر جور حساب کنیم وقتی در ظرف وسط باید فرد تا باشه و در ظرف اول زوج تا. پس ظرف سوم هم می شه زوج.
من به ذهنم می رسه باید از عدم شمول استفاده کرد این جوری:
ظرف اول: ۲a
ظرف دوم: ۲b+1
ظرف سوم‌: ۲C
در نتیجه:
۲a+2b+1+2c=21
۲a+2b+2c=20
a+b+c=10
البته کلا شک دارم. چون پاسخ هر جور که فکر می کنم ۳ به توان ۲۱ در نمیاد. با ماشین حساب که حساب کردم جوای سنجش در میاد: ۲۶۱۵۰۸۸۳۰۱ حالت!!!!!!!!!!!!!!!!!


الان دارم بیشتر فکر می کنم.
اخه این فصل‌ها رو من تازه مطالعه کردم خیلی مسلط نیستم... ولی راه حل شما می دونم اشتباه

یک مثال می زنم:
اگه توی ظرف اول ۲۰ مهره باشه در ظرف دوم فقط مجاز به استفاده از ۱ حالت که همون ۱ مهره است هستید.
اگر توی ظرف اول ۱۸ مهره بذاریم توی ظرف دوم ۲ حالت داریم...

نمی شه این جوری که شما ضرب کردید ضرب کنیم

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی) - ihelpu - 27 آذر ۱۳۹۰ ۰۸:۰۰ ق.ظ

دقیقا درسته . من دیشب بی دقتی کردم و خواستم بیام درستش کنم ولی به کامپیوتر دسترسی نداشتم .بعدا فرمول حل این مساله رو براتون آپلود میکنم. راه حلمو حذف میکنم که کسی گمراه نشه .

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی) - ihelpu - 27 آذر ۱۳۹۰ ۱۱:۳۱ ق.ظ

در ترکیبات ۴ حالت مهم به نام مدلهای مهره و جعبه داریم . که براتون نوشتم حتما حتما حتما حفظ کنید که خیلی سادس .

اما حل این سوال هم کاملا درست بود که البته نتونستم کامل حل کنم ولی پاسخ من خیلی شبیه به حله البته از طریق احتمالات هم رفتم .

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی) - reyhaneh64 - 27 آذر ۱۳۹۰ ۰۶:۱۹ ب.ظ

ممنون از پاسختون
اما کتاب پوران پاسخ این سوال رو
۴/(۲۱^۳+۱) داده
و گزینه های سوال همگی شامل۴/ (۲۱^۳) هست......
راه حلشم نا مفهومه.

ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی) - Jooybari - 28 آذر ۱۳۹۰ ۰۲:۳۴ ق.ظ

با سلام
توضیح این رابطه ای که میگم توی بحث ترکیبیاته ولی ما توی آمار داشتیم(!!!)
[tex](a b c)^{21}=\sum_{0<=i,j,k<=21}^{ }\binom{21}{i j k}a^{i}b^{j}c^{k}[/tex]
رابطه بالا همون بسط ۳ جمله ایه. برای a,c مقدار ۱ و برای b یکبار ۱ و یکبار ۱- معادل میکنیم. به ۲ معادله زیر میرسیم:
[tex](1 (-1) 1)^{21}=\sum_{0<=i,j,k<=21}^{ }\binom{21}{i j k}1^{i}(-1)^{j}1^{k}=1[/tex]
[tex](1 1 1)^{21}=\sum_{0<=i,j,k<=21}^{ }\binom{21}{i j k}1^{i}1^{j}1^{k}=3^{21}[/tex]
رابطه اول به ما میگه روش توزیع ۲۱ شی متفاوت در ۳ ظرف متفاوت به شرطی تعداد اشیای ظرف ۲ فرد باشه یکی کمتر همین توزیع با فرض زوج بودنشه. (توان ۱- نشون میده که چندبار تکرار شده؛ اگه حاصل ۱- شد یعنی توان اون جمله فرده و تعداد اشیای ظرف ۲ هم فرده و اگه ۱ شد یعنی تعداد اشیای ظرف ۲ زوجه)
رابطه دوم هم به ما میگه روش توزیع ۲۱ شی متفاوت در ۳ ظرف متفاوت ۳ به توان ۲۱ حالت داره.
با استفاده از این ۲ عبارت میتوان به این نتیجه رسید که تعداد حالات توزیع ۲۱ شی متفاوت در ۳ ظرف متفاوت به شرطی تعداد اشیای ظرف ۲ فرد باشه میشه [tex](3^{21}-1)/2[/tex]
یکی از جوابهای این رابطه [tex]1^0(-1)^{21}1^0[/tex] هست. این جواب جزء جواب معادله ما محسوب میشه چون تعداد اشیای ظرف ۱ و ۳ زوج هستند ولی برای اینکه از فرمول زیر استفاده کنیم این حالت رو جدا میکنیم.
با جداکردن حالت فوق تعداد [tex](3^{21}-3)/2[/tex] عبارت داریم که میدونیم تعداد اشیای ظرف دوم اونا فرد هستن و مجموع محتوای دو ظرف اول و سوم یک عدد زوج بین ۲ و ۲۰ میشه. (حالتی که مجموعشون ۰ بود رو جدا کردیم.) با توجه به رابطه زیر:
[tex]\forall p>=1 ; ((-1) 1)^{2p}=\sum_{i=0}^{2p}\binom{2p}{i}(-1)^i1^{2p-i}=0[/tex]
مشخص میشه تعداد حالاتی که هر کدام از ظروف اول و سوم محتوای تعداد زوج شئ باشن با حالاتی که هر کدام از ظروف اول و سوم محتوای تعداد فرد شئ باشن برابرن و برابر نصف تعداد کلی ما هستن.
[tex]((3^{21}-3)/2)/2=(3^{21}-3)/4[/tex]
یک حالت خاص هم در بالا داشتیم که با اضافه کردن اون به جواب داریم:
[tex](3^{21}-3)/4 1=(3^{21} 1)/4[/tex]
که همون جواب مسئلمونه.

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی) - reyhaneh64 - 29 آذر ۱۳۹۰ ۰۷:۴۲ ب.ظ

(۲۸ آذر ۱۳۹۰ ۰۲:۳۴ ق.ظ)Lakikharin نوشته شده توسط:  با سلام
توضیح این رابطه ای که میگم توی بحث ترکیبیاته ولی ما توی آمار داشتیم(!!!)
[tex](a b c)^{21}=\sum_{0<=i,j,k<=21}^{ }\binom{21}{i k k}a^{i}b^{j}c^{k}[/tex]
رابطه بالا همون بسط ۳ جمله ایه. برای a,c مقدار ۱ و برای b یکبار ۱ و یکبار ۱- معادل میکنیم. به ۲ معادله زیر میرسیم:
[tex](1 (-1) 1)^{21}=\sum_{0<=i,j,k<=21}^{ }\binom{21}{i k k}1^{i}(-1)^{j}1^{k}=1[/tex]
[tex](1 1 1)^{21}=\sum_{0<=i,j,k<=21}^{ }\binom{21}{i k k}1^{i}1^{j}1^{k}=3^{21}[/tex]
رابطه اول به ما میگه روش توزیع ۲۱ شی متفاوت در ۳ ظرف متفاوت به شرطی تعداد اشیای ظرف ۲ فرد باشه یکی کمتر همین توزیع با فرض زوج بودنشه. (توان ۱- نشون میده که چندبار تکرار شده؛ اگه حاصل ۱- شد یعنی توان اون جمله فرده و تعداد اشیای ظرف ۲ هم فرده و اگه ۱ شد یعنی تعداد اشیای ظرف ۲ زوجه)
رابطه دوم هم به ما میگه روش توزیع ۲۱ شی متفاوت در ۳ ظرف متفاوت ۳ به توان ۲۱ حالت داره.
با استفاده از این ۲ عبارت میتوان به این نتیجه رسید که تعداد حالات توزیع ۲۱ شی متفاوت در ۳ ظرف متفاوت به شرطی تعداد اشیای ظرف ۲ فرد باشه میشه [tex](3^{21}-1)/2[/tex]
یکی از جوابهای این رابطه [tex]1^0(-1)^{21}1^0[/tex] هست. این جواب جزء جواب معادله ما محسوب میشه چون تعداد اشیای ظرف ۱ و ۳ زوج هستند ولی برای اینکه از فرمول زیر استفاده کنیم این حالت رو جدا میکنیم.
با جداکردن حالت فوق تعداد [tex](3^{21}-3)/2[/tex] عبارت داریم که میدونیم تعداد اشیای ظرف دوم اونا فرد هستن و مجموع محتوای دو ظرف اول و سوم یک عدد زوج بین ۲ و ۲۰ میشه. (حالتی که مجموعشون ۰ بود رو جدا کردیم.) با توجه به رابطه زیر:
[tex]\forall p>=1 ; ((-1) 1)^{2p}=\sum_{i=0}^{2p}\binom{2p}{i}(-1)^i1^{2p-i}=0[/tex]
مشخص میشه تعداد حالاتی که هر کدام از ظروف اول و سوم محتوای تعداد زوج شئ باشن با حالاتی که هر کدام از ظروف اول و سوم محتوای تعداد فرد شئ باشن برابرن و برابر نصف تعداد کلی ما هستن.
[tex]((3^{21}-3)/2)/2=(3^{21}-3)/4[/tex]
یک حالت خاص هم در بالا داشتیم که با اضافه کردن اون به جواب داریم:
[tex](3^{21}-3)/4 1=(3^{21} 1)/4[/tex]
که همون جواب مسئلمونه.

من کامل جوابو درک نکردم، ۱ و -۱ رو میشه با مثال برام بگین که چطور یکی کمتر میشه؟

به نظرم تست خیلی سختی بود.

ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی) - Jooybari - 29 آذر ۱۳۹۰ ۰۹:۳۵ ب.ظ

مقادیری که ۱ هستن توی شمارش ما تاثیر ندارن. توان اینها، همون تعداد اشیاشونه. منظور از مقداری که ۱- دادیم اینه فرد بودن و زوج بودن تعداد اشیاش مهمه. معمولاً وقتی از این روش استفاده میشه که زوج بودن یا فرد بودن محتوای یک ظرف مشخص مدنظرمون باشه.
فرض کنید میخاین تعداد حالات توزیع ۴ مهره متفاوت توی ۳ ظرف متفاوت روحساب کنید به شرطی که محتوای ظرف ۳ تعداد فرد مهره باشه. ۴ مهره ما هرکدوم ۳ انتخاب دارن. اگه با اصل شمارش بریم یا ظرف ۳ یا باید ۱ باشه یا ۳/ اگه محتواش ۱ باشه ۴*۸ حالت داریم و اگه ۳ باشه ۴*۲ حالت داریم که در مجموع میشه ۴۰ حالت.
با استفاده از روش بالا، چون ۳ تا ظرف داریم و ۴ شئ از [tex](a b c)^4[/tex] استفاده میکنیم. محتوای ظروف ۱ و ۲ ظو صرف نظر میکنیم و به a,b مقدار ۱ میدیم. به ظرف ۳، ۱- میدیم که تعداد زوج با فرد بودنش متفاوت باشه. اگه جواب هر جمله ۱ باشه یعنی محتوای ظرف ۳ زوجه و اگه جواب ۱- باشه یعنی محتوای ظزف ۳ توی این حالت فرده. مثلاً توی حالت [tex](1)^1(1)^2(-1)^1[/tex] جواب این جمله ۱- شده و محتوای ظرف اول و دوم و سوم به ترتیب ۱ و ۲ و ۱ شده.(البته در محاسبه، این مقدار ضریب هم داره.) با این کار به رابطه [tex](1 1 (-1))^4=1[/tex] میرسیم که نشون میده تعداد جملاتی که توی اونا تعداد اشیای ظرف ۳ فرده از حالت زوج بودنش یکی کمتره. (اگه جواب توی حالتی به فرض ۵- میشد یعنی تعداد جملات با تعداد اشیای فرد ۵ تا بیشتر از حالت زوجشه.) اگه توی همون رابطه بالا به c هم ۱ بدیم یعنی تعداد اشیای ظرف ۳ هم مثل ۱ و ۲ برامون مهم نیست. این حالت کل جوابهای این توزیع رو بدون محدودیت به ما میده که جوابش ۸۱ میشه. با حل دستگاه دو معادله با ۲ مجهول، جواب مسئلمون ۴۰ بدست میاد.

برای حل این مسئلهلازم نیست از این روش استفاده کنیم. یه راه برای حل این مسئله اینه:
[tex]\sum_{i=0}^{9}\binom{21}{2i 1}2^{19-2i} 1[/tex]
عدد ۱ حالت ۲۱تایی بودن ظرف ۲ رو میگه و برای بقیه حالتهای ظرف ۲، شئ آخرمون انتخابی نداره. چون بقیه اشیامون دو حالت ظرف ۱ و ظرف ۳دارن بجز شئ آخرمون که برای زوج شدن محتوای این دو ظرف انتخابی نداره. روشی که توی پست قبلی نوشته بودم احتیاج به حل سیکما نداشت.

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی) - reyhaneh64 - 30 آذر ۱۳۹۰ ۰۷:۵۸ ب.ظ

ممنون دوست عزیز
جواب جالبی بود.