বিন্যাসে হাতেখড়ি | Basics of Permutation

ছোটবেলা থেকেই কিন্তু মনের অজান্তে আমরা বিন্যাস ব্যবহার করে আসছি। কখনো নিজের নামের অক্ষরগুলো নিয়ে, কখনো নাম্বার ঘুরিয়ে ঘুরিয়ে ব্রিফকেস বা লাগেজের লক খুলতে গিয়ে আবার কখনো বা নিজের ফোনের লক স্ক্রিনের পাসওয়ার্ড ভুলে গেলে! এমনকি বন্ধুর মোবাইল নাম্বার ভুলে গেলে অনেক সময় বিন্যাস এর কনসেপ্ট কাজে লাগিয়ে নাম্বার বের করার চেষ্টা করেছি!

Photo by James Sutton on Unsplash

বিন্যাসকে ইংরেজিতে আমরা বলি পারমিউটেশন। কম্পিউটার সায়েন্স, স্ট্যাটিস্টিকস, ডাটা সায়েন্স সহ আরো ডিমান্ডিং সাব্জেক্টগুলি পড়তে গেলে বিন্যাস বা পারমিউটেশনের কন্সেপ্ট খুব কাজে আসবে। এমনকি ব্যক্তিগত জীবনেও বিন্যাস - সমাবেশের কনসেপ্ট জানা খুবই জ্রুরি।

সহজ কথায়, বিন্যাস হলো নির্দিষ্ট সংখ্যক জিনিস নিয়ে তাদেরকে নিজেদের মধ্যে যতভাবে পারা যায় ততভাবে সাজানো।

তোমার নামের অক্ষরগুলির কথাই না হয় ভাব। কত উপায়ে তোমার নাম সাজিয়ে লেখা যায় বলতে পারবে? তোমার ডাকনাম যদি ৩/৪ অক্ষরের হয়ে থাকে তাহলে হয়তো খাতায় একটু কলম ঘষাঘষি করে বলে দিতে পারবে। যেমন, RAJ নামটির কথা চিন্তা কর। কিকি হতে পারে রাজ থেকে? চলো দেখা যাক - RAJ, RJA, ARJ, AJR, JRA & JAR। এইতো, এই ৬টি বিন্যাস সম্ভব। সহজ তো!

 কিন্তু তোমার নাম যদি হয় SHAKIL, তাহলে কি আদৌ বলতে পারবে? গুনে গুনে বলাটা সহজ হবে না কারণ, এই নামের ৭২০ টি বিন্যাস সম্ভব!

বিন্যাস এর সমস্যাগুলি বুঝতে হলে সবসময় মনে মনে কিছু পাশাপাশি রাখা ফাকা বক্সের কথা ভাববে। যতগুলো, জিনিস নিয়ে বিন্যাস করবে ঠিক ততগুলো বক্সের কথা কল্পনা করবে। এরপর কোন বক্সে কয়টি করে জিনিস বসাতে পারবে তা ঠিক করে ফেলবে। SHAKIL নামের অক্ষরগুলি সাজাতে তুমি ৬টি বক্সের কথা চিন্তা করো। প্রথম বক্সে তুমি যদি 'S', 'H', 'A', 'K', 'I' এবং 'L' থেকে একটি অক্ষর নাও, ধরো, 'S' নাও তাহলে, পরের বক্সে বসানোর জন্য তোমাকে 'H', 'A', 'K', 'I' এবং 'L' থেকে একটি অক্ষর সিলেক্ট করতে হবে। এখানে কিন্তু তোমার হাতে আর আগের মতো ৬টি অপশন নেই। তাই বাকি ৫টি থেকে তুমি একটি অক্ষর নিবে। ধরো, 'H' সিলেক্ট করলে। এবার তৃতীয় বাক্সটির জন্য তাহলে থাকলো 'A', 'K', 'I' এবং 'L'। তৃতীয় বাক্সে একটি অক্ষর রাখলে চতুর্থ বাক্সে রাখার জন্য অবশ্যই তোমাকে ৩টি অক্ষর থেকে ১টি সিলেক্ট করতে হবে। এভাবে ৫ম ও ষষ্ঠ বাক্সে একটি করে অক্ষর রাখতে চাইলে হাতে অপশন থাকবে যথাক্রমে ২টি ও ১টি। তাহলে তুমি মোট 6×5×4×3×2×1 বা 6! উপায়ে বক্সের মধ্যে অক্ষরগুলো সাজাতে পারবে।

