Inclusion–exclusion আর derangement

১ · দুই সেট থেকে তিন সেট — যোগ, বিয়োগ, আবার যোগ

পর্ব ১৫ “সেটের অপারেশন — union, intersection, Venn diagram আর identity”-এ আপনি প্রমাণ করেছেন |A ∪ B| = |A| + |B| − |A ∩ B|, আর তিন সেটের সূত্রটি দেখেছেন। সেখানে সাধারণ n সেটের রূপ আর তার প্রমাণ এই পর্বের জন্য রাখা ছিল। এই নীতির নাম inclusion–exclusion: “অন্তর্ভুক্ত করা আর বাদ দেওয়া”। আগে তিন সেটে হাত পাকাই, তারপর সাধারণ প্রমাণে যাই।

বাজারঘরের উদাহরণ। বাজারঘর ১ থেকে ১০০ পর্যন্ত অর্ডার নম্বরে একটি অফার দেয়: অর্ডার নম্বর 2, 3 বা 5-এর যেকোনোটি দিয়ে বিভাজ্য হলে ছাড়। কতগুলো অর্ডার ছাড় পাবে? ধরুন A, B, C হলো যথাক্রমে 2, 3, 5-এর গুণিতকের সেট। m ≤ 100-এর গুণিতক ⌊100/m⌋টি (floor, অর্থাৎ নিচের দিকে পূর্ণসংখ্যা), আর দুটি ভিন্ন মৌলিক সংখ্যা দিয়ে একসঙ্গে বিভাজ্য মানে তাদের গুণফল দিয়ে বিভাজ্য। নিচের ছবিতে Venn diagram-এর আটটি অঞ্চলের প্রতিটিতে কয়টি সংখ্যা পড়ে, তা দেখানো আছে (scratch-এ গুনে মেলানো)।

1A, B, C সংজ্ঞা2+ একক সেট3− জোড়ায় ছেদ4+ তিনটির ছেদ5অঞ্চল ধরে যাচাই6complement: 26

লক্ষ করুন, ধাপ ৩-এর পরে উত্তর 71, যা আসল উত্তরের চেয়ে কম, আর ধাপ ২-এর পরে 103, যা বেশি। আংশিক যোগফল সত্যিকারের উত্তরের দুই পাশে দোলে। এই পর্যবেক্ষণটি সেকশন ৭-এ Bonferroni অসমতা হিসেবে প্রমাণ হবে।

২ · সাধারণ নীতি আর তার প্রমাণ

n-টি সেটের জন্য লেখা সহজ করতে একটি সংকেত নিই। প্রতিটি k-এর জন্য S_k হলো k-টি করে সেট বেছে তাদের ছেদের আকারের যোগফল:

S_k = ∑_{1 ≤ i1 < i2 < … < ik ≤ n} |A_i1 ∩ A_i2 ∩ … ∩ A_ik|

এই যোগফলে C(n, k)টি পদ আছে, কারণ n-টি সেট থেকে k-টি বাছাইয়ের উপায় C(n, k) (পর্ব ৩৩)। সেকশন ১-এ S₁ = 103, S₂ = 32, S₃ = 3.

প্রমাণের কৌশলটি double counting-এর মতো: সূত্রের দুই পাশে প্রতিটি উপাদান কতবার গোনা হয়, তা আলাদা করে হিসাব করি।

1. বাইরের উপাদান: x যদি কোনো A_i-তে না থাকে, তাহলে বাঁ পাশে সে নেই, আর ডান পাশের কোনো ছেদেও নেই। দুই পাশেই অবদান 0. — সংজ্ঞা
2. ভেতরের উপাদান: ধরুন x ঠিক r-টি সেটে আছে, r ≥ 1. বাঁ পাশে সে ঠিক 1 বার গোনা হয়। — union-এর সংজ্ঞা
3. S_k-তে অবদান: k-টি সেটের একটি ছেদে x থাকে ঠিক যখন বাছাই করা k-টি সেটের সবগুলো x-এর সেই r-টি সেটের মধ্যে পড়ে। এমন বাছাই C(r, k)টি, আর k > r হলে একটিও নেই। তাই S_k-তে x গোনা হয় C(r, k) বার। — বাছাই গোনা
4. ডান পাশে মোট অবদান: ∑_k=1^r (−1)^k+1 C(r, k) = 1 − ∑_k=0^r (−1)^k C(r, k). — k = 0 পদটি (C(r, 0) = 1) আলাদা করা
5. Binomial theorem: ∑_k=0^r (−1)^k C(r, k) = (1 − 1)^r = 0, কারণ r ≥ 1. তাই অবদান 1 − 0 = 1. — পর্ব ৩৪-এর একান্তর যোগফল
6. প্রতিটি উপাদান দুই পাশে সমান বার গোনা হয় (0 বা 1), তাই দুই পাশ সমান। ∎ — যোগের নিয়ম

