গণনার মূল নিয়ম — যোগ, গুণ, বিয়োগ আর ভাগ

১ · গোনার প্রশ্ন সবখানে — বাজারঘরের চারটি সমস্যা

কাল্পনিক অনলাইন দোকান বাজারঘরের প্রযুক্তি দল এক সকালে চারটি প্রশ্ন নিয়ে বসেছে। প্রথম প্রশ্ন: কুপন কোডে দুটি ইংরেজি বড় হাতের অক্ষর আর চারটি অঙ্ক থাকলে মোট কতগুলো আলাদা কুপন বানানো যায়, আর তা কি এক বছরের প্রচারণার জন্য যথেষ্ট? দ্বিতীয় প্রশ্ন: password-এর দৈর্ঘ্য ৬ থেকে ৮, আর তাতে অন্তত একটি অঙ্ক থাকতে হবে; এমন password কয়টি? তৃতীয় প্রশ্ন: বার্ষিক সভায় ৬ জন বিভাগীয় প্রধান একটি গোল টেবিলে বসবেন; কত রকম বসার ব্যবস্থা আসলে আলাদা? চতুর্থ প্রশ্ন: অর্ডার মেলানোর একটি প্রোগ্রামে দুটি nested loop আছে; n = 10,000 অর্ডারে ভেতরের লাইনটি কতবার চলবে?

চারটি প্রশ্নের মূলে একটিই কাজ: একটি সসীম সেটের উপাদান গোনা, তালিকা না বানিয়ে, কারণ উপাদান লাখ বা কোটির ঘরে। গণিতের যে শাখা এমন সেটের আকার বের করে, তার নাম combinatorics, বাংলায় সমাবেশবিদ্যা বা গণনাতত্ত্ব। এই মডিউলের সাতটি পর্ব তার মূল হাতিয়ার শেখাবে, আর পর্ব ৩৮ “বিচ্ছিন্ন সম্ভাবনা — sample space, event আর Laplace-এর সংজ্ঞা” থেকে সম্ভাবনা পুরোটাই এই গণনার ওপর দাঁড়াবে।

ভিত্তি আগেই তৈরি। পর্ব ১৪-এ দেখেছেন সসীম সেটের cardinality |A| মানে উপাদানের সংখ্যা, |A × B| = |A| · |B|, আর power set-এ 2ⁿটি subset. পর্ব ১৫-এ প্রমাণ হয়েছে |A ∪ B| = |A| + |B| − |A ∩ B|, আর পর্ব ১৬-এ গোনা হয়েছে n^mটি ফাংশন। এখানে এই তথ্যগুলোকে চারটি সাধারণ নিয়মে গুছিয়ে নেব: যোগ, গুণ, বিয়োগ আর ভাগ।

ছবির ওপরের দুটি বাক্স একে অপরকে ছোঁয় না: কোনো রাইডার দুই হাবে নেই, তাই কাউকে দুবার গোনার ভয় নেই। নিচের অংশ হলো Cartesian product {D1, D2, D3} × {C1, C2, C3, C4}: প্রতিটি সারি একজন ঢাকার রাইডার, প্রতিটি কলাম একজন চট্টগ্রামের, আর প্রতিটি বিন্দু একটি জোড়া। ছক আয়তাকার বলেই গুণ খাটে: প্রতিটি সারিতে সমান সংখ্যক বিন্দু।

২ · যোগের নিয়ম — “অথবা” মানে আলাদা আলাদা ভাগ

প্রথমে কাজের ভাষায় নিয়মটি বলি, তারপর সেটের ভাষায় নিখুঁত করি। একটি কাজ দুই ভাবে করা যায়: প্রথম ভাবে n₁ উপায়ে, দ্বিতীয় ভাবে n₂ উপায়ে, আর কোনো উপায় দুই দলেই পড়ে না। তাহলে কাজটি n₁ + n₂ উপায়ে করা যায়। এটিই যোগের নিয়ম (sum rule). “কোনো উপায় দুই দলেই পড়ে না” শর্তটি নিয়মের প্রাণ; এটি বাদ দিলে নিয়মটি মিথ্যা।

এখানে ∪ হলো union (যেকোনো একটিতে আছে এমন সব উপাদান), আর ∩ হলো intersection (দুটিতেই আছে এমন উপাদান)। প্রমাণ m-এর ওপর পর্ব ১০-এর mathematical induction দিয়ে, আর ভিত্তি হিসেবে পর্ব ১৫-এর দুই সেটের সূত্র।

প্রমাণ: P(m) বিবৃতিটি হলো “যেকোনো m-টি জোড়ায় জোড়ায় বিচ্ছিন্ন সসীম সেটের জন্য সূত্রটি সত্য”।

