Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۶:ترکیبیات:سوال ۱

درخت تصادفی

می‌خواهیم یک درخت با رأس‌های 1,2,,n بسازیم. ابتدا رأس ۱ را ریشه‌ی درخت قرار داده و در مرحله‌ی i ام (2in)، رأس i را به طور تصادفی فرزند یکی از رئوس 1,2,,i1 قرار می‌دهیم. عدد درخت را مجموع شماره‌ی رئوس در مسیر رأس n به رأس 1 در نظر می‌گیریم. توجه کنید خود رأس‌های 1 و n را نیز حساب می‌کنیم. امید ریاضی عدد درخت را بر حسب n بیابید.


ابزار صفحه