: تناظر بین مسائل و شمارش

||V{maketoc}||

^@#16:

!تناظر یک به یک و مسائل مربوط به شمارش

فرض کنید در یک کلاس، {TEX()} {n} {TEX}دانش آموز نشسته باشند. اگر این کلاس 20 نیمکت داشته باشد و هر دانش آموز روی یک نیمکت نشسته باشد، واضح است که {TEX()} {n \le 20} {TEX}. ولی اگر بدانیم روی هر نیمکت حداقل یک دانش آموز نشسته باشد، واضح است که {TEX()} {n \ge 20} {TEX}. همچنین اگر بدانیم روی هر نیمکت دقیقا یک نفر نشسته است، بدون شمردن تعداد دانش آموزان، می توانیم بگوییم که {TEX()} {n=20} {TEX}.

---

!!تعریف

تابع {TEX()} {f:A \rightarrow B} {TEX} را یک تابع یک به یک می نامیم. اگر

@@{TEX()} { \forall x,y \in A \ , \ x \neq y \ : \ f(x) \neq f(y)} {TEX}@@

به عبارت دیگر تابع {TEX()} {f} {TEX}، به هیچ دو عضو دلخواه {TEX()} {A} {TEX}، یک مقدار را نسبت ندهد.

اصل رابطه یک به یک. اگر یک رابطه یک به یک (تابع ((یک به یک))) از ((مجموعه)) {TEX()} {A} {TEX}به مجموعه {TEX()} {B} {TEX}وجود داشته باشد، آنگاه {TEX()} {|A| \le |B|} {TEX}.

---

!!تعریف

تابع {TEX()} {f:A \rightarrow B} {TEX} را یک ((تناظر یک به یک)) می نامیم اگر یک به یک و ((پوشا)) باشد.

اصل تناظر یک به یک. اگر یک تناظر یک به یک از مجموعه {TEX()} {A} {TEX}به مجموعه {TEX()} {B} {TEX}وجود داشته باشد، آنگاه {TEX()} {|A|=|B|} {TEX}.

دقت کنید که در اصول فوق لزومی ندارد مجموعه های {TEX()} {A} {TEX}و {TEX()} {B} {TEX}متناهی باشد

---

#@

@#16:

!!مثال

با استفاده از تناظر یک به یک ثابت کنید:

@@{TEX()} { {n \choose k}={n\choose {n-k}}} {TEX}@@

__حل.__

ثابت می کنیم که یک تناظر یک به یک بین تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی مجموعه ی {TEX()} { S =\{1, 2, \cdots , n\}} {TEX} و تعداد زیر مجموعه ی{TEX()} { n – k } {TEX} عضوی{TEX()} {\Big( {n\choose {n-k}} \Big)} {TEX} آن وجود دارد؛ در نتیجه تساوی برقرار است.

اگر{TEX()} {A=\{ a_1,a_2,\cdots ,a_k \}} {TEX} یک زیر مجموعه ی {TEX()} {k} {TEX}عضوی مجموعه {TEX()} {S} {TEX}باشد، آن گاه{TEX()} { S – A } {TEX} هم یک زیر مجموعه ی{TEX()} { n – k } {TEX} عضوی، مجموعه ی {TEX()} {S} {TEX}است و برعکس. به عبارت دیگر انتخاب شدن {TEX()} {k} {TEX}عنصر از بین {TEX()} {n} {TEX}عنصر مثل انتخاب نکردن{TEX()} { n – k } {TEX} عنصر از بین {TEX()} {n} {TEX}عنصر است. زیرا برای انتخاب {TEX()} {k} {TEX}عنصر از بین {TEX()} {n} {TEX}عنصر می توان ابتدا{TEX()} { n – k } {TEX} عنصر را انتخاب کرد و با حذف آنها {TEX()} {k} {TEX}عنصر را به دست آورد.

---

!!مثال( مسئله ی مسیر)

شخصی در ساختمانی کار می کند که هفت بلوک در شرق و هشت بلوک در شمال خانه اش قرار دارد. این فرد برای رسیدن به محل کارش هر روز 15 بلوک را طی می کند. این شخص به چند طریق می تواند به محل کارش برود؟