ধাপ ৫-ই নীতির প্রাণ: r = 3 হলে 3 − 3 + 1 = 1, r = 4 হলে 4 − 6 + 4 − 1 = 1. পালাক্রমের চিহ্ন কোনো কৌশলের জন্য বসানো নয়; এটি binomial theorem থেকে বাধ্যতামূলকভাবে আসে।

Complement রূপ — “কোনো খারাপ ধর্ম নেই”

বাস্তবে প্রায়ই প্রশ্নটি উল্টো: একটি সার্বিক সেট U-তে N-টি বস্তু, আর কয়েকটি “খারাপ” ধর্ম P₁, …, P_n; A_i হলো P_i আছে এমন বস্তুর সেট। কতগুলো বস্তুর কোনো খারাপ ধর্ম নেই? এর উত্তর union-এর complement-এর আকার।

প্রমাণ এক লাইনের: De Morgan-এর নিয়মে Ā₁ ∩ … ∩ Ā_n হলো A₁ ∪ … ∪ A_n-এর complement, তাই আকার N − |A₁ ∪ … ∪ A_n|, আর উপপাদ্য ২.১ বসালেই হয়। ∎ এই পর্বের বাকি সব প্রয়োগ, onto ফাংশন, derangement, φ(n), মৌলিক-গণনা, আসলে এই প্রতিসম রূপের ভিন্ন ভিন্ন সাজ। প্রতিটিতে একই চার প্রশ্ন: U কী, N কত, খারাপ ধর্মগুলো কী, আর k-টি ধর্মের ছেদের আকার কত?

৩ · Onto ফাংশন গোনা আর Stirling সংখ্যা

পর্ব ১৬ “ফাংশন — one-to-one, onto, inverse আর composition”-এ m উপাদানের সেট থেকে n উপাদানের সেটে onto ফাংশনের সংখ্যার সূত্রটি দেওয়া হয়েছিল, প্রমাণ এই পর্বের জন্য রেখে। বাজারঘরের ভাষায়: সকালে m-টি আলাদা অর্ডার n জন রাইডারের মধ্যে ভাগ করতে হবে, আর প্রত্যেক রাইডার অন্তত একটি অর্ডার পাবেন। প্রতিটি বণ্টন একটি ফাংশন f: {অর্ডার} → {রাইডার}, আর “সবাই অন্তত একটি” মানে f onto.

1. সার্বিক সেট: U = X থেকে Y-তে সব ফাংশন। প্রতিটি উপাদানের n-টি পছন্দ, স্বাধীনভাবে, তাই N = n^m. — গুণের নিয়ম, পর্ব ৩১
2. খারাপ ধর্ম: Y = {y₁, …, y_n}. A_j = যেসব ফাংশন y_j-কে কখনো মান হিসেবে নেয় না। f onto ঠিক তখন, যখন f কোনো A_j-তে নেই। — onto-র সংজ্ঞা
3. k-টির ছেদ: নির্দিষ্ট k-টি y_j বাদ দিলে প্রতিটি উপাদানের হাতে n − k-টি মান থাকে, তাই ছেদের আকার (n − k)^m, কোন k-টি বাদ তার ওপর নির্ভর করে না। — গুণের নিয়ম
4. প্রতিসম রূপ: উপপাদ্য ২.২-এ N_k = (n − k)^m বসালে onto(m, n) = ∑ (−1)^k C(n, k)(n − k)^m. ∎ — উপপাদ্য ২.২

শেষ পদ k = n-এ (n − n)^m = 0^m = 0 (m ≥ 1), তাই সেটি সবসময় শূন্য; তবু সাধারণ সূত্রে রাখা সুবিধাজনক। নিচের stepper পাঁচটি অর্ডার আর তিনজন রাইডারে হিসাবটি চালায়।

1N = 3⁵2k = 1: একজন বাদ3k = 2: দুজন বাদ4k = 3: তিনজন বাদ5যোগফল আর S(5, 3)

প্রমাণ। প্রতিটি onto ফাংশন f একটি partition দেয়: একই রাইডারের অর্ডারগুলো এক দল, অর্থাৎ দলগুলো f⁻¹(y₁), …, f⁻¹(y_n), সবগুলো অশূন্য কারণ f onto. উল্টো দিকে একটি partition আর তার n-টি দলের সঙ্গে n রাইডারের একটি one-to-one মিল (n!টি উপায়) মিলে ঠিক একটি onto ফাংশন দেয়। তাই onto ফাংশনগুলো (partition, মিল) জোড়ার সঙ্গে bijection-এ, আর গুণের নিয়মে onto(m, n) = S(m, n) · n!. ∎

