Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

تابع آبی‌ رو!

  1. به A(x)=i=0ai×xii! تابع مولد نمایی دنباله‌ی a0,a1, می‌گوییم. صورت صریح تابع مولد نمایی‌ای را بیابید که دنباله‌ی 1,1, را تولید کند. (۱۰ نمره)
  2. فرض کنید P یک ویژگی روی گراف‌های همبند باشد. تعداد گراف‌های همبند n رأسی برچسب‌دار که ویژگی P را دارند، cn در نظر بگیرید و فرض کنید C(x)=i=0cixii! تابع مولد نمایی دنباله‌ی c0,c1, باشد. ثابت کنید ضریب xnn! در تابع مولد نمایی D(x)=12(C(x))2 برابر با تعداد گراف‌های n رأسی برچسب‌دار با دقیقن دو مؤلفه‌ی همبندی است که هر کدام از مؤلفه‌های همبندی، ویژگی P را دارند. (۳۰ نمره)
  3. فرض کنید k یک عدد طبیعی دل‌خواه باشد. ثابت کنید ضریب xnn! در تابع مولد نمایی E(x)=1k!(C(x))k برابر با تعداد گراف‌های n رأسی برچسب‌دار با دقیقن k مؤلفه‌ی همبندی است که هر کدام از مؤلفه‌های همبندی، ویژگی P را دارند. (۳۰ نمره)
  4. تابع مولد نمایی‌ای در نظر بگیرید که ضریب xnn! در آن برابر تعداد تمام گراف‌های n رأسی برچسب‌دار باشد که هر مؤلفه‌ی آن، ویژگی P را دارد. یک رابطه‌ی صریح بر حسب xو C(x) برای تابع مولد گفته شده بیابید. (۳۰ نمره)

توجه: در این سوال در هر قسمت می‌توانید از قسمت‌های قبلی بدون اثبات استفاده کنید.


ابزار صفحه