৬ থেকে ১ পর্যন্ত গুন দেওয়ার ব্যপারটা যদি এখনো পরিষ্কার না হয়ে থাকে তাহলে বলব আরেকটু চিন্তা করতে। সহজ ভাবে মনে রাখ, প্রত্যেকটি ফাঁকা বক্সে যতগুলি সংখ্যক জিনিস বসতে পারবে সেই সংখ্যাগুলি বের করে গুন দিলেই বিন্যাস এর উত্তর পেয়ে যাবে। 

লক্ষ করো, এখানে কিন্তু তুমি ৬টি অক্ষর থেকে প্রতিবারে ৬টি করে নিয়েই সাজাচ্ছো। কিন্তু যদি তোমাকে এই ৬টি লেটার থেকে প্রতিবারে ৩টি করে নিয়ে সাজাতে বলা হয় তাহলে কতগুলো বিন্যাস করা সম্ভব? এক্ষেত্রে বক্স হবে ৩টি -

বুঝতেই পারছ এবার তাহলে বিন্যাস সংখ্যা হচ্ছে -

তাহলে, n সংখ্যক জিনিস হতে r সংখ্যক জিনিস নিয়ে বিন্যাস করলে nPr কেনো হয় তা নিশ্চয়ই পরিষ্কার হল।

এবারে যদি আরেকটু পরিবর্তন এনে জানতে চাই যে RAHAT নামটির অক্ষরগুলো নিয়ে বিন্যাস করলে উত্তর কতো হবে? এখানে ৫টি লেটারের জন্য 5! বা 120 উত্তর বলে দিলে কিন্তু হবে না। এর বিন্যাস সংখ্যা হবে 60টি। খেয়াল করো, এখানে কিন্তু A দুবার এসেছে। A দুটো যদি নিজেদের জায়গা অদলবদল করে তাহলে কিন্তু একই শব্দই থাকছে কিন্তু পূর্বের নিয়মে আমরা দুটি ভিন্ন বিন্যাস পাচ্ছি। অতএব, বুঝেছ হয়তো যে পূর্বের নিয়মে বিন্যাস করলে যেব,পাবে তার মধ্যে একইরকম শব্দ অনেকগুলো চলে আসবে। সুতরাং, কিছু বিন্যাস বাদ দিতে হবে। শুধু এটুকু মনে রাখলেই চলবে যে, যতবার একটা লেটার রিপিট হবে তার ফ্যাক্টরিয়াল নিয়ে মোট বিন্যাস কে ভাগ দিতে হবে। এক্ষেত্রে যেহেতু দুটো A আছে তাই 5! কে 2! দিয়ে ভাগ দিলেই উত্তর চলে আসবে যা হলো 60। A যদি 3টি থাকতে তাহলে 3! দিয়ে ভাগ দিতে হতো। 

ধরো আবার যদি শব্দটি হতো ENGINEER, তাহলে? এখানে 2টি N ও 3টি E আছে। এক্ষেত্রে মোট বিন্যাস বা 8! কে 2!×3! দিয়ে ভাগ করলেই মোট সম্ভাব্য শব্দসংখ্যা পেয়ে যাবে। 2টি N এর জন্য 2! এবং 3টি E এর জন্য 3! দিয়ে ভাগ করা হলো।

এতকিছু বুঝে থাকলে এবার তাহলে তোমার কাছে একটি সহজ প্রশ্ন ছুড়ে দেই। প্রশ্ন না বলে তুমি এটাকে ধাঁধাঁও বলতে পারো। বিন্যাস সমাবেশ শেখানোর পর আমার যত ছাত্রছাত্রীকে প্রশ্নটি করেছি তার সিংহভাগই ভুল উত্তর দিয়েছে! নিচের ছবিটির তালাটি দেখো -

Photo by Everyday basics on Unsplash

