50 مثال حل شده از اصل شمارش – جایگشت و ترکیب
آنچه در این مقاله میخوانید
Toggleاصل شمارش – جایگشت – ترکیب
کاربران عزیز سایت تاتوره سلام. در جلسات گذشته به مبحث اصل شمارش اشاره داشتیم. اصل ضرب ، اصل جمع ، فاکتوریل و فرمول استرلینگ را برای شما توضیح دادیم که زیر مجموعه ی اصل شمارش به حساب می آیند. در این جلسه نیز تصمیم داریم جایگشت و ترکیب را توضیح دهیم و مثال هایی از این دست برای شما حل نماییم. پس با ما همراه باشید تا جایگشت و ترکیب را بهتر از قبل یاد بگیرید.
جایگشت و ترکیب – این مبحث جایگشت + مثال + مسائل حل شده
تعریف: اگر گردایه ای از \(n\) شی متمایز داشته باشیم، هر آرایش (خطی) این اشیا را یک جایگشت آن گردایه میگوییم.
مثال: چند جایگشت از سه حرف a – b – c وجود دارد؟
حل: آرایشهای ممکن عبارتند از: abc – acb – bac – bca – cab – cba
بنابراین تعداد جایگشت های متمایز برابر با ۶ است.
قضیه: تعداد جایگشت های متمایز \(n\) شی متمایز برابر \(n!\) است.
مثال: برای معرفی ۵ بازیکن شروع کننده بازی یک تیم بسکتبال به تماشاگران، چند راه مختلف وجود دارد؟
\[۵!=۵\times 4\times 3\times 2\times 1=120\]
راه برای معرفی بازیکن ها وجود دارد.
مثال: تعداد جایگشت های چهار حرف a,b,c,d برابر ۲۴ است. اما اگر فقط دو حرف از چهار حرف را انتخاب کنیم، یا اگر همان طور که معمولاً عنوان میشود چهار حرف را دو به دو اختیار کنیم، تعداد جایگشت ها چند تا است؟
حل:دو مکان داریم تا اولی را با چهار انتخاب و سپس دومیرا با سه انتخاب پر کنیم. در نتیجه تعداد کل جایگشت ها ۱۲ = ۳ × ۴ است.
با تعمیم استدلالی که در مثال قبل به کار بردیم در مییابیم که اگر \(n\) شی متمایزی را که انتخاب کرده ایم، (نیز از \(n\) شی متمایز \(r\) تا انتخاب کنیم) میتوانیم به
$$n\;\left( {n\;–\;1} \right)\;\left( {n\;–\;2} \right) \ldots \left( {n\;–\;r\; + \;1} \right)$$
طریق آرایش داد. این حاصل ضرب را با نماد \(p\left( {n,\;r} \right)\) یا \(nPr\) نمایش میدهند. بنا به تعریف قرار میدهیم :
قضیه: تعداد جایگشت های \(n\) شی متمایز که \(r\) به\(r\) انتخاب میشوند، یا به بیان بهتر، تعداد آرایشها یا جایگشت های \(r\) شی از\(n\) شی برای \(r\; = 0,\;1,\;2,\; \ldots ,\;n\) عبارت است از:
$$p\left( {n,r} \right) = \frac{{n!}}{{\left( {n – r} \right)!}}$$
اثبات: فرمولp\(\;\left( {n,\;r} \right)\; = \;n\;\left( {n\;–\;1} \right)..\;\left( {n\;–\;r\; + \;1} \right)\) را نمیتوان برای \(r = 0\) به کاربرد اما فرمول زیر رامیتوان به کار برد.
$$p\left( {n,0} \right) = \frac{{n!}}{{\left( {n – 0} \right)!}} = 1$$
برای \(r{\rm{\;}} = {\rm{\;}}1,{\rm{\;}}2,{\rm{\;}} \ldots ,{\rm{\;}}n\) داریم :
\(p\left( {n,\;r} \right) = n\;\left( {n – 1} \right)\left( {n – 2} \right) \ldots \left( {n – r + 1} \right) = \)
\(\frac{{n\left( {n – 1} \right)\left( {n – 2} \right) \ldots \left( {n – r + 1} \right)\left( {n – r} \right)!}}{{\left( {n – r} \right)!}} = \frac{{n!}}{{\left( {n – r} \right)!}}\)
از سراسر وب: مرجی – مرجع مطالب خانه و آشپزخانه، آرایشی و بهداشتی و سبک زندگی
مثال: از فهرست نام ۲۴ عضو یک باشگاه برای انتخاب رئیس، نایب رئیس، خزانه دار و منشی، ۴ نام استخراج میشود. به چند راه مختلف میتوان این کار را انجام داد؟
حل: تعداد جایگشت های متمایزی که ۴ به ۲۴ اختیار میشوند برابر است با
\(p\left( {24,4} \right) = \frac{{24!}}{{\left( {24 – 4} \right)!}} = \frac{{24!}}{{20!}} = 255024\)
اگر به مثال بالا دقت کنید، میبینید که ترتیب قرار گرفتن اعضا اهمیت دارد، مثلاً (از چپ به راست) منشی- خزانه دار- نایب رئیس- رئیس با رئیس- نایب رئیس- منشی- خزانه دار متفاوت است. (تفاوت آنها برای ما اهمیت دارد. یعنی ترتیب مهم است).
مثال: ۵ پسر و ۴ دختر اعضای یک خانواده هستند و میخواهند عکس دست جمعی بگیرند.
الف) به چند طریق میتوانند در یک صف کنار هم قرار بگیرند.
ب) در چند تا از این حالات، پسرها پهلوی هم قرار دارند (یعنی هیچ دختری بین پسرها نیست)
پ) در چند تا از این حالات، پسر ها و دختر ها جداگانه پهلوی هم قرار دارند. (یعنی هیچ دختری بین پسر ها و هیچ پسری بین دختر ها نیست)
ت) در چند تا از این حالات، دختر ها و پسر ها یک در میان کنار هم قرار دارند.
ث) اگر تعداد پسر ها و دختر ها برابر بود (۵ پسر و ۵ دختر داشت) قسمت (ت) را حل کنید.
حل:
الف) چون روی هم ۹ نفرند، پس به \(۹!\) طریق میتوانند کنار هم بایستند.
ب) چون میخواهیم پسر ها پهلوی هم باشند، بنابراین پسر ها را طناب پیچ کرده و یک شی محسوب میکنیم. بنابراین ۴ دختر و یک شی طناب پیچ شده داریم. که به \(۵!\) حالت میتوانند در یک صف قرار بگیرند. اما در هر یک از این !۵ حالت بدست آمده، پسرها به \(۵!\) طریق میتوانند با هم جابجا شوند. در نتیجه بنابراصل ضرب تعداد حالات ممکن برابر است با \(۵! \times 5!\) .
پ) پسرها و دخترها را جداگانه طناب پیچ میکنیم و در داخل یک جعبه میگذاریم. پس عملاً دو شی طناب پیچ شده داریم که به\(۲!\) طریق میتوانند جابجا شوند. اما پسر ها به !۵ و دختر ها به !۴ طریق کنار هم میتوانند جابجا شوند، پس تعداد حالت های ممکن برابر است با: \(۲! \times 5! \times 4!\)
ت) برای یک در میان ایستادن ابتدا با یک پسر شروع میکنیم، بعد یک دختر، دوباره یک پسر، بعد یک دختر و همین طور ادامه میدهیم. پس شکل ایستادن آنها بصورت زیر است: \(\;B\;G\;B\;G\;B\;G\;B\;G\;B\)
که در آن \({\rm{B}}\) به جای پسر و \({\rm{G}}\) به جای دختر است. پسر ها در مکان های \({\rm{B}}\) به \(۵!\) طریق و دخترها در مکان های \({\rm{G}}\) به \(۴!\) طریق با هم جابجا میشوند. بنابر اصل ضرب تعداد حالتهای ممکن برابر است با \(۵! \times 4!\) .
ث) این قسمت همانند قسمت (ت) است. با این تفاوت که تعداد پسرها و دخترها با هم برابرند. این تفاوت در چیدمان آنها بصورت زیر اهمیت پیدا میکند. به چیدمان زیر توجه کنید: \(B\;G\;B\;G\;B\;G\;B\;G\;B\;G\;\;,\;G\;B\;G\;B\;G\;B\;G\;B\;G\;B\)
بنابراین تعداد حالت ممکن برابر است با : \(۲ \times 5! \times 5!\)
تا اینجا متوجه شدیم که جایگشت و ترکیب چه کاربردهایی دارد. اکنون جایگشت با تکرار را بررسی می کنیم. پس با ما همراه باشید.
جایگشت با تکرار
در بسیاری از مسائل باید تعداد جابجا شدنهای \(n\) را حساب کنیم که در آن همه اشیا متمایز نیستند. مثلاً جمله ی \({x^3}{y^2}\) را در نظر بگیرید، این عبارت از ضرب سه تا \(x\) و دو تا \(y\) بدست میآید. حالاتی که \({x^3}{y^2}\) را ایجاد میکند عبارت است از:
\(x\;xx\;y\;y,\;x\;x\;y\;x\;y,\;x\;y\;y\;x\;x\;, \ldots \)
بنابراین برای اینکه تعداد روش هایی را که سه تا \(x\) و دو تا \(y\) کنار هم قرار گیرند تا یک جمله \({x^3}{y^2}\) را بسازند بشماریم. باید تعداد جابجا شدن های سه تای \(x\) و دو تای \(y\) را حساب کنیم. به این نوع جایگشت ها (تبدیلات)، جایگشت (تبدیل) با تکرار میگوییم.
امیدواریم که از مبحث جایگشت و ترکیب خسته نشده باشید. بریم سراغ مثال بعدی.
مثال: با حروف کلمه \(SEED\) چند کلمه چهار حرفی با معنی و بی معنی میتوان ساخت؟
حل: اگر \({\rm{E}}\) ها متمایز بودند تعداد \(۴!\) میشد. در زیر فهرست همه \(۴!\) کلمه چهار حرفی که با حروف کلمه \(SEED\) میتوان ساخت آورده شده است. چون \(E\) ها را متمایز فرض کرده ایم یکی را با \(e\) و دیگری را با \(E\) نشان دادهایم.
\(SEeD\) | \(SEDe\) | \(SeED\) | \(SeDE\) | \(SDEe\) |
\(ESDe\) | \(ESeD\) | \(EeSD\) | \(EeDS\) | \(EDSe\) |
\(DESe\) | \(DEeS\) | \(DeES\) | \(DeSE\) | \(DSEe\) |
\(eESD\) | \(eEDS\) | \(eDSE\) | \(eDES\) | \(eSED\) |
\(SDeE\) | \(EDeS\) | \(DSeE\) | \(eSDE\) |
مثال، \(SEeD\) و \(SeED\) به شکل \(SEED\) تبدیل میشوند، یعنی اگر \(E\) ها را یکسان بگیریم، در بالا برای هر یک، تبدیل مشابه وجود دارد. بنابراین تعداد کل کلمات برابر است با \(\frac{{4!}}{2}\) .
صورت کلی مثال بالا را در قالب یک قضیه بیان میکنیم.
قضیه: فرض کنید \(n\) شی داریم که در آن \(k\) نوع شی متمایز وجود دارد. فرض کنید \({n_1}\) تا از آنها از نوع اول، \({n_2}\) تا از آنها از نوع دوم،… و \({n_k}\) تا از نوع \(k\) ام میباشند. بطوری که \({n_1}\; + {n_2}\; + \; \ldots \; + {n_k}\; = n\) در اینصورت تعداد جایگشت های (تبدیلات) متمایز این \(n\) شی برابر است با:
\(\frac{{n!}}{{{n_1}!{n_2}! \ldots {n_k}!}}\)
اثبات: بدیهی است در صورت متمایز بودن اشیاء تعداد تبدیلات آنها مساوی \(n!\) است. ولی اگر در بین \(n\) شی، شی ایی به تعداد \({n_1}\) بار تکرار شده باشد آنگاه همین \({n_1}\) شی یکسان به \({n_1}!\) طریق بین خودشان جابجا میشوند ولی صورت جدیدی ایجاد نمیکنند. به همین طریق شی نوع دوم که \({n_2}\) بار ظاهر شدهاند به \({n_2}!\) طریق بین خودشان جابجا میشوند ولی صورت جدیدی ایجاد نمیکنند و بلاخره شی نوع \(k\) ام به \({n_k}!\) طریق بین خودشان جابجا شده ولی صورت جدیدی را ایجاد نمیکنند. از این رو تعداد جایگشت های متمایز این \(n\) شی برابر است با: \(\frac{{n!}}{{{n_1}!{n_2}! \ldots {n_k}!}}\)
مثال: حروف \(MASSASAUGA\) را در نظر بگیرید. از آرایش همهی حرفهای \(MASSASAUGA\) در مییابیم که تعداد \(\frac{{10!}}{{4!3!1!1!1!}} = 32400\) آرایش ممکن وجود دارد. در بین این آرایشها \(\frac{{7!}}{{3!1!1!1!1!}} = 140\) آرایش وجود دارند که در آنها هر چهار \(A\) با هم ظاهر شده اند. برای بدست آوردن این نتیجه اخیر همه آرایشهای مرکب از هفت نماد \(AAAA\) (یک نماد)، \(G,\;U,\;M,\;S,\;S\;,S\) را در نظر گرفتهایم.
خوب، در مسائل جایگشت و ترکیب یه مبحثی داریم به اسم جایگشت دوری. بیا با هم اون رو یاد بگیریم.
تعریف: جایگشت های اشیا: وقتی اشیا روی دایرهای مرتب شدهاند، جایگشت های دوری خوانده میشود.
اگر اشیا متناظر در دو آرایش، اشیا قبل و بعد یکسان داشته باشند، دو آرایش را مختلف تلقی نمیکنیم (و آنها را یکپارچه به حساب میآوریم). مثلاً اگر چهار نفر دور یک میز نشسته باشند وقتی کسی به صندلی راست خود منتقل شود، جایگشت مختلفی بوجود نمیآید.
مثال: چند جایگشت دوری از ۴ نفر که دور یک میز گرد نشسته اند وجود دارد؟
حل: اگر به دلخواه جای یک نفر از ۴ نفر را در مکان ثابتی در نظر بگیریم، سه نفر دیگر را میتوانیم به ۳ راه مختلف بنشانیم (مرتب کنیم) به عبارت دیگر شش جایگشت مختلف وجود دارد.
با تعمیم استدلالی که در مثال فوق ارائه شد، نتیجه را در غالب قضیه زیر بیان میکنیم.
قضیه: تعداد جایگشت های \(n\) شی متمایز که روی یک دایره مرتب شدهاند برابر است با : \(\left( {n{\rm{\;}}–{\rm{\;}}1} \right)!\).
مثال: ۵ پسر بچه را به چند طریق میتوان دور یک میز نشاند؟
حل:\(\left( {5{\rm{\;}}–{\rm{\;}}1} \right)! = {\rm{\;}}4! = 24\)
مثال: به چند طریق ۵ پسر بچه و ۵ دختر بچه را یک در میان دور یک میز میتوان نشاند؟
حل: ۵ پسر بچه را به \(\left( {5{\rm{\;}}–{\rm{\;}}1} \right)!\) یعنی \(۴!\) طریق میتوان دور یک میز نشاند.
چون بین هر دو پسر میبایست یک دختر بنشیند، لذا ۵ جا داریم که این ۵ جا را میتوان به !۵ طریق پر کرد. بنابراین طبق اصل ضرب تعداد حالتهای ممکن برابر با !۴ × !۵ است.
جایگشت و ترکیب – این قسمت ترکیب ها
در بحث جایگشت و ترکیب، اکنون به مبحث ترکیب رسیدم. در این قسمت به همراه مثال های فروان بحث ترکیب را دنبال می کنیم. پس با ما همراه باشید.
مسائل زیادی وجود دارند که در آنها تعیین تعداد راه های انتخاب \(r\) شی از بین \(n\) شی متمایز بدون توجه به ترتیب انتخابشان مهم است. چنین انتخابهایی را آرایش ها یا ترکیب ها میگویند.
تعریف: فرض کنید \(n\) شی متمایز\({{\rm{Q}}_n},{\rm{\;}} \ldots ,{\rm{\;}}{{\rm{Q}}_2},{\rm{\;}}{{\rm{Q}}_1}\) داده شده است. هر ترکیب\(r\) تایی از این \(n\) شی، انتخاب \(r\) شی از این \(n\) شی است بدون در نظر گرفتن ترتیب برای آنها. (ترتیب برای آنها مهم نیست).
تعداد ترکیبهای \(r\) عنصر از \(n\) شی را با نماد \(\left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right)\) یا \({}_n^{}{C_r}\)نشان میدهند.
مثال: فردی که دادههایی برای یک سازمان بازاریابی جمع میکند، به چند راه میتواند با سه خانواده از ۲۰ خانواده ساکن در یک مجتمع مسکونی مصاحبه کند؟
حل: اگر به ترتیب خانوادهها توجه داشته باشیم، جواب عبارت است از:
\(P\left( {20,\;3} \right) = \;20 \times 19 \times 18 = 6840\)
اما هر مجموعه از ۳ خانواده \(۳!{\rm{\;}} = {\rm{\;}}6\) بار به حساب میآید. اگر ما به ترتیب انتخاب خانوادهها توجه نداشت باشیم، در اینصورت فقط۱۱۴۰ \(\frac{{6840}}{{3!}} = \) راه وجود دارد که فردی که داده ها را جمع آوری میکند با ۳ خانواده از ۲۰ خانواده مصاحبه کند.
قضیه: تعداد ترکیبات \(r\) تایی \(n\) شی برای \(r\; = \;0,\;1,\;2,\; \ldots ,\;n\)برابر است با :
\(\left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \frac{{n!}}{{\left( {n – r} \right)!r!}}\)
اثبات: هر گردایه \(r\) تایی را میتوان به\(r!\) طریق جابجا کرد، در نتیجه با هر گردایه r تایی، \(r!\) تبدیل میتوان ساخت، بنابراین :
تعداد تبدیلات \(r\)تایی \(n\) شی = \(r!\) × (تعداد ترکیب های \(r\) تایی \(n\) شی)
یعنی:
\(\left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \frac{{p\left( {n,r} \right)}}{{r!}} = \frac{{\frac{{n!}}{{\left( {n – r} \right)!}}}}{{r!}} = \frac{{n!}}{{\left( {n – r} \right)!r!}}\)
مثال: از میان ۱۰ مرد و ۷ زن میخواهیم یک هیئت سه نفره تشکیل دهیم، تعداد روش های انتخاب این سه نفر برابر است با :
\(\left( {\begin{array}{*{20}{c}}17\\3\end{array}} \right) = \frac{{17!}}{{3!14!}}\)
مثال: از میان ۱۰ مرد و ۷ زن میخواهیم ۵ نفر انتخاب کنیم که شامل ۳ مرد و ۲ زن باشد. به چند طریق این کار امکان پذیر است؟
حل:
مرحله اول: تعداد حالت های ممکن برای انتخاب ۳ مرد از میان ۱۰ مرد برابر است: \(\left( {\begin{array}{*{20}{c}}{10}\\3\end{array}} \right)\)
مرحله دوم: تعداد حالت های ممکن برای انتخاب ۲ زن از میان ۷ زن برابر است با: \(\left( {\begin{array}{*{20}{c}}7\\2\end{array}} \right)\)
چون نتیجه هر انتخاب مرحله اول در انتخاب مرحله دوم تأثیری ندارد، لذا طبق اصل ضرب تعداد حالتهای ممکن برای این انتخاب برابر است با: \(\left( {\begin{array}{*{20}{c}}{10}\\3\end{array}} \right) \times \left( {\begin{array}{*{20}{c}}7\\2\end{array}} \right)\)
مثال: به چند راه مختلف میتوان از بین هشت کتاب ریاضی و شش کتاب اقتصاد، دو کتاب ریاضی و سه کتاب اقتصاد انتخاب کرد؟
حل: به \(\left( {\begin{array}{*{20}{c}}8\\2\end{array}} \right)\) راه ممکن میتوان دو کتاب ریاضی و به \(\left( {\begin{array}{*{20}{c}}6\\3\end{array}} \right)\) راه ممکن میتوان سه کتاب اقتصاد را انتخاب کرد. بنابر اصل ضرب تعداد راه های مختلفی که میتوان دو کتاب ریاضی و سه کتاب اقتصاد را انتخاب کرد برابر است با: \(\left( {\begin{array}{*{20}{c}}8\\2\end{array}} \right) \times \left( {\begin{array}{*{20}{c}}6\\3\end{array}} \right) = 560\).
برخی خواص ترکیب
برخی از خواص \(\left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right)\)
قضیه: برای تمام اعداد طبیعی \(n\) و\(۰ \le r \le n\) داریم:\(\left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \left( {\begin{array}{*{20}{c}}n\\{n – r}\end{array}} \right)\)
اثبات:
\(\left( {\begin{array}{*{20}{c}}n\\{n – r}\end{array}} \right) = \frac{{n!}}{{\left[ {n – \left( {n – r} \right)} \right]!\left( {n – r} \right)!}} = \frac{{n!}}{{r!\left( {n – r} \right)!}} = \left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right)\)
قضیه (قاعده پاسکال): برای هر عدد طبیعی \(r\; = \;0,\;1,\;2,\; \ldots ,\;n – 1,\;n\) داریم:
\(\left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{n – 1}\\{r – 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{n – 1}\\r\end{array}} \right)\)
اثبات:
\(\left( {\begin{array}{*{20}{c}}{n – 1}\\{r – 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{n – 1}\\r\end{array}} \right) = \frac{{\left( {n – 1} \right)!}}{{\left[ {\left( {n – 1} \right) – \left( {r – 1} \right)} \right]!\left( {r – 1} \right)!}} + \frac{{\left( {n – 1} \right)!}}{{\left[ {\left( {n – 1} \right) – r} \right]r!}} = \)
\(\frac{{\left( {n – 1} \right)!}}{{\left( {n – r} \right)!\left( {r – 1} \right)!}} + \frac{{\left( {n – 1} \right)!}}{{\left( {n – 1 – r} \right)!r!}} = \)
\(\frac{{\left( {n – 1} \right)!}}{{\left( {n – r} \right)\left( {n – r – 1} \right)!\left( {r – 1} \right)!}} + \frac{{\left( {n – 1} \right)!}}{{\left( {n – r – 1} \right)!r\left( {r – 1} \right)!}} = \)
\(\frac{{\left( {n – 1} \right)!\left( {r + n – r} \right)}}{{\left( {n – r} \right)\left( {n – r – 1} \right)!r\left( {r – 1} \right)!}} = \frac{{n!}}{{\left( {n – r} \right)!r!}} = \left( {\begin{array}{*{20}{c}}n\\r\end{array}} \right)\)
مثال: درستی تساوی زیر را نشان دهید.
\(\left( {\begin{array}{*{20}{c}}m\\k\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{m – 1}\\{k – 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{m – 2}\\{k – 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{m – 3}\\{k – 2}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{m – 3}\\k\end{array}} \right)\)
حل: بنابر قاعده پاسکال داریم :
\(\left( {\begin{array}{*{20}{c}}m\\k\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{m – 1}\\{k – 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{m – 1}\\k\end{array}} \right)\)
اینک مجدداً قاعده پاسکاال را برای \(\left( {\begin{array}{*{20}{c}}{m – 1}\\k\end{array}} \right)\) به کار میبریم، از این رو داریم:
\(\left( {\begin{array}{*{20}{c}}m\\k\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{m – 1}\\{k – 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{m – 2}\\{k – 1}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{m – 2}\\k\end{array}} \right)\)
بلاخره، اگر قاعده پاسکال را برای \(\left( {\begin{array}{*{20}{c}}{m – 2}\\k\end{array}} \right)\) هم به کار بندیم، حکم ثابت میشود.
یکی از کاربردهای بسیار مهم آنالیز ترکیبی آن است که میتوان با استفاده از ترکیب های \(r\) عضو از\(n\) شی بسط جبری \({\left( {x\; + \;y} \right)^n}\) را حساب کرد.
قضیه (بسط دو جمله ای): برای هر عدد طبیعی \(n\) داریم:
\({\left( {x + y} \right)^n} = \mathop \sum \limits_{k = 0}^n \left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right){y^k}{x^{n – k}}\)
اثبات: با در نظر گرفتن حالتهای خاصی مانند:
\({\left( {x\; + \;y} \right)^2}\; = \;\left( {x\; + \;y} \right)\;\left( {x\; + \;y} \right)\; = \;{x^2}\; + \;2xy\; + {y^2}\)
و
\({\left( {x\; + \;y} \right)^3} = \;\left( {x\; + \;y} \right)\left( {x\; + \;y} \right)\left( {x\; + \;y} \right) = \)
\({x^3} + \;\;{x^2}y + \;y{x^2}\; + \;x{y^2}\; + \;y{x^2}\; + \;x{y^2} + \;x{y^2}\; + \;{y^3}\)
روشن میشود که وقتی حاصل ضرب طرف راست مساوی های فوق را محاسبه میکنیم، میبینیم:
جملاتی بصورت \(x{\;^{n – k}}{y^k}\;\;0 \le k \le n\) بدست میآوریم. بنابراین، همه آنچه را که باید انجام دهیم آن است که معلوم کنیم جمله \(x{\;^{n – k}}{y^k}\) چند بار ظاهر میشود. به آسانی معلوم میشود که این تعداد برابر است با \(\left( {\begin{array}{*{20}{c}}n\\{n – k}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right)\). زیرا\(x{\;^{n – k}}{y^k}\) وقتی ظاهر میشود که\(x\) های عامل از \(\left( {x\; + \;y} \right)\) را در\({\rm{y}}\)های بقیه\(k\) عامل \(\left( {x\; + \;y} \right)\) ضرب کنیم. پس:
\({\left( {x + y} \right)^n} = \left( {\begin{array}{*{20}{c}}n\\0\end{array}} \right){x^n} + \left( {\begin{array}{*{20}{c}}n\\1\end{array}} \right)x{y^{n – 1}} + \left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right){x^2}{y^{n – 2}} + \ldots + \)
\(\left( {\begin{array}{*{20}{c}}n\\{n – 1}\end{array}} \right)x{y^{n – 1}} + \left( {\begin{array}{*{20}{c}}n\\n\end{array}} \right){y^n}\)
مثال: ضریب \({x^2}{y^3}\) را بسط \({\left( {2x\; + \;3y} \right)^5}\) بدست آورید.
حل: فرض کنید \(u = 2x\) و \(v = 3y\) بنابراین \({\left( {2x\; + \;3y} \right)^5}\; = {\left( {u\; + \;v} \right)^5}\). ضریب\({u^2}{v^3}\) در بسط\({\left( {u + v} \right)^5}\) برابر است با \(\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)\)، و داریم: \({u^2}{v^3} = \left( {{2^2} \times {3^3}} \right){x^2}{y^3}\)
بنابراین ضریب \({x^2}{y^3}\) در بسط \({\left( {2x\; + \;3y} \right)^5}\) برابر است با \(\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)\left( {{2^2} \times {3^3}} \right) = 1080\)
مثال: مجموع \(\left( {\begin{array}{*{20}{c}}n\\0\end{array}} \right) + \left( {\begin{array}{*{20}{c}}n\\1\end{array}} \right) + \ldots + \left( {\begin{array}{*{20}{c}}n\\n\end{array}} \right)\) را حساب کنید.
حل: از بسط دو جملهای داریم:
\({\left( {x + y} \right)^n} = \sum \left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right){x^k}{y^{n – k}}\)
حال اگر \(x = y = 1\) قرار دهیم، با استفاده از بسط دو جمله ای فوق خواهید دید که جواب \({2^n}\) خواهد شد. (محاسبات را خودتان انجام دهید.)
مثال: مجموع \(\left( {\begin{array}{*{20}{c}}n\\1\end{array}} \right) + 2\left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right) + \ldots + n\left( {\begin{array}{*{20}{c}}n\\n\end{array}} \right)\) را حساب کنید.
حل: داریم:
\(i\left( {\begin{array}{*{20}{c}}n\\i\end{array}} \right) = i \times \frac{{n!}}{{\left( {n – i} \right)!i!}} = \frac{{n\left( {n – 1} \right)!}}{{\left( {n – i} \right)!\left( {i – 1} \right)!}} = n\left( {\begin{array}{*{20}{c}}{n – 1}\\{i – 1}\end{array}} \right)\)
از این رو داریم:
\(\left( {\begin{array}{*{20}{c}}n\\1\end{array}} \right) + 2\left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right) + 3\left( {\begin{array}{*{20}{c}}n\\3\end{array}} \right) + \ldots + n\left( {\begin{array}{*{20}{c}}n\\n\end{array}} \right) = \)
\(n\left[ {\left( {\begin{array}{*{20}{c}}{n – 1}\\0\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{n – 1}\\1\end{array}} \right) + \ldots + \left( {\begin{array}{*{20}{c}}{n – 1}\\{n – 1}\end{array}} \right)} \right]\)
از طرفی با توجه به مثال قبلی داریم :
\(\left( {\begin{array}{*{20}{c}}{n\; – 1\;}\\{0\;}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{n\; – 1}\\{1\;}\end{array}} \right) + \ldots + \left( {\begin{array}{*{20}{c}}{n – 1}\\{n – 1}\end{array}} \right) = {2^{n – 1}}\)
بنابراین
\(n\left[ {\left( {\begin{array}{*{20}{c}}{n – 1}\\{0\;}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{n – 1}\\{1\;}\end{array}} \right) + \ldots + \left. {\left( {\begin{array}{*{20}{c}}{n – 1}\\{n – 1}\end{array}} \right)} \right] = n{2^{n – 1}}} \right.\)
پس داریم :
\(\mathop \sum \limits_{i = 0}^n i\left( {\begin{array}{*{20}{c}}n\\i\end{array}} \right) = n{2^{n – 1}}\)
مثال: فرض کنید بخواهیم \(n\) مهره متمایز را در \(k\) خانه متمایز توزیع کنیم به طوریکه در اولین خان \({n_1}\) مهره، در دومین خانه\({n_2}\) مهره و… و در \(k\) امین خان \({n_k}\) مهره قرار گیرد که در آن \({n_1} + \ldots + {n_k} = n\). برای شمارش تعداد راههای ممکن انجام این کار،\(\left( {\begin{array}{*{20}{c}}n\\{{n_1}}\end{array}} \right)\)طریق برای توزیع \({n_1}\) مهره در خانه اول وجود دارد. به ازای هر انتخاب \({n_1}\) مهره در خانه÷ اول،\(\left( {\begin{array}{*{20}{c}}{n – {n_1}}\\{{n_2}}\end{array}} \right)\) انتخاب برای توزیع \({n_2}\) مهره در خانه دوم ، و \(\left( {\begin{array}{*{20}{c}}{n – {n_1} – {n_2}}\\{{n_3}}\end{array}} \right)\) انتخاب برای توزیع \({n_3}\) مهره در خانه سوم،راه وجود دارد، و \( \cdots \). پس با توجه به تعمیم اصل شمارش، تعداد کل این توزیعها برابر است با:
\(\left( {\begin{array}{*{20}{c}}n\\{{n_1}}\end{array}} \right)\left( {\begin{array}{*{20}{c}}{n – {n_1}}\\{{n_2}}\end{array}} \right) \ldots \left( {\begin{array}{*{20}{c}}{n – {n_1} – {n_2} – \ldots {n_{k – 1}}}\\{{n_k}}\end{array}} \right) = \)
\(\frac{{n!}}{{\left( {n – {n_1}} \right)!{n_1}!}} \times \frac{{\left( {n – {n_1}} \right)!}}{{\left( {n – {n_1} – {n_2}} \right)!{n_2}!}} \times \ldots \times \frac{{\left( {n – {n_1} – {n_2} \ldots – {n_{k – 1}}} \right)!}}{{\left( {n – {n_1} \ldots – {n_k}} \right)!{n_k}!}} = \frac{{n!}}{{{n_1}!{n_2} \ldots {n_k}!}}\)
زیرا: \(\left( {n – {n_1} – {n_2} \ldots . – {n_k}} \right) = 1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;,\;\;\;\;\;\;\;\;\;\;\;\;\;\;{n_1} + {n_2} + \ldots + {n_k} = n\)
با توجه به مثال فوق می توانیم قضیه زیر را بیان کنیم.
قضیه (بسط چند جملهای): در بسط \({({x_1} + {x_2} + \ldots + {x_k})^n}\)ضریب جمله \({x_1}^{{n_1}}{x_2}^{{n_2}} \cdots {x_k}^{{n_k}}\) که در آن \({n_1} + {n_2} + \ldots + {n_k} = n\)، برابر است با :\(\frac{{n!}}{{{n_1}!{n_2}!{n_3}! \ldots {n_k}!}}\) بنابراین:
\(\;{({x_1} + {x_2} + \ldots + {x_k})^n} = \mathop \sum \limits_{{n_1} + {n_2} + \ldots {n_k} = n} \frac{{n!}}{{{n_1}!{n_2}! \ldots {n_k}!}}{x_1}^{{n_1}}{x_2}^{{n_2}} \cdots {x_k}^{{n_k}}\)
مثال : ضریب \({x^3}{y^2}{t^2}\) را در بسط \({(x + y + t)^7}\)بدست آورید.
حل :
\(\frac{{7!}}{{3!2!2!}}\).
مثال: ضریب \({a^3}{b^2}{c^3}\) را در بسط \({(۳a + 2b + 4c)^n}\) بدست آورید :
حل : \({۳^۳} \times {\rm{\;}}{2^2} \times {\rm{\;}}{4^3}\frac{{8!}}{{3!2!3!}}\)
در اینجا تعاریف و قضایا و مثال هایی در خصوص جایگشت و ترکیب را توضیح دادیم. جایگشت و ترکیب زیر مجموعه اصل شمارش به حساب می آیند. در ادامه میتوانید تعدادی از مسائل حل شده در زمینه جایگشت و ترکیب را مطالعه نمایید.
جایگشت و ترکیب – مسائل حل شده
جایگشت و ترکیب را در موارد زیر حساب کنید.
۱–\(p\left( {10,10} \right)\)
حل:\(p\left( {10,10} \right) = \frac{{10!}}{{\left( {10 – 10} \right)!}} = \frac{{10!}}{{0!}} = 10!\)
۲- \(p\left( {10,0} \right) = \frac{{10!}}{{\left( {10 – 0} \right)!}} = \frac{{10!}}{{10!}} = 1\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;p\left( {10,0} \right)\)
۳– به چند طریق می توان حروف کلمه Course را جابه جا کرد؟
حل: \(۶! = ۷۲٫\)
۴– با ارقام۰و۲و۲و۲و۳و۴ چند عدد سه رقمی می توان ساخت؟
حل: رقم اول (از سمت چپ) نباید صفر باشد. بنابراین برای اولین رقم از سمت چپ ۵ حالت داریم. از این رو تعداد ارقام برابر است با :\(۵ \times 5 \times 4 = 100\)
۵– در مبنای ۸ چند عدد سه رقمی وجود دارد ؟
حل: در مبنای ۸ فقط ارقام ۰،۱،۲،….،۷ وجود دارد. چون اولین رقم از سمت چپ نباید صفر باشد، لذا داریم :
۶– ۵ مهره سیاه و ۴ مهره سفید متمایز را به چند طریق میتوان در یک ردیف قرار داد بطوری که
در ابتدا و انتهای صف، مهره ها همرنگ نباشند.
بنابراین تعداد حالات ممکن است با \(۴ \times 7! \times 5 + 5 \times 7! \times 4 = 40 \times 7!\)
۷– چند عدد سه رقمی زوج با ارقام متمایز وجود دارد که فاقد ۴ است ؟
اگر رقم یکان صفر باشد
۳طریق ۷ طریق ۷ طریق ۱ طریق ۷ طریق ۸ طریق
\(\left( {8 \times 7 \times 1} \right) + \left( {7 \times 7 \times 3} \right) = 203\)
و یا
۸– حروف کلمه « discrete » را به چند طریق می توان جابه جا کرد ؟
حل : کلمه مزبور ۶ حرف متمایز و ۲ حرف یکسان دارد. بنابراین تعداد جابجا شدن های این کلمه برابر است با\(\frac{{8!}}{{2!}}\) .
به نظرتون بحث جایگشت و ترکیب جالبه؟ به نظر من که خیلی. بیا مثال بعدی.
۹– چند دنباله۱۲تایی متشکل از هفت \({\rm{B}}\) و پنج \({\rm{A}}\) میتوان ساخت بطوری که هیچ دو \(A\)ایی کنار هم نباشند؟
حل : هفت B را در یک ردیف بصورت زیر می چینیم، ۸ فضای خالی وجود دارد که پنج تای آنها را انتخاب کرده و A ها را قرار می دهیم. پس تعداد حالات ممکن برابر است با :
\(\left( {\begin{array}{*{20}{c}}8\\5\end{array}} \right) = 56\)
B B B B B B B
۱۰– به چند طریق می توان ۳ کتاب از ۵ کتاب سال اول و ۴ کتاب از ۶ کتاب سال دوم را یک در میان قفسه ایی چید ؟
حل: به \(\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)\) طریق ۳ کتاب را از ۵ کتاب سال می توان انتخاب کرد.
و به \(\left( {\begin{array}{*{20}{c}}6\\4\end{array}} \right)\) طریق می توان ۴ کتاب از ۶ کتاب سال دوم را انتخاب کرد.
اکنون ۳ کتاب سال اول و ۴ کتاب سال دوم داریم که آنها را می توان به \(۳! \times 4!\) طریق کنار هم چید. بنابر اصل ضرب تعداد حالات ممکن برابر است با :
\(\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right) \times \left( {\begin{array}{*{20}{c}}6\\4\end{array}} \right) \times 3! \times 4!\)
تا اینجا ده تا از مسائل مبحث جایگشت و ترکیب رو با هم حل کردیم. بریم سراغ بقیه مسائل حل شده جایگشت و ترکیب.
۱۱– از معادله\(\;p\left( {n,4} \right) + \;\left( {\begin{array}{*{20}{c}}n\\4\end{array}} \right) = 25\left( {\begin{array}{*{20}{c}}n\\5\end{array}} \right)\)، مقدار \(n\) را بدست آورید.
حل :
\(۲۴\left( {n – 4} \right)! = 5!\left( {n – 5} \right)! \Rightarrow \;n – 4 = 5 \Rightarrow n = 9\)
۱۲– کودکی۱۲ مکعب دارد که ۶ تای آنها سفید، ۴ تا قرمز و یکی آبی است. اگر او بخواهد مکعبها را در یک ردیف قرار دهد، چند ترکیب متفاوت امکان پذیر است.
\(\frac{{12!}}{{6! \times 4! \times 1! \times 1!}} = 31680\)
۱۳- به چند طریق ۸ نفر میتوانند در یک ردیف بنشینند اگر :
الف) هیچ محدودیتی در نشستن آنها وجود نداشته باشد.
ب) فرد A و گرد B باید پهلوی هم بنشینند.
پ) ۴ نفر مرد و ۴ نفر زن باشند، هیچ دو مرد و هیچ دو زنی نتوانند کنار هم بنشینند.
ت) پنج مرد باشند و باید پهلوی هم بنشینند.
ث) ۴ زوج باشند و باید هر زوج پهلوی هم بنشینند.
حل :
الف) \(۸!\; = \;۴۰۳۲۰\)
ب) فرد \({\rm{A}}\) و فرد \({\rm{B}}\) را یک نفر در نظر میگیریم، پس در در واقع ۷ نفر داریم. در نتیجه \(۷!\) جایگشت داریم. در ضمن \({\rm{B\;}},{\rm{A}}\) بین خودشان به \(۲!\) طریق می توانند جابجا شوند، بنابر اصل ضرب داریم: \(۷! \times 2! = 10080\)
پ) دو ترکیب متفاوت داریم :
\(WMWMWMWM\) یا \(MWMWMWMW\)
برای هر یک داریم : \(۴ \times 4 \times 3 \times 2 \times 2 \times 1 \times 1\)
پس پاسخ عبارت است از: \(۲ \times {(4!)^2} = 1152\)
ت) ۵ نفر را به ۵! طریق می توان جابجا کرد. در ضمن پنج نفر حکم یک نفر را دارند و در واقع ۴ نفر داریم، پس جواب برابر است با: \(۵! \times 4! = 2880\)
ث) ۴ زوج را به ! ۴ طریق می توان کنار هم نشاند، در ضمن هر زوج به !۲ طریق میتوانند جابجا شوند، بنابراین داریم: \(۴! \times {(2!)^4} = 384\)
۱۴– از گروهی متشکل از ۸ زن و ۶ مرد، شورایی مرکب از ۳ زن و ۳ مرد بایستی تشکیل شود. این کار به چند طریق امکان پذیر است اگر :
الف) ۲ نفر از مردها نخواهند با هم انتخاب شوند.
ب) ۲ نفر از زنها نخواهند با هم انتخاب شوند.
پ)یکی از زنها و یکی از مردها نخواهند با هم انتخاب شوند.
حل:
الف) به تعداد \(\left( {\begin{array}{*{20}{c}}8\\3\end{array}} \right)\) انتخاب برای زنها وجود دارد. یا هیچکدام از مردهایی که نمی خواهند با هم باشند را انتخاب نمی کنیم که این کار به \(\left( {\begin{array}{*{20}{c}}2\\0\end{array}} \right)\) حالت امکان دارد و مردها را از ۴ نفر باقیمانده انتخاب می کنیم که به \(\left( {\begin{array}{*{20}{c}}4\\3\end{array}} \right)\) حالت امکان دارد. یا یک نفراز آن دو مرد را انتخاب می کنیم که به \(\left( {\begin{array}{*{20}{c}}2\\1\end{array}} \right)\) حالت امکان دارد و ۲ نفر باقیمانده را از آن ۴ مرد باقیمانده انتخاب می کنیم که به \(\left( {\begin{array}{*{20}{c}}4\\2\end{array}} \right)\) حالت امکان دارد. بنابر اصل ضرب و اصل جمع داریم:
۸۹۶ =\(\left( {\begin{array}{*{20}{c}}4\\2\end{array}} \right)\) ×\(\left( {\begin{array}{*{20}{c}}2\\1\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}8\\3\end{array}} \right) + \left( {\begin{array}{*{20}{c}}4\\3\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}2\\0\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}8\\3\end{array}} \right)\)
ب) مانند استدلال (الف) داریم :
۱۰۰۰ =\(\left( {\begin{array}{*{20}{c}}6\\2\end{array}} \right)\) ×\(\left( {\begin{array}{*{20}{c}}2\\1\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}6\\3\end{array}} \right)\)+\(\left( {\begin{array}{*{20}{c}}6\\3\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}2\\0\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}9\\3\end{array}} \right)\)
پ) یا هیچکدام از زن و مردهایی که نمی خواهند با هم باشند را انتخاب نمی کنیم که این کار به \(\left( {\begin{array}{*{20}{c}}7\\3\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)\) حالت امکان دارد. یا آن مردی را که نمیخواهد با زن مذکور باشد را انتخاب میکنیم. که به \(\left( {\begin{array}{*{20}{c}}7\\3\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}5\\2\end{array}} \right)\) طریق امکان پذیر است. یا آن زنی که نمیخواهد با مرد مذکور انتخاب شود انتخاب میکنیم، بنابراین در این حالت هم تعداد حالات ممکن برای انتخاب شورا برابر است با: \(\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}7\\2\end{array}} \right)\)
از این رو بنابر اصل ضرب و جمع داریم :
۹۱۰ =\(\left( {\begin{array}{*{20}{c}}5\\2\end{array}} \right)\) ×\(\left( {\begin{array}{*{20}{c}}7\\3\end{array}} \right)\)+\(\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}7\\2\end{array}} \right)\)+\(\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}7\\3\end{array}} \right)\)
۱۵– فردی ۸ دوست دارد که میخواهد ۵ نفر از آنها را در یک مهمانی دعوت کند، چند انتخابدارد اگر:
الف) دو نفر از دوستان وی با هم اختلاف داشته باشند و نخواهند با هم شرکت کنند.
ب) دو نفر از دوستان وی در صورتی که با هم دعوت شوند در مهمانی شرکت می کنند.
حل: الف)۳۰\( = \left( {\begin{array}{*{20}{c}}6\\4\end{array}} \right)\)×\(\left( {\begin{array}{*{20}{c}}2\\1\end{array}} \right)\)+\(\left( {\begin{array}{*{20}{c}}6\\5\end{array}} \right)\)
\(\left( {\begin{array}{*{20}{c}}6\\5\end{array}} \right) + \left( {\begin{array}{*{20}{c}}6\\3\end{array}} \right) = 26\;\;(\) ب
تا اینجا 15 مساله درباره جایگشت و ترکیب با هم حل کردیم و یاد گرفتیم. امیدوارم از این مثالهای جایگشت و ترکیب خسته نشده باشید. بریم سراغ بقیه مسائل حل شده.
۱۶– پنج نقطه بر محیط دایره ایی داده شده است. چه تعداد چند ضلعی محاطی با این نقاط می توان ساخت.
حل:
تعداد سه ضلعی محاطی:\(\left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right)\)
تعداد چهار ضلعی محاطی: \(\left( {\begin{array}{*{20}{c}}5\\4\end{array}} \right)\)
تعداد پنج ضلعی محاطی:\(\left( {\begin{array}{*{20}{c}}5\\5\end{array}} \right)\)
بنا بر اصل جمع داریم:\(\left( {\begin{array}{*{20}{c}}5\\5\end{array}} \right) + \left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right) + \left( {\begin{array}{*{20}{c}}5\\4\end{array}} \right) = 16{\rm{\;\;\;\;}}\)
بنابراین ۱۶ چند ضلعی محاطی با این نقاط می توان ساخت.
۱۷– یک \(n\) ضلعی محدب چند قطر دارد ؟
حل: در یک \(n\) ضلعی محدب به ازای هر دو راس مفروض \(n\) ضلعی یک پاره خط وجود دارد که این راس مفروض نقاط ابتدایی و انتهایی پاره خط هستند. بنابراین تعداد این خطوط \(\left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right)\) است. ولی \(n\) تا از این خطوط، ضلعهای \(n\) ضلعی هستند و مابقی قطر هستند، بنابراین تعداد قطرها برابر است با: \(\left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right) – n = \frac{{n\left( {n – 3} \right)}}{2}\)
۱۸– ۴ نفر می خواهند سوار اتوبوس شوند. اگر فرد A قبل از فرد B وارد شود، چند حالت امکان دارد.
حل: از\(۴!\) حالت ممکن در نصف حالات فرد A قبل از فرد B وارد اتوبوس میشود، لذا تعداد حالات ممکن برابر است با: \(\frac{{4{\rm{\;}}!}}{2}\)
۱۹– الف) به چند طریق ۵ نفر برای سوار شدن به اتوبوس میتوانند صف ببندند.
ب) اگر دو نفر از پنج نفر از اینکه کنار هم باشند خودداری کنند، به چند طریق صف بندی ممکن است.
الف) \(۵!\)
ب) از \(۵!\)، تعداد حالتی را که دو نفر می توانند کنار هم باشند را کم می کنیم.
\(۵! – ۲! \times 4! = 72\)
۲۰– مجموعهای از نقاط را به شکل زیر در نظر بگیرید، فرض کنید که از نقطه \(A\) شروع کرده و در هر حرکت می توانید به طرف بالا یا به طرف راست یک قدم بردارید. اگر این حرکت ادامه یابد تا به نقطه \(B\) برسید، در این صورت چند مسیر از \(A\) به \(B\) امکان پذیر است؟ (راهنمایی توجه کنید که برای رفتن از نقطه \(A\) و رسیدن به نقطه \(B\) بایستی چهار قدم به طرف راست و سه قدم به طرف بالا برداشته شود).
حل: برای رسیدن از نقطه \({\rm{A}}\) به نقطه \(B\) باید حتما ۴ حرکت به سمت شرق و ۳ حرکت به سمت شمال انجام داد. مثلا مسیر مشخص شده را می توان با ENEENNE نشان داد. بنابراین مساله به محاسبه جایگشتهای ۷ شی که ۴ شی آنها از یک نوع و سه تای دیگر از نوع دیگرند میشود.بنابراین تعداد کل حالات برابر است با: \(\frac{{7\;!}}{{4\;!3!}} = 35\)
۲۱– در مساله ۲۰ چند مسیر از Aبه B وجود دارد در صورتی که مسیر از نقطه مشخص شده C بگذرد.
حل:
۶ \( = \frac{{4!}}{{2!2!}}\) تعداد حالات رسیدن از \(A\) به \({\rm{C}}\)
\(۳ \times 6 = 18\)
۳ \( = \frac{{3!}}{{2!1!}}\) تعدا حالات رسیدن از \({\rm{C}}\) به \({\rm{B}}\)
۲۲– یک آزمایشگاه روانسنجی از ۳ قسمت که در هر قسمت ۲ تخت وجود دارد تشکیل شده است. اگر سه جفت دو قلوی یکسان را بخواهیم در این مرکز بستری کنیم، بطوری که که هر جفت دو قلو در یک قسمت روی تخت خواب های متفاوت بستری شوند. این عمل به چند طریق امکان پذیر است ؟
حل: برای هر جفت دو قلو در هر اتاق دو قسمت وجود دارد و با توجه به اینکه هر جفت باید در یک قسمت باشند، داریم : \(۳\;! \times {(2!)^3} = 48\)
۲۳– ثابت کنید \(\left( {k!} \right)!\) بر\({\left( {k!} \right)^{\left( {{\rm{k}} – 1} \right)!}}\) بخش پذیر است.
حل: فرض کنید \(k!\) شی داریم بطوری که \(k\) تای آن از نوع اول\(k, \ldots ,\;\) تای آن از نوع \(\left( {k – 1} \right)!\)ام است. تعداد روشهای جابه جا کردن این اشیاء برابر است با .چون تعداد روشهای جابه جا کردن این اشیاء عدد طبیعی است، پس کسر فوق یک عدد صحیح است، لذا \(\left( {k!} \right)!\) بر \({\left( {k!} \right)^{\left( {{\rm{k}} – 1} \right)!}}\) بخش پذیر است.
۲۴- عبارت \({(۳{x^2} + y)^5}\) را بسط دهید.
\({(۳{x^2} + y)^5} = \left( {\begin{array}{*{20}{c}}5\\0\end{array}} \right){(3{x^2})^5} + \left( {\begin{array}{*{20}{c}}5\\1\end{array}} \right){(3{x^2})^4}y + \left( {\begin{array}{*{20}{c}}5\\2\end{array}} \right){(3{x^2})^3}{y^2}\)
\( + \left( {\begin{array}{*{20}{c}}5\\3\end{array}} \right){(3{x^2})^2}{y^3} + \left( {\begin{array}{*{20}{c}}5\\4\end{array}} \right)(3{x^2}){y^4} + \left( {\begin{array}{*{20}{c}}5\\5\end{array}} \right){y^5} = \)
\(۲۴۳{x^1} + 405{x^8}y + 270{x^6}{y^2} + 90{x^4}{y^3} + 15{x^2}{y^4} + {y^5}\)
خسته نشو. بیا تا باهم بقیه مسائل جایگشت و ترکیب رو حداقل یه مروری داشته باشیم.
۲۵– عبارت \({({x_1} + 2{x_2} + 3{x_3})^4}\) را بسط دهید.
حل :
\({({x_1} + 2{x_2} + 3{x_3})^4} = \sum \left( {\begin{array}{*{20}{c}}4\\{{n_1},{n_2},{n_3}}\end{array}} \right){x_1}^{{n_1}}{(2{x_2})^{{n_2}}}{(3{x_3})^{{n_3}}}\)
( توجه \((\left( {\begin{array}{*{20}{c}}n\\{{n_1},{n_2},{n_3}}\end{array}} \right) = \frac{{n!}}{{{n_1}!,{n_2}!,{n_3}!}}\)
۲۶– حاصل مجموع \(\left( {\begin{array}{*{20}{c}}{15}\\{13}\end{array}} \right)\) +…. +\(\left( {\begin{array}{*{20}{c}}{15}\\3\end{array}} \right)\)+\(\left( {\begin{array}{*{20}{c}}{15}\\2\end{array}} \right)\) را بدست آورید
حل: می دانیم \(\left( {\begin{array}{*{20}{c}}n\\0\end{array}} \right) + \left( {\begin{array}{*{20}{c}}n\\1\end{array}} \right) + \ldots \left( {\begin{array}{*{20}{c}}n\\n\end{array}} \right) = {2^n}\)پس:
\(\left( {\begin{array}{*{20}{c}}{15}\\2\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{15}\\3\end{array}} \right) + \ldots + \left( {\begin{array}{*{20}{c}}{15}\\{13}\end{array}} \right) = {2^{15}} – \left( {\begin{array}{*{20}{c}}{15}\\0\end{array}} \right) – \left( {\begin{array}{*{20}{c}}{15}\\1\end{array}} \right) – \left( {\begin{array}{*{20}{c}}{15}\\{14}\end{array}} \right) – \left( {\begin{array}{*{20}{c}}{15}\\{15}\end{array}} \right) = {2^{15}} – 32\;\)
۲۷– مجموع \(\left( {\begin{array}{*{20}{c}}{14}\\{12}\end{array}} \right)\) +\(\left( {\begin{array}{*{20}{c}}{13}\\{11}\end{array}} \right)\) +\(\left( {\begin{array}{*{20}{c}}{12}\\{10}\end{array}} \right)\)+\(\left( {\begin{array}{*{20}{c}}{12}\\9\end{array}} \right)\) را بیابید.
حل : با توجه به قاعده پاسکال داریم :
\(\left( {\begin{array}{*{20}{c}}{13}\\{10}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{13}\\{11}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{14}\\{12}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{14}\\{11}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{14}\\{12}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}{15}\\{12}\end{array}} \right)\)
۲۸– حاصل \(\left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 2}\end{array}} \right)\) +\(\left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 1}\end{array}} \right)\) 2+\(\left( {\begin{array}{*{20}{c}}{n – 2}\\{\;\;\;k\;\;\;\;}\end{array}} \right)\) چیست.
حل : بنا به قاعده پاسکال داریم :
\(\left( {\begin{array}{*{20}{c}}{n – 2}\\k\end{array}} \right){\rm{\;}} + 2\left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 1}\end{array}} \right){\rm{\;}} + \left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 2}\end{array}} \right) = \)
\(\left( {\begin{array}{*{20}{c}}{n – 2}\\{\;\;\;\;k\;\;\;\;\;}\end{array}} \right){\rm{\;}} + \left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 1}\end{array}} \right){\rm{\;}} + \left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 1\;\;\;}\end{array}} \right) + \left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 2}\end{array}} \right) = \)
\(\left[ {\left( {\begin{array}{*{20}{c}}{n – 2}\\k\end{array}} \right){\rm{\;}} + \left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 1}\end{array}} \right)} \right] + \left[ {\left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 1\;\;}\end{array}} \right){\rm{\;}} + \left( {\begin{array}{*{20}{c}}{n – 2}\\{k – 2}\end{array}} \right)} \right] = \left( {\begin{array}{*{20}{c}}{n – 1}\\k\end{array}} \right){\rm{\;}} + \left( {\begin{array}{*{20}{c}}{n – 1}\\{k – 1}\end{array}} \right) = \left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right)\)
۲۹– نشان دهید اگر \(n \ge 1\;,\;n \in \mathbb{N}\) آنگاه :
\(\left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right){\rm{\;}} + \left( {\begin{array}{*{20}{c}}{2n}\\{n – 1}\end{array}} \right) = \frac{1}{2}\left( {\begin{array}{*{20}{c}}{2n + 2}\\{\;\;\;n + 1\;\;\;}\end{array}} \right)\)
حل :
\(\left( {\begin{array}{*{20}{c}}{2n}\\n\end{array}} \right){\rm{\;}} + \left( {\begin{array}{*{20}{c}}{2n}\\{n – 1}\end{array}} \right) = \frac{{\left( {2n} \right)!}}{{n!n!}} + \frac{{\left( {2n} \right)!}}{{\left( {n – 1} \right)!\left( {n + 1} \right)!}} = \frac{{\left( {2n} \right)!{{(n + 1)}^2} + \left( {2n} \right)!n\left( {n + 1} \right)}}{{\left( {n + 1} \right)!\left( {n + 1} \right)!}}\)
\( = \frac{1}{2}\left[ {\frac{{\left( {2n} \right)!\left( {2n + 2} \right)\left( {n + 1} \right) + \left( {2n} \right)!\left( {2n + 2} \right)n}}{{\left( {n + 1} \right)!\left( {n + 1} \right)!}}} \right] = \frac{1}{2}\left( {\begin{array}{*{20}{c}}{2n + 2}\\{n + 1}\end{array}} \right)\)
حالا بگو ببینم از جایگشت و ترکیب خوشت اومده؟ اگه جوابت مثبته پس بزن بریم تا مسائل مربوط به جایگشت و ترکیب های بعدی رو ببینیم.
۳۰– نشان دهید \(n \in \mathbb{N}\;.\left( {\begin{array}{*{20}{c}}{ – n}\\r\end{array}} \right) = {\left( { – 1} \right)^r}\left( {\begin{array}{*{20}{c}}{n + r – 1}\\r\end{array}} \right)\) اگر \(n \in \mathbb{N}\)
حل :
\(\left( {\begin{array}{*{20}{c}}{ – n}\\r\end{array}} \right) = \frac{{\left[ {\left( { – n} \right)\left( { – n – 1} \right)\left( { – n – 2} \right) \ldots \left( { – n – r + 1} \right)} \right]}}{{r!}} = \)
\(\left( {\begin{array}{*{20}{c}}{ – n}\\r\end{array}} \right) = \frac{{\left[ {\left( { – n} \right)\left( { – n – 1} \right)\left( { – n – 2} \right) \ldots \left( { – n – r – 1} \right)} \right]}}{{r!}} = \)
\(\frac{{{{\left( { – 1} \right)}^r}n\left( {n + 1} \right)\left( {n + 2} \right) \ldots \left( {n + r – 1} \right)}}{{r!}} = \frac{{{{\left( { – 1} \right)}^r}\left( {n + r – 1} \right)!}}{{\left[ {\left( {n – 1} \right)!r!} \right]}} = {\left( { – 1} \right)^r}\left( {\begin{array}{*{20}{c}}{n + r – 1}\\r\end{array}} \right)\)
۳۱– برای عدد صحیح و مثبت \({\rm{n}}\)، مجموع زیر را حساب کنید.
\(\left( {\begin{array}{*{20}{c}}n\\0\end{array}} \right) + 2\left( {\begin{array}{*{20}{c}}n\\1\end{array}} \right) + {2^2}\left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right) + \ldots + {2^k}\left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right) + \ldots + {2^n}\left( {\begin{array}{*{20}{c}}n\\n\end{array}} \right)\)
حل: با توجه به بسط دو جملهای داریم :
\({(\;x + y)^n} = \mathop \sum \limits_{k = 0}^n \left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right){x^k}{y^{n – k}}\)
حال \(y = 1\;,\;x = 2\) قرار می دهیم، در این صورت داریم :
\(\mathop \sum \limits_{i = 0}^{50} \left( {\begin{array}{*{20}{c}}{50}\\i\end{array}} \right){8^i} = {(1 + 8)^{50}} = {9^{50}} \Rightarrow {x^{100}} = {9^{50}} \Rightarrow {x^2} = 3 \Rightarrow x = \pm 3\)
۳۲– در بسط \({(۲x + 3y – 4t + w)^9}\) ضریب \({x^3}{y^2}{t^3}w\) را بیابید.
حل :
\({(۲x + 3y – 4t + w)^9} = \mathop \sum \limits_{{n_1} + {n_2} + {n_3} + {n_4} = 9} \left( {\begin{array}{*{20}{c}}9\\{{n_1},{n_2},{n_{3,}}{n_4}}\end{array}} \right){\left( {2x} \right)^{{n_1}}}{\left( {3y} \right)^{{n_2}}}{\left( { – 4t} \right)^{{n_3}}}{\left( w \right)^{{n_4}}}\)
بنابراین ضریب \({x^3}{y^2}{t^3}w\) برابر است با \(\frac{{9!}}{{3!2!3!1!}}{2^3}{3^2}{\left( { – 4} \right)^3}\) .
خوب، این هم از مسائل جایگشت و ترکیب که 32 تا از اونها را با هم حل کردیم و یاد گرفتیم. امیدوارم که خوب خوب مبحث جایگشت و ترکیب براتون روشن شده باشه و البته مفید فایده.
در جلسات گذشته ، بخش هایی از اصل شمارش توضیح داده شد. در صورت تمایل میتوانید روی لینک های زیر کلیک نمایید:
مطالب زیر را حتما مطالعه کنید
اصل شمارش (۲- فاکتوریل و فرمول استرلینگ)
اصل شمارش (۱- اصل ضرب و اصل جمع)
2 دیدگاه
به گفتگوی ما بپیوندید و دیدگاه خود را با ما در میان بگذارید.
دیدگاهتان را بنویسید لغو پاسخ
برای نوشتن دیدگاه باید وارد بشوید.
لطفاً برخي اغلاط متن را اصلاح بفرمائيد:
در مثال: فرض کنید بخواهیم n مهره متمایز را در ۴ خانه متمایز توزیع کنیم (با توجه به ادامه مطلب 4 بايد به k تغيير کند)
سلام آقای درفشدار
سپاس از توجه شما. متن مورد نظر اصلاح شد.