گام به گام گسسته فصل سه صفحه ۶۱

 دوستان در این نوشته ،گام به گام گسسته فصل سه صفحه 61

کار در کلاس این صفحه  رو براتون گذاشتم .

امیدوارم که با مطالعه این نوشته در این مبحث رفع اشکال بشید.

می دانیم که:

قضیه:تعداد جوابهای صحیح و نامنفی معادله    x₁ + x_{2 +…+}x_k=n  برابر است با تعداد انتخاب‌های دلخواه n شاخه گل از بین k  نوع گل یعنی برابر است با:

c(n+k-1,k-1)

در این کار در کلاس از این قضیه استفاده می کنیم

جواب:

برای این که از قضیه فوق استفاده کنیم باید تمام متغیرهای بزرگتر مساوی صفر باشد ولی در این مثال متغیرها مثبت هستند پس با تغییر متغیر مسئله را به قضیه فوق تبدیل می کنیم

​\( x_{1} \geq 1 \Longrightarrow x_{1}-1 \geq 0 \Longrightarrow y_{1} \geq 0 , y_{1}=x_{1}-1 \Longrightarrow x_{1}=y_{1}+1 ,y_{1} \geq 0 \)​

​\( x_{2} \geq 1 \Longrightarrow x_{2}-1 \geq 0 \Longrightarrow y_{2} \geq 0 , y_{2}=x_{2}-1 \Longrightarrow x_{2}=y_{2}+1 ,y_{2} \geq 0 \)​

​\( x_{3} \geq 1 \Longrightarrow x_{3}-1 \geq 0 \Longrightarrow y_{3} \geq 0 , y_{3}=x_{3}-1 \Longrightarrow x_{3}=y_{3}+1 ,y_{3} \geq 0 \)​

اکنون با تغییر متغیر مسئله را به قضیه تبدیل می کنیم

​\( x_{1}+x_{2}+x_{3}=7 \Longrightarrow y_{1}+1+y_{2}+1+y_{3}+1=7 \Longrightarrow y_{1}+y_{2}+y_{3}=4 \)​

بنابر قضیه تعداد حالات مسئله را بدست می آوریم

​\( C(4+3-1,3-1)=C(12,2)= \frac{6!}{2! \times 4!}= \frac{6 \times 5}{2} =15 \)​

پس جواب نهایی 15 است.

جواب:

باید تمام متغیر ها را به صورت زیر تغییر دهیم

​\( x_{i} \geq 1 \Longrightarrow x_{i}-1 \geq 0 \Longrightarrow y_{i} \geq 0 , y_{i}=x_{i}-1 \Longrightarrow x_{i}=y_{i}+1 ,y_{i} \geq 0 \)​

پس معادله به صورت زیر تغییر می کند

​\( x_{1}+x_{2}+…+x_{k}=n \Longrightarrow y_{1}+1+y_{2}+1+…+y_{k}+1=n \Longrightarrow y_{1}+y_{2}+…+y_{k}=n-k \)​

اکنون بنابر قضیه فوق معادله را حل می کنیم

\( \binom{(n-k)+k-1}{k-1}=\binom{n-1}{k-1} \)

جواب:

\( x_{1}> 1 \Longrightarrow x_{1}\geq 2 \Longrightarrow x_{1}-2 \geq 0 \Longrightarrow y_{1} \geq 0 , y_{1}=x_{i}-2 \Longrightarrow x_{1}=y_{1}+2 ,y_{1} \geq 0 \)

​\( x_{3}> 1 \Longrightarrow x_{3}\geq 4 \Longrightarrow x_{3}-4 \geq 0 \Longrightarrow y_{3} \geq 0 , y_{3}=x_{3}-4 \Longrightarrow x_{3}=y_{3}+4 ,y_{3} \geq 0 \)​

​\( x_{1}+x_{2}+…+x_{5}=14 \Longrightarrow y_{1}+2+x_{2}+y_{3}+4+x_{4}+x_{5}=14 \Longrightarrow y_{1}+x_{2}+y_{3}+x_{4}+x_{5}=8 \)​

اکنون بنابر قضیه فوق معادله را حل می کنیم

\( \binom{8+5-1}{5-1}=\binom{12}{4} \)

و جواب حاصل می شود

جواب:

از شرط قرار داده شده تمام رها بزرگتر مساوی یک هستند مشخص است که در این مسئله تعداد جواب های صحیح و مثبت یعنی اعداد طبیعی در معادله مورد نظر است و بنابر سوال ۲ این مسئله را می‌توان به صورت زیر حل نمود

​\( \binom{11-1}{5-1}=\binom{10}{4} \)​

یعنی جواب نهایی 210 است.

جواب:

​\( x_{5}> 2 \Longrightarrow x_{5}\geq 3 \Longrightarrow x_{5}-3 \geq 0 \Longrightarrow y_{5} \geq 0 , y_{5}=x_{5}-3 \Longrightarrow x_{5}=y_{5}+2 ,y_{5} \geq 0 \)​

از طرفی x₃=4 است اکنون دو متغییر را در سوال قرار می دهیم تا معادله استاندارد حاصل شود.

​\( x_{1}+x_{2}+…+x_{6}=12 \Longrightarrow x_{1}+x_{2}+4+x_{4}+y_{5}+2 +x_{6}=12 \Longrightarrow x_{1}+x_{2}+x_{4}+y_{5}+x_{6}=6 \)​

بنابر حل مسئله دو جواببه صورت

​\( \binom{6-1}{5-1}=\binom{5}{4}=5 \)​

صفحه 60

گام به گام گسسته فصل سه درس یک

صفحه 62