تعداد صفحات: ۱۸ | قابل ویرایش
ترکیبات
شاید در نگاه اول ترکیبات یک بخش معماگونه و سطحی از ریاضیات به نظر برسد که دارای کاربرد چندانی نبوده و فقط مفهوم های انتزاعی را معرفی می کند ولی این شاخه از ریاضیات دارای گستره‌ی وسیع بوده و دارای شاخه های زیادی نیز می باشد.
ابتدا به مسأله ای زیبا از ترکیبات برای آشنا شدن بیشتر با این مبحث ارائه می کنیم.
سوال : یک اتاقی مشبک شده به طول ۸ و عرض ۸ داریم که خانه‌ی بالا سمت چپ و خانه‌ی پایین سمت راست آن حذف شده است (مانند شکل زیر)
حال ما دو نوع موزاییک داریم . یکی ۲*۱ ( ) و دیگری ۱×۲ ( ) سوال این است که آیا می توان این اتاق را با این دو نوع موزائیک فرش کرد.
احتمالاً اگر شخص آشنایی با ترکیبات نداشته باشد می گوید «آری» و سعی می کند با کوشش و خطا اتاق را فرش کند ولی این کار شدنی نیست ؟! و اثبات جالبی نیز دارد.
اثبات : جدول را بصورت شطرنجی رنگ می کنیم مانند شکل زیر:
حال با کمی دقت متوجه می شویم که هر موزائیک یک خانه از خانه های سیاه و یک خانه از خانه‌های سفید را می پوشاند یعنی اگر قرار باشد که بتوان با استفاده از این موزائیک ها جدول پوشانده شود باید تعداد خانه های سیاه با تعداد خانه های سفید برابر باشد ولی این گونه نیست زیرا تعداد خانه های سفید جدول برابر ۳۲ و تعداد خانه های سیاه برابر ۳۰ می باشد . در نتیجه این کار امکان امکان پذیر نیست.
اصل لانه کبوتری
اصلی ساده در ترکیبات است که بسیاری از مسائل با آن حل می‌شوند و صورت آن به شرح زیر است:
اصل لانه کبوتری: اگر مروارید را در داخل k جعبه بگذاریم حتماً جعبه‌ای وجود دارد که حداقل عدد مروارید در آن می‌باشد.
یکی از مثالهای ساده و زیبای این اصل سئوال زیر است:
در جمعی n نفر حضور دارند بعضی از اشخاص این جمع با هم دست می‌دهند ثابت کنید این جمع دو نفر وجود دارند که با تعداد برابر دست داده‌اند.
اثبات: هر نفر می‌تواند با ۰ تا n-1 نفر دست دهد حال اگر فردی باشد که با همه دست داده باشد آنگاه فردی نیست که با کسی دست نداده باشد و بالعکس بنابراین در این جمع هیچکاه دو نفر وجود ندارد که یکی با ۰ و دیگری با n-1 نفر دست داده باشد. حال فرض کنیم هیچ شخصی وجود نداشته باشد که به تعداد برابری دست داده باشند و چون تعداد این دست دادنها از ۰ تا n-1 است
( کلاً n عدد) پس هم باید ۰ بیاید و هم n-1 که این خلاف گفته‌های بالا می‌باشد.
یک مثال نسبتاً سخت: ثابت کنید اعداد در مجموعه وجود دارند که در معادله‌ای زیر صدق بکند:( همه ها نمی‌توانند صفر باشند.
نظریه گراف
نظریه گراف شاخه‌‌‌‌‌ای از ریاضیات است که به شدت درحال رشد است و هرچه بیشتر در آن جلو می‌رویم مسائل حل نشده و مهم زیادی را می‌بینیم.
تعریف گراف:
گراف را با مجموعه رئوس ۷ و مجموعه یالهای E تعریف می‌کنند بطوریکه هر یال دو رأس را به هم وصل می‌کند( یالها ممکن است جهت‌دار باشند) معمولاً گراف را در صفحه با نقطه برای نمایش رأسها و خط برای نمایش یالهای استفاده می‌شود.