::{picture=img/daneshnameh_up/b/b3/com0021a.jpg}::

__حل.__

مسئله ی مسیر را با تعداد کلمات 15 حرفی با 7 حرف {TEX()} {E} {TEX}و 8 حرف {TEX()} {N} {TEX}می توانیم متناظر کنیم. اگر هر حرف {TEX()} {N} {TEX}نشان گر رفتن به سمت شمال و هر حرف {TEX()} {E} {TEX}نشان گر رفتن به سمت شرق باشد، واضح است که به ازای هر مسیر، یک کلمه با 7 حرف {TEX()} {E} {TEX}و 8 حرف {TEX()} {N} {TEX}وجود دارد و بالعکس. به عنوان مثال مسیر متناظر با شکل بالا، به صورت{TEX()} { EENNENEENNNENNE } {TEX} می باشد. بنابراین یک تناظر یک به یک بین مسیرها و کلماتی که با 7 حرف {TEX()} {E} {TEX}و 8 حرف {TEX()} {N} {TEX}ساخته می شوند، وجود دارد. در نتیجه تعداد مسیرهای مورد نظر برابر است با{TEX()} {{15}\choose 8} {TEX}.

به طور کلی اگر بخواهیم در صفحه ی مختصات از نقطه ی{TEX()} { (a, b) } {TEX}به نقطه ی{TEX()} { (c, d)} {TEX}، برویم؛ با این شرط که در هر حرکت از نقطه ی{TEX()} {(x, y) } {TEX} بتوانیم به یکی از نقاط{TEX()} { (x + 1, y) } {TEX}، {TEX()} { (x – 1, y)} {TEX}، {TEX()} { (x, y + 1) } {TEX} و{TEX()} { (x, y – 1) } {TEX}برویم، تعداد کوتاه ترین مسیرها از ((نقطه)) ی{TEX()} { (a, b) } {TEX}به نقطه ی{TEX()} { (c, d)} {TEX} برابر است با تعداد کلماتی که با{TEX()} { |a – c| } {TEX}تا x و{TEX()} { |b – d| } {TEX}تا {TEX()} {y} {TEX}ساخته می شوند. در نتیجه تعداد این مسیرها برابر است با{TEX()} {{{|a-c|+|b-d|}\choose {|a-c|} }} {TEX}.

اگر {TEX()} {X} {TEX}یک مجموعه باشد، مجموعه ی تمام زیر مجموعه های {TEX()} {X} {TEX}را مجموعه ی توانی {TEX()} {X} {TEX}می نامند و با{TEX()} { P(X) } {TEX}نشان می دهند. به عنوان مثال اگر{TEX()} { X =\{1, 2, 3\} } {TEX} باشد، مجموعه ی توانی {TEX()} {X} {TEX}برابر است با:

@@{TEX()} {P(X)=\{ \emptyset , \{1 \} , \{2 \} , \{3 \} , \{1,2 \} , \{1,3 \} , \{2,3 \} , \{1,2,3 \} \}} {TEX}@@

---

#@

@#16:

!!مثال

اگر {TEX()} {S} {TEX}یک مجموعه ی {TEX()} {n} {TEX}عضوی باشد. تعداد اعضای{TEX()} { P(S)} {TEX} چقدر است؟

__حل.__

بین زیر محموعه های یک مجموعه ی {TEX()} {n} {TEX}عضوی و دنباله های دودویی به طول {TEX()} {n} {TEX}، یک تناظر یک به یک برقرار می کنیم.

فرض کنید{TEX()} {S=\{a_1,a_2,\cdots ,a_n \}} {TEX} و

@@{TEX()} {B=\{b_1b_2 \cdots b_n |b_i=0,1 \ ; \ i=1,\cdots , n \}} {TEX}@@

@@{TEX()} {\forall A \in P(S) \ , \ f(A)=c_1c_2\cdots c_n} {TEX}@@

