PDA

نسخه کامل مشاهده نسخه کامل : روشهای شمارش



farshchian58
05-05-2010, 14:09
سلام دوستان
می خوام یه استدلال کامل و ساده برای توزیع n شی بین k جعبه را بدونم
1- وقتی n شی مشابه هستند.
2- وقتی n شی متفاوت هستند.
دوباره برای همین دو حالت اینکه
a) حد اقل r شی در هر جعبه باشد.
b) حد اکثر r شی در هر جعبه باشد.
لطفاً استدلال بدست آورد فرمول رو بگین.
اگر کسی جزوه یا pdf در زمینه شمارش و قوانین آن و مسالهای جالب و متنوع داره معرفی کنه.
ممنون

davy jones
06-05-2010, 11:54
سلام دوستان
می خوام یه استدلال کامل و ساده برای توزیع n شی بین k جعبه را بدونم
1- وقتی n شی مشابه هستند.
2- وقتی n شی متفاوت هستند.
دوباره برای همین دو حالت اینکه
a) حد اقل r شی در هر جعبه باشد.
b) حد اکثر r شی در هر جعبه باشد.
لطفاً استدلال بدست آورد فرمول رو بگین.
اگر کسی جزوه یا pdf در زمینه شمارش و قوانین آن و مسالهای جالب و متنوع داره معرفی کنه.
ممنون

1- وقتی n شیئ مشابهند، از اون جایی که معمولا جعبه ها هم مشابه هم فرض میشوند مساله تبدیل به مساله معروف ball-wall میشه. یعنی جعبه ها در حکم دیوار فرض میشن. اگه k جعبه داشته باشیم، باید k-1 دیوار فرض کنیم که بین این n شیئ (توپ) میذاریم و اونها رو به این وسیله به k دسته تقسیم میکنیم. ولی از اونجایی که یه جعبه میتونه خالی هم باشه، پس این که بگیم از بین n-1 فضای خالی بین توپها k-1 تاش رو انتخاب میکنیم، غلطه چون این طوری مساله رو با فرض وجود حداقل یک توپ در هر جعبه حل کردیم.
روش درست حل این مساله اینه که بگیم به ازای هر توپ یک حرف b و به ازای هر یک از جعبه یک حرف w میگذاریم. البته تعداد حروف w دقیقا برابر با k تا نیست بلکه برابر با k-1 فرض میشود.(k-1 دیوار توپها رو به k دسته تقسیم میکنند) حالا مساله رو این طور نگاه میکنیم که با n تا حرف b و k-1 تا حرف w چند کلمه میتوان نوشت؟ جواب این سوال برابر است با :

[ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ]



2- وقتی توپها متفاوتند میتونیم مساله رو از دید توپها ببینیم. یعنی بگیم توپ شماره ی یک، چند انتخاب داره؟ توپ شماره ی 2 چند تا؟ و ...
پس جواب میشه k به توان n (اگر فرض کنیم که جعبه ها میتوانند خالی هم باشند)




a- روش حل این سوال هم عینا مشابه حالت 1 هستش با این تفاوت که از اول و تنها با یک حالت باید در هر جعبه r تا توپ بریزیم. چون توپها و جعبه ها مشابهند این کار به چند حالت انجام نمیشه و فقط یک حالت داره پس اصلا تا اینجا هیچ تغییری در مساله ایجاد نمیکنه و مثل این میمونه که به جای n تا توپ، n-kr تا توپ داریم و جعبه ها هم خالی هستند و میخواهیم مثل حالت 1 اونها پر کنیم. پس جواب میشه:

[ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ]





b- این یکی رو دارم روش فکر میکنم. ام شاء ا... بعدا جوابش رو میذارم.

موفق باشین.
88/2/16