نحوه رعایت شرط حلقه for در شمارش تعداد تکرار دستور Written

Question

منطق مثال بالا استفاده از فرمول \binom{n+k-1}{k} برای انتخاب k شی با تکرار از میان n شی متمایز می باشد. مشکل اینجاست که خودش هم ذکر کرده شرط زیر حتما باید برقرار باشد:

1 <= k <= j <= i <= 20

اما تغییری در فرمول یا راه حل داده نشده. این شرط چطور برقرار شده؟

Comments

@Saturn شما مدتی‌است که در سایت عضو هستید، انتظار می‌رود با قوانین سایت آشنا باشید.
۱- آیا چیزی که عکس گذاشته‌اید یک شکل است؟
۲- اینکه در مرجع مشخصات آورده‌اید خوب است، البته اسم کتاب را نیاورده‌اید! اینکه شما کتابی را به اصطلاح خاصی صدا می‌کنید الزامی نمی‌کند که همه هم همان کار را می‌کنند. چند ثانیه بیشتر برای نوشتن زمان بگذارید ارزشش را دارد. «کتاب ریاضیات گسسته و ترکیبیاتی، نوشتهٔ رالف گریمالدی، ترجمهٔ محمدعلی رضوان و بیژن شمس، انتشارات فاطمی، ویرایش سوم، جلد اول، مثال ۳۴.۱» روی علامت مدادشکل زیر پرسش‌تان کلیک کنید و این تصحیح را اعمال کنید.
۳- عنوان پرسش‌تان هیچ جور به ذهن خواننده نمی‌رساند که هدف اصلی پرسش‌تان دقیقا چه بوده‌است!

این سه مورد را اعمال کنید. نگران زمانی که صرف می‌کنید نباشید، چون پاسخ‌دهنده‌ها بیشتر از زمانی که شما برای نوشتن پرسش‌تان می‌کنید، برای نوشتن پاسخ‌هایتان صرف می‌کنند!
و اما پاسخِ پرسش شما. به `for`های نوشته شده در کُد برنامه دقت کنید!

---

ممنون از این به بعد حتما حواسم به مواردی که گفتید هست.

حلقه های for نوشته شده در برنامه مربوط به صورت سوال هستند و متوجه شدم که این شرط باید درشون برقرار باشه. چیزی که متوجه نشدم این بود که بنظر میرسد با وجود این شرط تفاوتی در فرمول اصلی ایجاد نشده و میخواستم بدونم چطور از شمارش مواردی مثل

i = 10, j = 12, k = 14

پرهیز شده.

---

@Saturn ویرایش را انجام دهید تا برایتان پاسخ را قرار دهم. چرا از دفعه‌های بعد؟ همین زمانی که برای تایپ دیدگاه گذاشتید را می‌توانستید برای کپی-پیست کردن چیزی که به عنوان مرجع برایتان نوشتن در قسمت مرجع پرسش و همینطور یک دستی کشیدن به عنوان و متن پرسش صرف کنید، نه؟
 برگردیم به دیدگاه‌تان. چطور هیچ تغییری در حاصل ایجاد نمی‌کند؟ برای نمونه در `for`-ِ دومی امتحان کردید که اگر کران بالا به جای $i$، عدد ۲۰ باشد آیا حاصل یکی می‌شود؟ مشکل شما در متوجه شدن دستور `for` است و گر نه از روی همان کران‌های حلقه مشخص است که چرا مثالی که گفتید شمرده نشده است.

---

ویرایش انجام شد.
من دو ساله برنامه نویسی کار میکنم. دیروز حلقه رو یاد نگرفتم که مشکل به این پایه ای داشته باشم. من کاری که میگفتید انجام دادم اگه میشه شما هم به توضیحاتی که الان از فهم خودم میدم گوش بدید و یه یاری برسونید.
فهم من از فرمول انتخاب با تکرار اینه: سه عدد میخوایم انتخاب کنیم (i j k) و جوری که توی فرمول پاسخ مثال قرار داده شده رنج این اعداد از 1 تا 20 هست. پس از بین 20 انتخاب میخوایم سه عدد با تکرار انتخاب کنیم. اگر این فرمول رو اعمال کنیم مواردی از قبیل

i = 10, j = 12, k = 14

نیز انتخاب میشوند زیرا در رنج 1 تا 20 قرار دارند. این شمارش رو امتحان کردم و صحیح هست پس چطور این موارد توسط فرمول شمرده نشدند؟

اگر متوجه شده باشید سوال من راجع به نحوه اعمال شرط هست نه اینکه شرط از کجا آمده

