Permutation আর combination

১ · ক্রম গোনে কি না — permutation আর combination-এর মূল প্রশ্ন

বাজারঘরের গুদামে দুটি কাজ এসেছে। প্রথম কাজ: অ্যাপের হোম পেজের সামনের তাকে তিনটি ঘর, বামে, মাঝে আর ডানে; সাতটি নতুন পণ্য থেকে তিনটি বেছে এই তিন ঘরে সাজাতে হবে। দ্বিতীয় কাজ: আট জন ডেলিভারি রাইডার থেকে তিনজনকে বেছে আজকের সিলেট রুটের দল বানাতে হবে। দুটিই “কয়েকটি থেকে কয়েকটি বাছাই”, কিন্তু উত্তর একেবারে আলাদা। তাকে চাল-ডাল-তেল আর তেল-ডাল-চাল আলাদা চেহারা, তাই আলাদা সাজানো। অথচ রাইডার রনি, সুমি আর জামিলের দল আর জামিল, রনি, সুমির দল একই দল; নাম কোন ক্রমে লেখা হলো, তাতে কিছু বদলায় না।

এই পর্বের পুরো কাজ ওই পার্থক্যটি নিখুঁত করা। পর্ব ১৪ “সেট — সংজ্ঞা, subset, power set আর Cartesian product”-এর ভাষায়: ক্রমসহ বাছাই হলো একটি sequence বা tuple (যেমন Cartesian product-এর উপাদান), আর ক্রমহীন বাছাই হলো একটি subset. সেটে {রনি, সুমি, জামিল} = {জামিল, রনি, সুমি}; tuple-এ (চাল, ডাল, তেল) ≠ (তেল, ডাল, চাল)। প্রশ্নটি তাই সবসময় এক: আমি কি tuple গুনছি, না subset?

গোনার হাতিয়ার আসে পর্ব ৩১ “গণনার মূল নিয়ম — যোগ, গুণ, বিয়োগ আর ভাগ” থেকে। এখানে দুটি নিয়ম বারবার লাগবে। গুণের নিয়ম (product rule): কাজটি পরপর k ধাপে হয়, আর আগে যা-ই বাছা হোক, i-তম ধাপে সবসময় m_iটি পছন্দ থাকে; তাহলে মোট উপায় m₁ · m₂ ⋯ m_k. ভাগের নিয়ম (division rule): সসীম সেট A থেকে B-তে এমন একটি onto ফাংশন আছে, যাতে B-এর প্রতিটি উপাদানের ঠিক d-টি preimage; তাহলে |B| = |A|/d. অর্থাৎ প্রতিটি জিনিস ঠিক d বার গোনা হলে মোটকে d দিয়ে ভাগ করুন। ফাংশন আর preimage এসেছে পর্ব ১৬ “ফাংশন — one-to-one, onto, inverse আর composition”-এ।

দুটি সংজ্ঞাতেই “আলাদা” শব্দটি জরুরি: একই জিনিস দুবার নেওয়া চলে না। পুনরাবৃত্তি চললে (কুপন কোডে একই অঙ্ক বারবার) উত্তর n^r, যা পর্ব ৩১-এর বিষয়; আর পুনরাবৃত্তিসহ ক্রমহীন বাছাই পর্ব ৩৫ “পুনরাবৃত্তিসহ বাছাই — stars and bars আর multinomial”-এর বিষয়। মোট চারটি প্রশ্ন:

এখানে n! (n factorial) মানে 1 · 2 ⋯ n, আর নিয়ম অনুযায়ী 0! = 1. এই নিয়মটি খেয়ালখুশি নয়: শূন্যটি জিনিস সাজানোর ঠিক একটি উপায় আছে, কিছুই না করা। পরের অংশে দেখবেন এই নিয়মের জন্যই সূত্রগুলো r = 0 আর r = n-এও কোনো ব্যতিক্রম ছাড়া কাজ করে।

২ · r-permutation — P(n, r) = n!/(n − r)!

প্রমাণ: S-এর একটি r-permutation বানানো মানে পরপর r-টি ঘর ভরা: আগে x₁, তারপর x₂, এভাবে x_r পর্যন্ত।