এই Stirling সংখ্যা পর্ব ৩৫ “পুনরাবৃত্তিসহ বাছাই — stars and bars আর multinomial”-এর twelvefold way সারণির “আলাদা বল, একই রকম বাক্স, প্রতিটিতে অন্তত একটি” ঘর। তার recurrence S(m, n) = nS(m − 1, n) + S(m − 1, n − 1), সারণি আর Bell সংখ্যা পর্ব ৫০ “বিশেষ সংখ্যা — Catalan, Stirling আর partition”-এর বিষয়। নিচের ব্লক সূত্রটি সব ফাংশন একটি একটি করে গুনে মেলায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
from math import comb, factorial

def onto(m, n):                      # inclusion-exclusion formula
    return sum((-1) ** k * comb(n, k) * (n - k) ** m for k in range(n + 1))

def onto_brute(m, n):                # try every function {1..m} -> {1..n}
    return sum(1 for f in product(range(n), repeat=m) if len(set(f)) == n)

terms = [(-1) ** k * comb(3, k) * (3 - k) ** 5 for k in range(4)]
print("m=5, n=3 terms:", terms, "sum =", sum(terms))

print(" m n   onto  brute  S(m,n)")
for m, n in [(3, 2), (4, 2), (4, 3), (5, 3), (6, 3), (7, 4), (8, 5)]:
    a, b = onto(m, n), onto_brute(m, n)
    assert a == b and a % factorial(n) == 0
    print(f"{m:2}{n:2} {a:6} {b:6} {a // factorial(n):6}")

