কম্বিনেটরিক্সের হাবিজাবি ১.১

আমাদের এক সহজাত প্রবৃত্তি হচ্ছে গুণতে বসে যাওয়া। বড় হতে শুরু করার আগেই আমরা তারা গণা শুরু করে দেই। আর তাই, গণিতের এক বিশাল শাখাই তৈরি হয়ে গেছে ‘কম্বিনেটরিক্স’ (Combinatorics) নামে। এই শাখায় আমরা বিন্যাস, সমাবেশ, সম্ভাব্যতা বের করার সমস্যা নিয়ে চিন্তিত হই। সমস্যার সমাধান করতে করতে গণিতের অন্যান্য শাখার সাথে এর যোগসূত্রও আমরা খুঁজে বের করে ফেলি। কম্বিনেটরিক্সের হাবিজাবি শিখতে শিখতে আমরা তাই হয়ে উঠব একেকজন ‘গণনবিদ’!

কম্বিনেটরিক্সের ব্যাপারস্যাপার বুঝাতে আর বুঝতে বাংলা ব্যবহার করলেও টেকনিক্যাল টার্মগুলো আমরা শিখব ইংরেজিতে। (কারণ, বেশিরিভাগ টার্মের পরিভাষা আমার জানা নেই। আর সবগুলো টার্মের পরিভাষা আদৌ আছে কিনা তাও জানি না!) তাহলে শুরু করা যাক আমাদের কম্বিযাত্রা!

প্রথমেই আমরা যেটার সাথে পরিচিত হব তা হচ্ছে string বা sequence বা word। কিছু নির্দিষ্ট উপাদানের তৈরি একটা সুনির্দিষ্ট ক্রমের তালিকাকেই আমরা string বলব। যাদের মাথার উপর দিয়ে যাচ্ছে তাদের উদ্দেশ্যে বলছি যে, হতাশ হওয়ার কিছু নেই। কারণ, প্রতিক্ষেত্রেই আমি পর্যাপ্ত উদাহরণ দেয়ার চেষ্টা করব। এখন, string এর উদাহরণ দেয়া যাক তবে!

1. ধরা যাক, ZERIN একটা শব্দ। আমরা যদি {E, I, N, R, Z} সেটটি বিবেচনা করি তাহলে দেখা যাবে যে শব্দটি এই সেটের উপাদানগুলো দিয়ে তৈরি। আবার, সেটের উপাদানগুলো উলটাপালটা বেছে নিয়ে কিন্তু আমরা ZERIN শব্দটি পাইনি। বরং আমাদের একটা নির্দিষ্ট ক্রম অনুসরণ করতে হয়েছে। ক্রমটি হল: 5ম উপাদান> 1ম উপাদান> 4র্থ উপাদান> 2য় উপাদান> 3য় উপাদান। তার মানে আমরা উপরোক্ত সেটটি থেকে একটা নির্দিষ্ট ক্রমে উপাদানগুলো বেছে নিয়ে ZERIN শব্দটি তৈরি করেছি। এই তৈরি করা শব্দটিকেই বলে একটা word বা string বা sequence!
2. এবার আমরা {0,1} -এই সেটটি নিয়ে কথা বলব। এই 0 আর 1 কে বাইনারি সিস্টেমে আমরা bits বলি। তার মানে 110101101 এই string টি {0,1} সেট থেকে একটা নির্দিষ্ট ক্রমে bit বেছে নিয়ে সাজানো একটা তালিকা। আর এই কারণেই একে আমরা একটা string বলে চিহ্নিত করছি।
3. আবার {0,1,2,…,9} সেটটি দশভিত্তিক সংখ্যা পদ্ধতির মুলভিত্তি। এই সেটের উপাদানগুলোকে বলে digits। আমরা যেসব ধনাত্মক পূর্ণসংখ্যা লেখি তার সবগুলোই হচ্ছে উপরের সেটটি থেকে উপাদান ব্যবহার করে তৈরি করা string বা sequence।

