اجتماع مجموعهها ... سؤال همراه با جواب
سؤال
اگر S مجموعهاي از «اعداد صحيح» باشد، تعريف ميكنيم:
چند زيرمجموعه مانند S از مجموعهي
وجود دارد بهطوري كه:
جواب
بهازاي هر زيرمجموعه از S يك دنباله بهطول n از صفر و يك در نظر ميگيريم بهطوري كه عضو Iام اين دنباله 1 است اگر و فقط اگر
.
در اين صورت مجموعههايي كه داراي خاصيت مسأله هستند شامل دو صفر متوالي نبوده همچنين عضو nام آنها صفر است (چرا)؟ عضو اول و
ام آنها نيز 1 ميباشد. حال مسأله منجر به شمارش تعداد دنبالههاي بهطول
از صفر و يك است كه شامل دو صفر متوالي نباشد.
اگر
تعداد اين دنبالهها باشد داريم:
(رابطهي 1)
و با حل اين دنبالهي بازگشتي تعداد جوابهاي مسأله بهدست ميآيد.