print("m < n gives 0:", [onto(m, 5) for m in range(5)])
print("onto(n, n) = n!:", all(onto(n, n) == factorial(n) for n in range(10)))
print("onto(20, 6) =", onto(20, 6), "S(20,6) =", onto(20, 6) // 720)

m=5, n=3 terms: [243, -96, 3, 0] sum = 150
 m n   onto  brute  S(m,n)
 3 2      6      6      3
 4 2     14     14      7
 4 3     36     36      6
 5 3    150    150     25
 6 3    540    540     90
 7 4   8400   8400    350
 8 5 126000 126000   1050
m < n gives 0: [0, 0, 0, 0, 0]
onto(n, n) = n!: True
onto(20, 6) = 3100376804676480 S(20,6) = 4306078895384

৪ · Derangement — কেউ নিজের উপহার ফেরত পান না

বাজারঘরের অফিসে বছর শেষে একটি গোপন উপহার বিনিময় হয়: n জন কর্মী নিজের নাম লেখা চিরকুট একটি বাক্সে ফেলেন, তারপর প্রত্যেকে এলোমেলোভাবে একটি চিরকুট তোলেন আর সেই মানুষের জন্য উপহার কেনেন। মুশকিল হয় যদি কেউ নিজের নামই তোলেন। কতগুলো বিন্যাসে কেউই নিজের নাম পান না? পুরোনো সংস্করণে গল্পটি ছিল রেস্তোরাঁর টুপি-ঘরের: কর্মচারী টুপিগুলো এলোমেলো ফেরত দিলে কেউ নিজের টুপি পান না, তার সম্ভাবনা কত? এজন্য একে hat-check সমস্যাও বলে।

পর্ব ৪০ “Random variable আর প্রত্যাশা — linearity-র জাদু”-এ আপনি দেখেছেন, এলোমেলো permutation-এ fixed point-এর গড় সংখ্যা যেকোনো n-এ ঠিক 1, indicator আর linearity দিয়ে। কিন্তু “একটিও নেই”-এর সম্ভাবনা গড় দিয়ে বের হয় না; সেখানে প্রমাণ এই পর্বে রাখা ছিল।

1. সার্বিক সেট: U = {1, …, n}-এর সব permutation, N = n!. — পর্ব ৩৩
2. খারাপ ধর্ম: A_i = যেসব permutation-এ σ(i) = i. Derangement মানে কোনো A_i-তে না থাকা। — সংজ্ঞা ৪.১
3. k-টির ছেদ: নির্দিষ্ট k-টি i নিজের জায়গায় স্থির হলে বাকি n − k-টি উপাদান বাকি n − k-টি জায়গায় যেকোনোভাবে বসতে পারে: (n − k)!টি, কোন k-টি তার ওপর নির্ভর করে না। — গুণের নিয়ম
4. প্রতিসম রূপ: D_n = ∑ (−1)^k C(n, k)(n − k)!. — উপপাদ্য ২.২
5. সরল করা: C(n, k)(n − k)! = n!/(k!(n − k)!) · (n − k)! = n!/k!. ∎ — বীজগণিত

1N = 4! = 242k = 1: একজন নিজেরটা3k = 2: দুজন নিজেরটা4k = 3: তিনজন5k = 4: সবাই6D₄ = 9, তালিকা

1/e কোথা থেকে আসে

উপপাদ্য ৪.২-কে n! দিয়ে ভাগ করলে এলোমেলো চিরকুট তোলায় কেউ নিজের নাম না পাওয়ার সম্ভাবনা পাওয়া যায় (পর্ব ৩৮-এর Laplace-এর সংজ্ঞা, সব n! বিন্যাস সমান সম্ভাব্য ধরে):

p_n = D_n/n! = 1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!

Calculus থেকে জানা আছে (এখানে প্রমাণ ছাড়া ব্যবহার করছি) e^x = ∑_k≥0 x^k/k!, তাই x = −1-এ e⁻¹ = ∑_k≥0 (−1)^k/k!. p_n এই অসীম ধারার প্রথম n + 1টি পদ। তাই n → ∞-এ p_n → 1/e ≈ 0.367879. বিস্ময়কর অংশটি গতি: n = 5-এ 11/30 ≈ 0.3667, n = 7-এ 0.367857, আর তারপর পরিবর্তন চার দশমিক ঘরেও চোখে পড়ে না। অফিসে ৬ জন হোক বা ৬০০ জন, কারও নিজের নাম না ওঠার সম্ভাবনা প্রায় ৩৭%; অর্থাৎ প্রায় ৬৩% ক্ষেত্রে অন্তত একজন নিজের নাম তুলবেন, তখন আবার তোলা লাগবে।

1. n!/e − D_n = n! ∑_k>n (−1)^k/k!. — ধারার বাকি অংশ
2. এই বাকি অংশটি একটি একান্তর ধারা, যার পদের মান ক্রমশ কমে আর শূন্যে যায়; এমন ধারার যোগফলের মান তার প্রথম পদের মানের চেয়ে কম (একান্তর ধারার পরিচিত সীমা, প্রমাণ ছাড়া)। প্রথম পদ (−1)ⁿ⁺¹/(n + 1)!. — calculus
3. তাই |n!/e − D_n| < n!/(n + 1)! = 1/(n + 1) ≤ 1/2, কারণ n ≥ 1. ∎ — বীজগণিত

যেমন 4!/e ≈ 8.829, যার নিকটতম পূর্ণসংখ্যা 9 = D₄. কিন্তু সাবধান: উপপাদ্যটি সত্যিকারের বাস্তব সংখ্যার জন্য; কম্পিউটারের float-এ n!/e হিসাব করলে বড় n-এ এটি ভেঙে পড়ে, নিচের ব্লক তা দেখাবে।

৫ · Derangement-এর recurrence আর simulation

সূত্রের পাশাপাশি D_n-এর একটি সুন্দর recurrence আছে, যার প্রমাণ গণনা দিয়ে, বীজগণিত দিয়ে নয়। এ ধরনের প্রমাণকে combinatorial proof বলে।

1. σ(j) মানে কর্মী j যার নাম তুলেছেন। একটি derangement-এ কর্মী n যার নাম তুলেছেন, ধরুন i = σ(n); i ≠ n, তাই i-এর n − 1টি সম্ভাব্য মান। নিচে দেখাব, প্রতিটি i-এর জন্য σ(n) = i এমন derangement ঠিক D_n−1 + D_n−2টি। — ক্ষেত্রভাগ
2. ক্ষেত্র ক, অদলবদল: σ(i) = n, অর্থাৎ i আর n পরস্পরের নাম তুলেছেন। এই দুজনকে সরিয়ে দিলে বাকি n − 2 জন নিজেদের নামগুলোই নিজেদের মধ্যে তুলেছেন, কেউ নিজেরটা নয়: ঠিক D_n−2টি। — বাকি অংশ স্বাধীন
3. ক্ষেত্র খ: σ(i) ≠ n. তাহলে n-এর নাম তুলেছেন i ছাড়া অন্য কেউ, ধরুন j. কর্মী n-কে বাদ দিয়ে j-এর হাতে n-এর চিরকুটের বদলে i-এর চিরকুটটি দিন (যেটি এতক্ষণ n-এর হাতে ছিল)। এতে 1, …, n − 1-এর একটি permutation τ পাওয়া যায়, আর j ≠ i বলে τ(j) = i ≠ j; অন্য সবার চিরকুট বদলায়নি। তাই τ একটি derangement. — চিরকুট বদল
4. উল্টো দিক: n − 1 জনের যেকোনো derangement τ নিন; i-এর চিরকুট যিনি তুলেছেন, তাকে j বলুন। j-কে n-এর চিরকুট দিন আর n-কে i-এর; এতে σ(n) = i আর σ(i) = τ(i) ≠ n, অর্থাৎ ক্ষেত্র খ-এর একটি σ. দুই কাজ পরস্পরের উল্টো, তাই ক্ষেত্র খ-তে ঠিক D_n−1টি বিন্যাস। — bijection
5. দুই ক্ষেত্র পরস্পর বিচ্ছিন্ন আর মিলে সব ঢাকে, তাই প্রতিটি i-এ D_n−1 + D_n−2, আর n − 1টি i মিলে D_n = (n − 1)(D_n−1 + D_n−2). ∎ — যোগ আর গুণের নিয়ম

যাচাই: D₂ = 1 · (0 + 1) = 1 (শুধু অদলবদল 21), D₃ = 2 · (1 + 0) = 2 (231 আর 312), D₄ = 3 · (2 + 1) = 9, stepper-এর সঙ্গে মেলে। Cycle-এর ভাষায় ক্ষেত্র ক মানে n একটি দৈর্ঘ্য-২ cycle-এ আছে, আর ক্ষেত্র খ মানে দৈর্ঘ্য ৩ বা বেশির cycle-এ; ধাপ ৩-এর কাজটি আসলে সেই cycle থেকে n-কে তুলে নেওয়া।

উপপাদ্য ৪.২-এর সূত্র থেকে আরেকটি সহজ recurrence সরাসরি আসে: D_n = nD_n−1 + (−1)ⁿ (অনুশীলন ১)। এগুলো exponential generating function দিয়েও পাওয়া যায়, যেখানে derangement-এর EGF e^−x/(1 − x); সেই পথ পর্ব ৪৮ “Generating function — গণনাকে বীজগণিতে রূপান্তর”-এ। নিচের ব্লক চারটি পথ মেলায়: brute force, সূত্র, recurrence আর round(n!/e), তারপর একটি seeded simulation.

from fractions import Fraction
from itertools import permutations
from math import factorial, comb, e
import random

def D_formula(n):                    # n! * sum (-1)^k / k!, exact
    return sum((-1) ** k * comb(n, k) * factorial(n - k) for k in range(n + 1))

D = [1, 0]                           # D(0) = 1, D(1) = 0
for n in range(2, 21):
    D.append((n - 1) * (D[n - 1] + D[n - 2]))

print(" n  brute formula round(n!/e)   D(n)/n!")
for n in range(1, 9):
    brute = sum(1 for p in permutations(range(n))
                if all(p[i] != i for i in range(n)))
    r = round(factorial(n) / e)
    assert brute == D_formula(n) == D[n] == r
    print(f"{n:2} {brute:6} {D[n]:7} {r:8}   {float(Fraction(D[n], factorial(n))):.6f}")

print("D(20) =", D[20], "| float round(20!/e) =", round(factorial(20) / e))
print("1/e   =", f"{1 / e:.6f}")

random.seed(49)                      # secret gift draw, 10 people
trials, hits = 20000, 0
for _ in range(trials):
    names = list(range(10))
    random.shuffle(names)
    hits += all(names[i] != i for i in range(10))
print("simulated P(no one draws own name), n=10:", hits / trials)
print("exact:", Fraction(D[10], factorial(10)), "=", f"{D[10] / factorial(10):.6f}")

 n  brute formula round(n!/e)   D(n)/n!
 1      0       0        0   0.000000
 2      1       1        1   0.500000
 3      2       2        2   0.333333
 4      9       9        9   0.375000
 5     44      44       44   0.366667
 6    265     265      265   0.368056
 7   1854    1854     1854   0.367857
 8  14833   14833    14833   0.367882
D(20) = 895014631192902121 | float round(20!/e) = 895014631192902144
1/e   = 0.367879
simulated P(no one draws own name), n=10: 0.37015
exact: 16481/44800 = 0.367879

৬ · সংখ্যাতত্ত্বে চালনি — Euler-এর φ আর Legendre-এর সূত্র

সেকশন ১-এর complement প্রশ্নটি, “1 থেকে x-এর মধ্যে কয়টি সংখ্যা কয়েকটি মৌলিক সংখ্যার কোনোটি দিয়েই বিভাজ্য নয়”, সংখ্যাতত্ত্বের একটি মৌলিক হাতিয়ার। এর নামই চালনি (sieve): খারাপ সংখ্যাগুলো ছেঁকে ফেলে বাকিগুলো গোনা।

প্রমাণ। A_i = p_i-এর গুণিতক। আলাদা মৌলিক সংখ্যার একটি দল দিয়ে একসঙ্গে বিভাজ্য হওয়া মানে তাদের গুণফল দিয়ে বিভাজ্য হওয়া (unique factorization, পর্ব ২০), তাই T-তে থাকা সেটগুলোর ছেদের আকার ⌊x/∏p_i⌋. উপপাদ্য ২.২ বসালেই হয়। ∎

Euler-এর φ, দ্বিতীয় প্রমাণ

পর্ব ২৪ “Fermat-এর ছোট উপপাদ্য আর Euler-এর totient”-এ φ(n) = n ∏(1 − 1/p) প্রমাণ হয়েছে multiplicative ধর্ম আর CRT দিয়ে। Inclusion–exclusion একটি সরাসরি দ্বিতীয় প্রমাণ দেয়।

1. k ∈ {1, …, n} n-এর সঙ্গে সহমৌলিক ঠিক তখন, যখন কোনো p_i k-কে ভাগ করে না। — gcd আর মৌলিক উৎপাদক
2. প্রতিটি p_i n-কে ভাগ করে, তাই প্রতিটি গুণফল d = ∏_i∈T p_i-ও n-কে ভাগ করে, আর ⌊n/d⌋ = n/d নির্ভুলভাবে, কোনো floor-এর ক্ষতি নেই। — বিভাজ্যতা
3. লেমা ৬.১-এ φ(n) = ∑_T (−1)^|T| n/∏_i∈T p_i. — লেমা ৬.১
4. গুণফল (1 − 1/p₁) ⋯ (1 − 1/p_r) খুললে প্রতিটি T ⊆ {1, …, r}-এর জন্য ঠিক একটি পদ (−1)^|T|/∏_i∈T p_i আসে; n দিয়ে গুণ করলে ধাপ ৩-এর যোগফল। ∎ — distributive নিয়ম

যেমন 60 = 2² · 3 · 5: φ(60) = 60 − (30 + 20 + 12) + (10 + 6 + 4) − 2 = 16, আর 60 · (1/2)(2/3)(4/5) = 16. ধাপ ২-টি গুরুত্বপূর্ণ: x যখন গুণফলগুলোর গুণিতক নয় (যেমন সেকশন ১-এ x = 100, d = 3), তখন floor থেকে যায়, আর গুণফলের সুন্দর রূপ আর মেলে না; 100 · (1/2)(2/3)(4/5) = 26.67, অথচ আসল উত্তর 26.

Legendre-এর সূত্র — মৌলিক সংখ্যা গোনা

পর্ব ২০-এর Eratosthenes-এর চালনি-র মূল তথ্য: x-এর সমান বা ছোট একটি যৌগিক সংখ্যার অন্তত একটি মৌলিক উৎপাদক √x-এর সমান বা ছোট। তাই √x পর্যন্ত মৌলিক সংখ্যাগুলোর গুণিতক ছেঁকে ফেললে 1 থেকে x-এ বাকি থাকে শুধু 1 আর √x-এর চেয়ে বড় মৌলিক সংখ্যাগুলো। π(x) = x পর্যন্ত মৌলিক সংখ্যার সংখ্যা ধরলে লেমা ৬.১ থেকে আসে Legendre-এর সূত্র:

π(x) − π(√x) + 1 = ∑_{T ⊆ {p ≤ √x}} (−1)^|T| ⌊x / ∏_p∈T p⌋

বাঁ পাশের +1 হলো সংখ্যা 1, যা কোনো মৌলিক দিয়ে বিভাজ্য নয় অথচ মৌলিকও নয়; আর −π(√x) কারণ ছোট মৌলিকগুলো নিজেরাই ছাঁকা পড়েছে। x = 100-এ √x = 10, মৌলিক 2, 3, 5, 7: ডান পাশ 100 − (50 + 33 + 20 + 14) + (16 + 10 + 7 + 6 + 4 + 2) − (3 + 2 + 1 + 0) + 0 = 22, তাই π(100) = 22 − 1 + 4 = 25, যা পর্ব ২০-এর সারণির সঙ্গে মেলে। নিচের ব্লক φ আর π(x) দুটিই যাচাই করে, আর দেখায় সূত্রটি কোথায় অকেজো হয়।

from itertools import combinations
from math import gcd, isqrt, prod

def primes_upto(x):
    return [p for p in range(2, x + 1) if all(p % q for q in range(2, isqrt(p) + 1))]

def avoid_count(x, ps):              # how many of 1..x are divisible by no p in ps
    total = 0
    for k in range(len(ps) + 1):
        for S in combinations(ps, k):
            total += (-1) ** k * (x // prod(S))
    return total

def phi_ie(n):
    ps = [p for p in primes_upto(n) if n % p == 0]
    return avoid_count(n, ps), ps

for n in (60, 360, 1001, 2026):
    v, ps = phi_ie(n)
    by_gcd = sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)
    print(f"phi({n}) primes {ps}: by I-E {v}, by gcd {by_gcd}")

for x in (100, 1000, 10000):         # Legendre: count survivors of the sieve
    small = primes_upto(isqrt(x))
    print(f"x={x}: {len(small)} small primes, {2 ** len(small)} terms", end="")
    if len(small) > 12:
        print(" -> too many terms, stop")
        continue
    left = avoid_count(x, small)     # 1 and the primes in (sqrt x, x]
    pi_x = left - 1 + len(small)
    print(f", survivors {left}, pi(x) = {pi_x} (direct {len(primes_upto(x))})")

phi(60) primes [2, 3, 5]: by I-E 16, by gcd 16
phi(360) primes [2, 3, 5]: by I-E 96, by gcd 96
phi(1001) primes [7, 11, 13]: by I-E 720, by gcd 720
phi(2026) primes [2, 1013]: by I-E 1012, by gcd 1012
x=100: 4 small primes, 16 terms, survivors 22, pi(x) = 25 (direct 25)
x=1000: 11 small primes, 2048 terms, survivors 158, pi(x) = 168 (direct 168)
x=10000: 25 small primes, 33554432 terms -> too many terms, stop

৭ · ঊর্ধ্বসীমাসহ সমাধান, Bonferroni অসমতা আর পরীক্ষার অঙ্ক

ঊর্ধ্বসীমাসহ পূর্ণসংখ্যার সমাধান। পর্ব ৩৫-এ stars and bars দিয়ে দেখেছেন, x₁ + … + x_n = r-এর অঋণাত্মক পূর্ণসংখ্যা সমাধান C(r + n − 1, n − 1)টি, আর ঊর্ধ্বসীমা থাকলে একটি যোগ-বিয়োগের সূত্র দেখেছেন, প্রমাণ ছাড়া। এখন প্রমাণটি সহজ।

প্রমাণ। U = সীমা ছাড়া সব অঋণাত্মক সমাধান। খারাপ ধর্ম A_i: x_i ≥ u + 1. নির্দিষ্ট j-টি চলকে আগেই u + 1 করে বসিয়ে দিলে (y_i = x_i − (u + 1)) বাকি যোগফল r − j(u + 1), যার সমাধান stars and bars-এ C(r − j(u + 1) + n − 1, n − 1), কোন j-টি তার ওপর নির্ভর না করে। প্রতিসম রূপ বসালেই হয়। ∎

উদাহরণ: বাজারঘর ১২টি একই রকম উপহার-বাক্স ৪টি জেলার গুদামে রাখবে, কোনো গুদামে ৫টির বেশি জায়গা নেই। উত্তর C(15, 3) − 4 · C(9, 3) + 6 · C(3, 3) = 455 − 336 + 6 = 125; j = 3-এ 12 − 18 < 0, পদ নেই।

Bonferroni অসমতা — মাঝপথে থামলে কী হয়

সেকশন ১-এ দেখেছেন, চলতি যোগফল 103, 71, 74: একবার বেশি, একবার কম। এটি সবসময় ঘটে।

প্রমাণের রূপরেখা উপপাদ্য ২.১-এর মতোই: r-টি সেটে থাকা উপাদানের অবদান ∑_k=1^t (−1)^k+1C(r, k), আর Pascal-এর নিয়ম দিয়ে t-এর ওপর induction-এ দেখানো যায় এটি 1 − (−1)^tC(r − 1, t), তাই t বিজোড় হলে ≥ 1, জোড় হলে ≤ 1. প্রথম অসমতা |∪| ≤ S₁-ই সম্ভাবনায় union bound, যা মডিউল ৭-এ বারবার কাজে লেগেছে। বড় সমস্যায় সব 2ⁿটি পদ হিসাব করা অসম্ভব হলে প্রথম দুই-তিনটি পদ দিয়ে উত্তরকে দুই দিক থেকে আটকানো যায়। নিচের ব্লক উপহার-বাক্সের হিসাব আর তিনটি N-এ Bonferroni সীমা যাচাই করে।

from itertools import product
from math import comb

def bounded(r, n, u):                # x1+...+xn = r, 0 <= xi <= u
    total = 0
    for j in range(n + 1):
        rest = r - j * (u + 1)       # j boxes forced to hold u+1 or more
        if rest >= 0:
            total += (-1) ** j * comb(n, j) * comb(rest + n - 1, n - 1)
    return total

def brute(r, n, u):
    return sum(1 for t in product(range(u + 1), repeat=n) if sum(t) == r)

print("12 boxes, 4 depots, at most 5 each:")
for j in range(3):
    print(f"  j={j}: {(-1) ** j} * C(4,{j}) * C({12 - 6 * j + 3},3) ="
          f" {(-1) ** j * comb(4, j) * comb(12 - 6 * j + 3, 3)}")
print("  formula", bounded(12, 4, 5), "brute", brute(12, 4, 5))

print("Bonferroni, multiples of 2, 3, 5 up to N:")
for N in (30, 100, 1000):
    S1 = N // 2 + N // 3 + N // 5
    S2 = N // 6 + N // 10 + N // 15
    S3 = N // 30
    union = sum(1 for x in range(1, N + 1) if x % 2 == 0 or x % 3 == 0 or x % 5 == 0)
    print(f"  N={N}: S1={S1} >= {union} >= S1-S2={S1 - S2};"
          f" S1-S2+S3={S1 - S2 + S3}")

12 boxes, 4 depots, at most 5 each:
  j=0: 1 * C(4,0) * C(15,3) = 455
  j=1: -1 * C(4,1) * C(9,3) = -336
  j=2: 1 * C(4,2) * C(3,3) = 6
  formula 125 brute 125
Bonferroni, multiples of 2, 3, 5 up to N:
  N=30: S1=31 >= 22 >= S1-S2=21; S1-S2+S3=22
  N=100: S1=103 >= 74 >= S1-S2=71; S1-S2+S3=74
  N=1000: S1=1033 >= 734 >= S1-S2=701; S1-S2+S3=734

অঙ্ক ১: তিন শর্তের গণনা

১ থেকে ১০০০-এর মধ্যে কয়টি সংখ্যা 2, 3, 5 বা 7-এর কোনোটি দিয়েই বিভাজ্য নয়?

1. S₁ = 500 + 333 + 200 + 142 = 1175.
2. S₂ = ⌊1000/6⌋ + ⌊1000/10⌋ + ⌊1000/14⌋ + ⌊1000/15⌋ + ⌊1000/21⌋ + ⌊1000/35⌋ = 166 + 100 + 71 + 66 + 47 + 28 = 478.
3. S₃ = ⌊1000/30⌋ + ⌊1000/42⌋ + ⌊1000/70⌋ + ⌊1000/105⌋ = 33 + 23 + 14 + 9 = 79; S₄ = ⌊1000/210⌋ = 4.
4. উত্তর 1000 − 1175 + 478 − 79 + 4 = 228 (scratch-এ brute force-এ মেলানো)।

অঙ্ক ২: onto আর derangement

(ক) ৬টি আলাদা অর্ডার ৩ জন রাইডারে, প্রত্যেকে অন্তত একটি: কয় উপায়ে? (খ) ৬ জনের উপহার বিনিময়ে কারও নিজের নাম না ওঠার সম্ভাবনা?

1. (ক) 3⁶ − 3 · 2⁶ + 3 · 1⁶ − 0 = 729 − 192 + 3 = 540; S(6, 3) = 540/6 = 90.
2. (খ) D₆ = 6 · D₅ + 1 = 6 · 44 + 1 = 265, তাই 265/720 = 53/144 ≈ 0.3681, 1/e-এর খুব কাছে।

যুক্তির ভুল ধরুন: “চিহ্নের গোলমাল”

একজন লিখলেন: “৫টি অর্ডার ৩ জন রাইডারে, সবাই অন্তত একটি। মোট 3⁵ = 243. একজন বাদ পড়ার বণ্টন 3 · 2⁵ = 96 বাদ দিই, দুজন বাদ পড়ার বণ্টন 3 · 1⁵ = 3-ও বাদ দিই, কারণ সেগুলোও খারাপ। উত্তর 243 − 96 − 3 = 144.”

ভুল কোথায়: “দুজন বাদ” এমন বণ্টন, যেমন সব অর্ডার রাইডার ১-এর কাছে, “২ বাদ” আর “৩ বাদ” দুই সেটেই আছে, তাই 96-এর ভেতরে সেটি ইতিমধ্যে দুবার বাদ গেছে। আবার বাদ দিলে তিনবার বাদ পড়ে। সঠিক কাজ হলো ফেরত যোগ করা: 243 − 96 + 3 = 150. প্রতিকার: চিহ্ন মুখস্থ না করে একটি উপাদান বেছে দেখুন সে মোট কতবার গোনা হলো; শেষ ফল 1 (ভালো হলে 0) না হলে সূত্রে ভুল আছে। ছোট ক্ষেত্রে brute force-এ মিলিয়ে নিলেও ভুলটি সঙ্গে সঙ্গে ধরা পড়ে।

৮ · AI-এর যুগে — inclusion–exclusion-এর হিসাব যাচাই

Inclusion–exclusion-এর প্রশ্নে AI সহকারী সাধারণত ঠিক সূত্রটির নাম বলে, কিন্তু চিহ্ন, শেষ পদ বা ছেদের আকারে ভুল করে। ভুল চিহ্নে উত্তর প্রায়ই “বিশ্বাসযোগ্য” আকারের থাকে, তাই চোখে পড়ে না। যে ভুলগুলো নিয়মিত দেখা যায়:

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

• U, N আর প্রতিটি খারাপ ধর্ম স্পষ্ট লেখা আছে কি না দেখেছি
• প্রতিটি k-এর ছেদের আকার নিজে একবার হিসাব করেছি
• চিহ্ন পালাক্রমে বদলেছে, আর শেষ পদ (−1)ⁿS_n আছে কি না দেখেছি
• ছোট ক্ষেত্রে Python-এ brute force দিয়ে উত্তর মিলিয়েছি
• বড় সংখ্যায় int বা Fraction দিয়ে হিসাব করেছি, float নয়
• উপপাদ্যের শর্ত (সসীম সেট, আলাদা মৌলিক, m, n ≥ 1) মিলিয়েছি
• সাল আর নাম বিশ্বস্ত উৎসে মিলিয়েছি

এই বিষয়ে যাচাই সস্তা: কয়েক লাইনের itertools ছোট ক্ষেত্রে সব বস্তু গুনে ফেলে। কিন্তু মনে রাখুন, ছোট ক্ষেত্রে মিল একটি জাল, প্রমাণ নয়; প্রমাণ আসে “প্রতিটি উপাদান ঠিক একবার” যুক্তি থেকে।