به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+2 امتیاز
8,295 بازدید
در دبیرستان توسط saderi7 (7,822 امتیاز)
ویرایش شده توسط AmirHosein

تعداد حالت‌های ممکن برای انجام ۴ کار زیر را با اثبات بدست آورید.

  1. توزيع $n$ شیء متمايز در $k$ دستهٔ متمايز.

  2. توزيع $n$ شیء متمايز در $k$ دستهٔ یکسان.

  3. توزيع $n$ شیء یکسان در $k$ دستهٔ متمايز.

  4. توزيع $n$ شیء یکسان در $k$ دستهٔ یکسان.

1 پاسخ

+4 امتیاز
توسط fardina (17,196 امتیاز)
انتخاب شده توسط AmirHosein
 
بهترین پاسخ

لطفا در هر سوالی که ایجاد می کنید فقط یک موضوع را بپرسید. و راهنمای سایت رو بخونید. این سوال شما جزو سوالاتی میشه که انگار می خواهید کاربران برای شما کتاب بنویسند. این مطالبی که گفتید معمولا در اکثر کتاب ها بیان و اثبات شده اند. به هر حال من سعی میکنم به طور مختصر توضیح بدم.

تعداد راه هایی که می توان $n$ شی متمایز را در $k$ جعبه متمایز قرار داد

برابر است با $k^n$ زیرا $k$ راه برای انتخاب اولین شی، $k$ راه برای انتخاب دومین شی و به همین ترتیب برای انتخاب آخرین شی وجود دارد.

تعداد راه هایی که می توان $n$ شی متمایز را در $k$ جعبه همانند قرار داد

چون اشیاء متفاوت اند می توان فرض کرد یک مجموعه ی $n$ عضوی داریم(چون در مجموعه تکرار نداریم). در اینصورت دنبال تعداد افرازهای این مجموعه ی $n$ عضوی به $k$ زیر مجموعه هستیم. فرض کنید $G(n,k)$ تعداد توزیعهای $n$ شیء متفاوت در $k$ جعبه ی همانند باشد و $g(n,k)$ تعداد راه های توزیع $n$ شی متمایز در $k$ جعبه ی همانند باشد بدون آنکه جعبه ای تهی باشد در اینصورت $$G(n,k)=g(n,k)+g(n,k-1)+g(n,k-2)+...+g(n,1)$$ که $$g(n,k)=\frac 1{k!}[k^n-{k\choose 1}(k-1)^n+{k\choose 2}(k-2)^n-...+(-1)^{k-1}{k\choose k-1}1^n]$$

اثبات این مطلب یه کم طولانیه! و نیاز به مطالب دیگر دارد لطفا برای اثبات به کتاب ها رجوع کنید به عنوان مثال کتاب ریاضیات انتخاب یا چگونه بدون شمارش بشماریم نوشته ی ایوان نیون که ترجمه هم شده است یا در اینجا نسخه ی لاتین را دانلود کنید.

تعداد راه هایی که می توان $n$ شیء همانند را در $k$ جعبه متفاوت قرار داد

برابر است با تعداد جواب هایصحیح نامنفی معادله ی $$x_1+x_2+...+x_k=n$$ که این هم برابر است با تعداد راه های مختلف قرار گرفتن $n$ تا $1$ و $k$ تا $|$برای جدا کردن جعبه ها از هم: $$1|1|11|...|1$$ که این هم برابر است با $\frac{(m+k-1)!}{m!(k-1)!}$ چون $(m+k-1)$ تا شی داریم که به $(m+k-1)!$ حالت کنار هم قرار میگیرند ولی $m$ تا از $1$ ها مشابه هستند و $(k-1)$ تا $|$ هم مشابه هستند در نهایت بر $m!(k-1)!$ تقسیم می شوند. که اگر بررسی کنید $\frac{(m+k-1)!}{m!(k-1)!} $ برابر است با ${mk-1\choose k-1}={m+k-1\choose m}$.

تعداد راه هایی که می توان $n$ شی همانند را در $k$ جعبه همانند قرار داد

برابر است با تعداد افرازهای عدد صحیح مثبت $n$ به $k$ تا جمعوند صحیح مثبت. مثلا افراز های عدد $4$ برابر $$5\qquad 4+1\qquad 3+1+1\qquad 2+1+1+1\\ \qquad\ 3+2\qquad 2+2+1\qquad 1+1+1+1+1+1$$

پس افراز های عدد $5$ برابر $7$ است. اگر تعداد افرازهای $n$ را با $p(n)$ نمایش دهیم در اینصورت $p(5)=7$ .

افراز های با یک جمعوند عدد $5$ برابر $1$ افرازهای با دوجمعوند برابر $2$ افرازهای با سه جمعوند برابر $2$ و افرازهای با چهار و پنج جمعوند برابر $1$ است.

در حالت کلی فکر کنم فرمول خاصی برای $p(n)$ وجود نداره ولی فرمول هایی وجود دارند که به طور بازگشتی بیان می شوند.

اگر فرض کنیم $p_k(n)$ برابر تعداد افراز هایی از $n$ باشد که هیچ یک از جمعوندهای آن از $k$ بزرگتر نباشد. در اینصورت می توان نشان داد جواب مساله ی ما یعنی تعداد افرازهای با دقیقا $k$ برابر است با $p_k(n)$ .

همچنین $p_k(n)$ در فرمول بازگشتی $p_k(n)=p_{k-1}(n)+p_k(n-k)$ برای $1< k< n$صدق می کند.

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

موفق باشید.


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...