1. ভিত্তি, m = 1: |A₁| = |A₁|, কিছু প্রমাণের নেই। — সরাসরি
2. m = 2: পর্ব ১৫-এর উপপাদ্য ৩.১ অনুযায়ী |A₁ ∪ A₂| = |A₁| + |A₂| − |A₁ ∩ A₂|, আর বিচ্ছিন্ন বলে |A₁ ∩ A₂| = |∅| = 0. — দুই সেটের inclusion–exclusion
3. ধাপ: ধরি P(m) সত্য, আর A₁, …, A_m+1 জোড়ায় জোড়ায় বিচ্ছিন্ন। লিখি B = A₁ ∪ ⋯ ∪ A_m. — inductive hypothesis
4. B ∩ A_m+1 = (A₁ ∩ A_m+1) ∪ ⋯ ∪ (A_m ∩ A_m+1) = ∅ ∪ ⋯ ∪ ∅ = ∅. — distributive law, পর্ব ১৫
5. তাই m = 2-এর ক্ষেত্র থেকে |B ∪ A_m+1| = |B| + |A_m+1|, আর P(m) থেকে |B| = |A₁| + ⋯ + |A_m|. দুটি মিলিয়ে P(m + 1). ∎ — বসানো

কাজের রূপে “প্রথম ভাবে করার সব উপায়” হলো A₁, “দ্বিতীয় ভাবে” A₂, আর কোনো উপায় দুই দলে না পড়া মানে A₁ ∩ A₂ = ∅.

কয়েকটি উদাহরণ

• রাইডার বাছাই: জরুরি একটি পার্সেল ঢাকার ৩ জন অথবা চট্টগ্রামের ৪ জন রাইডারের যেকোনো একজন নিতে পারেন। কেউ দুই হাবে নেই, তাই 3 + 4 = 7.
• বিভিন্ন দৈর্ঘ্যের কোড: একটি string একসঙ্গে দুই দৈর্ঘ্যের হতে পারে না, তাই দৈর্ঘ্য অনুযায়ী ভাগ সবসময় বিচ্ছিন্ন। password গোনায় ঠিক এটিই করব।

৩ · গুণের নিয়ম — “এবং তারপর” মানে ধাপে ধাপে বাছাই

বাজারঘরের কুপন কোডের গঠন LLDDDD: প্রথম দুটি ঘরে A থেকে Z-এর একটি অক্ষর, পরের চারটিতে 0 থেকে 9-এর একটি অঙ্ক। একটি কোড বানানো মানে ছয়টি ধাপে পরপর ছয়টি বাছাই। প্রথম ঘরের ২৬টি পছন্দের প্রতিটির সঙ্গে দ্বিতীয় ঘরের ২৬টি মেলে, তাই প্রথম দুই ঘরে 26 · 26 = 676টি জোড়া; প্রতিটির সঙ্গে আবার অঙ্কের ঘরগুলো। সব মিলিয়ে 26² · 10⁴ = 6,760,000টি কুপন।

প্রমাণ: m = 2-এর ক্ষেত্রটি পর্ব ১৪-এর উপপাদ্য ৫.২. এখানে সেটিকে যোগের নিয়ম থেকে আরেকবার দেখি, কারণ এই যুক্তিটিই গুণের নিয়মের আসল ব্যাখ্যা।

1. A × B = ⋃_{a ∈ A} ({a} × B): প্রতিটি জোড়া (a, b) ঠিক সেই অংশে পড়ে, যার প্রথম উপাদান a. — সংজ্ঞা
2. a ≠ a′ হলে {a} × B আর {a′} × B বিচ্ছিন্ন, কারণ তাদের জোড়াগুলোর প্রথম উপাদান আলাদা। — ordered pair-এর সমতা
3. প্রতিটি {a} × B-তে |B|টি উপাদান, কারণ b ↦ (a, b) একটি bijection. — পর্ব ১৬
4. যোগের নিয়মে |A × B| = |B| + |B| + ⋯ + |B| (|A| বার) = |A| · |B|. — উপপাদ্য ২.১
5. সাধারণ m: m-এর ওপর induction. (a₁, …, a_m+1) ↦ ((a₁, …, a_m), a_m+1) একটি bijection A₁ × ⋯ × A_m+1 → (A₁ × ⋯ × A_m) × A_m+1, তাই আকার সমান। m = 2-এর ক্ষেত্র আর inductive hypothesis মিলিয়ে |A₁| ⋯ |A_m| · |A_m+1|. ∎ — induction

ধাপ ৪ দেখায় গুণ আসলে সমান মাপের সারির বারবার যোগ। এ থেকেই কাজের ভাষার নিয়মটি আসে, যা সেটের রূপের চেয়ে একটু বেশি শক্তিশালী।

সূক্ষ্ম বিষয়টি খেয়াল করুন: পছন্দের সেট আগের বাছাইয়ের ওপর নির্ভর করতে পারে, কিন্তু পছন্দের সংখ্যা নয়। কুপনের দুটি অক্ষর আলাদা হতে হবে, এমন নিয়ম হলে প্রথম অক্ষরে ২৬টি পছন্দ, দ্বিতীয়টিতে ২৫টি; কোন ২৫টি, তা প্রথম অক্ষরের ওপর নির্ভর করে, কিন্তু সংখ্যা সবসময় ২৫. তাই 26 · 25 · 10⁴ = 6,500,000. ১৫ জনের ক্রিকেট স্কোয়াড থেকে অধিনায়ক আর সহ-অধিনায়ক বাছাইও তাই: 15 · 14 = 210. কিন্তু সংখ্যাও বদলালে, যেমন “দ্বিতীয় অক্ষর বর্ণমালায় প্রথমটির পরে”, সরল গুণ চলে না; তখন প্রথম অক্ষর অনুযায়ী ভাগ করে যোগ (25 + 24 + ⋯ + 0), অথবা §৫-এর tree diagram.