به طوری که به ازای هر{TEX()} { i = 1, 2, \cdots , n } {TEX} اگر{TEX()} {a_i \in A} {TEX}، آن گاه{TEX()} {c_i=1} {TEX} و در غیر این صورت{TEX()} {c_i=0} {TEX}. به عنوان مثال اگر{TEX()} { S = \{1, 2, 3, 4, 5, 6 \}} {TEX} و{TEX()} { A = \{1, 4, 6 \} } {TEX}باشد؛ آن گاه{TEX()} {f(A)=100101} {TEX}.

واضح است که تابع فوق یک به یک و پوشا است. بنابراین{TEX()} { |P(S)| = |B| } {TEX}. ولی می دانیم که{TEX()} {|B|=2^n} {TEX}، پس تعداد زیر مجموعه های یک مجموعه ی {TEX()} {n} {TEX}عضوی برابر است با{TEX()} {2^n} {TEX}.

---

!!مثال

فرض کنید{TEX()} { X = \{1, 2, \cdots , n \}} {TEX}. تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی {TEX()} {X} {TEX}که شامل هیچ دو عضو متوالی نباشند را بیابید.

__حل.__

بین زیر مجموعه های {TEX()} {k} {TEX}تای {TEX()} {X} {TEX}که شامل هیچ دو عضو متوالی نیستند و تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی مجموعه ی{TEX()} { Y = \{1, 2, \cdots , n – k + 1 \}} {TEX} یک تناظر یک به یک برقرار می کنیم.

فرض کنید{TEX()} {A= \{a_1,a_2,\cdots , a_k \}} {TEX} یک زیر مجموعه {TEX()} {k} {TEX}عضوی {TEX()} {X} {TEX}باشد که شامل هیچ دو عضو متوالی نباشد. بدون کاسته شدن از کلیت مسئله می توان فرض کرد{TEX()} {a_1<a_2<\cdots < a_k} {TEX}، ولی چون هیچ دو عنصری در {TEX()} {A} {TEX}متوالی نیستند بنابراین داریم: {TEX()} {a_1 <a_2-1} {TEX}،{TEX()} {a_2<a_3-1} {TEX}، ... و{TEX()} {a_{k-1}<a_k-1} {TEX}. در ----

---

#@

@#16:

!!نتیجه

@@{TEX()} {1 \le a_1<a_2-1 <a_3-2 <\cdots <a_k-k+1 \le n-k+1} {TEX}@@

حال اگر قرار دهیم:

@@{TEX()} {b_1=a_1 \ , \ b_2=a_2-1 \ , \ b_k=a_k-k+1} {TEX}@@

به ازای هر مجموعه ای مانند {TEX()} {A} {TEX}، یک مجموعه ی {TEX()} {k} {TEX}عضوی مانند{TEX()} {B=\{b_1,b_2,\cdots , b_k \} \subset Y} {TEX} وجود دارد و بالعکس. بنابراین یک تناظر یک به یک بین زیر مجموعه های مورد نظر و ((زیر مجموعه)) های {TEX()} {k} {TEX}عضوی {TEX()} {Y} {TEX}وجود دارد. پس تعداد زیر مجموعه های مورد نظر برابر است با تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی {TEX()} {Y} {TEX}، یعنی برابر است با {TEX()} {{n-k+1}\choose k} {TEX}.

---

!!مثال

در یک مسابقه ی تیر اندازی، نه گوی در یک ستون دو تایی، یک ستون سه تایی و یک ستون چهار تایی مانند شکل زیر آویزان شده اند. یک تیرانداز ماهر می خواهد با روش زیر هر نه گوی را بشکند:

•ابتدا او یک ستون را انتخاب می کند تا هدفی از آن را بشکند.

•سپس او پایین ترین گویی را که قبلاً نشکسته است، هدف قرار می دهد.

اگر هیچ کدام از تیرهای این تیرانداز خطا نرود، او به چند طریق می تواند هر نه گوی را بشکند.

::{picture=img/daneshnameh_up/7/71/com0021b.jpg}::

__حل.__

