یک سوال کاربردی آنالیز ترکیبی و احتمال

mrajaei

New Member
ارسال ها
4
لایک ها
0
امتیاز
0
#1
دوستان لطفا مسئله زیر را حل کنید
ورودی:
دو مجموعه کالا داریم که از هر کالا در هر مجموعه به یک تعداد معینی موجود است. مجموع تعداد کالاهای هر دو مجموعه با هم برابر (برابر با N ) است. به صورت فرمال ورودی به صورت زیر است:
[TABLE="width: 500, align: center"]
[TR]
[TD]تعداد
[/TD]
[TD]نام کالا[/TD]
[TD][/TD]
[TD]تعداد[/TD]
[TD]نام کالا[/TD]
[/TR]
[TR]
[TD]p[SUB]1[/SUB][/TD]
[TD]Y[SUB]1[/SUB][/TD]
[TD][/TD]
[TD]q[SUB]1[/SUB][/TD]
[TD]X[SUB]1[/SUB][/TD]
[/TR]
[TR]
[TD]p[SUB]2[/SUB][/TD]
[TD]Y[SUB]2[/SUB][/TD]
[TD][/TD]
[TD]q[SUB]2[/SUB][/TD]
[TD]X[SUB]2[/SUB][/TD]
[/TR]
[TR]
[TD].
.
.[/TD]
[TD].
.
.[/TD]
[TD][/TD]
[TD].
.
.[/TD]
[TD].
.
.[/TD]
[/TR]
[TR]
[TD]p[SUB]k[/SUB][/TD]
[TD]Y[SUB]k[/SUB][/TD]
[TD][/TD]
[TD]q[SUB]m[/SUB][/TD]
[TD]X[SUB]m[/SUB][/TD]
[/TR]
[/TABLE]

که p[SUB]1[/SUB]+p[SUB]2[/SUB]+…+p[SUB]k[/SUB]=N و q[SUB]1[/SUB]+q[SUB]2[/SUB]+…+q[SUB]m[/SUB]=N
خروجی 1: می خواهیم تا تعداد زیر مجموعه های مجاز Nتایی از ترکیب این دو مجموعه (که دارای m*kعضو است) را بدست آوریم.
زیر مجموعه های مجاز Nتایی: زیرمجموعه ای که شامل N ترکیب باشد به طوری که تعداد رخداد هر کالا از هر یک از مجموعه ها برابر تعداد مشخص شده در ورودی مساله باشد ، و ترکیب تکراری در یک زیرمجموعه مجاز وجود ندارد.
در حالت کلی ما m*k حالت متفاوت از ترکیب این دو مجموعه حاصل می شود که تعداد زیرمجموعه های Nتایی آن برابر انتخاب N از mk است اما مشکل این است که همه این حالت ها مجاز نیستند.
خروجی 2: می خواهیم حداکثر احتمال حضور یک ترکیب در مجموعه مجاز را محاسبه کنیم.
بدست آوردن خروجی 2 برای من مهمتر است. ولی با بدست آوردن خروجی 1 نیز می توانم مشکلم را برطرف کنم.

حالت توسعه یافته مساله:
اگر به جای 2 مجموعه r مجموعه به صورت فوق داشته باشیم. که بخواهیم خروجی 1 و 2 را برای زیر مجموعه های Nتایی مجاز از ترکیب r مجموعه کالا را بدست آوریم.

مثال 1:
[TABLE="width: 500, align: center"]
[TR]
[TD]تعداد
[/TD]
[TD]نام کالا[/TD]
[TD][/TD]
[TD]تعداد[/TD]
[TD]نام کالا[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]a[/TD]
[TD][/TD]
[TD]2[/TD]
[TD]X[/TD]
[/TR]
[TR]
[TD]2[/TD]
[TD]b[/TD]
[TD][/TD]
[TD]1[/TD]
[TD]Y[/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD]1[/TD]
[TD]Z[/TD]
[/TR]
[/TABLE]

تعداد کل ترکیب­های این دو مجموعه برابر 6 است :{Xa,Xb,Ya,Yb,Za,Zb} و تعداد زیرمجموعه های 4 تایی مجاز برابر 2 است :{Xa,Xb,Ya,Zb} و {Xa,Xb,Yb,Za} همانطور که مشاهده می کنید تعداد رخدادهای x در هر دو مجموعه برابر 2 و تعداد رخدادهای Y برابر 1 و .....
اما پاسخ خروجی 2 برابر 1 است زیرا Xa در هر دو زیرمجموعه مجاز وجود داردیا به عبارتی حداکثر احتمال حضور مربوط به عنصری است که از ترکیب حداکثر عناصر در هر مجموعه بدست آمده باشد.
 

mrajaei

New Member
ارسال ها
4
لایک ها
0
امتیاز
0
#2
پاسخ : یک سوال کاربردی آنالیز ترکیبی و احتمال

اگر مجموعه nتایی مجاز بتواند شامل عناصر تکراری نیز باشد . آیا به ایتن شکل می توانید راه حلی برای آن ارائه دهید.
دو ستان لطفا راهنمایی کنید چطور می توان مسئله را حل کرد
 
بالا