زمان کنونی: ۰۵ آبان ۱۳۹۹, ۰۸:۰۷ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

ساختمان گسسته ، آیتی ۸۴(فصل آنالیز ترکیبی)

ارسال:
  

reyhaneh64 پرسیده:

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

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

۰
ارسال:
  

مازیار صفایی پاسخ داده:

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی)

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


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

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

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

ارسال:
  

ihelpu پاسخ داده:

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی)

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

۰
ارسال:
  

ihelpu پاسخ داده:

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی)

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

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


فایل‌(های) پیوست شده

۰
ارسال:
  

Jooybari پاسخ داده:

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

با سلام
توضیح این رابطه ای که میگم توی بحث ترکیبیاته ولی ما توی آمار داشتیم(!!!)
[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]
که همون جواب مسئلمونه.

ارسال:
  

reyhaneh64 پاسخ داده:

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی)

(۲۸ آذر ۱۳۹۰ ۰۲:۳۴ ق.ظ)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 پاسخ داده:

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

مقادیری که ۱ هستن توی شمارش ما تاثیر ندارن. توان اینها، همون تعداد اشیاشونه. منظور از مقداری که ۱- دادیم اینه فرد بودن و زوج بودن تعداد اشیاش مهمه. معمولاً وقتی از این روش استفاده میشه که زوج بودن یا فرد بودن محتوای یک ظرف مشخص مدنظرمون باشه.
فرض کنید میخاین تعداد حالات توزیع ۴ مهره متفاوت توی ۳ ظرف متفاوت روحساب کنید به شرطی که محتوای ظرف ۳ تعداد فرد مهره باشه. ۴ مهره ما هرکدوم ۳ انتخاب دارن. اگه با اصل شمارش بریم یا ظرف ۳ یا باید ۱ باشه یا ۳/ اگه محتواش ۱ باشه ۴*۸ حالت داریم و اگه ۳ باشه ۴*۲ حالت داریم که در مجموع میشه ۴۰ حالت.
با استفاده از روش بالا، چون ۳ تا ظرف داریم و ۴ شئ از [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]
عدد ۱ حالت ۲۱تایی بودن ظرف ۲ رو میگه و برای بقیه حالتهای ظرف ۲، شئ آخرمون انتخابی نداره. چون بقیه اشیامون دو حالت ظرف ۱ و ظرف ۳دارن بجز شئ آخرمون که برای زوج شدن محتوای این دو ظرف انتخابی نداره. روشی که توی پست قبلی نوشته بودم احتیاج به حل سیکما نداشت.

۰
ارسال:
  

reyhaneh64 پاسخ داده:

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی)

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

۰
ارسال:
  

reyhaneh64 پاسخ داده:

RE: ساختمان گسسته‌، آیتی ۸۴(فصل آنالیز ترکیبی)

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  کارنامه اولیه و نهایی دکتری رشته آیتی lotuss ۹ ۴۶۱ ۰۳ شهریور ۱۳۹۹ ۰۶:۱۸ ب.ظ
آخرین ارسال: Rezaja
  ساختمان داده و پایگاه داده پارسه امیدوار ۴ ۶۰۵ ۱۲ خرداد ۱۳۹۹ ۰۸:۰۳ ب.ظ
آخرین ارسال: marvelous
  ریاضی گسسته روزن ویرایش ۷ همراه با کتاب حل تمرین ها livestrong ۱۲ ۱۱,۱۷۵ ۱۷ اردیبهشت ۱۳۹۹ ۰۴:۳۷ ب.ظ
آخرین ارسال: raziyeh.karbasi
  مشکل در حل تست ۲۲ فصل اول کتاب گسسته یوسفی pure.yaser ۷ ۲,۴۲۲ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۵۴ ب.ظ
آخرین ارسال: mohsentafresh
Information فروش کتابهای گسسته گریمالدی ۴ جلد + راهنمای حل مسائل tabassomesayna ۱ ۸۹۹ ۲۷ فروردین ۱۳۹۹ ۰۴:۵۶ ب.ظ
آخرین ارسال: tabassomesayna
  فصل HEAP از کتاب ساختمان داده طورانی (پارسه) tourani ۳۷ ۱۷,۵۰۷ ۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ
آخرین ارسال: hossein4070
  منبع ساختمان داده RASPINA ۷ ۳,۵۴۲ ۱۶ آذر ۱۳۹۸ ۰۱:۳۰ ق.ظ
آخرین ارسال: Behnam‌
  مهمترین فصل های ذخیره و بازیابی مقسمی enofcom ۱۰ ۱,۲۳۰ ۲۵ آبان ۱۳۹۸ ۰۵:۲۳ ب.ظ
آخرین ارسال: alma1988
Question بهترین منبع ساختمان داده برای کنکور ارشد marvelous ۹ ۱,۸۹۰ ۱۹ آبان ۱۳۹۸ ۱۰:۰۱ ب.ظ
آخرین ارسال: marvelous
  ساختمان داده پوران، فصل اول، راهنمایی برای حل یک مثال ساده marvelous ۲ ۸۳۳ ۲۲ مرداد ۱۳۹۸ ۰۳:۳۰ ب.ظ
آخرین ارسال: marvelous

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close