কাটালান নাম্বারের কিচ্ছা কাহিনী—পর্ব ১

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

ধরো A জায়গাটায় আমাদের ক্যাম্প আছে, আর B তে হলো টাউন হল। আর মাঝের দাগগুলো হলো রাস্তা, তো ক্যাম্পার রা আসলে অনেকভাবে ঘুরে A থেকে B তে যেতে পারে, যেমন:

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

আমাদের প্রথম সমস্যাটায় ফিরি। ধরি আমাদের ম্যাপটা একটা গ্রিড, যেইটায় n টা সারি আর m টা কলাম আছে, যেগুলা প্রত্যেকটা একটা করে রাস্তা নির্দেশ করে। এখন আমাদের বের করতে হবে আমরা মোট কতভাবে A থেকে B তে যেতে পারবো, যেখানে আমরা শুধুই হয় নিচে যাবো বা ডানে যেতে পারব।

যেমন আমরা ১ম চিত্রের মতো করে যেতে পারবো, কিন্তু ২য় চিত্রের মতো করে যেতে পারব না।

এইটার সমাধানের ক্ষেত্রে একজন সাধারণ প্রবলেম সলভার হিসেবে আমরা শুরুতে যেইটা করতে পারি সেইটা হলো ছোট ছোট কিছু m আর n এর জন্য গুনে গুনে কতভাবে যেতে পারি সেইটা বের করতে পারি। যেমন n বা m যদি ১ হয়, তাহলে কিন্তু শুধু মাত্র একটাই রাস্তা থাকবে (সোজা ডানে/ সোজা নিচে) আবার ধরো m,n=2, সেক্ষেত্রে মোট ২ টি উপায়ে যেতে পারব। m=3, n=3 হলে মোট 6 ভাবে। আসলে ছোট ছোট ঘটনা দিয়ে আমরা কিন্তু তেমন কোনো উপকার পাচ্ছি না, বা প্যাটার্নটা বুঝতে পারছি না।

আমরা যদি এভাবে ছোট ছোট কেস গুলো নিয়ে চিন্তা করি, তাহলে খুব দ্রুতই একটা বিষয় লক্ষ করতে পারবো, সেইটা হলো, আমাদের যদি n*m এ বামের উপরের  কোণা থেকে নিচের ডানের কোণায় যেতে চাই, আমরা যেদিক দিয়েই যাই না কেন, আমাদের ডানের কোণায় যেতে একেবারে ঠিক n বার ডানে যেতে হয়

যেমন ধরো, n=4 হলে, আমরা যেভাবেই A থেকে B তে যাই না কেনো, আমাদের প্রত্যেকবার ই, চার বার বাম থেকে ডানে যেতে হয়।

ঠিক একইভাবে n*m এ আমরা যদি উপরের বাম কোণা থেকে নিচের ডানের কোণায় যেভাবে ই যাই না কেন আমাদের প্রত্যেকবারেই কিন্তু m ঘর নিচে যেতে হবে। এবং মোটের উপর আমরা যদি উপরের বামের কোণা থেকে নিচের ডানের কোণায় শুধুমাত্র নিচে নেমে এবং ডানে গিয়ে যেতে চাই, আমরা যেভাবেই যাই না কেনো, আমাদের মোটে মিলে ঠিক m+n টা ঘর ই অতিক্রম করতে হবে, এবং যার মধ্যে n টা বার আমাদের ডানে যেতে হয়, এবং বাকী m বার আমাদের নিচে যেতে হয়।

এখানে m=4 হলে আমরা যে উপায়েই B তে যাই না কেনো, আমাদের চারবার নিচে নামতে হয়।

এই প্রবলেম টার সাথে এখন আরেকটা প্রবলেম মিলায়ে দিবো এবার। ধরো একটা জায়গায় n টা সাদা গুটি আর m টা কালো গুটি আছে, আর তুমি এখন এদের একটা সারিতে রাখবা, সাদা গুটী আর কালো গুটীগুলোর মধ্যে কোনো তফাত নেই। তাহলে এদের কে কতভাবে সাজানো যাবে? কম্বিনেটরিক্স থেকে আমরা দেখেছি, যদি n+m টা ভিন্ন ভিন্ন অবজেক্ট এরকম একটা সারিতে রাখতে বলতো তাহলে তার বিন্যাসের সংখ্যা হতো , কিন্তু এখানে যেহেতু n টা একইরকম,আবার m টা একই রকম, তাই সাজানোর মোট উপায় হবে (n+m)!/(n!∙m!)

এই প্রবলেমটার সাথে এবার আমরা আগের প্রবলেমটাকে রিলেট করতে পারি আমরা যদি ডানে যাওয়ার অর্ডারকে D আর নিচে যাওয়ার অর্ডারকে L দিয়ে চিহ্নিত করি, তাহলে আমাদের রাস্তা যদি নিচের চিত্রের মতো হয়, আমাদের অর্ডার হবে DDDLLDLL

এখানে D এর সংখ্যা ও নির্দিষ্ট থাকবে (n বার) আবার L এর সংখ্যাও নির্দিষ্ট থাকবে। তো আমাদের গ্রিডের প্রবলেমটা তখন হবে এমন, যে একটা জায়গায় n টা D গুটী আর m টা L গুটি আছে, এখন এদের কে একটা রেখা বরাবর সাজাতে হবে, এবং এইটা মোট কতভাবে বের করা যায় সেইটা বের করতে হবে। আমরা এর আগের প্রবলেম থেকেই এর সলুশন টা জানি ,আর তা হলো (n+m)!/(n!∙m!)।  আমরা মোট (n+m)!/(n!∙m!)  ভাবে A থেকে B তে যেতে পারবো, যেখানে আমরা শুধুই হয় নিচে যাবো বা ডানে যেতে পারব।

পরবর্তী পর্বে আমরা দেখতে পারবো, এই যাতায়াতের উপায়গুলার মধ্যে যদি আমরা কিছু রেস্ট্রিকশন দেই, তাহলে আরো অনেক সুন্দর সুন্দর অবজারভেশন বের হয়, বের হয় আরো সুন্দর সুন্দর নাম্বার।