مديري در طول روز در زمان‌هاي مختلف، نامه‌اي را براي تايپ به منشي مي‌دهد و هر بار نامه را روي ستون نامه‌هاي روي ميز منشي مي‌گذارد ... سؤال همراه با جواب
مديري در طول روز در زمان‌هاي مختلفي نامه‌اي را براي تايپ به منشي مي‌دهد و هر بار نامه را روي ستون نامه‌هاي روي ميز منشي مي‌گذارد. هر وقت كه موقعش برسد منشي نامه‌ي رويي را برمي‌دارد و آن را تايپ مي‌كند.
امروز 9 نامه بايد تايپ شوند و مدير آنها را به‌ترتيب 1، 2، 3، 4، 5، 6، 7، 8 و 9 به منشي مي‌دهد.
هنگام ناهار، منشي به همكارش مي‌گويد كه نامه‌ي 8 تايپ شده است اما از اينكه پيش‌از ظهر چه نامه‌هايي تايپ شده است هيچ‌چيز نمي‌گويد.
همكار منشي از خود مي‌پرسد كه بعد از ناهار كدام‌يك از 9 نامه و به چه ترتيبي بايد تايپ شوند.
براساس اطلاعات بالا، چند تا ترتيب تايپ بعد از ناهار ممكن است وجود داشته باشد؟ (اينكه هيچ نامه‌اي براي تايپ نمانده باشد هم يكي از حالت‌هاي ممكن است).
جواب :
در هر زماني، نامه‌ها از بالا به پايين به ترتيب نزولي قرار دارند. بنابراين دنباله نامه‌ها به طور يكتا با مجموعه نامه‌ها مشخص مي‌شود. دو حالت داريم: نامه 9 پيش از ناهار به منشي داده شده است يا بعد از ناهار.
حالت 1. چون نامه 9 پيش از ناهار به منشي داده شده است، هيچ نامه ديگري داده نخواهد شد و تعداد ترتيبهاي ممكن تعداد زيرمجموعه‌هاي مجموعه {9, 7, 6, … , 2, 1}T = است، كه ممكن است نامه‌هاي متناظرشان باقي مانده باشند. در حقيقت، هر يك از زيرمجموعه‌هاي T ممكن است جواب باشد، زيرا ممكن است منشي نامه‌هايي را كه در اين زيرمجموعه نيستند بلافاصله پس از تحويل آنها تايپ كند و هيچ نامه ديگري را تايپ نكند. چون T هشت عضو دارد تعداد زيرمجموعه هايش (با احتساب مجموعه تهي) برابر است با 8 2 يا 256.
حالت 2. چون نامه 9 پيش از ناهار به منشي داده نشده است، سوال اين است كه رديف قرار دادن اين نامه براي تايپ كجاست؟ هر جايي در هر زيرمجموعه اي از مجموعه {7, 6, … , 2, 1}كه نامه‌هاي متناظرش به هنگام ناهار باقي مانده‌اند ممكن است جاي نامه 9 باشد. مثلاً، اگر هنگام ناهار نامه هاي باقي‌مانده 6، 3 و 2 باشند، ترتيب نامه‌ها ممكن است 6، 3، 9 و 2 باشد، زيرا ممكن است مدير درست پس از اينكه نامه 3 تايپ شد نامه 9 را بدهد. به نظر مي‌یسد كه در دنباله‌اي از k نامه، 1 + k جا براي قراردادن نامه 9 وجود دارد. با اين وجود، اگر نامه 9 را در ابتداي اين دنباله قرار دهيم (يعني روي ستون نامه‌ها بگذاريم، در نتيجه اين نامه پيش از اينكه نامه‌هاي تايپي پس از ناهار تايپ شوند رسيده است)، يكي از ترتيبهاي حالت (1) را تكرار كرده‌ايم. بنابراين اگر پس از بازگشتن از ناهار k نامه مانده باشند، k جا براي گذاشتن نامه 9 وجود دارد (و هيچ ترتيبي از حالت (1) را تكرار نكرده‌ايم). بنابراين تعداد ترتيبهاي جديد در حالت (2) برابر است با
بنابراين تعداد ترتيبهاي تايپ كردن نامه‌ها برابر است با 448 + 256 كه برابر است با 704