এই ধরণের তালার সাথে সবাই কম বেশি পরিচিত। প্রত্যেকটি নাম্বারের হুইলে 0-9 পর্যন্ত ডিজিট রয়েছে আর পাশাপাশি তিনটি ডিজিটের সঠিক পাসওয়ার্ড পেলেই তালাটি খুলে যায়। মনে কর, তুমি তালাটির পাসওয়ার্ড জানো না কিন্তু তোমাকে তালাটি খুলতেই হবে। প্রশ্ন হচ্ছে, মোট কতবার পাসওয়ার্ড বসালে তালাটি এক না একবার অবশ্যই খুলে যাবে?

উত্তরটি দেখার আগে একটু ভাবো যে এখানে কি হতে পারে। বিন্যাসের কন্সেপ্টের সাথে এটা কিভাবে সম্পর্কিত, nPr দিয়ে এটা সমাধান করা আদৌ যাবে কিনা এসব নিয়ে ভাববে। যদি উত্তর পেয়ে গিয়েও থাকো তাহলে চেষ্টা কর বিন্যাসের কন্সেপ্ট ব্যবহার করে তোমার উত্তরকে ভেরিফাই করার।

উত্তরঃ এই ধাধার উত্তর খুজতে গিয়ে জটিল গানিতিক হিসাব নিকাশে যাবার কোনো দরকার নেই। এর উত্তর হবে ১০০০। হ্যা, তোমাকে ১০০০ বার চেষ্টা করতে হবে তালাটি খোলার জন্য! কারণ তিন ডিজিটের মোট সংখ্যা হলো ৯৯৯টি। এই ৯৯৯ টি সংখ্যার মধ্যে একটি সংখ্যা অবশ্যই পাসওয়ার্ড হবে। যেমন - '078', '105', '250', '987' ইত্যাদি। কিন্তু '000' এই সংখ্যাটিও তো পাসওয়ার্ড হতে পারে। সুতরাং, সম্ভাব্য পাসওয়ার্ড সংখ্যা ৯৯৯+১=১০০০। তাই তোমাকে ১০০০ বার চেষ্টা করতে হবে পাসওয়ার্ড ক্র্যাক করতে হলে।

এবার ফিরে আসি বিন্যাসে। এই সমস্যাটি কিন্তু বিন্যাসের কনসেপ্টের উপরেই দাঁড়িয়ে আছে। 0-9 পর্যন্ত 10টি ডিজিট আছে। এই দশটি ডিজিট থেকেই কিন্তু আমি ৩টা করে নিয়ে প্রতিবার সাজাচ্ছি। সুতরাং, 10P3 হবার কথা! তাই না? কিন্তু 10P3=720 হয়! তাহলে ভুলটা কোথায় হচ্ছে? 

এখানে বক্স আগের মতো ৩টি ই হবে তবে প্রত্যেকটি বক্সেই তুমি ১০টি করে সংখ্যা রাখতে পারবে। অর্থাৎ, বিন্যাস সংখ্যা হবে - 10×10×10 বা  বা 1000।  আগের মতো তুমি যদি 10×9×8 বসাও তবে কিন্তু এই বিন্যাসগুলো তুমি ইগ্নোর করছো - 111, 454, 800 ইত্যাদি। আমরা নামের লেটারগুলো নিয়ে যে বিন্যাস করা শিখেছি তাতে কিন্তু কখনো এভাবে লেটার রিপিট হয়নি যাতে করে 'SHAKIL' নামের কোনো বিন্যাস 'SSSSSS' হয়! আরেকটু ভালোভাবে বুঝতে নিচের চিত্রটি লক্ষ করো - 

তার মানে এই তালার সমস্যা থেকে যা বুঝলাম তা হলো, আমরা যদি n সংখ্যক জিনিস থেকে r সংখ্যক জিনিস নিয়ে সাজাই তাহলে -

• বিন্যাসে প্র্যতেকটি জিনিস ইউনিক হলে মোট বিন্যাস সংখ্যা - 
• বিন্যাসে জিনিসগুলি ইচ্ছামতো রিপিট হওয়ার সুযোগ থাকলে মোট বিন্যাস সংখ্যা - 

