# গোনার আগে সম্ভাবনাগুলো দেখা

## দুটি জিনিস: subset-এর সব শাখা

```mermaid
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-এ ডানে বা নিচে গিয়ে পথ গোনা

```dsa
kind: grid
title: "প্রতিটি ঘরে পৌঁছানোর পথের সংখ্যা"
steps:
  - label: "ওপরের বাঁ কোণা থেকে নিচের ডান কোণা"
    rows: [[1, 1, 1], [1, 2, 3]]
    active: [[1, 2]]
    note: "শেষ ঘরের 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: ওপরের দুই ঘরের যোগ

```dsa
kind: array
title: "Pascal triangle-এর প্রথম পাঁচটি row"
steps:
  - label: "Row 0"
    values: [1]
    indices: false
    note: "প্রতিটি row-এর দুই প্রান্তে 1 থাকে।"
  - label: "Row 1"
    values: [1, 1]
    indices: false
  - label: "Row 2"
    values: [1, 2, 1]
    indices: false
  - label: "Row 3"
    values: [1, 3, 3, 1]
    indices: false
    active: [1, 2]
    note: "এই দুইটি 3 পরের row-এর মাঝের ঘর তৈরি করে।"
  - label: "Row 4"
    values: [1, 4, 6, 4, 1]
    indices: false
    active: [2]
    note: "মাঝের 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টি আলাদা বাক্স

```dsa
kind: array
title: "একই 5টি জিনিসের তিনটি সম্ভাব্য বণ্টন"
steps:
  - label: "প্রথম বণ্টন: (2, 3, 0)"
    values: ["★", "★", "|", "★", "★", "★", "|"]
    indices: false
    active: [2, 6]
    note: "★ একটি জিনিস; | দুটি দলের সীমানা। শেষ সীমানার পরে কিছু নেই, তাই তৃতীয় বাক্স খালি।"
  - label: "দ্বিতীয় বণ্টন: (0, 2, 3)"
    values: ["|", "★", "★", "|", "★", "★", "★"]
    indices: false
    active: [0, 3]
    note: "শুরুতেই সীমানা, তাই প্রথম বাক্স খালি। বাক্সগুলোর পরিচয় আলাদা।"
  - label: "তৃতীয় বণ্টন: (1, 1, 3)"
    values: ["★", "|", "★", "|", "★", "★", "★"]
    indices: false
    active: [1, 3]
    note: "তিনটি দলে 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 যুক্তি; কোন খোপ সেটি জানার দরকার নেই।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)