পুরোনো ফলাফল, নতুন চোখে

আগের মডিউলের তিনটি বিখ্যাত গণনা আসলে একই গুণের নিয়ম। প্রতিটির পেছনে একটি “প্রতিটি অবস্থানে একটি বাছাই” আছে।

শেষ সারিটি পর্ব ৩৩ “Permutation আর combination”-এর আগাম স্বাদ। subset আর bit string-এর উত্তর একই, কারণ দুটির মধ্যে একটি bijection আছে; “bijection থাকলে আকার সমান” নীতিটি পর্ব ৩৭ “গণনার কৌশল — lattice path, bijection আর double counting”-এ নিজস্ব নাম পাবে।

নিচের ব্লক একটি খেলনা কুপন-নিয়মে (অক্ষর A, B, C আর অঙ্ক 0, 1) itertools.product দিয়ে সব কোড বানিয়ে গোনে, তারপর আসল নিয়মে সূত্র দিয়ে হিসাব করে। product ঠিক Cartesian product বানায়, অর্থাৎ উপপাদ্য ৩.১-এর যন্ত্রচালিত রূপ। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
from string import ascii_uppercase, digits

# toy version: letters from {A,B,C}, digits from {0,1}: LLDD
toy = ["".join(t) for t in product("ABC", "ABC", "01", "01")]
print("toy codes:", len(toy), "formula 3*3*2*2 =", 3 * 3 * 2 * 2)
print("first five:", toy[:5])

# product rule: |A1 x A2 x A3 x A4 x A5 x A6| for LLDDDD
L, D = len(ascii_uppercase), len(digits)
print("real LLDDDD codes:", L**2 * D**4)

# letters must differ: still the same number of choices at each stage
pairs = sum(1 for a, b in product(ascii_uppercase, repeat=2) if a != b)
print("letters different:", pairs * D**4, "= 26*25*10^4 =", 26 * 25 * 10**4)

# sum rule: a code is 5 characters OR 6 characters (disjoint sets)
five = L * D**4       # LDDDD
six = L**2 * D**4     # LLDDDD
print("5-char or 6-char codes:", five + six)

# functions and subsets are the product rule again
funcs = list(product(range(4), repeat=3))   # f(a1), f(a2), f(a3) from 4 values
subsets = list(product((0, 1), repeat=5))   # in or out, for each of 5 elements
print("functions 3 -> 4:", len(funcs), "| subsets of a 5-set:", len(subsets))

toy codes: 36 formula 3*3*2*2 = 36
first five: ['AA00', 'AA01', 'AA10', 'AA11', 'AB00']
real LLDDDD codes: 6760000
letters different: 6500000 = 26*25*10^4 = 6500000
5-char or 6-char codes: 7020000
functions 3 -> 4: 64 | subsets of a 5-set: 32

৪ · বিয়োগের নিয়ম আর complement — বাজারঘরের password নীতি

দুই দলে মিল থাকলে যোগের নিয়ম মিলের অংশটি দুবার গোনে। সংশোধন সহজ: একবার বাদ দিন। এটিই বিয়োগের নিয়ম (subtraction rule), যাকে দুই সেটের inclusion–exclusion-ও বলে।

প্রমাণ পর্ব ১৫-এর উপপাদ্য ৩.১-এ আছে (A ∪ B-কে তিনটি বিচ্ছিন্ন অংশ A ∖ B, A ∩ B আর B ∖ A-তে ভেঙে যোগের নিয়ম)। তিন বা তার বেশি সেটের সাধারণ সূত্র, যেখানে চিহ্ন পালাক্রমে বদলায়, পর্ব ৪৯ “Inclusion–exclusion আর derangement”-এর বিষয়। এখানে একটি উদাহরণ: ৮ bit-এর কতগুলো string 1 দিয়ে শুরু অথবা 00 দিয়ে শেষ? A = “1 দিয়ে শুরু”, বাকি ৭টি ঘর মুক্ত, |A| = 2⁷ = 128. B = “00 দিয়ে শেষ”, বাকি ৬টি ঘর মুক্ত, |B| = 2⁶ = 64. A ∩ B-তে প্রথম ঘর আর শেষ দুই ঘর স্থির, |A ∩ B| = 2⁵ = 32. উত্তর 128 + 64 − 32 = 160.

Complement: উল্টো দিক থেকে গোনা

বিয়োগের নিয়মের সবচেয়ে কাজের রূপটি হলো complement rule. মহাবিশ্ব U-এর মধ্যে A-এর complement Ā = U ∖ A.