এখন আরেকটি প্রশ্ন - 1, 2, 3, 4, 5, 6 এ সংখ্যাগুলো থেকে ৩ অংকের কতগুলো বিজোড় সংখ্যা গঠন করা যায়? নিচে কিছু পড়ার আগে নিজে একবার ভেবে দেখো অঙ্কটি কিভাবে সমাধান করতে পারবে। এখানে কিন্তু বক্স থাকবে ৩টি এবং শেষের বক্সটিতে 1, 3, 5 এই তিনটির একটি বসবে যেহেতু বিজোড় সংখ্যা গঠন করতে বলা হয়েছে। প্রথমে, শেষের বক্সে 1 ফিক্সড করে রাখো। তাহলে ব্যাপারটা অনেকটা এরকম দারাচ্ছে - 

এক্ষেত্রে মোট বিন্যাস হবে - 

এভাবেই যদি আমরা একবার 3 কে এবং আরেকবার 5 কে শেষ বক্সে ফিক্সড রেখে দেই তাহলে একই রকম বিন্যাস সংখ্যা পাবো। তাহলে মোট বিন্যাস হচ্ছে -  

এবার আরো প্র্যাক্টিকাল কিছু প্রশ্ন করি - 

১। ৭টি চিঠি কত উপায়ে ৫টি পোস্ট অফিস থেকে পোস্ট করা যায়?

২। ১৩ টি আংটি কত উপায়ে দশটি আঙুলে পড়া যায়?

সমাধানঃ

১। 

২। 

ব্যাখ্যাঃ

প্রথমত, এখানে  প্রযোজ্য হবে এতে নিশ্চয়ই সন্দেহ নাই। কিন্তু কোনটিকে n ধরবে আর কোনটিকে r ধরবে? প্রথম ক্ষেত্রে, একটি পোস্ট অফিসে কিন্ত একাধিক চিঠি পোস্ট করা সম্ভব কিন্তু একটি ছিঠি কিন্তু একাধিক পোস্ট অফিসে তুমি পোস্ট করতে পারবে না। তাই চিঠি গুলো এখানে এক একটি বক্স হিসেবে বিবেচিত হবে এবং প্রত্যেকটি চিঠিকেই ৭টির মধ্যে যেকোনো একটি পোস্ট অফিসে পোস্ট করতে হবে। ব্যাপারটা এরকম -

তাহলে  কিভাবে হলো তা এবার বুঝেছ। একই ভাবে ২ নং সমস্যার থেত্রে চিন্তা করলে উত্তরের পেছনে ব্যাখ্যা নিজে থেকে দাড় করাতে পারবে।

এবারে চক্রাকার পারমিউটেশন (Cyclic Permutation) সম্পর্কে জানবো। ধরো, কোন অফিসের মিটিং বা কনফারেন্স রুমে গোল টেবিল আছে এবং গোল টেবিল ঘিরে ৬টি চেয়ার আছে। কত উপায়ে ৬ জন মানুষকে মিটিংএ সাজানো সম্ভব হবে?

উপরের চিত্রে কিন্তু একটিই বিন্যাস দুভাবে দেখানো হয়েছে। মনে রাখবে, চক্রাকার বিন্যাসের ক্ষেত্রে সবসময় একটি বিন্যাস অর্থ একটি ইউনিক চক্র! আমরা কিন্তু 'CBAFED' আর 'DCBAFE' কে এর আগে আলদা দুটি পারমিউটেশন হিসেবে দেখেছি। কিন্তু এখানে দেখো দুটোকে এক বলার কারণ হচ্ছে তাদের সিকুয়েন্স বা ক্রমটা কিন্তু একই। কারণ, দুই ক্ষেত্রেই A এর পরে আছে F, F এর পরে আছে E, E এর পরে D, তারপরে C আর C এরপরে আছে B আর এই B এর পরে আবার সেই A। এইভাবে কিন্তু এই একটি বিন্যাস মোট ৬ ভাবে লেখা যায় যার প্র্যকেক্টির সিকুয়েন্স এক। সেগুলো হলো - 