1. x₁-এর জন্য S-এর যেকোনো উপাদান চলে: n-টি পছন্দ। — সংজ্ঞা
2. x₁ যা-ই হোক, x₂ হতে হবে x₁ ছাড়া অন্য কিছু: ঠিক n − 1টি পছন্দ। সাধারণভাবে, i-তম ঘরের আগে i − 1টি আলাদা উপাদান ব্যবহার হয়ে গেছে, তাই x_i-এর জন্য ঠিক n − (i − 1) = n − i + 1টি পছন্দ, আগের বাছাই যা-ই হোক। — উপাদানগুলো আলাদা হওয়ার শর্ত
3. প্রতিটি ধাপে পছন্দের সংখ্যা আগের বাছাইয়ের ওপর নির্ভর করে না (কোন কোন উপাদান বাকি, তা নির্ভর করে, কিন্তু কয়টি বাকি, তা নয়)। তাই গুণের নিয়ম খাটে: মোট n(n − 1)⋯(n − r + 1). — গুণের নিয়ম
4. এই গুণফলকে (n − r)! দিয়ে গুণ আর ভাগ করলে লবে n(n − 1)⋯(n − r + 1) · (n − r)(n − r − 1)⋯1 = n!, তাই P(n, r) = n!/(n − r)!. r = 0-তে খালি গুণফল 1, আর সূত্রেও n!/n! = 1; r = n-এ n!/0! = n!. ∎

ধাপ ৩-এর বন্ধনীর কথাটি সূক্ষ্ম কিন্তু জরুরি: গুণের নিয়মের জন্য পছন্দের সংখ্যা স্থির থাকলেই চলে, পছন্দগুলো নিজে বদলালেও। ফাংশনের ভাষায় এটি পর্ব ১৬-এর উপপাদ্য ৬.১(খ)-এর আরেক রূপ: r-টি উপাদানের সেট থেকে n-টি উপাদানের সেটে one-to-one ফাংশনের সংখ্যাও n!/(n − r)!. কারণ একটি r-permutation (x₁, …, x_r) মানে ঠিক একটি one-to-one ফাংশন i ↦ x_i; এই মিলটি একটি bijection, তাই দুই সংখ্যা সমান। আর r > n হলে কোনো r-permutation নেই (r-টি আলাদা উপাদান নেওয়ার মতো উপাদানই নেই); Python-এর math.perm(n, r) তখন 0 দেয়।

এবার বাজারঘরের তাক। সাতটি পণ্য A থেকে G (চাল, ডাল, তেল, চিনি, লবণ, আটা, সুজি), তিনটি ঘর। নিচের stepper-এ প্রতিটি ঘর ভরার সময় পছন্দ কমে যাওয়া দেখুন।

1ঘর: [ বাম ][ মাঝ ][ ডান ]2বাম  ← 7টি থেকে একটি3মাঝ  ← বাকি 6টি থেকে4ডান  ← বাকি 5টি থেকে5P(7,3) = 7 · 6 · 5

শেষ ধাপের ব্যাখ্যাটি মনে রাখার মতো। n!/(n − r)! সূত্রটিকে একটি ভাগের নিয়ম হিসেবেও পড়া যায়: সাতটি পণ্যের সব 7!টি পূর্ণ সারি সাজান, তারপর শুধু প্রথম তিনটি ঘর দেখুন। প্রথম তিনটি একই রেখে পরের চারটি 4!টি ক্রমে থাকতে পারে, তাই প্রতিটি 3-permutation ঠিক 4! বার এসেছে। এই “যা গুনতে চাই না, তার ক্রম দিয়ে ভাগ” চিন্তাটিই পরের অংশে combination-এর সূত্র দেবে।

৩ · r-combination — ভাগের নিয়মে C(n, r)

এবার রাইডারের দল। আট জন রাইডার A থেকে H, দলে তিনজন। ক্রম গুরুত্বহীন, তাই সরাসরি গুণের নিয়ম খাটে না: “প্রথম সদস্য, দ্বিতীয় সদস্য, তৃতীয় সদস্য” বলে কিছু নেই। কৌশলটি হলো ইচ্ছা করে ক্রম যোগ করা, তারপর বাড়তি গোনাটুকু ভাগ করে বাদ দেওয়া।

প্রমাণ (ভাগের নিয়ম): A = S-এর সব r-permutation-এর সেট, B = S-এর সব r-উপাদানের subset-এর সেট।

1. ফাংশন φ: A → B সংজ্ঞায়িত করি: φ(x₁, …, x_r) = {x₁, …, x_r}, অর্থাৎ তালিকা থেকে ক্রম মুছে ফেলা। উপাদানগুলো আলাদা, তাই ফলটি সত্যিই r-উপাদানের subset. — সংজ্ঞা
2. φ onto: যেকোনো r-উপাদানের subset T-এর উপাদানগুলো যেকোনো ক্রমে লিখলে এমন একটি তালিকা পাই, যার ছবি T. — onto-র ছক
3. প্রতিটি T-এর preimage ঠিক T-এর উপাদানগুলোর সব ক্রম, অর্থাৎ T-এর permutation; উপপাদ্য ২.১ অনুযায়ী এদের সংখ্যা P(r, r) = r!. তাই φ একটি r!-to-1 ফাংশন। — উপপাদ্য ২.১
4. ভাগের নিয়মে |B| = |A|/r!, অর্থাৎ C(n, r) = P(n, r)/r! = n!/((n − r)! r!). ∎

