পারমুটেশন

Permutations

৭ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

পারমুটেশন (Permutation) মানে ক্রমবিন্যাস — যেখানে বস্তুর সাজানোর ক্রম গুরুত্বপূর্ণ।
$n$টি ভিন্ন বস্তু থেকে $r$টি বেছে সাজানোর সংখ্যা: $P(n,r) = \dfrac{n!}{(n-r)!}$।
সবগুলো $n$টি বস্তু সাজানোর মোট উপায়: $n!$ (n ফ্যাক্টরিয়াল)।
যদি পুনরাবৃত্তি অনুমোদিত হয় (একই বস্তু একাধিকবার ব্যবহার করা যায়), তাহলে মোট উপায় $n^r$।
গত পাঠের (L12) গুণের নিয়মেরই এটি একটি সরাসরি, নাম-দেওয়া প্রয়োগ — প্রতিটি স্থান বাছাইয়ের পর বাকি বিকল্প এক করে কমে।

এই পাঠে যা শিখবেন

পারমুটেশনের সংজ্ঞা এবং $P(n,r)$ সূত্র কীভাবে আসে
$n!$ (ফ্যাক্টরিয়াল) — সবগুলো বস্তু সাজানোর গণনা
পুনরাবৃত্তিসহ পারমুটেশন ($n^r$) — কখন এটি প্রযোজ্য
Python-এর math.perm ও itertools.permutations দিয়ে হাতে-করা গণনা যাচাই

১ · পারমুটেশন মানে ক্রম গুরুত্বপূর্ণ

গত পাঠে (L12) আমরা দেখেছি গুণের নিয়ম কীভাবে স্বাধীন ধাপ গোনে। কিন্তু কিছু কাউন্টিং সমস্যায় ধাপগুলো সম্পূর্ণ স্বাধীন নয় — একটি বস্তু একবার বাছাই হলে সেটি আর দ্বিতীয়বার বাছাই করা যায় না। এই ধরনের অর্ডার-সংবেদনশীল, পুনরাবৃত্তি-ছাড়া গণনাকে বলা হয় PermutationPermutation (পারমুটেশন)একটি সসীম সেটের বস্তুর একটি ক্রমবিন্যাস — যেখানে বস্তুর সাজানোর ক্রম গুরুত্বপূর্ণ এবং প্রতিটি বস্তু সর্বোচ্চ একবার ব্যবহৃত হয়।।

$n$টি ভিন্ন বস্তু থেকে $r$টি বেছে সাজানোর সংখ্যা $P(n,r)$ দিয়ে লেখা হয়। গুণের নিয়ম দিয়ে সরাসরি এটি বের করা যায়: প্রথম স্থানের জন্য $n$টি বিকল্প, দ্বিতীয় স্থানের জন্য $n-1$টি (একজন ইতিমধ্যে বাছাই), তৃতীয় স্থানের জন্য $n-2$টি — এভাবে $r$টি স্থান পর্যন্ত।

$P(n,r)$ সূত্র

$$P(n,r) = n \times (n-1) \times (n-2) \times \cdots \times (n-r+1) = \frac{n!}{(n-r)!}$$

২ · উদাহরণ — $P(5,3)$

ধরুন ৫ জন প্রতিযোগী থেকে ১ম, ২য়, ৩য় স্থান বিজয়ী বেছে নিতে হবে (ক্রম গুরুত্বপূর্ণ — কে ১ম আর কে ৩য় তা আলাদা)। মোট উপায়:

সমাধান