প্রমাণ:

1. U = A ∪ Ā, কারণ U-এর প্রতিটি উপাদান হয় A-তে, নয় A-এর বাইরে। — complement-এর সংজ্ঞা
2. A ∩ Ā = ∅, কারণ একটি উপাদান একসঙ্গে A-তে আর A-এর বাইরে থাকতে পারে না। — সংজ্ঞা
3. যোগের নিয়মে |U| = |A| + |Ā|, তাই |A| = |U| − |Ā|. ∎ — উপপাদ্য ২.১

এর কাজ কোথায়? যখন A-এর বর্ণনায় “অন্তত একটি” থাকে। “অন্তত একটি অঙ্ক” মানে একটি, দুটি, তিনটি, … অঙ্ক, আর প্রতিটিতে কোন ঘরে, তা নিয়ে উপ-ক্ষেত্র। কিন্তু complement “একটিও অঙ্ক নেই” মানে শুধু একটি সহজ শর্ত: প্রতিটি ঘরে একটি অক্ষর।

এবার বাজারঘরের নিয়ম। password-এ শুধু ছোট হাতের ইংরেজি অক্ষর (a–z, ২৬টি) আর অঙ্ক (0–9, ১০টি) চলে, মোট ৩৬টি চিহ্ন। দৈর্ঘ্য ৬, ৭ বা ৮, আর অন্তত একটি অঙ্ক থাকতে হবে। P_n দিয়ে n দৈর্ঘ্যের বৈধ password-এর সেট বোঝাই। দৈর্ঘ্য আলাদা হলে password আলাদা, তাই প্রথমে যোগের নিয়ম, তারপর প্রতিটি দৈর্ঘ্যে complement.

1P = P₆ ∪ P₇ ∪ P₈2|U₆| = 36⁶3|P₆| = 36⁶ − 26⁶4|P₇| = 36⁷ − 26⁷5|P₈| = 36⁸ − 26⁸6|P| = |P₆| + |P₇| + |P₈|

এত বড় সংখ্যা brute force করা যায় না, কিন্তু একই পদ্ধতি ছোট alphabet-এ মেলানো যায়। নিচের ব্লক a, b, c আর 0, 1 নিয়ে ২ থেকে ৪ দৈর্ঘ্যের সব string পরীক্ষা করে, আর একটি জনপ্রিয় ভুল পদ্ধতিও চালায়: “আগে অঙ্কের জন্য একটি ঘর বাছি (n উপায়), সেখানে একটি অঙ্ক বসাই (২ উপায়), বাকি ঘর যা খুশি (5ⁿ⁻¹)”.

from itertools import product

letters, digs = "abc", "01"           # toy alphabet: 3 letters + 2 digits
alpha = letters + digs

def has_digit(w):
    return any(ch in digs for ch in w)

total = 0
for n in range(2, 5):                 # lengths 2, 3, 4 (sum rule over lengths)
    brute = sum(1 for w in product(alpha, repeat=n) if has_digit(w))
    formula = len(alpha)**n - len(letters)**n      # all minus 'no digit'
    wrong = n * len(digs) * len(alpha)**(n - 1)    # 'pick the digit spot' method
    print(f"n={n}: brute {brute}, complement {formula}, wrong {wrong}")
    total += brute
print("toy policy total:", total)

# the Bazarghar rule: a-z and 0-9, length 6..8, at least one digit
real = sum(36**n - 26**n for n in (6, 7, 8))
print("real policy:", real, f"(about {real:.2e})")

# why 'wrong' overcounts: a string with two digits is counted twice
w = ("0", "1")
spots = [i for i, ch in enumerate(w) if ch in digs]
print(w, "is counted", len(spots), "times by the wrong method")

n=2: brute 16, complement 16, wrong 20
n=3: brute 98, complement 98, wrong 150
n=4: brute 544, complement 544, wrong 1000
toy policy total: 658
real policy: 2684483063360 (about 2.68e+12)
('0', '1') is counted 2 times by the wrong method

এই সংখ্যা নিরাপত্তার পূর্ণ মাপ নয়, কারণ মানুষ সব password সমান সম্ভাবনায় বাছেন না। ব্যবহারিক দিক Cybersecurity কোর্সের পর্ব ১৫ আর পর্ব ১৩-এ।

৫ · Tree diagram — যখন পরের পছন্দ আগের পছন্দের ওপর নির্ভর করে

গুণের নিয়মের শর্ত ছিল প্রতিটি ধাপে পছন্দের সংখ্যা স্থির। শর্তটি না খাটলে একটি নির্ভরযোগ্য বিকল্প হলো tree diagram: শিকড় থেকে শুরু করে প্রতিটি সম্ভাব্য পছন্দের জন্য একটি শাখা আঁকুন, আর প্রতিটি শাখার শেষ থেকে পরের ধাপের শাখা। শিকড় থেকে একটি পাতা (leaf) পর্যন্ত প্রতিটি পথ ঠিক একটি সম্পূর্ণ ফল, তাই উত্তর হলো পাতার সংখ্যা। অবৈধ শাখা শুরুতেই কেটে ফেলা যায়।

