به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+2 امتیاز
2,587 بازدید
سوال شده در دبیرستان توسط

ارائه واثبات فرمول براي اين چهار مسئله؟؟

1-تعداد راه هاي توزيع nشي متمايز درkدسته ي متمايز؟؟

2-تعداد راههاي توزيع nشي متمايز درkدسته ي يكسان؟؟

3-تعداد را ههاي توزيعnشي يكسان درk دسته ي متمايز؟؟

4تعداد راههاي توزيعnشي يكسان درk دسته ي يكسان؟؟

مرجع: عليرضا علي پور
دارای دیدگاه توسط
+1
می‌شود اسم کتاب را نیز بیاورید؟ اسم نویسندهٔ تنها به عنوان مرجع کفایت نمی‌کند مگر بین جمع چند نفر که همه‌شان می‌دانند پیرامون چه کتابی حرف می‌زنند.

1 پاسخ

+2 امتیاز
پاسخ داده شده توسط
انتخاب شده توسط
 
بهترین پاسخ

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

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

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

موفق باشید.

دارای دیدگاه توسط
+1
سلام
چشم...
بازم ممنونfardina@
به محفل ریاضی ایرانیان خوش آمدید!
کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
حمایت مالی
...