ترکیب r شیئ منتخب از مجموعه ای از n شیئ متمایز رو میتونیم یه اِفراز (partition) از n شیئ به دو زیرمجموعه در نظر گرفت، که این دو زیرمجموعه به ترتیب شامل r شیئ منتخب و n-r شیئ باقیمونده هست. اغلب ما با مسئله افراز مجموعه ای از n شیئ متمایز به k زیرمجموعه سروکار داریم که هریک از n شیئ تنها به یکی از زیرمجموعه ها تعلق دارن و ترتیب اشیاء داخل زیرمجموعه ها اصلا مهم نیست.
In how many ways can seven businessmen attending a convention be assigned to one triple and two double hotel rooms?
تو این مسئله میخوایم 7 نفر رو به سه گروه افراز کنیم. برای اینکار اول سه نفر رو انتخاب میکنیم، بعد دو نفر رو از 4 نفر باقیمونده انتخاب میکنیم و در آخر هم دو نفر باقی میمونن که میرن اتاق سوم. پس تعداد تقسیم کردن 7 نفر به سه اتاق برابره با:
C(7,3)C(4,2)C(2,2))=7!/3!4!×4!/2!2!×2!/2!=7!/3!2!2!
قضیه: تعداد راه های افراز n شیئ متمایز به k زیرمجموعه با n1 شیئ در زیرمجموعه اول و n2 شیئ در زیرمجموعه دوم و ... nk شیئ در زیرمجموعه kkام برابره با : !(n!/(n1! n2!…nk
قضیه: برای هر عدد صحیح مثبت n داریم:
(x+y)^n=C(n,0) xn+C(n,1) x(n-1) y+C(n,2) x(n-2) y2+⋯+C(n,n-2) x2 y(n-2)+C(n,n-1))xy(n-1)+C(n,n)) yn
n!/(r1!r2!…rk!) برابره با x1r1x2r2 …xkrk ضریب (x1+x2+...+xk)n قضیه: در چند جمله ای
What is the coefficient of x13 x2 x32 in the expansion of (x1+x2+x3 )6?
6!/3!1!2!=60 با توجه به قضیه بالا جواب برابره با
A college team plays 10 football games during a season.
In how many ways can it end the season with five wins, four losses, and one tie?
10!/5!4!1! خب با توجه به قضیه افراز داریم
حالا فرض کنید که n شیئ داشته باشیم که متمایز نباشند و بخواهیم آن ها را به k دسته یا زیرمجموعه تقسیم کنیم. دقت کنید که هر دسته میتواند به هر تعداد دلخواه از اشیاء را داشته باشد. مثلا یکی از حالت ها این است که دسته اول شامل کل اشیاء باشد و بقیه دسته ها خالی باشند.
در اینصورت تعداد حالت ها برابر است با: (C(n+k-1,n
At the end of the day, a bakery gives everything that is unsold to food banks for the needy. If it has 12 apple pies left at the end of a given day, in how many different ways can it distribute these pies among six food banks for the needy?
C(12+6-1,12)=C(17,12)