একটি উদাহরণ নিই। বাজারঘরের একটি গুদামের সেন্সর প্রতি ঘণ্টায় একটি bit পাঠায়: 0 মানে স্বাভাবিক, 1 মানে সতর্কতা। নিয়ম হলো পরপর দুটি সতর্কতা (অর্থাৎ “11”) এলে লাইন বন্ধ হয়। ৪ ঘণ্টায় লাইন চালু থাকে, এমন কতগুলো bit string সম্ভব? এখানে পছন্দের সংখ্যা স্থির নয়: শেষ bit 0 হলে পরেরটি 0 বা 1 (২টি পছন্দ), শেষ bit 1 হলে পরেরটি শুধু 0 (১টি)।

2, 3, 5, 8 কেন Fibonacci? n দৈর্ঘ্যের বৈধ string-এর সংখ্যা a_n ধরুন, আর শেষ bit অনুযায়ী বৈধ string-গুলোকে দুই বিচ্ছিন্ন দলে ভাগ করুন। শেষ bit 0 হলে সামনের অংশ যেকোনো বৈধ (n − 1) দৈর্ঘ্যের string: a_n−1টি। শেষ bit 1 হলে তার আগের bit অবশ্যই 0, অর্থাৎ শেষ দুই bit “01”, আর সামনের অংশ যেকোনো বৈধ (n − 2) দৈর্ঘ্যের string: a_n−2টি। যোগের নিয়মে a_n = a_n−1 + a_n−2, যেখানে a₁ = 2, a₂ = 3. এই কৌশলের পূর্ণ রূপ পর্ব ৪৪ “Recurrence দিয়ে মডেল — Fibonacci, Hanoi আর bit string”-এ; Fibonacci-র ধর্মগুলো পর্ব ১২-এ দেখেছেন।

Tree diagram ছোট সমস্যায় অসাধারণ, কারণ এটি কোনো শর্ত ভুলে যেতে দেয় না। ক্রিকেটের “best of three” সিরিজের কথা ভাবুন: যে দল আগে দুটি ম্যাচ জেতে, সিরিজ তার। দুই দল A আর B হলে সিরিজ কতভাবে শেষ হতে পারে? Tree আঁকলে পাতাগুলো AA, ABA, ABB, BAA, BAB, BB: মোট ৬টি। পথের দৈর্ঘ্যও আলাদা (২ বা ৩ ম্যাচ), যা সরল গুণে ধরা যায় না। অসুবিধা হলো tree দ্রুত বড় হয়; তখন তার গঠন থেকে recurrence বের করাই পথ।

৬ · ভাগের নিয়ম — k-to-1 ফাংশন আর গোল টেবিল

বার্ষিক সভার প্রশ্নে ফিরি। ৬ জন বিভাগীয় প্রধান (A থেকে F) একটি গোল টেবিলে বসবেন। দুটি ব্যবস্থাকে একই ধরা হয়, যদি প্রত্যেকের বাঁ পাশের আর ডান পাশের প্রতিবেশী একই থাকেন; অর্থাৎ সবাই মিলে এক চেয়ার ঘুরে বসলে নতুন ব্যবস্থা হয় না। চেয়ারে কোনো নম্বর নেই, শুধু কে কার পাশে, সেটিই গুরুত্বপূর্ণ।

সরাসরি গোনা কঠিন, কিন্তু একটি সহজ জিনিস গোনা সহজ: ৬ জনকে একটি সরলরেখায় সাজানো, 6! = 720 উপায়ে (factorial, গুণের নিয়মে 6 · 5 · 4 · 3 · 2 · 1). এখন প্রতিটি সারি থেকে একটি টেবিল-ব্যবস্থা পাওয়া যায়: সারির প্রথম জন একটি চেয়ারে, বাকিরা ঘড়ির কাঁটার দিকে পরপর। কিন্তু একই টেবিল একাধিক সারি থেকে আসে: যেখান থেকেই পড়া শুরু করুন, একই বৃত্ত। গোনার ভাষায় আমরা প্রতিটি টেবিল কয়েকবার গুনেছি। কতবার, সেটি জানা থাকলে ভাগ করলেই চলে।

প্রমাণ:

1. A = ⋃_{b ∈ B} f⁻¹(b), কারণ প্রতিটি a ঠিক একটি b = f(a)-এর preimage-এ পড়ে। — ফাংশনের সংজ্ঞা
2. b ≠ b′ হলে f⁻¹(b) ∩ f⁻¹(b′) = ∅, কারণ একটি a-এর দুটি আলাদা ছবি থাকতে পারে না। — ফাংশন well-defined
3. প্রতিটি f⁻¹(b)-এর আকার k, আর k ≥ 1 বলে প্রতিটি b-এর অন্তত একটি preimage আছে, তাই B-ও সসীম। — k-to-1-এর সংজ্ঞা
4. যোগের নিয়মে |A| = ∑_{b ∈ B} |f⁻¹(b)| = k · |B|, তাই |B| = |A| / k. ∎ — উপপাদ্য ২.১