একই প্রমাণ গুণের নিয়মেও লেখা যায়: একটি r-permutation বানাতে আগে কোন r-টি উপাদান নেবেন তা বাছুন (C(n, r) উপায়), তারপর তাদের সাজান (r! উপায়)। প্রতিটি r-permutation ঠিক একবার তৈরি হয়, তাই P(n, r) = C(n, r) · r!. অজানা C(n, r) বের হলো এমন সমীকরণ থেকে, যার বাকি সব অংশ জানা; গোনায় এই কৌশল বারবার ফিরে আসে।

1ক্রমসহ গুনি: P(8,3)2একটি দল {A,B,C} ক'বার?3প্রতিটি দল ঠিক 3! বার4C(8,3) = 336 / 65বাদ পড়া 5 জন: C(8,5)

৪ · C(n, r) = C(n, n − r) — বীজগণিত আর combinatorial প্রমাণ

একটি identity (সব মানে সত্য সমতা) প্রমাণের দুটি সম্পূর্ণ আলাদা পথ আছে। বীজগাণিতিক পথে সূত্র বসিয়ে দুই পাশ একই রাশিতে নামানো হয়। Combinatorial proof-এ দেখানো হয় দুই পাশ একই জিনিসের সংখ্যা: হয় একই সেটকে দুইভাবে গোনা (double counting, পর্ব ৩৭-এ বিস্তারিত), নয়তো দুই পাশের গোনা সেটের মধ্যে একটি bijection দেখানো। দ্বিতীয় পথটি প্রায়ই বলে দেয় কেন সমতাটি সত্য।

প্রমাণ ১ (বীজগাণিতিক):

1. উপপাদ্য ৩.১ অনুযায়ী C(n, n − r) = n!/((n − r)! (n − (n − r))!). — সূত্রে r-এর জায়গায় n − r, যা 0 আর n-এর মধ্যে আছে
2. n − (n − r) = r, তাই C(n, n − r) = n!/((n − r)! r!). — সরলীকরণ
3. হরের দুটি গুণনীয়কের ক্রম বদলালে গুণফল বদলায় না, তাই এটি n!/(r! (n − r)!) = C(n, r). ∎

প্রমাণ ২ (combinatorial, bijection দিয়ে): S একটি n-উপাদানের সেট।

1. A = S-এর সব r-উপাদানের subset, B = S-এর সব (n − r)-উপাদানের subset. সংজ্ঞা অনুযায়ী |A| = C(n, r) আর |B| = C(n, n − r). — সংজ্ঞা ১.১
2. g: A → B, g(T) = S − T (T-এর complement) সংজ্ঞায়িত করি। |T| = r হলে |S − T| = n − r, তাই g(T) সত্যিই B-তে। — পর্ব ১৫-এর set difference
3. h: B → A, h(U) = S − U-ও একইভাবে সংজ্ঞায়িত। S − (S − T) = T, তাই h∘g = ι_A আর g∘h = ι_B; অর্থাৎ g একটি bijection. — পর্ব ১৬-এর উপপাদ্য ৩.২
4. সসীম দুই সেটের মধ্যে bijection থাকলে তাদের আকার সমান, তাই C(n, r) = C(n, n − r). ∎

দুই প্রমাণই সঠিক, কিন্তু দ্বিতীয়টি একটি গল্প বলে: “কাদের নেবেন” আর “কাদের রেখে যাবেন” একই সিদ্ধান্ত। তাই ১৫ জনের স্কোয়াড থেকে একাদশ বাছা C(15, 11) উপায়ে, আর বাদ পড়া চারজন বাছা C(15, 4) উপায়ে; দুটিই 1365. হিসাবেও সুবিধা: C(100, 98)-এর বদলে C(100, 2) = 100 · 99/2 = 4950.

সংজ্ঞা থেকেই C(n, 0) = C(n, n) = 1 আর C(n, 1) = n. আর r = 0 থেকে n পর্যন্ত সব C(n, r) যোগ করলে পাই power set-এর আকার 2ⁿ (পর্ব ১৪)। এমন identity-র পুরো তালিকা পর্ব ৩৪ “Binomial coefficient, Pascal-এর ত্রিভুজ আর combinatorial identity”-এর বিষয়।

এবার সব কিছু brute force দিয়ে মিলিয়ে দেখা যাক। Python-এর itertools.permutations(S, r) সব r-permutation একে একে তৈরি করে, আর itertools.combinations(S, r) সব r-combination; math.perm আর math.comb সরাসরি সূত্রের মান দেয় (Python 3.8 থেকে আছে)। নিচের ব্লক দুই পথের সংখ্যা মেলায়, তারপর আট রাইডারের সব 336টি তালিকাকে দলে ভাগ করে দেখে প্রতিটি দল কতবার এসেছে। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import permutations, combinations
from math import perm, comb
from collections import Counter