AFEDCB, FEDCBA, EDCBAF, DCBAFE, CBAFED ও BAFEDC। এতো গেলো মাত্র একভাবে সাজানো। তাহলে, মোট ইউনিক চক্রের সংখ্যা পেতে তোমাকে মোট বিন্যাস কে ৬ দিয়ে ভাগ করতে হবে যেহেতু প্রতি ৬টি সাজানো তে একটি ইউনিক চক্র পাই। সুতরাং, এখানে মোট বিন্যাস সংখ্যা - 

তাহলে n সংখ্যক জিনিস নিয়ে চক্রাকারে সাজালে মোট বিন্যাস সংখ্যা হবে -

 

চক্রাকার পারমিউটেশনের মধ্যে আবার একটি ব্যতিক্রমধর্মী সমস্যা থাকতে পারে। যদি জিজ্ঞাসা করি, n সংখ্যক স্বচ্ছ পার্ল (Pearl) বা পুতি ব্যবহার করে হাতের ব্রেসলেট কিংবা গলার নেকলেস মোট কত উপায়ে বানানো যাবে? এটাও কিন্তু Cyclic Permutation। কিন্তু এক্ষেত্রে  না হয়ে হবে  - 

এখানে পুতিগুলো কিন্তু দুই পাশ থেকেই দেখতে একইরকম লাগে। মানে আমাদের জামা-কাপড়ের মতো ব্রেসলেট বা নেকলেস এর এখানে সামনে পিছনে বলে কিছু নেই। দুটো র‍্যান্ডম বিন্যাসে দেখ - 'ABC' ও 'CBA'। এই দুটি নিজেদের প্রতিচ্ছবি। সামনে থেকে দেখলে দেখবে ABC আর পেছন থেকে দেখলে হয়তো CBA দেখবে। এরকম ভাবে চক্রাকারে পার্লগুলো সাজালেও তুমি প্রতিটি বিন্যাসের জন্য একটি করে প্রতিচ্ছবি পাবে। ধরো A, B, C - এই তিনটি পার্ল দিয়ে তুমি সাজাচ্ছ। তাহলে, ABC ক্রমে সাজালেই কিন্তু তুমি উলটা করে ব্রেসলেট দেখলে দেখবে CBA হয়ে গিয়েছে। কিন্তু সাজিয়েছো তুমি একবার। তাই মোট পারমিউটেশন যা হয় তাকে তুমি অবশ্যই দুই দিয়ে ভাগ করবে এক্ষেত্রে।

এবার প্রথমদিকের কিছু কন্সেপ্টের উপর বেইজড আরো কিছু সহজ প্রবলেম দেখো -

 

১। ELEPHANT শব্দটির অক্ষরগুলো সাজালে কতবার স্বরবর্ণগুলো একত্রে থাকবে?

২। INSTITUTE শব্দটি কতবার সাজালে ব্যঞ্জনবর্ণগুলো বিজোড় স্থানে অবস্থান করবে?

৩। 0, 1, 2, 3, 4, 5, 6 ডিজিটগুলো থেকে কতটি এমন চার অংকের জোড় সংখ্যা বানানো যাবে যা 5000 থেকে ছোট হবে?

৪। 0171 অথবা 0172 দিয়ে শুরু হয় কিন্তু শেষে 5 দিয়ে শেষ হয় এমন মোবাইল নাম্বারের সংখ্যা কতগুলো হতে পারে? (হিন্ট - বাংলাদেশে মোবাইল নাম্বার ১১ ডিজিটের হয়)

সমাধান - 

১। স্বরবর্ণগুলোকে যেহেতু একত্রে রাখতে হবে সেহেতু স্বরবর্ণগুলোকে একত্রে একটি অক্ষর ধরে নিব। ধরি - EEA = X। এবার, XLPHNT নিয়ে বিন্যাস করলে যেই প্যাটার্নগুলো পাবো তার প্রত্যেকটিতেই কিন্তু স্বরবর্ণগুলো একত্রে থাকছে। কারণ, X মানেই EEA! সুতরাং EEA কে একসাথে রেখে মোট 6! বা 720 ধরণের বিন্যাস সম্ভব! কিন্তু, স্বরবর্ণ সবসময় একসাথে থাকা মানে এই নয় যে প্রত্যেকবার E, E, A - এই ক্রমে থাকবে! E, A, E বা A,  E,  E এরকম ক্রমেও একসাথে থাকতে পারবে। তাই EEA নিজেরা কতবার বিন্যস্ত হতে পারে সেটাও কিন্তু জানা দরকার। EEA নিজেরা আবার নিজেদের মধ্যে 3!/2! 

