فرض کنید{ x={1, 2, . . . , n ، چند زیر مجموعه ی k عضوی از X وجود دارد که تفاضل هر دو عضو آن حداقل m باشد؟
چنین مجموعه هایی را m- مجزا می نامیم.
سلام. فرض کنید k عضو قراره انتخاب کنیم. میشه با مشخص کردن k پارامتر که مجموعشون کوچکترمساوی n میشه و ترتیبشون اهمیت داره این اعداد رو مشخص کرد. به عنوان مثال k=3 و n=8 و ۳ پارامتر برابر ۱,۲,۲ باشن. در این صورت دو عدد انتخاب شده برابر ۱ و ۱+۲ و ۱+۲+۲ خواهند بود. پس فقط کافیه k پارامتر با مجموع کوچکترمساوی n پیدا کنیم. داریم:
[tex]x_1 x_2 ... x_k\leq n\Rightarrow x_1 x_2 ... x_{k 1}= n[/tex]
چون قراره اختلاف اعضاحداقل m باشه داریم:
[tex]x_2,x_3,...,x_k\geq m[/tex]
درنظر میگیریم:
[tex]y_1=x_1,y_{k 1}=x_{k 1},y_i(i=2..k)=x_i-m[/tex]
در رابطه اول جایگزین میکنیم:
[tex]x_1 x_2 ... x_{k 1}= n\Rightarrow y_1 y_2 ... y_{k 1}=n-m(k-1)[/tex]
تعداد حالات میشه [tex]\binom{n m k-mk}{k}[/tex].