এটি গুণের নিয়মের প্রমাণ উল্টো দিক থেকে পড়া। ভাগগুলো (preimage) একটি equivalence relation-এর শ্রেণি: “দুটি সারি একই টেবিল দেয়”. নিয়মটি খাটে ঠিক তখন, যখন প্রতিটি শ্রেণির আকার সমান।

1A = সারিতে সাজানো, |A| = 6!2f(সারি) = টেবিল-ব্যবস্থা3ABCDEF, BCDEFA, …, FABCDE4প্রতিটি টেবিলে ঠিক 6টি সারি5|B| = 720 / 6 = 1206যাচাই: A স্থির, বাকি 5! = 120

গোল টেবিলে এমন বসানোকে বলে circular permutation; পর্ব ৩৩-এ এটি permutation-এর একটি রূপ হিসেবে আবার আসবে। আয়নার প্রতিচ্ছবিও একই ধরলে (যেমন উল্টে দেওয়া যায় এমন মালা) n ≥ 3-এ শ্রেণি দ্বিগুণ বড়, উত্তর (n − 1)!/2; ৬ জনে 60. নিচের ব্লক n = 3 থেকে 7 পর্যন্ত সব সারিকে এমনভাবে ঘোরায় যাতে ব্যক্তি 0 সামনে আসে, সেই রূপ দিয়ে টেবিল আলাদা করে, আর প্রতিটি শ্রেণির আকার ছাপে।

from itertools import permutations
from math import factorial

def seat_class(p):                    # rotate so that person 0 comes first
    i = p.index(0)
    return p[i:] + p[:i]

for n in range(3, 8):
    classes = {}
    for p in permutations(range(n)):  # all n! straight-line orders
        classes.setdefault(seat_class(p), []).append(p)
    sizes = {len(v) for v in classes.values()}
    print(f"n={n}: line orders {factorial(n):4}, tables {len(classes):3}, "
          f"class sizes {sizes}, (n-1)! = {factorial(n - 1)}")

# when the division rule FAILS: 2 red + 2 blue beads on a ring
lines = set(permutations("RRBB"))
ring = {}
for w in lines:
    key = min("".join(w[i:] + w[:i]) for i in range(4))
    ring.setdefault(key, []).append("".join(w))
print("lines:", len(lines), "-> 6/4 =", len(lines) / 4)
for k, v in sorted(ring.items()):
    print(" ring", k, "has", len(v), "line forms:", sorted(v))

n=3: line orders    6, tables   2, class sizes {3}, (n-1)! = 2
n=4: line orders   24, tables   6, class sizes {4}, (n-1)! = 6
n=5: line orders  120, tables  24, class sizes {5}, (n-1)! = 24
n=6: line orders  720, tables 120, class sizes {6}, (n-1)! = 120
n=7: line orders 5040, tables 720, class sizes {7}, (n-1)! = 720
lines: 6 -> 6/4 = 1.5
 ring BBRR has 4 line forms: ['BBRR', 'BRRB', 'RBBR', 'RRBB']
 ring BRBR has 2 line forms: ['BRBR', 'RBRB']

সমান নয় এমন শ্রেণির সাধারণ সমাধান Burnside-এর lemma, যা ভাবনার প্রশ্ন ৩-এ সংক্ষেপে আর পর্ব ৫১ “Symmetry দিয়ে গণনা — Burnside-এর lemma আর Pólya”-তে বিস্তারিত আছে।

৭ · অ্যালগরিদমে গণনা — nested loop কতবার চলে

একটি nested loop মানে একটি loop-এর ভেতরে আরেকটি। ভেতরের লাইন কতবার চলে, তা গোনা মানে যে সব (i, j) জোড়ায় লাইনটি চলে, তাদের সেটের আকার বের করা। চারটি নিয়মই এখানে কাজে লাগে।

• গুণ: for i in range(n): for j in range(n) — জোড়ার সেট {0, …, n − 1} × {0, …, n − 1}, আকার n².
• যোগ: পরপর দুটি আলাদা loop, বা if/else-এর দুই শাখা, বিচ্ছিন্ন ঘটনা; ধাপের সংখ্যা যোগ হয়।
• ভাগ: for j in range(i + 1, n) শুধু i < j জোড়া নেয়। i ≠ j এমন ক্রমযুক্ত জোড়া গুণের নিয়মে n(n − 1)টি। প্রতিটি অক্রমিক জোড়া {i, j} ঠিক দুটি ক্রমযুক্ত জোড়া দেয় ((i, j) আর (j, i)), আর তার ঠিক একটিতে i < j. তাই 2-to-1 ফাংশনে ভাগের নিয়ম: n(n − 1)/2.
• তিন স্তর: i < j < k এমন triple. তিনটি আলাদা সংখ্যার ক্রমযুক্ত triple n(n − 1)(n − 2)টি, আর প্রতিটি সেট {i, j, k} তিনটি সংখ্যার 3! = 6টি ক্রমে আসে, যার ঠিক একটি ছোট থেকে বড়। তাই n(n − 1)(n − 2)/6.