به ستون اول حرف {TEX()} {A} {TEX}، به ستون دوم حرف {TEX()} {B} {TEX}و به ستون سوم حرف {TEX()} {C} {TEX}را نسبت می دهیم. هرگاه این تیرانداز ستونی را برای هدف گیری انتخاب کرد، حرف متناظر با آن ستون را می نویسیم. به این ترتیب یک تناظر یک به یک بین تعداد راه های تیراندازی و تعداد جایگشت ها کلمه ی{TEX()} { AABBBBCCC } {TEX} برقرار می شود. پس تعداد راه های تیراندازی برابر است با{TEX()} {\frac{9!}{2!4!3!}} {TEX}.

---

#@

@#16:

!!مثال

یک مستطیل {TEX()} {m \times n} {TEX}را با رسم خط هایی ((موازی)) عرض و طول آن به {TEX()} { mn } {TEX} مربع واحد تقسیم کرده ایم.

__الف.__در شکل حاصل چند مستطیل دیده می شود؟

__‌ب.__در شکل حاصل چند مربع دیده می شود؟

::{picture=img/daneshnameh_up/c/c7/com0021c.jpg} ::

__حل. __

__الف.__می دانیم از تقاطع هر دو خط افقی و دو خط عمودی یک و فقط یک ((مستطیل)) ساخته می شود. بنابراین تعداد مستطیل های شکل فوق برابر است با تعداد راه های انتخاب دو خط افقی و دو خط عمودی. پس طبق اصل تناظر یک به یک چون{TEX()} { m + 1 } {TEX}خط افقی و{TEX()} { n + 1 } {TEX}خط عمودی داریم، تعداد مستطیل هایی که در شکل بالا دیده می شود برابر است با{TEX()} {{{m+1}\choose 2}{{n+1}\choose 2}} {TEX}.

__‌ب. __می دانیم که هر مربع{TEX()} { (ABCD) } {TEX} در شکل بالا با انتخاب نقطه ی گوشه ی سمت راست بالا (نقطه {TEX()} {A} {TEX}) و طول آن مشخص می شود. حال تعداد مربع های به ضلع {TEX()} {k} {TEX}را می شماریم. نقطه ی {TEX()} {A} {TEX}روی تقاطع هر یک از{TEX()} { m – k + 1} {TEX} خط افقی اول با هر یک از{TEX()} { n – k + 1 } {TEX}خط عمودی اول می تواند باشد. پس نقطه ی {TEX()} {A} {TEX}را به{TEX()} { (m – k + 1)(n – k + 1) } {TEX}طریق می توان انتخاب کرد. پس تعداد مربع های به ضلع k در شکل فوق برابر است با{TEX()} { (m – k + 1)(n – k + 1)} {TEX}. در نتیجه تعداد مربع های موجود در شکل فوق برابر است با{TEX()} {\sum_{k=1}^{min(m,n)} (m-k+1)(n-k+1)} {TEX}.

---

!!مثال

جایگشت{TEX()} {x_1x_2\cdots x_{2n-1}x_{2n}} {TEX} از مجموعه{TEX()} { S = \{1, 2, \cdots , 2n – 1, 2n \}} {TEX} را در نظر بگیرید. این جایگشت دارای خاصیت {TEX()} {P} {TEX}است اگر به ازای حداقل یک {TEX()} {i} {TEX}بین 1 تا{TEX()} { 2n – 1} {TEX} داشته باشیم{TEX()} {|x_i –x_{i+1}|=n} {TEX}.

ثابت کنید به ازای هر {TEX()} {n} {TEX}، تعداد ((جایگشت)) های دارای خاصیت {TEX()} {P} {TEX}از تعداد جایگشت هایی که این خاصیت را ندارند بیش تر است.

به عنوان مثال اگر{TEX()} { n = 2 } {TEX}و {TEX()} {A} {TEX}مجموعه ی جایگشت های بدون خاصیت {TEX()} {P} {TEX}و {TEX()} {B} {TEX}مجموعه ی جایگشت های دارای خاصیت {TEX()} {P} {TEX}باشد، داریم:

@@{TEX()} { A = \{1234, 1432, 2143, 2341, 3214, 3412, 4123, 4321 \} } {TEX}@@

@@{TEX()} { B = \{1243, 13 24, 13 42, 1423, 2134, 2314, 24 13, 24 31 ,31 24, 31 42, 3241, 3421, 4132, 42 13, 42 31, 4312 \} } {TEX}@@

