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

Question

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

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

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

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

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

Answer 1

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

تعداد راه هایی که می توان $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$صدق می کند.

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

موفق باشید.