---

@Saturn همین هست که نحوهٔ نوشتن پرسش مهم می‌شود. چیزی که نوشته بودید این حس را می‌داد که با نحوهٔ کار چرخه‌های `for` مشکل دارید ولی دیدگاه آخرتان در مورد نحوهٔ محاسبهٔ تعداد حالت‌ها است. تعداد حالت‌ها وقتی کران بالای `for`ها را محدود به اندیس‌های قبلی نکنیم و همه را ۲۰ بگذاریم با فرمول ترکیب محاسبه نمی‌شود. در این حالت تعداد حالت‌ها $20^3$ می‌شود.

Answer 1

توجه کنید که یک دستورِ for در برنامه‌نویسی دارای چند بخش است.

• یک اندیس، برای نمونه i که یک متغیر است که در چرخهٔ for قرار است شمارهٔ گام‌های چرخه را کنترل کنید.
• یک مقدار آغازین که اندیسِ چرخه از این گام شروع می‌کند، برای نمونه 1.
• اندازهٔ هر گام یا به عبارتی طول پرش بین گام‌ها، برای نمونه 1.
• مقدار پایانی برای اندیسِ چرخه که بیشتر از این گام ادامه ندهد، برای نمونه 10.

پس اگر چرخهٔ ما با مشخصاتی که در بالا برای نمونه ذکر کنیم تعریف شده‌باشد آنگاه یک متغیر $i$ به وجود می‌آید و برنامه شروع می‌کند به ترتیب به آن مقدارهای ۱ سپس ۲ سپس ۳ سپس ۴ سپس ... سپس ۹ سپس ۱۰ می‌دهد و بعد از ۱۰ دیگر مقدار نمی‌دهد و از چرخه بیرون می‌آید. در نرم‌افزار Maple به این شکل این چرخه را می‌نویسیم:

for i from 1 by 1 to 10 do
...;
end do;

که به جای سه‌نقطه دستور کارهایی که در این چرخه قرار است رخ بدهند را می‌نویسیم. جلوی for نام اندیس، جلوی from مقدار آغازین، جلوی by درازای پرش بین گام‌ها، جلوی to مقدار پایانی را می‌نویسیم. در زبان برنامه‌نویسی Python به شکل زیر می‌نویسیم:

for i in range(1,11,1):
    ...

در پایتون باید دقت کنید که به جای رفتن تا خود مقدار پایانی به یک واحد پیش از مقدار پایانی خاتمه می‌دهد برای همین به جای ۱۰ از ۱۱ استفاده کردیم. در زبان برنامه‌نویسی Pascal هم ساختار یکسان است ولی یک بخش کمتر دارد، و آن هم اندازهٔ پرش گام‌ها است. یعنی شما باید همیشه به یاد داشته باشید که زمانی که یک چرخه در پاسکال با for می‌سازید اندازه فاصلهٔ بین گام‌ها همیشه ۱ واحد است (برای درازای پرش متفاوت باید از ترفندهای دیگر استفاده کنید). پس for-ِ ما که با پایتون و میپل نوشته‌بودیم در پاسکال به شکل زیر می‌شود.

for i := 1 to 10 do
    ...;

اگر می‌خواهید برنامهٔ پاسکالی را بدون نصب چیزی بر روی رایانه امتحان کنید می‌توانید از برخی سایت‌های اینترنتی کمک بگیرید. برای نمونه https://www.tutorialspoint.com/compile_pascal_online.php ممکن است سایت‌های بهتری هم باشند که با جستجو می‌توانید بیابید. فرض کنید می‌خواهید مقدارهای داخل $i$ در هر مرحله از چرخهٔ بالا را بر روی صفحهٔ خروجی نمایش دهید. پس در صفحهٔ اجراکنندهٔ برخط همه چیز را پاک کنید و متن کُدِ زیر را در این بگذارید. سپس بر روی Execute کلیک کنید.

program Test;
var
i : integer;
begin
For i := 1 to 10 do
    writeln(i)
end.

نتیجه مانند شکل زیر خواهدبود.

در هر خط از خروجی مقدار $i$ در گام متناظرش نمایش داده شده‌است. اکنون که با ساختارِ چرخهٔ for آشنا شدیم به سراغ کد آمده در پرسش شما برویم.

program Test;
var
i : integer;
j : integer;
k : integer;
begin
For i := 1 to 20 do
    For j := 1 to i do
        For k := 1 to j do
            writeln(i*j+k)
end.