কম্বিনেটরিক্সে আমরা আসলে যে কাজ করি তা হচ্ছে কোনো নির্দিষ্ট শর্ত মেনে চলে এমন string এর সংখ্যা হিসাব কষে বের করা। এবারে যেহেতু আমরা string চিনে গেছি তাই string গণনার যাত্রা শুরু করে দেয়া যায়। প্রথমেই আমরা 2-digit strings এর সংখ্যা হিসাব করব। অর্থাৎ, মাত্র দুটি digit ব্যবহার করে কতগুলো string লেখা যায় তাই এখন আমাদের বিবেচ্য বিষয়।

আমরা দুটি খালিঘরের কথা চিন্তা করতে পারি। প্রথম খালিঘরটিতে 10 টি সংখ্যার যেকোনো একটি বসতে পারে। প্রথম ঘরটিতে যেকোনো একটি সংখ্যা নির্দিষ্ট করে বসানোর পর দ্বিতীয় ঘরটিতে 10 উপায়ে digit বসানো যায়। তাহলে, মোট উপায় দাঁড়াচ্ছে 10+10+10+10+10+10+10+10+10+10=100 টি। আগের লাইনের ক্যালকুলেশন অবশ্য আরো সহজেই লেখা সম্ভব। যেমন, 10 X 10=100; কারণ এটিও বুঝায় যে, প্রথম ঘরটি দশ উপায়ে পূরণ করা যায় এবং প্রত্যেকটি উপায়ের জন্য আবার দ্বিতীয় ঘরটি দশ উপায়ে পূরণ করা যায়। নিচের ডায়াগ্রাম দেখলে বিষয়টি আরো পরিষ্কার হবে।

এখানে লক্ষ্য করার আরেকটি বিষয় আছে। 2-digit strings গণনা করার সময় কিন্তু আমরা 0 থেকে 99 পর্যন্ত কতগুলো integer (পূর্ণ সংখ্যা) আছে তাও গণনা করে ফেলেছি। কারণ 00,01,02,…,09 string গুলি 0,1,2,…,9 এই integer গুলোকে প্রকাশ করছে। কিন্তু, কেউ যদি আমাদের বলে দুই অংকের কতগুলো positive integer আছে তা বের কর তাহলে আমরা কি করব? তখন আমরা বুঝে নিব যে প্রথম খালিঘরটিতে 0 বসতে পারে না। কারণ, প্রথমে 0 বসলে integer টি আর দুই অংকবিশিষ্ট থাকে না, বরঞ্চ এক অংকবিশিষ্ট হয়ে যায়। (মানে, 00,01,02,03,…,09 string গুলো এক অংকবিশিষ্ট positive integer কে প্রকাশ করে।) ফলে দুই অংকবিশিষ্ট positive integer হতে পারে 9 X 10=90 টি। এরকমভাবে আমরা নির্দিষ্ট অংকবিশিষ্ট কতগুলো সংখ্যা থাকতে পারে তা গুণতে পারব।

তাহলে এখন কয়েকটা সমস্যার সমাধান করে ফেল!

• কতগুলো 11-bit strings লেখা সম্ভব?
• Alphabet (A to Z) ব্যবহার করে কতগুলো 5-letter word বা string লেখা যায়?

এতক্ষণ আমরা যে হিসাবগুলো করেছি সেখানে একটা সেটের সকল উপাদানই পুনরাবৃত্তি করা যেত। কিন্তু, এখন যদি এমন একটা শর্ত জুড়ে দেয়া হয় যার কারণে একটা উপাদান একবারের বেশি ব্যবহার করা যাবে না তখন আমরা কিভাবে string এর সংখ্যা হিসাব করব?

ধরা যাক, আমাদের বলা হল 5-digit strings কতগুলো আছে তা গুণতে হবে এবং আরো বলে দেয়া হল যে কাঙ্ক্ষিত strings গুলোতে একটা digit একবারের বেশি ব্যবহার করা যাবে না। এই সমস্যার সমাধান খুব কঠিন কি? মোটেও না। তাহলে দেখা যাক আমরা কিভাবে সমাধান বের করি!

