গোনার আগে সম্ভাবনাগুলো দেখা¶
দুটি জিনিস: subset-এর সব শাখা¶
flowchart TD
R["শুরু: খালি set"] -->|"A নিই না"| X["খালি"]
R -->|"A নিই"| Y["A"]
X -->|"B নিই না"| E["খালি set"]
X -->|"B নিই"| B["B"]
Y -->|"B নিই না"| A["A"]
Y -->|"B নিই"| AB["A, B"]দুটি স্বাধীন yes/no সিদ্ধান্তে 2²=4টি subset। এখানে একটি leaf-ও বাদ দেওয়া হয়নি।
Permutation ও combination-এর পার্থক্য¶
| A,B,C থেকে দুজন | সব উত্তর | সংখ্যা |
|---|---|---|
| প্রথম ও দ্বিতীয় পদ আলাদা | AB, AC, BA, BC, CA, CB | 6 |
| শুধু দল বাছাই | {A,B}, {A,C}, {B,C} | 3 |
প্রতি দলকে 2! উপায়ে সাজানো যায়। তাই C(3,2)=P(3,2)/2!=3।
2×3 grid-এ ডানে বা নিচে গিয়ে পথ গোনা¶
ওপরের বাঁ কোণা থেকে নিচের ডান কোণা
11112চিহ্নিত ঘর: 3শেষ ঘরের 3 = ওপরের 1 + বাঁয়ের 2। কেবল ডানে বা নিচে যাওয়া যায়।
ওপরের বাঁ কোণা start। প্রতিটি ঘরে পৌঁছানোর সংখ্যা = ওপরের ঘর + বাঁয়ের ঘর। শেষের 3টি পথ হলো RRD, RDR, DRR। এখানে বাধা নেই; obstacle থাকলে সেই ঘরের count 0 ধরতে হবে।
একই জিনিস দুবার গুনলে¶
1–10-এর মধ্যে 2-এর গুণিতক: {2,4,6,8,10}; 3-এর গুণিতক: {3,6,9}। দুটি তালিকা যোগ করলে 6 দুবার আসে। তাই অন্তত একটি দিয়ে বিভাজ্য সংখ্যা 5+3-1=7টি। এটিই inclusion–exclusion-এর প্রথম ধাপ।
Pascal triangle: ওপরের দুই ঘরের যোগ¶
Row 0
1প্রতিটি row-এর দুই প্রান্তে 1 থাকে।
Row 1
11Row 2
121Row 3
1চিহ্নিত ঘর: 3চিহ্নিত ঘর: 31এই দুইটি 3 পরের row-এর মাঝের ঘর তৈরি করে।
Row 4
14চিহ্নিত ঘর: 641মাঝের 6 = আগের row-এর 3 + 3।
শূন্য-ভিত্তিক row 4, column 2-তে 6: C(4,2)=C(3,1)+C(3,2)=3+3। চারজনকে চারটি আলাদা পদে বসানোর factorial count 4×3×2×1=24।
Stars and bars: 5টি একই জিনিস, 3টি আলাদা বাক্স¶
প্রথম বণ্টন: (2, 3, 0)
★★চিহ্নিত ঘর: |★★★চিহ্নিত ঘর: |★ একটি জিনিস; | দুটি দলের সীমানা। শেষ সীমানার পরে কিছু নেই, তাই তৃতীয় বাক্স খালি।
দ্বিতীয় বণ্টন: (0, 2, 3)
চিহ্নিত ঘর: |★★চিহ্নিত ঘর: |★★★শুরুতেই সীমানা, তাই প্রথম বাক্স খালি। বাক্সগুলোর পরিচয় আলাদা।
তৃতীয় বণ্টন: (1, 1, 3)
★চিহ্নিত ঘর: |★চিহ্নিত ঘর: |★★★তিনটি দলে 1, 1 ও 3টি জিনিস। প্রতিবার একই 7টি স্থানে দুটি সীমানা বসিয়েছি।
5টি star ও 2টি separator-এর মোট 7টি স্থানে separator-এর জায়গা বাছি: C(7,2)=21। পরপর separator বা শুরু/শেষে separator খালি বাক্স বোঝায়।
Derangement ও pigeonhole¶
তিনজনের টুপি কারও নিজের কাছে না গেলে মাত্র দুটি বিন্যাস: (A→B, B→C, C→A) এবং (A→C, C→B, B→A)।
4টি জিনিস 3টি খোপে রাখলে প্রত্যেক খোপে সর্বোচ্চ 1টি ধরে মোট রাখা যেত 3টি। চতুর্থটি রাখলেই কোনো খোপে অন্তত 2টি হবে—এটাই pigeonhole যুক্তি; কোন খোপ সেটি জানার দরকার নেই।