◄◄◄◄◄◄◄◄╡ماراتن سه روزه ی شمارش ╞►►►►►►►►

Goharshady · 1389/2/6

abdi گفت

فکر می کنم بهتر بود این طوری می نوشتید:
[center:f228729c09]

${\color{blue} \sum_{A_{i},A_{j}\subseteq X}^{ }\left | A_{i}\cap A_{j} \right |=?}$

[/center:f228729c09]

Olympiad · 1389/2/6

سوال پنجم : تعداد راه هاي توزيع n شيء متمايز يه دور 2 ميز يكسان(

$s(n,2)$

(عدد استرلينگ نوع اول)) را بيابيد به طوريكه هيچ ميزي خالي نباشد .

Goharshady · 1389/2/6

[center:968c853ca0]

$\sum_{i\leq \frac{n}{2}}^{ }(i-1)!(n-i-1)!$

جدی نگیرید

[/center:968c853ca0]

Goharshady · 1389/2/6

Olympiad گفت

یک رابطه ی بازگشتی ثابت می کنم:

$s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)$

اثبات: شی یک را در نظر بگیرید. یا به تنهایی دور یک میز قرار می گیرد که در این صورت بقیه به

$s(n-1,k-1)$

طریق قرار می گیرند یا به تنهایی قرار نمی گیرد در این صورت بقیه را به

$s(n-1,k)$

طریق قرار می دهیم و سپس به

$n-1$

یکی از سایر اشیا را انتخاب می کنیم و شی یک را به صورت ساعتگرد بلافاصله پس از آن قرار می دهیم. پس رابطه ی بازگشتی ثابت است.
حالا رابطه ی بازگشتی را که در حالت کلی ثابت کردیم برای k=2 می نویسیم:
[center:ca55ba6013]

$s(n,2)=s(n-1,1)+(n-1)s(n-1,2)$

[/center:ca55ba6013]از آنجا که می دانیم

$s(n-1,1)= (n-2)!$

داریم :

$s(n,2)=(n-2)!+(n-1)s(n-1,2)$

اگر

$s(n,2)$

را به صورت

$f(n)$

نشان دهیم به رابطه ی بازگشتی

$f(n)=(n-2)!+(n-1)f(n-1)$

می رسیم که حل آن آسان است.

Goharshady · 1389/2/6

Olympiad گفت

لطفا بگید از کجا اومده

Olympiad · 1389/2/6

فهميدم غلطه!!!

Goharshady · 1389/2/6

ولی من خیلی مشتاقم که بدونم از کجا اومده
حتی راه حلهای غلط هم بسیار عبرت آموز هستند.

Goharshady · 1389/2/7

در این لحظه ، پایان این ماراتن را اعلام می کنم
مفید بود
با آرزوی موفقیت برای همه ی بچه های المپیاد کامپیوتر

◄◄◄◄◄◄◄◄╡ماراتن سه روزه ی شمارش ╞►►►►►►►►

Goharshady

New Member

Olympiad

New Member

Goharshady

New Member

Goharshady

New Member

Goharshady

New Member

Olympiad

New Member

Goharshady

New Member

Goharshady

New Member