واضح است که{TEX()} {16 = |B| > |A| = 8. } {TEX}

#@

@#16:

__حل. __

حالت{TEX()} { n = 1،} {TEX} بدیهی است. پس فرض می کنیم{TEX()} {n \ge 2} {TEX} باشد. فرض کنید{TEX()} { (B) A } {TEX} مجموعه ی همه ی جایگشت های {TEX()} {S} {TEX}که دارای خاصیت {TEX()} {P} {TEX}نمی باشند (می باشند) باشد. برای این که نشان دهیم{TEX()} { |B| > |A|} {TEX} کافی است نشان دهیم تابع{TEX()} {f:A \rightarrow B} {TEX} ((یک به یک)) و غیر پوشا است وجود دارد.

برای سادگی کار، زوج{TEX()} { (k = 1, 2, \cdots , n) \ \{k, n + k \}} {TEX} را یک زوج متناظر می نامیم. همچنین اگر زوج{TEX()} { \{k, n + k \}} {TEX} در جایگشتی متوالی باشند، آنها را زوج متناظر متوالی می نامیم.

فرض کنید{TEX()} {\alpha=x_1x_2\cdots x_{2n}} {TEX} یک عضو {TEX()} {A} {TEX}باشد. فرض کنید{TEX()} {x_r} {TEX} عضو متناظر{TEX()} {x_1} {TEX} باشد، چون{TEX()} {\alpha} {TEX} دارای خاصیت {TEX()} {P} {TEX}نیست. پس{TEX()} {3 \le r \le 2r} {TEX}. حال تعریف می کنیم:

{TEX()} {f(\alpha) =x_2x_3\cdots x_{r-1}x_1x_2x_{r+1} \cdots x_{2n}} {TEX}

تابع {TEX()} {f} {TEX}، {TEX()} {x_1} {TEX} را دقیقاً قبل از{TEX()} {x_r} {TEX} قرار می دهد. واضح است که{TEX()} {\{ x_1,x_2 \}} {TEX} تنها زوج متناظر ماولی در{TEX()} {f(\alpha)} {TEX} است. (به عنوان مثال، {TEX()} { f(1234) = 2134} {TEX} و {TEX()} { f(2143) = 1243. } {TEX}) واضح است که{TEX()} {f(\alpha )\in B} {TEX} و {TEX()} {f} {TEX}یک تابع از {TEX()} {A} {TEX}به {TEX()} {B} {TEX}می باشد.

حال نشان می دهیم که {TEX()} {f} {TEX}یک به یک است. فرض کنید

@@{TEX()} {\alpha=x_1x_2\cdots x_{2n}} {TEX}@@

@@{TEX()} {\beta =y_1y_2\cdots y_{2n}} {TEX}@@

دو عضو {TEX()} {A} {TEX}باشند که{TEX()} {x_r} {TEX} زوج متناظر{TEX()} {x_1} {TEX} و{TEX()} {y_s} {TEX} زوج متناظر{TEX()} {y_1} {TEX} باشند، به طوری که{TEX()} {3 \le r \ , \ s \le 2n} {TEX}. فرض کنید {TEX()} {f(\alpha )=f( \beta )} {TEX}

@@{TEX()} {x_2x_3\cdots x_{r-1}x_1x_rx_{r+1} \cdots x_{2n}=y_2y_3 \cdots y_{s-1}y_1y_{s+1} \cdots y_{2n}} {TEX}@@

