منو
 صفحه های تصادفی
ارزش احترام به فرزندان فاطمه علیهاسلام
hemorrhoids
انفاق در راه خدا
ترتیبات و مقررات لازم جهت انجام آزمایشات توپ تنیس
سود و زیان
بهره برداری از آتشفشان
پروتئین Rec A
یک فشار سنج بسازید
ام هانی
حمل و نقل
 کاربر Online
716 کاربر online
Lines: 1-143Lines: 1-143
 ||V{maketoc}|| ||V{maketoc}||
-||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| +||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
 ^@#16: ^@#16:
 !تناظر یک به یک و مسائل مربوط به شمارش !تناظر یک به یک و مسائل مربوط به شمارش
 فرض کنید در یک کلاس، {TEX()} {n} {TEX}دانش آموز نشسته باشند. اگر این کلاس 20 نیمکت داشته باشد و هر دانش آموز روی یک نیمکت نشسته باشد، واضح است که {TEX()} {n \le 20} {TEX}. ولی اگر بدانیم روی هر نیمکت حداقل یک دانش آموز نشسته باشد، واضح است که {TEX()} {n \ge 20} {TEX}. همچنین اگر بدانیم روی هر نیمکت دقیقا یک نفر نشسته است، بدون شمردن تعداد دانش آموزان، می توانیم بگوییم که {TEX()} {n=20} {TEX}.  فرض کنید در یک کلاس، {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()} {f:A \rightarrow B} {TEX} را یک تابع یک به یک می نامیم. اگر
 @@{TEX()} { \forall x,y \in A \ , \ x \neq y \ : \ f(x) \neq f(y)} {TEX}@@ @@{TEX()} { \forall x,y \in A \ , \ x \neq y \ : \ f(x) \neq f(y)} {TEX}@@
 به عبارت دیگر تابع {TEX()} {f} {TEX}، به هیچ دو عضو دلخواه {TEX()} {A} {TEX}، یک مقدار را نسبت ندهد.  به عبارت دیگر تابع {TEX()} {f} {TEX}، به هیچ دو عضو دلخواه {TEX()} {A} {TEX}، یک مقدار را نسبت ندهد.
 اصل رابطه یک به یک. اگر یک رابطه یک به یک (تابع ((یک به یک))) از ((مجموعه)) {TEX()} {A} {TEX}به مجموعه {TEX()} {B} {TEX}وجود داشته باشد، آنگاه {TEX()} {|A| \le |B|} {TEX}. اصل رابطه یک به یک. اگر یک رابطه یک به یک (تابع ((یک به یک))) از ((مجموعه)) {TEX()} {A} {TEX}به مجموعه {TEX()} {B} {TEX}وجود داشته باشد، آنگاه {TEX()} {|A| \le |B|} {TEX}.
 --- ---
 !!تعریف !!تعریف
  تابع {TEX()} {f:A \rightarrow B} {TEX} را یک ((تناظر یک به یک)) می نامیم اگر یک به یک و ((پوشا)) باشد.   تابع {TEX()} {f:A \rightarrow B} {TEX} را یک ((تناظر یک به یک)) می نامیم اگر یک به یک و ((پوشا)) باشد.
 اصل تناظر یک به یک. اگر یک تناظر یک به یک از مجموعه {TEX()} {A} {TEX}به مجموعه {TEX()} {B} {TEX}وجود داشته باشد، آنگاه {TEX()} {|A|=|B|} {TEX}. اصل تناظر یک به یک. اگر یک تناظر یک به یک از مجموعه {TEX()} {A} {TEX}به مجموعه {TEX()} {B} {TEX}وجود داشته باشد، آنگاه {TEX()} {|A|=|B|} {TEX}.
 دقت کنید که در اصول فوق لزومی ندارد مجموعه های {TEX()} {A} {TEX}و {TEX()} {B} {TEX}متناهی باشد دقت کنید که در اصول فوق لزومی ندارد مجموعه های {TEX()} {A} {TEX}و {TEX()} {B} {TEX}متناهی باشد
 --- ---
 #@ #@
 @#16: @#16:
 !!مثال !!مثال
  با استفاده از تناظر یک به یک ثابت کنید:  با استفاده از تناظر یک به یک ثابت کنید:
 @@{TEX()} { {n \choose k}={n\choose {n-k}}} {TEX}@@ @@{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()} {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}عنصر را به دست آورد. اگر{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 بلوک را طی می کند. این شخص به چند طریق می تواند به محل کارش برود؟  شخصی در ساختمانی کار می کند که هفت بلوک در شرق و هشت بلوک در شمال خانه اش قرار دارد. این فرد برای رسیدن به محل کارش هر روز 15 بلوک را طی می کند. این شخص به چند طریق می تواند به محل کارش برود؟
 ::{picture=img/daneshnameh_up/b/b3/com0021a.jpg}::  ::{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}.  مسئله ی مسیر را با تعداد کلمات 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()} { (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()} {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}@@ @@{TEX()} {P(X)=\{ \emptyset , \{1 \} , \{2 \} , \{3 \} , \{1,2 \} , \{1,3 \} , \{2,3 \} , \{1,2,3 \} \}} {TEX}@@
 --- ---
 #@ #@
 @#16: @#16:
 !!مثال !!مثال
  اگر {TEX()} {S} {TEX}یک مجموعه ی {TEX()} {n} {TEX}عضوی باشد. تعداد اعضای{TEX()} { P(S)} {TEX} چقدر است؟  اگر {TEX()} {S} {TEX}یک مجموعه ی {TEX()} {n} {TEX}عضوی باشد. تعداد اعضای{TEX()} { P(S)} {TEX} چقدر است؟
 __حل.__ __حل.__
  بین زیر محموعه های یک مجموعه ی {TEX()} {n} {TEX}عضوی و دنباله های دودویی به طول {TEX()} {n} {TEX}، یک تناظر یک به یک برقرار می کنیم.  بین زیر محموعه های یک مجموعه ی {TEX()} {n} {TEX}عضوی و دنباله های دودویی به طول {TEX()} {n} {TEX}، یک تناظر یک به یک برقرار می کنیم.
 فرض کنید{TEX()} {S=\{a_1,a_2,\cdots ,a_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()} {B=\{b_1b_2 \cdots b_n |b_i=0,1 \ ; \ i=1,\cdots , n \}} {TEX}@@
-مجموعه ی تمام ((دنباله)) های دودویی به طول {TEX()} {n} {TEX}باشد. تابع یک به یک و پوشای{TEX()} {f:P(S) \rightarrow B} {TEX} را به این شکل تعریف می کنیم. +مجموعه ی تمام ((مفهوم دنباله)) های دودویی به طول {TEX()} {n} {TEX}باشد. تابع یک به یک و پوشای{TEX()} {f:P(S) \rightarrow B} {TEX} را به این شکل تعریف می کنیم.
 @@{TEX()} {\forall A \in P(S) \ , \ f(A)=c_1c_2\cdots c_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()} { 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()} { |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()} { 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()} {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}. در ---- فرض کنید{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: @#16:
 !!نتیجه !!نتیجه
 @@{TEX()} {1 \le a_1<a_2-1 <a_3-2 <\cdots <a_k-k+1 \le n-k+1} {TEX}@@ @@{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()} {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}. به ازای هر مجموعه ای مانند {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}:: ::{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}.  به ستون اول حرف {TEX()} {A} {TEX}، به ستون دوم حرف {TEX()} {B} {TEX}و به ستون سوم حرف {TEX()} {C} {TEX}را نسبت می دهیم. هرگاه این تیرانداز ستونی را برای هدف گیری انتخاب کرد، حرف متناظر با آن ستون را می نویسیم. به این ترتیب یک تناظر یک به یک بین تعداد راه های تیراندازی و تعداد جایگشت ها کلمه ی{TEX()} { AABBBBCCC } {TEX} برقرار می شود. پس تعداد راه های تیراندازی برابر است با{TEX()} {\frac{9!}{2!4!3!}} {TEX}.
 --- ---
 #@ #@
 @#16: @#16:
 !!مثال !!مثال
  یک مستطیل {TEX()} {m \times n} {TEX}را با رسم خط هایی ((موازی)) عرض و طول آن به {TEX()} { mn } {TEX} مربع واحد تقسیم کرده ایم.  یک مستطیل {TEX()} {m \times n} {TEX}را با رسم خط هایی ((موازی)) عرض و طول آن به {TEX()} { mn } {TEX} مربع واحد تقسیم کرده ایم.
 __الف.__در شکل حاصل چند مستطیل دیده می شود؟ __الف.__در شکل حاصل چند مستطیل دیده می شود؟
 __‌ب.__در شکل حاصل چند مربع دیده می شود؟ __‌ب.__در شکل حاصل چند مربع دیده می شود؟
 ::{picture=img/daneshnameh_up/c/c7/com0021c.jpg} :: ::{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()} { 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()} { (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()} {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} {TEX}، تعداد ((جایگشت)) های دارای خاصیت {TEX()} {P} {TEX}از تعداد جایگشت هایی که این خاصیت را ندارند بیش تر است.
 به عنوان مثال اگر{TEX()} { n = 2 } {TEX}و {TEX()} {A} {TEX}مجموعه ی جایگشت های بدون خاصیت {TEX()} {P} {TEX}و {TEX()} {B} {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()} { 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()} { 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}  واضح است که{TEX()} {16 = |B| > |A| = 8. } {TEX}
 #@ #@
 @#16: @#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()} { 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()} { (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()} {\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(\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()} {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()} {f} {TEX}یک به یک است. فرض کنید
 @@{TEX()} {\alpha=x_1x_2\cdots x_{2n}} {TEX}@@ @@{TEX()} {\alpha=x_1x_2\cdots x_{2n}} {TEX}@@
 @@{TEX()} {\beta =y_1y_2\cdots y_{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()} {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()} {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()} {( \{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}می باشد. پس حکم ثابت شد. ولی{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: @#16:
 !!مثال !!مثال
  مجموعه ی{TEX()} { S = \{1, 2, \cdots , 1990 \} } {TEX} را در نظر بگیرید. یک زیر مجموعه ی 31 عضوی {TEX()} {S} {TEX}خوب نامیده می شود اگر مجموع اعضایش بر پنج بخش پذیر باشد. تعداد زیر مجموعه های 31 عضوی خوب {TEX()} {S} {TEX}را بیابید.   مجموعه ی{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()} {(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()} {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()} {\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()} {(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|} {TEX}@@
 . ولی می دانیم . ولی می دانیم
 @@{TEX()} {|S_0|+|S_1|+|S_2|+|S_3|+|S_4| ={{1990}\choose 5}} {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()} {|S_0|=\frac{1}{5} {{1990}\choose 5}} {TEX}.@@
 --- ---
 !!مثال !!مثال
- فرض کنید{TEX()} {a_n} {TEX} تعداد ((دنباله)) های دودویی به طول {TEX()} {n} {TEX}باشد که شامل هیچ زیر رشته ی010 نباشند و{TEX()} {b_n} {TEX} تعداد دنباله های دودویی به طول {TEX()} {n} {TEX}باشد که شامل هیچ زیر رشته ی1100 یا0011، نباشند. ثابت کنید برای هر ((عدد طبیعی)) {TEX()} {n} {TEX}،{TEX()} {b_{n+1}=2a_n} {TEX}. + فرض کنید{TEX()} {a_n} {TEX} تعداد ((مفهوم دنباله)) های دودویی به طول {TEX()} {n} {TEX}باشد که شامل هیچ زیر رشته ی010 نباشند و{TEX()} {b_n} {TEX} تعداد دنباله های دودویی به طول {TEX()} {n} {TEX}باشد که شامل هیچ زیر رشته ی1100 یا0011، نباشند. ثابت کنید برای هر ((عدد طبیعی)) {TEX()} {n} {TEX}،{TEX()} {b_{n+1}=2a_n} {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}.  به هر دنباله ی دودویی{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: @#16:
 !!مثال !!مثال
  تعداد ((ماتریس)) های {TEX()} {m\times n} {TEX} با درایه های 1 و 1- را پیدا کنید که حاصل ضرب عناصر هر سطر آن برابر 1- و حاصل ضرب عناصر هر ستون آن نیز برابر با 1- شود. ادعای خود را ثابت کنید.  تعداد ((ماتریس)) های {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 \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()} {(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()} {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}. نشان می دهیم. درایه های سطر و ستون آخر ماتریس جدید به شکل زیر ساخته می شوند. درایه‌ی{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] [http://Olympiad.roshd.ir/computer/content/pdf/0027.pdf]
 !همچنین ببینید !همچنین ببینید
 *((ترکیب با تکرار )) *((ترکیب با تکرار ))
 *((مثلث خیام پاسکال )) *((مثلث خیام پاسکال ))
 #@^ #@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:01 ]   4   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [07:24 ]   3   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [07:22 ]   2   زینب معزی      v  c  d  s 
 یکشنبه 12 شهریور 1385 [11:46 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..