ترکیبیات (ابزارهای شمارشی)

فرض کنید $n$ شی متمایز را می‌خواهیم در یک ردیف که شامل $n$ مکان می‌باشد، قرار دهیم.

در مکان اول می‌توانیم هر یک از $n$ شی را قرار دهیم، یعنی برای پر کردن مکان اول $n$ روش وجود دارد.

در مکان دوم از $\left(n-1\right)$ شی باقیمانده، انتخاب صورت می‌گیرد. 

در مکان سوم از $\left(n-2\right)$ شی باقیمانده، انتخاب صورت می‌گیرد. 

به‌همین ترتیب:

در مکان $n$ام از $\left(n-2\right)$ فقط یک شی برای قرار دادن وجود دارد.

لذا طبق اصل ضرب، تعداد جایگشت های $n$ شی متمایز برابر است با: 

$n\times (n-1)\times (n-2)\times \cdots \times 1=n!$

در یک صف دایره‌ای مکان اول، دوم و .... معنی ندارد، یعنی جای قرار گرفتن اشیا اهمیتی ندارد، بلکه قرار گرفتن هر شی در میان دو شی دیگر مهم است.

برای محاسبه تعداد جایگشت $n$ شی متمایز در یک صف دایره‌ای، کافی است جای یک شی را ثابت نگه داریم و $\left(n-1\right)$ شی باقیمانده را به $(n-1)!$ روش جابه‌جا کنیم. 

می‌دانیم جایگشت $n$ شی متمایز $n!$ است ولی چون $m_1$ تا از این اشیا، از یک نوع می‌باشند پس در $n!$ حالت یک شی $m_1$ بار تکرار شده است و چون این اشیا به $m_1!$ می‌توانند در یک ردیف بین خود جابه‌جا شوند لذا $m_1!$ از $n!$ حالت یکسان است.      

به‌همین ترتیب شی نوع دوم $m_2$ بار تکرار شده، لذا $m_2!$ از $n!$ حالت یکسان می‌باشد.   

بنابراین اگر تا شی $k$ام بررسی را انجام دهیم، تعداد جایگشت های $n$ شی برابر است با: 

$\frac{n!}{m_1!\times m_2!\times \cdots \times m_k!}$

برای یافتن فرمول مربوط به تعداد جایگشت های $n$ شی که در یک زمان $r$ شی از آن انتخاب شده باشد: 

عضو اول در این جایگشت را می‌توان به $n$ راه مختلف انتخاب کرد.

عضو دوم در این جایگشت را می‌توان به $\left(n-1\right)$ راه مختلف انتخاب کرد.

عضو سوم در این جایگشت را می‌توان به $\left(n-2\right)$ راه مختلف انتخاب کرد.

به‌همین ترتیب: 

عضو $r$ام یعنی عضو آخر را در این جایگشت می‌توان با $n-(r-1)=n-r+1$ راه مختلف انتخاب کرد. 

بنابر اصل شمارش:

$p(n,r)=n(n-1)(n-2)\mathrm{...}(n-r+1)=\frac{n(n-1)(n-2)\mathrm{...}(n-r+1)(n-r)!}{(n-r)!}=\frac{n!}{(n-r)!}$

قرار دادن آن شی خاص در یکی از $r$ مکان موجود (برای جایگشت $r$ تایی) به $r$ روش صورت می‌گیرد، بنابراین $\left(r-1\right)$ مکان دیگر باید با $\left(n-1\right)$ شی باقیمانده پر شوند، که جایگشت $\left(r-1\right)$ تایی $\left(n-1\right)$    شی است و برابر با $p(n-1,r-1)$ لذا طبق اصل ضرب، تعداد جایگشت های مطلوب عبارت است از:

$r.p(n-1,r-1)$

برای اثبات کافی است سوال را این‌گونه در نظر بگیریم که چند جایگشت $r$ تایی می‌توان با $n$ شی متمایز که فاقد $k$ شی خاص است یعنی $\left(n-k\right)$ تشکیل داد که این عمل به $p(n-k,r)$ طریق امکان پذیر است. 

دو مجموعه $A=\left\{a_1,a_2,\mathrm{...},a_r\right\}$ و $B=\left\{b_1,{\text{\hspace{0.17em}b\hspace{0.17em}}}_2,\mathrm{...},b_n\right\}$ را در نظر می‌گیریم، تابع یک‌به‌یک تابعی است که هر عضو از مجموعه $A$ را با یک و فقط یک عضو از مجموعه $B$ متناظر می‌کند، به‌عبارت دیگر هیچ زوج مرتبی یافت نشود که مولفه‌های دومش با هم برابر باشند، بنابراین:  

اولین عضو مجموعه $A$ با یکی از $n$ عضو مجموعه $B$ متناظر خواهد بود، برای این انتخاب $n$ روش وجود دارد.   

دومین عضو مجموعه $A$ با یکی از $\left(n-1\right)$ عضو باقیمانده مجموعه $B$ متناظر می‌شود. 

به‌همین ترتیب $r$امین عضو مجموعه $A$ با یکی از $\left(n-r+1\right)$ عضو باقیمانده مجموعه $B$ متناظر می‌گردد.   

بنابراین طبق اصل ضرب تعداد توابع یک‌به‌یک از مجموعه $r$ عضوی $A$ به مجموعه $n$ عضوی $B$ برابر است با:   

$p(n,r)=n(n-1)(n-2)\cdots (n-r+1)=\frac{n(n-1)(n-2)\cdots (n-r+1)(n-r)!}{(n-r)!}=\frac{n!}{(n-r)!}$