سری دوم سوالات

1)

nنقطه در صفحه داریم ؛ فاصله ی بین هر دو نقطه از آن حداقل یک است.حداکثر 3nزوج از این نقاط فاصله ای دقیقا برابر 1 دارند.

2)

گراف G را این طور میسازیم:

برای هر جایگشت nتایی یک راس میگیریم و دو راس دو جاییگشتaوb را به هم وصل میکنیم اگر a با یک حرکت به bتبدیل شود.

تعریف یک حرکت :
یک حرکت در یک جایگشت مانند a₁,a₂,a₃,...,a_n جای دو عضو مانند a_iوa_jرا با هم عوض میکند.

ثابت کنید Gدو بخشی است.

3)

نشان دهید تعداد درخت های باینری (باینری:هر راس داخلی دو فرزند دارد)با nراس داخلی(داخلی:برگ نیست)برابر با n امین عدد کاتالان میباشد.

برای n=3 در زیر نشان داده شده است