print(" n  r | itertools   perm | itertools  comb | P/C")
for n, r in [(7, 3), (8, 3), (6, 6), (5, 0), (10, 4)]:
    p = sum(1 for _ in permutations(range(n), r))   # ordered, no repeats
    c = sum(1 for _ in combinations(range(n), r))   # unordered r-subsets
    print(f"{n:2} {r:2} | {p:9} {perm(n, r):6} | {c:9} {comb(n, r):5} |"
          f" {p // c} = {r}!")

# the division rule, seen directly: 8 riders, ordered lists of 3
riders = "ABCDEFGH"
teams = Counter(frozenset(t) for t in permutations(riders, 3))
print("ordered lists:", sum(teams.values()), " distinct teams:", len(teams))
print("each team appears", set(teams.values()), "times")
print("orderings of {A,B,C}:", ["".join(t) for t in permutations("ABC")])

# symmetry C(n, r) = C(n, n - r), and what happens when r > n
print("C(8,3), C(8,5):", comb(8, 3), comb(8, 5))
print("symmetric for all n < 40:", all(comb(n, r) == comb(n, n - r)
                                      for n in range(40) for r in range(n + 1)))
print("perm(5, 7) =", perm(5, 7), " comb(5, 7) =", comb(5, 7))

 n  r | itertools   perm | itertools  comb | P/C
 7  3 |       210    210 |        35    35 | 6 = 3!
 8  3 |       336    336 |        56    56 | 6 = 3!
 6  6 |       720    720 |         1     1 | 720 = 6!
 5  0 |         1      1 |         1     1 | 1 = 0!
10  4 |      5040   5040 |       210   210 | 24 = 4!
ordered lists: 336  distinct teams: 56
each team appears {6} times
orderings of {A,B,C}: ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
C(8,3), C(8,5): 56 56
symmetric for all n < 40: True
perm(5, 7) = 0  comb(5, 7) = 0

৫ · একই রকম জিনিসের বিন্যাস — MISSISSIPPI থেকে NARAYANGANJ

এ পর্যন্ত সব জিনিস আলাদা ছিল। এখন বাজারঘরের নামটিই ইংরেজি হরফে লিখুন: BAZARGHAR. নয়টি অক্ষর, কিন্তু A তিনবার, R দুবার। এর অক্ষরগুলো কত রকমে সাজানো যায়? যদি 9! = 362880 বলেন, তাহলে বেশি গোনা হলো: তিনটি A-র নিজেদের মধ্যে জায়গা বদলালে চোখে কোনো নতুন শব্দ আসে না। এটি একটি multiset-এর (যে সংগ্রহে একই উপাদান একাধিকবার থাকতে পারে) বিন্যাস।

প্রমাণ ১ (জায়গা বাছাই, গুণের নিয়ম): একটি বিন্যাস মানে n-টি ঘরের কোনগুলোতে কোন ধরনের জিনিস বসবে, তা ঠিক করা।

1. প্রথম ধরনের n₁টি জিনিসের জন্য n-টি ঘর থেকে n₁টি বাছুন: C(n, n₁) উপায়। জিনিসগুলো একই রকম, তাই ওই ঘরগুলোর মধ্যে তাদের ক্রমের প্রশ্ন নেই। — সংজ্ঞা ১.১
2. বাকি n − n₁টি ঘর থেকে দ্বিতীয় ধরনের জন্য n₂টি: C(n − n₁, n₂) উপায়; প্রথম ধাপে কোন ঘর নেওয়া হলো, তাতে সংখ্যাটি বদলায় না। এভাবে শেষ ধরনের জন্য C(n_k, n_k) = 1. — গুণের নিয়ম
3. গুণফল C(n, n₁) · C(n − n₁, n₂) ⋯ = [n!/(n₁!(n − n₁)!)] · [(n − n₁)!/(n₂!(n − n₁ − n₂)!)] ⋯. প্রতিটি ভগ্নাংশের হরের দ্বিতীয় factorial পরের ভগ্নাংশের লবের সঙ্গে কাটা যায়, আর শেষে 0! = 1 থাকে। ফল n!/(n₁! ⋯ n_k!). ∎

প্রমাণ ২ (লেবেল লাগিয়ে, ভাগের নিয়ম): প্রতিটি একই রকম জিনিসের গায়ে সাময়িক লেবেল লাগান (A₁, A₂, A₃, R₁, R₂, …)। এখন সব আলাদা, বিন্যাস n!টি। লেবেল মুছে ফেলার ফাংশন প্রতিটি লেবেলহীন বিন্যাসকে ঠিক n₁! n₂! ⋯ n_k! বার পায়, কারণ প্রতিটি ধরনের লেবেলগুলো নিজেদের ঘরে যেকোনো ক্রমে থাকতে পারে, আর বিভিন্ন ধরনের ক্রম স্বাধীন। ভাগের নিয়মে উত্তর একই। ∎