ধরে নিই যে 5 টা খালিঘর আছে 5 টা digit বসানোর জন্য। প্রথম ঘরটিতে 10 টা digit এর যেকোনো একটা বসানো যাবে। যেহেতু আমরা একটা নির্দিষ্ট digit বসিয়ে ফেলেছি তাই এটা আর দ্বিতীয়বার ব্যবহার করা যাবে না। ফলে, সেটটি থেকে মাত্র 9 টা digit পাওয়া যাবে দ্বিতীয় ঘরে বসানোর জন্য। তৃতীয় ঘরের জন্য একইভাবে 8 টা digit আমরা বসাতে পারি। এভাবে যেতে থাকলে আমরা দেখব যে, প্রথম ঘরটি 10 ভাবে পূরণ করা গেলে প্রতিটি পূরণকৃত উপায়ের জন্য দ্বিতীয় ঘর 9 ভাবে, দ্বিতীয় ঘরের প্রত্যেক সম্ভাব্য উপায়ের জন্য তৃতীয় ঘর 8 ভাবে, …… , চতুর্থ ঘরের প্রত্যেক সম্ভাব্য উপায়ের জন্য পঞ্চম ঘরটি 6 ভাবে পূরণ করা সম্ভব। তাহলে, আমাদের কাঙ্ক্ষিত strings এর সংখ্যা দাঁড়াল 10 × 9 × 8 × 7 × 6 ।

এখন আমরা একটা ম্যাথমেটিকাল ফাংশন সংজ্ঞায়িত করব। আর এটা হচ্ছে factorial । এর চিহ্ন হচ্ছে ‘!’ যা আমরা অন্য সব ক্ষেত্রে বিস্ময়কর চিহ্ন হিসেবে ব্যবহার করি। যদি n কোনো একটা positive integer হয় তাহলে আমরা লিখতে পারি,

অর্থাৎ, n! হচ্ছে 1 থেকে n পর্যন্ত সকল positive integer এর গুণফল। এখন, আমরা উপরের সমস্যার সমাধানটিকে factorial দিয়ে লেখার চেষ্টা করব।

আমাদের সমস্যা ছিল- 10 digit এর একটা সেট থেকে উপাদান নিয়ে কতগুলো 5-digit strings তৈরি করা সম্ভব যেখানে কোনো উপাদানের পুনরাবৃত্তি হবে না? কিন্তু, এখন আমরা আরো সাধারণ ঘটনায় যাব। এখন, আমাদের সমস্যা হবে- n উপাদানের একটা সেট থেকে কতগুলো k-length strings বানানো সম্ভব যেখানে একটা উপাদান একবারের বেশি ব্যবহার করা যাবে না। এই সমস্যার সমাধান আগের উপায়েই করা সম্ভব। এক্ষেত্রে সমধান হবে,

এখানে একটা জিনিস বুঝে নেয়া প্রয়োজন। Strings গুলোর length যত হবে উপরের উপায়ে পাওয়া সমাধানে ততগুলো পদ হবে। প্রথম পদে n থেকে কোনো কিছু বিয়োগ করা হয়নি, দ্বিতীয় পদে 1 বিয়োগ করা হয়েছে; তাহলে kতম পদে (k-1) বিয়োগ করতে হবে। তাই সমাধানের শেষ পদটি হয়,

এবং উপরের সাধারণ সমাধানটাকেও আমরা factorial দিয়ে লিখতে পারব।

তার মানে আমাদেরকে যদি n উপাদানবিশিষ্ট সেট দেয়া হয় এবং তা থেকে k-length strings (k≤n) এর সংখ্যা হিসেব করতে বলা হয় যেখানে একটা উপাদান একবারের বেশি ব্যবহার করা যাবে না তাহলে, আমরা সরাসরি বলে দিতে পারি সমাধান হবে,