خب، پرسش چیست؟ این است که چه سه‌تایی‌هایِ $(i,j,k)$ای اجرا می‌شوند. بیاییم این چرخه‌های for را مانند متن عادی بخوانیم. می‌گوید؛

• اندیس $i$ از ۱ یک واحد یک واحد تا ۲۰ بیفزا.
• اندیس $j$ را از ۱ یک واحد یک واحد تا مقدار $i$ بیفزا.
• اندیس $k$ را از ۱ یک واحد یک واحد تا مقدار $k$ بیفزا.

پس مقدارهای $j$ در هر مرحله از بالا به مقدار $i$ای که در آن مرحله است کران‌دار است یعنی اگر در مرحله‌ای دارید $i=5$ آنگاه در آن مرحله $j$ فقط عددهای طبیعی بین ۱ تا ۵ است. در مثالی که خودتان در دیدگاه زیر پرسش‌تان پرسیدید نوشته‌اید چطوری $(i,j,k)=(10,12,14)$ شمرده نشده‌است، خب در این سه‌تایی که نام بردید مقدارِ $i$ چند است؟ ۱۰، اکنون مقدار $j$ چند است؟ ۱۲. به نظرتان آیا $j=12$ در شرطِ $1\leq j\leq i$ که توسطِ چرخهٔ for-ِ دوم‌تان در برنامه نوشته‌شده‌است صدق می‌کند؟ خیر. پس در این برنامه این سه‌تایی تولید نمی‌شود.

در پرسش هم گفته‌بودید که در خروجی تفاوتی ایجاد نمی‌شود. برای اینکه کل خروجی را در یک نگاه بتوانید ببینید، خیلی ساده بیایید دو برنامهٔ کوتاهِ زیر را اجرا کنید.

program Test;
var
i : integer;
j : integer;
begin
For i := 1 to 2 do
    For j := 1 to 2 do
        writeln(i,j)
end.

و

program Test;
var
i : integer;
j : integer;
begin
For i := 1 to 2 do
    For j := 1 to i do
        writeln(i,j)
end.

تصویر دو خروجی را در اینجا قرار دادیم. چه فرقی بین دو خروجی قرار دارد؟ در یکُمی شما هر چهار حالتِ

$$\lbrace (1,1),(1,2),(2,1),(2,2)\rbrace$$

را دارید ولی در دومی عضو دوم مجموعهٔ بالا را ندارید چون در شرطِ $1\leq j\leq i$ صدق نمی‌کند. پس در هنگام نوشتن یا خواندن forها به کران‌های پائین و بالای آنها توجه کنید.

---

افزوده‌شده پس از دیدگاه‌های جدید پرسش‌کننده:

فرض کنیم که شما به این که فرمول $\binom{n+3-1}{3}$ در حال دادن سه‌تایی‌های مرتب از بین عددهای ۱ تا ۲۰ و فقط شمردن جفت‌های افزایشی (نه الزاما اکید) است، شک دارید. بیاییم این مطلب را ثابت کنیم. پیش از این کار به یاد آورید که تعداد دوتایی‌های $(i,j)$ که $i$ و $j$ بین ۱ تا $n$ هستند و باید به شکل $(i,i)$ باشند یا از بین $(i,j)$ و $(j,i)$ که $i\neq j$ تنها یکی شمرده شود، با فرمول $\binom{n+2-1}{2}$ که همان $\frac{n(n+1)}{2}$ است شمرده می‌شد. چگونه به این فرمول می‌رسیدیم؟ می‌گفتیم دو حالت داریم: یا دو عضو متمایز انتخاب می‌کنیم که به $\binom{n}{2}$ حالت ممکن بود سپس به ۱ حالت آن دو را می‌چیندیم، پس $\binom{n}{2}\times 1$. یا از طرفی هر دو می‌توانند تکراری باشند که برابر با انتخاب ۱ عضو است و تکرار آن پس به $\binom{n}{1}$ حالت. پس در کل می‌شد $\binom{n}{2}+\binom{n}{1}$ که پس از ساده‌سازی با $\binom{n+1}{2}$ یکسان می‌شد.

در اینجا هم از همین روش استفاده کنید. تعداد سه‌تایی‌های $i\leq j\leq k$ که $i$ و $j$ و $k$ بین ۱ تا $n$ باشند برابر با جمع سه حالت است:

1. سه تا متمایز برداریم و مرتب بچینیم.
2. دو تا متمایز برداریم، یکی را دوبار تکرار کنیم و سپس مرتب بچینیم.
3. یکی برداریم، آن را سه بار تکرار کنیم.