BAZARGHAR-এ n = 9, A তিনটি, R দুটি, বাকি চারটি অক্ষর একটি করে: 9!/(3! 2!) = 362880/12 = 30240. বাংলাদেশের একটি জেলার নাম NARAYANGANJ-এ এগারোটি অক্ষর: A চারবার, N তিনবার, আর R, Y, G, J একবার করে; উত্তর 11!/(4! 3!) = 39916800/144 = 277200. পাঠ্যবইয়ের প্রিয় উদাহরণ MISSISSIPPI-তে I চারবার, S চারবার, P দুবার, M একবার: 11!/(4! 4! 2!) = 34650. নিচের ব্লক দুই রকমে মেলায়: ছোট শব্দে set(permutations(w)) দিয়ে সত্যিকারের brute force, আর বড় শব্দে “প্রথম অক্ষর কোনটি” ভাগে ভাগে গোনা একটি recursion, যা সব শব্দ না বানিয়েই গোনে।

from itertools import permutations
from math import factorial
from collections import Counter
from functools import cache

def formula(word):                      # n! / (n1! n2! ... nk!)
    r = factorial(len(word))
    for m in Counter(word).values():
        r //= factorial(m)
    return r

@cache
def count(left):                        # left = sorted tuple of letter counts
    if sum(left) == 0:
        return 1                        # the empty word: one arrangement
    total = 0
    for i, m in enumerate(left):        # choose which letter goes first
        if m:
            rest = list(left); rest[i] -= 1
            total += count(tuple(sorted(rest)))
    return total

for w in ["ABC", "AAB", "BAZAR", "BAZARGHAR"]:
    raw = factorial(len(w))             # treats equal letters as different
    seen = len(set(permutations(w)))    # brute force: 9! tuples for BAZARGHAR
    print(f"{w:10} n! = {raw:6}  distinct = {seen:5}  formula = {formula(w)}")

for w in ["MISSISSIPPI", "NARAYANGANJ"]:
    c = Counter(w)
    print(f"{w}: {dict(c)}")
    print(f"  first-letter recursion = {count(tuple(sorted(c.values())))}"
          f"  formula = {formula(w)}")

ABC        n! =      6  distinct =     6  formula = 6
AAB        n! =      6  distinct =     3  formula = 3
BAZAR      n! =    120  distinct =    60  formula = 60
BAZARGHAR  n! = 362880  distinct = 30240  formula = 30240
MISSISSIPPI: {'M': 1, 'I': 4, 'S': 4, 'P': 2}
  first-letter recursion = 34650  formula = 34650
NARAYANGANJ: {'N': 3, 'A': 4, 'R': 1, 'Y': 1, 'G': 1, 'J': 1}
  first-letter recursion = 277200  formula = 277200

৬ · গোল টেবিল — circular permutation

বাজারঘরের মাসিক সভায় পাঁচজন ব্যবস্থাপক একটি গোল টেবিলে বসবেন। সারিতে বসলে উপায় 5! = 120. কিন্তু গোল টেবিলে কোনো “প্রথম চেয়ার” নেই; সবাই একসঙ্গে এক চেয়ার ডানে সরে বসলে কারো ডান বা বাম পাশের মানুষ বদলায় না। তাই সেগুলোকে একই বসা ধরা হয়। একে বলে circular permutation.

প্রমাণ:

1. একটি গোল বসাকে কোনো একটি চেয়ার থেকে ঘড়ির কাঁটার দিকে পড়লে একটি সারি-বিন্যাস পাই। n-টি চেয়ার, তাই n-টি পড়া। — সংজ্ঞা
2. এই n-টি সারি সব আলাদা: মানুষগুলো আলাদা, তাই প্রথম স্থানে কে আছেন তা দিয়েই সারিগুলো আলাদা হয়। আবার প্রতিটি সারি-বিন্যাস ঠিক একটি গোল বসা থেকে আসে (সারিটিকে টেবিলে মুড়ে দিলেই হলো)। — মানুষগুলো আলাদা
3. অতএব “সারি থেকে গোল বসা” ফাংশনটি onto আর ঠিক n-to-1. ভাগের নিয়মে গোল বসা n!/n = (n − 1)!. — ভাগের নিয়ম
4. n ≥ 3 হলে প্রতিটি গোল বসা আর তার আয়নার প্রতিবিম্ব আলাদা (কারো ডানের মানুষ বামে চলে যায়), আর প্রতিবিম্বের প্রতিবিম্ব আসল বসা। তাই প্রতিবিম্বও একই ধরলে প্রতিটি নতুন শ্রেণিতে ঠিক দুটি গোল বসা; আবার ভাগের নিয়মে (n − 1)!/2. ∎