واضح است که{TEX()} {( \{y_1,y_s \} \{x_1, x_r \}} {TEX} تنها زوج متناظر متوالی{TEX()} {(f( \beta )) \ f(\alpha )} {TEX} هستند. در نتیجه{TEX()} { r = s } {TEX} ،{TEX()} {x_1=y_1} {TEX}، {TEX()} {x_r=y_s} {TEX}. پس به ازای هر{TEX()} { i = 1, 2, \cdots , 2n } {TEX}، {TEX()} {x_i=y_i} {TEX}. در نتیجه{TEX()} {\alpha=\beta} {TEX} و {TEX()} {f} {TEX}یک تابع یک به یک است.

ولی{TEX()} { f(A)} {TEX} مجموعه ی تمام جایگشت های دارای خاصیت {TEX()} {P} {TEX}است که دقیقاً یک زوج متناظر متوالی دارند. در نتیجه{TEX()} {f(A) \subset B} {TEX} و{TEX()} {f(A) \neq B} {TEX}. پس {TEX()} {f} {TEX}یک تابع یک به یک و غیر پوشا از {TEX()} {A} {TEX}به {TEX()} {B} {TEX}می باشد. پس حکم ثابت شد.

---

#@

@#16:

!!مثال

مجموعه ی{TEX()} { S = \{1, 2, \cdots , 1990 \} } {TEX} را در نظر بگیرید. یک زیر مجموعه ی 31 عضوی {TEX()} {S} {TEX}خوب نامیده می شود اگر مجموع اعضایش بر پنج بخش پذیر باشد. تعداد زیر مجموعه های 31 عضوی خوب {TEX()} {S} {TEX}را بیابید.

__حل.__

فرض کنید{TEX()} {(0 \le i \le 4 ) S_i} {TEX} مجموعه ی تمام زیر مجموعه های 31 عضوی {TEX()} {S} {TEX}باشد که باقی مانده ی آنها بر 5 برابر {TEX()} {i} {TEX}است. ثابت می کنیم یک تناظر یک به یک بین{TEX()} {S_i} {TEX} ها برقرار است.

فرض کنید{TEX()} {A={a_1,a_2,\cdots ,a_{31} \} \subset S} {TEX} یک عضو{TEX()} {(0 \le i \le 4 ) S_i} {TEX} باشد. از روی هر{TEX()} {A \in S_i} {TEX}، مجموعه {TEX()} {B=\{b_1,b_2,\cdots ,b_{31} \}} {TEX} را به این شکل می سازیم که{TEX()} {(1 \le j \le 31 ) \ b_j= (a_j mod \ 1990)+1} {TEX}، یعنی اگر {TEX()} {a_j<1990} {TEX} باشد،{TEX()} {b_j=a_j +1} {TEX} و اگر{TEX()} {a_j=1990} {TEX} باشد، {TEX()} {b_j=1} {TEX}. در نتیجه داریم:

@@{TEX()} {\sum_{j=1}^31 b_j \equive \sum_{j=1}^31 a_j+31 \equive i+1 \qquad (mod \ 5)} {TEX}@@

بنابراین تابع یک به یکی داریم که به هر عضو{TEX()} {(0 \le i \le 3)S_i} {TEX}، یک عضو{TEX()} {S_{i+1}} {TEX} و به هر عضو{TEX()} {S_4} {TEX} یک عضو {TEX()} {S_0} {TEX} را نسبت می دهد. در نتیجه

@@{TEX()} {|S_0|=|S_1|=|S_2|=|S_3|=|S_4|} {TEX}@@

. ولی می دانیم

@@{TEX()} {|S_0|+|S_1|+|S_2|+|S_3|+|S_4| ={{1990}\choose 5}} {TEX}.@@

پس

@@{TEX()} {|S_0|=\frac{1}{5} {{1990}\choose 5}} {TEX}.@@

---

!!مثال

__حل.__

به هر دنباله ی دودویی{TEX()} {x_1x_2\cdots x_n} {TEX} به طول {TEX()} {n} {TEX}، دو دنباله ی دودویی به طول{TEX()} { n + 1} {TEX} مانند{TEX()} {y_0y_1\cdots y_n} {TEX} و {TEX()} {z_0z_1\cdots z_n} {TEX}، به این شکل نسبت می دهیم که{TEX()} {y_0=0} {TEX}،{TEX()} {z_0=1} {TEX}،{TEX()} {y_i=(y_{i-1}+x_i ) \qquad (mod \ 2)} {TEX} و {TEX()} {(1 \le i \le n ), z_i=(z_{i-1}+x_i)} {TEX}. واضح است که این یک تناظر یک به یک بین دنباله های دودویی به طول {TEX()} {n} {TEX}و دنباله های دودویی به طول {TEX()} { n + 1} {TEX} که جمله ی اول آنها صفر (یک) است، می باشد. اگر به تناظر بالا نگاه کنیم می بینیم که باقی مانده ی ((تقسیم)){TEX()} {x_i} {TEX} و{TEX()} {y_{i-1}+y_i \ (z_{i-1}+z_i)} {TEX} بر دو یکسان است. در نتیجه تناظر یک به یک فوق هر دنباله ی دودویی به طول {TEX()} {n} {TEX}را که شامل زیر رشته ی010 نمی باشد به یک دنباله ی دودویی به طول{TEX()} { n + 1 } {TEX}که شامل هیچ زیر رشته ی0011 یا1100 نمی باشد و جمله ی اول آنها صفر (یک) است، متناظر می کند. پس به ازای هر دنباله ی دودویی به طول{TEX()} { n + 1 } {TEX} که شامل زیر رشته ی0011 یا1100 نمی باشد وجود دارد. در نتیجه {TEX()} {b_{n+1}=2a_n} {TEX}.

---

#@

@#16:

!!مثال

تعداد ((ماتریس)) های {TEX()} {m\times n} {TEX} با درایه های 1 و 1- را پیدا کنید که حاصل ضرب عناصر هر سطر آن برابر 1- و حاصل ضرب عناصر هر ستون آن نیز برابر با 1- شود. ادعای خود را ثابت کنید.

__اثبات.__

اگر چنین ماتریسی وجود داشته باشد باید{TEX()} {m \equive n \qquad (mod \ 2)} {TEX} باشد. زیرا از یک طرف حاصل ضرب تمام درایه های این ماتریس برابر است با حاصل ضرب حاصل ضرب درایه های سطرهای آن یعنی{TEX()} {(-1)^m} {TEX} و از طرف دیگر برابر است با حاصل ضرب حاصل ضرب درایه های ستون های آن یعنی{TEX()} {(-1)^n} {TEX}. پس باید داشته باشیم {TEX()} {(-1)^m=(-1)^n} {TEX} یعنی {TEX()} {m} {TEX}و {TEX()} {n} {TEX}دارای زوجیت یکسانی باشند، دقیقاً{TEX()} {2^{(m-1)(n-1)}} {TEX} ماتریس با شرط فوق وجود دارد. برای این کار نشان می دهیم که یک تناظر یک به یک بین تعداد ماتریس های{TEX()} {(m-1)\times (n-1)} {TEX} با درایه های 1 و 1- و این گونه ماتریس ها وجود دارد.

یک ماتریس{TEX()} {(m-1)\times (n-1)} {TEX} دلخواه با درایه های 1 و 1- را در نظر بگیرید. حال با سطر (سطر {TEX()} {m} {TEX}ام) و یک ستون (ستون {TEX()} {n} {TEX}ام) به آن اضافه می کنیم. حاصل ضرب عناصر سطر {TEX()} {i} {TEX}ام ماتریس اولیه را با{TEX()} {r_i} {TEX} و حاصل ضرب عناصر ستون {TEX()} {j} {TEX}ام ماتریس اولیه را با{TEX()} {c_j} {TEX} و حاصل ضرب تمام عناصر ماتریس اولیه را با

{TEX()} {A=c_1\times c_2 \times c_{n-1}=r_1 \times r_2 \times r_{m-1}} {TEX}

نشان می دهیم. درایه های سطر و ستون آخر ماتریس جدید به شکل زیر ساخته می شوند. درایه‌ی{TEX()} { (m, j) } {TEX}برابر است با{TEX()} {(-1)^mA=(-1)^nA} {TEX}. (چرا؟) واضح است که این تناظر یک به یک و ((پوشا)) می باشد. بنابراین تعداد ماتریس های مورد نظر برابر است با{TEX()} {2^{(n-1)(m-1)}} {TEX}.

---

! پیوند های خارجی

[http://Olympiad.roshd.ir/computer/content/pdf/0027.pdf]

!همچنین ببینید

*((ترکیب با تکرار ))

*((مثلث خیام پاسکال ))

#@^