উপায়ে বিন্যস্ত হতে পারে। তাহলে স্বরবর্ণগুলোকে একত্রে রেখে ELEPHANT শব্দটির মোট বিন্যাস সংখ্যা হবে - 

২। INSTITUTE শব্দটিতে লেটার আছে মোট 9টি (স্বরবর্ণ - 4টি, ব্যঞ্জনবর্ণ - 5টি)। এর মধ্যে আবার বিজোড় স্থান আছে ৫টি। চিত্রটি লক্ষ করো -

ব্যঞ্জনবর্ণ বিজোড় স্থানে রেখে  'INSTITUTE' এর বিন্যাস

জোড় স্থানগুলিতে স্বরবর্ণ বসানো যায় মোট 12 উপায়ে। আবার ব্যঞ্জনবর্ণগুলোকে বিজোড় স্থানে রাখা যায় 20 উপায়ে। অতএব, গুণ করে দিলেই মোট বিন্যাস সংখ্যা তুমি পেয়ে যাবে। উত্তর - 240।

৩। চার অংকের সংখ্যা ও পাচ হাজার থেকে ছোট হতে হলে অবশ্যই সংখ্যার প্রথম ডিজিটটি 5 থেকে ছোট হতে হবে। অর্থাৎ, প্রথম ডিজিট হতে পারবে - 1, 2, 3 অথবা 4 (প্রথম ডিজিট 0 হতে পারবে না)। এভাবে দ্বিতীয় ও তৃতীয় ডিজিটে তুমি প্রদত্ত 7 টি ডিজিট হতে যেকোনো ডিজিট বসাতে পারবে। আবার যেহেতু প্রশ্নে জোড় সংখ্যার কথা জানতে চাওয়া হয়েছে তাই শেষ ডিজিটটি অবশ্যই 0, 2, 4 অথবা 6 হবে। তাহলে বক্সের সেই আগের বক্সের কন্সেপ্ট ব্যবহার করলে - 

তাহলে, প্রদত্ত ডিজিটগুলি থেকে চার অংকের মোট জোড় সংখ্যা বানানো যাবে - 4×7×7×4 = 784টি।

৪। এই প্রশ্নের উত্তর তোমাদের নিজেদেরই দিতে পারার কথা। নিজে চেষ্টা করে না পারলে তাহলে সামনে পড়তে থাকো। বক্সের কন্সেপ্ট দিয়ে খুব সহজে উত্তর দিয়ে দেওয়া যায়। ১১ টা বক্স হবে যেহেতু মোবাইল নাম্বার ১১ডিজিটের হয় বাংলাদেশে। প্রথম তিনটি বক্স ও শেষের বক্সের ডিজিট কিন্তু ফিক্সড। তাহলে মাঝের ৭টি বক্স নিয়ে তুমি চিন্তা করো। এই সাতটি বক্সের মধ্যে আবার প্রথম বক্সে 1 অথবা 2 বসতে পারবে আর বাকিগুলোতে 0-9 এর মধ্য থেকে ইচ্ছামতো ডিজিট বসানো যাবে। তাহলে মোট বিন্যাস সংখ্যা বা মোবাইল নাম্বার সংখ্যা হবে - ।

বিন্যাস ও সমাবেশ গণিতের খুবই গুরুত্বপূর্ণ কনসেপ্ট যা হতে ম্যাথ অলিম্পিয়াড থেকে শুরু করে, SAT, GRE সহ বিভিন্ন প্রতিযোগিতামূলক পরীক্ষায় প্রশ্ন আসে। সমাবেশ (ইংরেজিতে Combination) এর বেসিক জানতে পড়ে ফেলো একটুখানি সমাবেশ - নোব্রেইনার স্কুল ! নতুন পোস্টের আপডেট মেইল এ পেতে ব্লগটি সাবস্ক্রাইব করো।