বিকল্প চিন্তা: একজনকে (ধরুন A) যেকোনো চেয়ারে বসিয়ে “নোঙর” করুন; সব চেয়ার একই রকম বলে এতে কোনো পছন্দ নেই। এরপর A-র ডান থেকে চেয়ারগুলো আলাদা হয়ে গেছে, বাকি n − 1 জনের জন্য (n − 1)!. শর্ত থাকলে “block” কৌশল: দুজনকে পাশাপাশি বসাতে হলে তাঁদের একটি একক ধরুন। পাঁচজনের টেবিলে তখন চারটি একক, গোল বসা (4 − 1)! = 6, আর block-এর ভেতরে দুজন দুই ক্রমে: মোট 2 · 6 = 12. নিচের ব্লক প্রতিটি বসাকে “০ নম্বর মানুষ প্রথমে” রূপে ঘুরিয়ে (canonical form) আলাদা বসা গোনে।

from itertools import permutations
from math import factorial

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

def round_table(n):              # seatings up to rotation
    return {canon(p) for p in permutations(range(n))}

def bracelet(n):                 # also identify a seating with its mirror image
    out = set()
    for q in round_table(n):
        mirror = (q[0],) + q[:0:-1]
        out.add(min(q, mirror))
    return out

print(" n | linear n! | round brute (n-1)! | mirror brute (n-1)!/2")
for n in range(3, 8):
    print(f"{n:2} | {factorial(n):9} | {len(round_table(n)):11} {factorial(n - 1):6}"
          f" | {len(bracelet(n)):12} {factorial(n - 1) // 2:6}")

# 5 people, persons 1 and 2 must sit side by side
seat = round_table(5)
together = [q for q in seat if abs(q.index(1) - q.index(2)) in (1, 4)]
print("5 at a round table:", len(seat), " with 1 and 2 adjacent:", len(together))
print("block method 2 * (4-1)! =", 2 * factorial(3))

 n | linear n! | round brute (n-1)! | mirror brute (n-1)!/2
 3 |         6 |           2      2 |            1      1
 4 |        24 |           6      6 |            3      3
 5 |       120 |          24     24 |           12     12
 6 |       720 |         120    120 |           60     60
 7 |      5040 |         720    720 |          360    360

5 at a round table: 24  with 1 and 2 adjacent: 12
block method 2 * (4-1)! = 12

৭ · শর্তসহ দল বাছাই — ক্রিকেট একাদশ আর কমিটি

বাস্তব প্রশ্নে বাছাই প্রায় কখনো শর্তহীন নয়। বাজারঘরের অফিস ক্রিকেট টুর্নামেন্টের জন্য ১৫ জনের স্কোয়াড: ৬ জন বোলার আর ৯ জন ব্যাটার (উইকেটরক্ষকসহ)। শর্ত: একাদশে অন্তত ৪ জন বোলার থাকবেন। কতভাবে একাদশ বাছা যায়?

“অন্তত” শব্দটি দেখলেই দুটি নির্ভরযোগ্য পথ মনে আনুন। ক্ষেত্রভিত্তিক গণনা: বোলারের সংখ্যা ঠিক ৪, ঠিক ৫ বা ঠিক ৬; এই ক্ষেত্রগুলো পরস্পর disjoint আর একসঙ্গে সব বৈধ দল ঢাকে, তাই যোগের নিয়ম খাটে। প্রতিটি ক্ষেত্রের ভেতরে গুণের নিয়ম: কোন বোলাররা, আর কোন ব্যাটাররা।

• ৪ জন বোলার, ৭ জন ব্যাটার: C(6, 4) · C(9, 7) = 15 · 36 = 540
• ৫ জন বোলার, ৬ জন ব্যাটার: C(6, 5) · C(9, 6) = 6 · 84 = 504
• ৬ জন বোলার, ৫ জন ব্যাটার: C(6, 6) · C(9, 5) = 1 · 126 = 126

মোট 540 + 504 + 126 = 1170. Complement দিয়ে: সব একাদশ C(15, 11) = 1365; খারাপগুলো, অর্থাৎ ৩ জন বা তার কম বোলার: ৯ জন ব্যাটারের বেশি কেউ নেই, তাই বোলার অন্তত ২ জন লাগেই; ২ জন বোলারে C(6, 2) · C(9, 9) = 15, ৩ জনে C(6, 3) · C(9, 8) = 20 · 9 = 180. মোট খারাপ 195, ভালো 1365 − 195 = 1170. দুই পথে একই উত্তর, যা আস্থার একটি ভালো লক্ষণ।