শেষ দুটি সংখ্যা আসলে C(n, 2) আর C(n, 3), n-টি থেকে ২টি বা ৩টি বাছাইয়ের উপায়; পর্ব ৩৩-এ এদের পূর্ণ তত্ত্ব আর ভাগের নিয়ম দিয়েই প্রমাণ আসবে। নিচের ব্লক চারটি loop সত্যিই চালিয়ে গোনে আর math.comb-এর সঙ্গে মেলায়। চতুর্থ loop-এ একটি if/else আছে: জোড় i-তে ভেতরের loop n বার চলে, বিজোড় i-তে মাত্র একটি ধাপ।

from math import comb

def count_loops(n):
    a = b = c = d = 0
    for i in range(n):
        for j in range(n):
            a += 1                    # every ordered pair (i, j)
    for i in range(n):
        for j in range(i + 1, n):
            b += 1                    # pairs with i < j
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                c += 1                # triples i < j < k
    for i in range(n):
        if i % 2 == 0:
            for j in range(n):
                d += 1                # even i: the inner loop runs n times
        else:
            d += 1                    # odd i: a single step
    return a, b, c, d

for n in (4, 10, 20):
    a, b, c, d = count_loops(n)
    print(f"n={n}: n*n={a}, i<j: {b} (C(n,2)={comb(n, 2)}), "
          f"i<j<k: {c} (C(n,3)={comb(n, 3)}), if/else: {d}")

n=4: n*n=16, i<j: 6 (C(n,2)=6), i<j<k: 4 (C(n,3)=4), if/else: 10
n=10: n*n=100, i<j: 45 (C(n,2)=45), i<j<k: 120 (C(n,3)=120), if/else: 55
n=20: n*n=400, i<j: 190 (C(n,2)=190), i<j<k: 1140 (C(n,3)=1140), if/else: 210

i < j loop n = 10,000 অর্ডারে 49,995,000 বার চলে, n²-এর প্রায় অর্ধেক, তাই বৃদ্ধির হার এখনো দ্বিঘাত। Big-O দিয়ে এই বৃদ্ধি প্রকাশ আর তুলনা করা DSA কোর্সের পর্ব ০৪-এর বিষয়, আর হাতে loop গুনে উত্তর বের করার অনুশীলন DSA কোর্সের পর্ব ৬৮-এ। এখানকার ভূমিকা হলো সঠিক সংখ্যাটি দেওয়া; DSA সেটিকে বৃদ্ধির হারে রূপ দেয়।

সব সম্ভাব্য উত্তর পরীক্ষা করা (brute force) মানে পুরো search space ঘুরে দেখা, আর গুণের নিয়ম তার আকার বলে: n উপাদানের subset 2ⁿটি, ক্রম n!টি। n = 60-এ 2⁶⁰ ≈ 1.15 × 10¹⁸, সেকেন্ডে শত কোটি পরীক্ষাতেও কয়েক দশক। পর্ব ২৭-এর key space গোনাও এই একই প্রশ্ন ছিল।

৮ · সাধারণ ভুল, পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

গণনার প্রায় সব ভুল চার ধরনের। প্রতিটির একটি ছোট লক্ষণ আছে, যা দেখে সন্দেহ করা যায়।

এবার পরীক্ষার ধাঁচের চারটি অঙ্ক; প্রতিটি সংখ্যা scratch-এ brute force করে মেলানো।

অঙ্ক ১: 1 থেকে 1000-এর মধ্যে কতগুলো সংখ্যা 3 অথবা 5 দিয়ে বিভাজ্য?

1. A = 3-এর গুণিতক: ⌊1000/3⌋ = 333টি। B = 5-এর গুণিতক: ⌊1000/5⌋ = 200টি। এখানে ⌊x⌋ মানে x-এর চেয়ে বড় নয় এমন বৃহত্তম পূর্ণসংখ্যা।
2. A ∩ B = 3 আর 5 দুটি দিয়েই বিভাজ্য = 15-এর গুণিতক (3 আর 5 সহমৌলিক): ⌊1000/15⌋ = 66টি।
3. বিয়োগের নিয়মে 333 + 200 − 66 = 467.

অঙ্ক ২: ৪ অঙ্কের PIN-এ (0000 থেকে 9999) অন্তত একটি অঙ্ক পুনরাবৃত্ত হয়, এমন PIN কয়টি?

1. মোট PIN: প্রতিটি ঘরে ১০টি, 10⁴ = 10000.
2. Complement “সব অঙ্ক আলাদা”: 10 · 9 · 8 · 7 = 5040 (প্রতি ধাপে আগের অঙ্কগুলো বাদ, পছন্দের সংখ্যা স্থির)।
3. উত্তর 10000 − 5040 = 4960, প্রায় অর্ধেক PIN.