উপরে যা লিখলাম তাকে ‘_nP_k’ ও বলা হয়। আমরা শর্ত হিসেবে লিখেছি যে k হয় n এর সমান অথবা k, n এর চেয়ে ছোট। কিন্তু, যখন k=n হয়, তখন আমরা একটা ছোটখাট ঝামেলায় পড়ে যাই। কারণ, (n-k) এর মান তখন হয় 0! যা আমরা প্রথমে সংজ্ঞায়িত করিনি। আমরা বলেছিলাম n! তখনই সম্ভব যখন n একটা positive integer। কিন্তু, এখানে 0! এসে পড়ায় আমরা কম্বিনেটরিয়াল আর্গুমেন্টের সাহায্য নিব। ধরা যাক, n উপাদানের সেট থেকে n-length strings গণনার দায়িত্ব পড়েছে। তাহলে, একদম প্রথম উপায়ে আমরা কিন্তু এটা গুণে বের করতে পারি। আর সেক্ষেত্রে সমাধান হবে,

কারণ, Strings গুলো n-length এর হওয়ায় সমাধানের পদও হবে n টা। সুতরাং, n তম পদ থেকে যা বিয়োগ করতে হবে তা হচ্ছে (n-1),

কিন্তু, সংজ্ঞানুসারে,

অর্থাৎ, সমস্যার সমাধান দাঁড়াচ্ছে n! ; এখন আমরা দ্বিতীয় পদ্ধতি ব্যবহার করলে যা পাব তা হচ্ছে,

কিন্তু, আমরা প্রথম পদ্ধতি থেকে জেনেছি যে সমস্যাটির সমাধান n!, আর তাই,

অর্থাৎ, এখন factorial ব্যবহার করা যাবে সকল nonnegative integer এর ক্ষেত্রে। (শুন্যসহ বাকি সব positive integer কে একত্রে বলে nonnegative integers ।)

এতক্ষণ আমরা যা শিখলাম তাতে কিন্তু Permutation গণনা শিখা হয়ে গেছে। Permutation এর সংজ্ঞা বলে যে, কোনো একটা নির্দিষ্ট সেট থেকে উপাদান (একটা উপাদান কেবলমাত্র একবার ব্যবহার করা যাবে) নিয়ে একটা নির্দিষ্ট length এর যতগুলো string বানানো যায় তার প্রত্যেকটিই একেকটা permutation। এই কারণে যতগুলো string তৈরি সম্ভব ঠিক ততগুলোই permutation আছে। এই কারণেই n!/(n-k)! কে _nP_k ও লেখা হয় যেখানে P বলতে permutation বুঝায়।

আজকে আমরা শেষ যে জিনিসটা শিখব তা হল Product Rule। মূলত এটাই আজকের সবচেয়ে গুরুত্বপূর্ণ ও বেসিক নিয়ম!

Product Rule: যদি k length এর কোনো string এর ক্ষেত্রে i তম পদটি n_i উপায়ে পূরণ করা যায় তাহলে, তাহলে মোট সম্ভাব্য string এর সংখ্যা হবে n₁n₂n₃…n_k ।

(i এর মান এখানে 1 থেকে k পর্যন্ত হতে পারে। আর, i তম পদ কত উপায়ে পূরণ করা যায় তা কিন্তু পূর্ববর্তী কোনো পদ কিভাবে পূরণ করা হয়েছে তার উপর নির্ভরশীল হতে পারবে না।)

আজকের সমাধানকৃত সব সমস্যাই Product Rule ব্যবহার করে করা যাবে। কিন্তু, এটা আর আমি দেখাবো না। যারা পড়ছে তাদেরকেই ব্যবহার করে দেখতে হবে!

শেষে আরো কিছু সমস্যা দিয়ে যাব। এগুলো সমধান করতে পারবে বলে আশা করছি।

• {A,B,C, … ,Z} সেটটি থেকে উপাদান ব্যবহার করে কতগুলো 5-letter word তৈরি করা সম্ভব, যদি word গুলোতে কমপক্ষে একটা A থাকা বাধ্যতামূলক হয়?
• {A,B,C} সেট থেকে উপাদানগুলো ব্যবহার করে কতগুলো 5-letter word বানানো যাবে, যদি প্রতিটি word এ সেটের উপাদান তিনটির প্রত্যেকটিই কমপক্ষে একবার উপস্থিত থাকা আবশ্যক হয়?