এবার খাতায় সম্ভবত সবচেয়ে বেশি দেখা ভুলটি: “আগে ৪ জন বোলার নিশ্চিত, C(6, 4) = 15; তারপর বাকি ১১ জন থেকে যেকোনো ৭ জন, C(11, 7) = 330; মোট 15 · 330 = 4950 উপায়।” উত্তরটি সঠিকের চার গুণেরও বেশি। ৫ জন বোলারের একটি একাদশ এই পদ্ধতিতে পাঁচবার তৈরি হয়: পাঁচজনের যেকোনো চারজনকে “নিশ্চিত” ধরে বাকিজনকে “যেকোনো ৭”-এ ফেলে। এটি overcounting: গুণের নিয়ম খাটে শুধু তখন, যখন প্রতিটি ফল ঠিক একবার তৈরি হয়। নিচের ব্লক 1365টি একাদশের প্রত্যেকটি তৈরি করে সরাসরি গোনে, আর ভুল পদ্ধতি প্রতিটি দলকে কতবার গোনে তাও দেখায়।

from itertools import combinations
from math import comb

bowlers = [f"B{i}" for i in range(1, 7)]       # 6 bowlers
batters = [f"T{i}" for i in range(1, 10)]      # 9 batters (keeper included)
squad = bowlers + batters                       # 15 players

def n_bowl(team):
    return sum(p in bowlers for p in team)

teams = list(combinations(squad, 11))
good = [t for t in teams if n_bowl(t) >= 4]
print("all XIs:", len(teams), "  with at least 4 bowlers:", len(good))

cases = {b: comb(6, b) * comb(9, 11 - b) for b in range(4, 7)}
print("by cases (bowlers: count):", cases, " sum =", sum(cases.values()))
bad = sum(comb(6, b) * comb(9, 11 - b) for b in range(0, 4))
print("complement:", comb(15, 11), "-", bad, "=", comb(15, 11) - bad)

wrong = comb(6, 4) * comb(11, 7)     # "first 4 bowlers, then any 7 others"
print("wrong method C(6,4)*C(11,7) =", wrong)
for b in range(4, 7):                # an XI with b bowlers is built C(b,4) times
    print(f"  XI with {b} bowlers is produced {comb(b, 4)} time(s)")
print("check:", sum(cases[b] * comb(b, 4) for b in cases), "=", wrong)

all XIs: 1365   with at least 4 bowlers: 1170
by cases (bowlers: count): {4: 540, 5: 504, 6: 126}  sum = 1170
complement: 1365 - 195 = 1170
wrong method C(6,4)*C(11,7) = 4950
  XI with 4 bowlers is produced 1 time(s)
  XI with 5 bowlers is produced 5 time(s)
  XI with 6 bowlers is produced 15 time(s)
check: 4950 = 4950

একই ধাঁচের আরেকটি প্রশ্ন stepper-এ ধাপে ধাপে করা যাক। বাজারঘরের ৪ সদস্যের একটি নিরাপত্তা কমিটি হবে ঢাকা অফিসের ৫ জন আর চট্টগ্রাম অফিসের ৪ জন, মোট ৯ জন থেকে; শর্ত: চট্টগ্রামের অন্তত ২ জন থাকবেন।

1ঢাকা 5, চট্টগ্রাম 4; দল 4 জন2চট্টগ্রাম ঠিক 23চট্টগ্রাম ঠিক 34চট্টগ্রাম ঠিক 45যোগ, আর complement-এ যাচাই6ভুল পথ: আগে 2 জন নিশ্চিত

ক্ষেত্রভিত্তিক গণনার তিনটি পরীক্ষা মনে রাখুন: ক্ষেত্রগুলো কি disjoint? সব মিলিয়ে কি প্রতিটি বৈধ ফল ঢাকে? আর প্রতিটি ক্ষেত্রের ভেতরে কি গুণের নিয়মের শর্ত (প্রতিটি ফল ঠিক একবার) মানা হয়েছে? দলে পদ থাকলে (অধিনায়ক, সহ-অধিনায়ক) প্রশ্ন আবার ক্রমযুক্ত হয়: একাদশ থেকে অধিনায়ক আর সহ-অধিনায়ক বাছার উপায় P(11, 2) = 110, C(11, 2) = 55 নয়, কারণ দুটি পদ আলাদা।

৮ · তাসের হাত, পরীক্ষার অঙ্ক আর ভুল ধরা

গোনার বইয়ে তাসের হাত গোনা একটি চিরাচরিত অনুশীলন: ৫২টি তাস মানে ১৩টি মান (rank) আর ৪টি রঙের (suit) সব জোড়া। কোনো খেলার নিয়ম লাগবে না; “৫টি তাসের হাত” মানে প্যাকেটের একটি 5-combination, কারণ তাস কোন ক্রমে এল তা গুরুত্বহীন। মোট হাত C(52, 5) = 2598960. কয়েকটি প্রচলিত ধরন:

full house-এর হিসাবে একটি সূক্ষ্মতা আছে: তিনটির মান আর দুটির মান আলাদা ভূমিকা পালন করে, তাই সেখানে মান দুটি বাছাই ক্রমযুক্ত, 13 · 12 = P(13, 2), C(13, 2) নয়। তিনটি সাত আর দুটি রাজা একটি হাত, তিনটি রাজা আর দুটি সাত আরেকটি। আর flush-এর 5148-এর মধ্যে একই রঙের পাঁচটি ধারাবাহিক মানের হাতও আছে; সেগুলো আলাদা ধরন ধরলে বাদ দিতে হয় (টেক্কাকে উঁচু ও নিচু দুভাবেই ধরলে এমন হাত 40টি, বাকি থাকে 5108টি হাত)। প্রতিটি সংখ্যা scratch-এ Python দিয়ে যাচাই করা।

পরীক্ষার অঙ্ক: পূর্ণ সমাধান

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর লিখিত পরীক্ষায় যে ধাঁচের অঙ্ক আসে, তার কয়েকটি:

1. বাজারঘরের চার অঙ্কের কুপন কোডে কোনো অঙ্ক পুনরাবৃত্ত হবে না, আর প্রথম অঙ্ক 0 হবে না। কয়টি কোড? প্রথম অঙ্ক 9টি (1–9), দ্বিতীয়টি 9টি (0 এখন চলে, কিন্তু প্রথমটি বাদ), তারপর 8, 7: 9 · 9 · 8 · 7 = 4536. বিকল্প: P(10, 4) = 5040 থেকে 0 দিয়ে শুরু হওয়াগুলো P(9, 3) = 504 বাদ, 5040 − 504 = 4536.
2. CHATTOGRAM শব্দের অক্ষরগুলো কতভাবে সাজানো যায়? দশটি অক্ষর, A দুটি, T দুটি: 10!/(2! 2!) = 3628800/4 = 907200.
3. ৮ জন রাইডার থেকে ৩ জনের দল, যেখানে রনি আর সুমি একসঙ্গে থাকবেন না। সব দল C(8, 3) = 56; দুজনেই আছেন এমন দল: তৃতীয় জন বাকি ৬ জনের যেকোনো, 6টি। উত্তর 56 − 6 = 50.

ভুল ধরুন: “অন্তত একজন”-এর ফাঁদ

একজন লিখলেন: “প্রশ্ন: ঢাকার ৫ জন আর চট্টগ্রামের ৪ জন থেকে ৪ জনের কমিটি, চট্টগ্রামের অন্তত একজন থাকবেন। সমাধান: আগে চট্টগ্রামের একজন বাছি, 4 উপায়। তারপর বাকি ৮ জন থেকে যেকোনো ৩ জন, C(8, 3) = 56. গুণের নিয়মে উত্তর 4 · 56 = 224টি কমিটি।” পড়ে ভুলটি নিজে খুঁজুন।

ভুল কোথায়: সঠিক উত্তর complement-এ: C(9, 4) − C(5, 4) = 126 − 5 = 121. 224 তো সব কমিটির সংখ্যা 126-এর চেয়েও বেশি, যা নিজেই লাল সংকেত। চট্টগ্রামের দুজন (X আর Y) আছেন এমন কমিটি দুবার গোনা হয়েছে: একবার X-কে “প্রথমে বাছা” ধরে, একবার Y-কে; অথচ কমিটিতে “প্রথমে বাছা” সদস্য বলে কিছু নেই। নিরাপদ নিয়ম: “অন্তত একজন” দেখলে আগে complement (“একজনও না”) ভাবুন।

৯ · AI-এর যুগে — গোনার উত্তর যাচাই

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

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

• ক্রম আর পুনরাবৃত্তি নিয়ে সিদ্ধান্তটি প্রশ্নের ভাষার সঙ্গে মিলিয়েছি
• উত্তরটি মোট সম্ভাব্য সংখ্যার চেয়ে বড় নয়, আর ঋণাত্মক বা ভগ্নাংশ নয়
• ছোট সংস্করণে (কম মানুষ, ছোট শব্দ) itertools দিয়ে brute force চালিয়ে সূত্র মিলিয়েছি
• দ্বিতীয় একটি পদ্ধতিতে (complement বা ক্ষেত্রভিত্তিক) একই উত্তর পেয়েছি
• ব্যবহৃত সূত্রের শর্ত আর কোনো উল্লেখিত বই বা ইতিহাস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি
• বড় সংখ্যার পাটিগণিত নিজে Python-এ (math.comb, math.perm) করেছি

সবচেয়ে সস্তা প্রথম পরীক্ষা: AI-এর যুক্তিটি সংখ্যা ছোট করে চালান। ১৫ জনের স্কোয়াডের বদলে ৫ জন, NARAYANGANJ-এর বদলে AAB. ছোট প্রশ্নে সব ফল হাতে বা itertools দিয়ে তালিকা করা যায়; সেখানে যুক্তি ভুল সংখ্যা দিলে বড় প্রশ্নেও ভুল।