অঙ্ক ৩: 1 থেকে 999-এর মধ্যে কতগুলো সংখ্যার সব অঙ্ক আলাদা?

1. অঙ্কের সংখ্যা অনুযায়ী তিনটি বিচ্ছিন্ন দল (যোগের নিয়ম)।
2. ১ অঙ্ক: 1–9, ৯টি। ২ অঙ্ক: প্রথম অঙ্ক 0 হতে পারে না (৯টি), দ্বিতীয়টি প্রথমটি বাদে যেকোনো (৯টি, 0 সহ): 81.
3. ৩ অঙ্ক: 9 · 9 · 8 = 648. মোট 9 + 81 + 648 = 738.

অঙ্ক ৪: ১৫ জনের স্কোয়াড থেকে একজন অধিনায়ক আর একজন সহ-অধিনায়ক, আবার আলাদাভাবে দুজন ওপেনিং ব্যাটসম্যান। দুটি সংখ্যা কত?

1. অধিনায়ক ১৫ জনের যেকোনো একজন, সহ-অধিনায়ক বাকি ১৪ জনের একজন: 15 · 14 = 210. এখানে ক্রম গুরুত্বপূর্ণ, কারণ দুটি পদ আলাদা।
2. দুজন ওপেনারে পদের পার্থক্য নেই (ধরে নিচ্ছি কে প্রথম বল খেলবেন, তা আলাদা সিদ্ধান্ত)। ক্রমযুক্ত 210টি জোড়ার প্রতিটি অক্রমিক জোড়া দুবার আসে, তাই ভাগের নিয়মে 210/2 = 105.

প্রমাণের ভুল ধরুন: “আংটির রং গোনা”

একজন লিখলেন: “দাবি: ২টি লাল আর ২টি নীল পুঁতি দিয়ে একটি আংটি (শুধু ঘোরানো চলে) 6/4 = 1.5 উপায়ে বানানো যায়, তাই উত্তর ভগ্নাংশ বলে প্রশ্নটি ভুল। প্রমাণ: সারিতে সাজানো যায় ৬ উপায়ে (RRBB, RBRB, RBBR, BRRB, BRBR, BBRR). আংটি ৪ রকম ঘোরানো যায়, তাই প্রতিটি আংটি ৪টি সারি থেকে আসে। ভাগের নিয়মে 6/4. ∎” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: “প্রতিটি আংটি ৪টি সারি থেকে আসে” দাবিটি মিথ্যা, অথচ উপপাদ্য ৬.২-এর শর্ত (f হলো k-to-1, প্রতিটি preimage-এর আকার k) ঠিক এটিই চায়। RBRB-কে ২ ধাপ ঘোরালে আবার RBRB, তাই তার শ্রেণিতে মাত্র ২টি সারি (RBRB, BRBR). অন্য শ্রেণিতে ৪টি (RRBB, RBBR, BBRR, BRRB). 4 + 2 = 6, আর আংটি ২টি। একটি ভগ্নাংশ উত্তর সবসময় সংকেত দেয় যে কোনো নিয়মের শর্ত ভাঙা হয়েছে; প্রশ্ন নয়, প্রমাণটিই ভুল।

৯ · AI-এর যুগে — গণনার উত্তর আর প্রমাণ যাচাই

গণনার প্রশ্নে AI সহকারীর ব্যাখ্যা যুক্তিসংগত শোনালেও সংখ্যাটি প্রায়ই ভুল হয়, কারণ দুবার গোনা বা বাদ পড়া শর্ত লেখায় চোখে পড়ে না। কয়েকটি ভুল নিয়মিত দেখা যায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রশ্নের একটি ছোট রূপ নিজে brute force করে সূত্রের সঙ্গে মিলিয়েছি
• প্রতিটি যোগে দলগুলো বিচ্ছিন্ন, প্রতিটি গুণে পছন্দের সংখ্যা স্থির, প্রতিটি ভাগে শ্রেণি সমান, তা দেখেছি
• সীমা আর ক্রম (0 থেকে নাকি 1 থেকে, ক্রমযুক্ত নাকি অক্রমিক) প্রশ্নের সঙ্গে মিলিয়েছি
• উত্তর পূর্ণসংখ্যা আর যুক্তিসংগত মাপের কি না দেখেছি; ভগ্নাংশ বা মোটের চেয়ে বড় উত্তর মানে ভুল
• প্রমাণে induction-এর ভিত্তি, প্রতিটি উপপাদ্যের শর্ত আর কোনো বৃত্তাকার যুক্তি নেই কি না দেখেছি
• উদ্ধৃত ইতিহাস, নাম আর বই বিশ্বস্ত উৎসে মিলিয়েছি

গণনার প্রায় প্রতিটি দাবি ছোট মাপে কয়েক লাইনের কোডে পরীক্ষা করা যায়। দুটি ভিন্ন পথে (যেমন সরাসরি আর complement, বা ভাগের নিয়ম আর একজনকে স্থির করা) একই উত্তর পেলে আস্থা অনেক বাড়ে।