$$P(5,3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{120}{2} = 60$$

সরাসরি গুণের নিয়মেও যাচাই করা যায়: প্রথম স্থানের জন্য ৫ উপায়, দ্বিতীয় স্থানের জন্য ৪ উপায় (একজন বাদ), তৃতীয় স্থানের জন্য ৩ উপায় (দুইজন বাদ) — $5 \times 4 \times 3 = 60$। দুইভাবেই একই উত্তর।

৩ · $n!$ — সবগুলো বস্তু সাজানো

যদি $r=n$ হয় (অর্থাৎ সবগুলো বস্তুই সাজাতে হবে), তাহলে $P(n,n) = \dfrac{n!}{0!} = n!$ (যেহেতু $0!=1$)। একে বলা হয় ফ্যাক্টরিয়ালFactorial (n!)$n! = n \times (n-1) \times \cdots \times 2 \times 1$, এবং সংজ্ঞানুসারে $0!=1$। $n$টি ভিন্ন বস্তু সাজানোর মোট উপায়ের সংখ্যা। — যেমন ৫ জন মানুষকে একটি লাইনে দাঁড় করানোর মোট উপায় $5! = 120$।

৪ · পুনরাবৃত্তিসহ পারমুটেশন

উপরের সূত্র ধরে নেয় প্রতিটি বস্তু সর্বোচ্চ একবার ব্যবহৃত হয়। কিন্তু যদি পুনরাবৃত্তি অনুমোদিত হয় — যেমন একটি ৪-ডিজিটের পিন কোড যেখানে প্রতিটি ডিজিট (০-৯) যেকোনো স্থানে পুনরায় ব্যবহার করা যায় — তাহলে প্রতিটি স্থানের বিকল্প সংখ্যা সবসময় $n$-ই থাকে, কমে না। মোট উপায় হয় $n^r$।

পুনরাবৃত্তি ছাড়া
$P(n,r) = n!/(n-r)!$ — প্রতিটি বাছাইয়ের পর বিকল্প কমে।

পুনরাবৃত্তিসহ
$n^r$ — প্রতিটি স্থানে সবসময় $n$টি বিকল্প থাকে।

Python

import math
import itertools

n, r = 5, 3

by_formula = math.perm(n, r)
by_enum = len(list(itertools.permutations(range(n), r)))

print(f"P({n},{r}) সূত্র দিয়ে (math.perm):", by_formula)
print(f"P({n},{r}) সরাসরি গণনা করে (itertools):", by_enum)
print("দুটো পদ্ধতি মিলে গেছে:", by_formula == by_enum)

math.perm(n, r) সরাসরি $P(n,r)$ সূত্র হিসাব করে, আর itertools.permutations(range(n), r) প্রতিটি সম্ভাব্য ক্রমবিন্যাস আসলেই তৈরি করে গোনে — দুটো ভিন্ন পদ্ধতি একই উত্তর ($60$) দেয়, যা সূত্রটির সঠিকতা নিশ্চিত করে।

মূল কথা · Key takeaway

পারমুটেশন হলো "ক্রম গুরুত্বপূর্ণ, পুনরাবৃত্তি নেই" এই দুই শর্তের কাউন্টিং। পরের পাঠে (L14) আমরা দেখব যখন ক্রম গুরুত্বপূর্ণ নয় — শুধু কোন বস্তুগুলো বাছাই হলো তা গুরুত্বপূর্ণ — তখন কম্বিনেশন ব্যবহার হয়, যা পারমুটেশনেরই একটি সরল রূপান্তর।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ ৮ জন শিক্ষার্থী থেকে ৩ জনকে বেছে একটি সভাপতি, সহ-সভাপতি ও সম্পাদক পদে বসাতে হবে (প্রতিটি পদ ভিন্ন)। এখানে পারমুটেশন নাকি কম্বিনেশন প্রযোজ্য, এবং উত্তর কত?

মূল উত্তর — পারমুটেশন। কারণ প্রতিটি পদ ভিন্ন — কে সভাপতি আর কে সম্পাদক তা গুরুত্বপূর্ণ, তাই ক্রম গুরুত্বপূর্ণ। $P(8,3) = \dfrac{8!}{5!} = 8 \times 7 \times 6 = 336$।

যদি প্রশ্নটি হতো "৩ জনের একটি কমিটি বেছে নিন" (কোনো পদ ছাড়া, শুধু কারা কমিটিতে থাকবে), তখন এটি কম্বিনেশন হতো — পরের পাঠে (L14) এই পার্থক্যটি বিস্তারিত দেখব।

প্র ০২ একটি ৪-ডিজিটের ATM পিন কোডে প্রতিটি ডিজিট (০-৯) পুনরাবৃত্তি হতে পারে। মোট কতগুলো ভিন্ন পিন কোড সম্ভব, এবং এটি কেন $P(n,r)$ সূত্র দিয়ে নয়?

মোট $10^4 = 10{,}000$টি পিন কোড সম্ভব। এটি $P(n,r)$ সূত্র দিয়ে নয়, কারণ $P(n,r)$ ধরে নেয় প্রতিটি বস্তু সর্বোচ্চ একবার ব্যবহৃত হয় (একবার বাছাই হলে বিকল্প কমে যায়)। কিন্তু পিন কোডে একই ডিজিট একাধিকবার আসতে পারে (যেমন "1122" বৈধ) — তাই প্রতিটি স্থানের বিকল্প সংখ্যা সবসময় $10$-ই থাকে, এবং সূত্র হয় $n^r = 10^4$।

প্র ০৩ কেন $0! = 1$ বলে সংজ্ঞায়িত করা হয়, শূন্য নয়? এই সংজ্ঞা $P(n,n)=n!$ সূত্রের সাথে কীভাবে সামঞ্জস্যপূর্ণ?

$0!=1$ একটি কনভেনশন যা কাউন্টিং সূত্রগুলোকে সামঞ্জস্যপূর্ণ রাখে। ভাবুন — "শূন্যটি বস্তু সাজানোর কতভাবে যায়?" উত্তর হলো ঠিক ১ উপায় — "কিছু না করা", যা একটি বৈধ, একক ফলাফল। যদি $0!=0$ হতো, তাহলে $P(n,n) = n!/0! = n!/0$ হয়ে যেত অসংজ্ঞায়িত (division by zero) — যা কাউন্টিংয়ের জন্য অর্থহীন।

$0!=1$ সংজ্ঞা দিয়ে $P(n,n) = n!/0! = n!/1 = n!$ ঠিক আমাদের প্রত্যাশিত ফলাফল দেয় — সবগুলো $n$টি বস্তু সাজানোর মোট উপায় $n!$।

অনুশীলন

গণনা করুন: একটি দৌড় প্রতিযোগিতায় ৬ জন অংশ নেয়। ১ম, ২য়, ৩য় স্থান কতভাবে বিতরণ করা যায় (ধরুন কোনো টাই নেই)?

এটি $P(6,3)$: $\dfrac{6!}{3!} = 6 \times 5 \times 4 = 120$টি উপায়।
যাচাই করুন: উপরের কোড সেলে n, r = 5, 3 পরিবর্তন করে n, r = 6, 3 বসান এবং হাতে-হিসাব করা $120$-এর সাথে কোড আউটপুট মিলিয়ে দেখুন।

math.perm(6, 3) এবং len(list(itertools.permutations(range(6), 3))) — দুটোই $120$ প্রিন্ট করা উচিত। যদি না মেলে, নিশ্চিত করুন range(n)-এর n ঠিক বসিয়েছেন, range(r) নয় — itertools.permutations-এ প্রথম আর্গুমেন্ট হলো মোট বস্তুর সেট।