تعداد حالت‌های انتخاب نخست برابر با $\binom{n}{3}$ است. توجه کنید که در فرمول ترکیب $\binom{n}{m}$ جایگشت‌های متفاوت عضوهای انتخاب‌شده حذف شده‌اند! یعنی انتخاب $1,2,3$ و $2,1,3$ خودبه‌خود یک‌بار شمرده‌شده‌است. چرا؟ چون انتخاب ۱ عضو از $n$ می‌شود $n$ حالت، انتخاب ۱ عضو از $n-1$ باقیمانده می‌شود $n-1$ تا به $n-m$. پس $n(n-1)...(n-m+1)=\frac{n!}{(n-m)!}$ تا حالت انتخاب $m$ تا عضو متفاوت ولی با چینِشِ‌های دلخواه داریم. این $m$ عضو به $m!$ حالت می‌توانند چینده شوند پس باید تقسیم شود ولی در اینصورت حاصل چیزی نیست به جز $\frac{n!}{(n-m)!m!}$ که خب همان $\binom{n}{m}$ است. پس در اینجا $\binom{n}{3}$ نیاز به ضرب و تقسیم در چیزی ندارد.

تعداد حالت‌های انتخاب دوم برابر با $\binom{n}{2}$ است. توجه کنید که این دو عضو ترتیب‌شان قبلا در فرمول ترکیب یک بار شمرده است. و عضو تکراری هم باید دقیقا کنار عضو همتایش بیاید پس مکانش ثابت است، ولی توجه کنید که مثلا اگر ۱ و ۲ انتخاب شده‌اند، هم می‌توانیم ۱ را تکرار کنیم یعنی $(1,1,2)$ و هم ۲ را یعنی $(1,2,2)$. پس هر حالت باید ضرب در ۲ شود. پس $\binom{n}{2}\times 2$.

تعداد حالت‌های انتخاب سوم نیز برابر است با $\binom{n}{1}$ که کار خاصی بعدش نیاز نیست.

در نتیجه پاسخ نهایی جمع این سه مقدار است که در زیر شروع به ساده‌سازی‌اش می‌کنیم.

$$\begin{align} \binom{n}{3}+2\binom{n}{2}+\binom{n}{1} &= \frac{n!}{(n-3)!3!}+2\frac{n!}{(n-2)!2!}+\frac{n!}{(n-1)!1!}\\ &= \frac{n!}{(n-1)!3!}(\frac{(n-1)(n-2)}{1}+\frac{2(3)(n-1)}{1}+\frac{3!}{1})\\ &= \frac{n!}{(n+2-3)!3!}((n-1)(n-2)+6(n-1)+6)\\ &= \frac{n!}{(n+2-3)!3!}(n^2-3n+2+6n-6+6)\\ &= \frac{n!}{(n+2-3)!3!}(n^2+3n+2)\\ &= \frac{n!(n+1)(n+2)}{(n+2-3)!3!}\\ &= \frac{(n+2)!}{(n+2-3)!3!}\\ &= \binom{n+2}{3}\\ &= \binom{n+3-1}{3} \end{align}$$

پس دیگر جای شکی نیست که فرمول $\binom{20+3-1}{3}$ تعداد گام‌های چرخهٔ سه‌گانهٔ آمده در کد است.

---

Comments

من تسلیم میشم. ممنون از توضیحات زیادتون ولی بازم متوجه مشکل من نشدید. مشکل من اینه که فرمول این عدد رو میشمره نه اینکه برنامه این مورد رو قبول میکنه یا نه. من توی برنامه نویسیش یا خروجیش مشکلی ندارم و مشکلم این نیست که چرا برنامه مقدار

i = 10, j = 12, k = 14

رو قبول نمیکنه و این برام بدیهیه. مشکلم توی شمارش هست. چون فکر میکنم فرمول به اشتباه این مقدار رو میشمره. سوال من در حقیقت مربوط به گسسته هست نه برنامه نویسی.

---

@Saturn کدام فرمول چه چیزی را می‌شمارد؟ فرمول $\binom{20+3-1}{3}$ تعداد سه‌تایی‌های برنامه با شرط $1\leq i\leq j\leq k\leq 20$ را می‌شمارد. هیچ مشکلی در این نیست. اگر هم شرط‌ها را به شکل دیگری بنویسید یعنی $1\leq i,j,k\leq 20$ آنگاه تعداد سه‌تایی‌ها برابر با $20^3$ می‌شود.