উৎপাদক ফাংশন

রিকার্শন অর্থাৎ পুনরাবৃত্তিমূলকের প্রথম উদাহরণের জন্য, উৎপাদকের ফাংশন দেখা যাক। আমরা $n$‍ এর উৎপাদককে $n!$‍ দিয়ে নির্দেশ করি। মূলত এটি 1 থেকে $n$‍ এর গুণফল। উদাহরণস্বরূপ, 5! সমান হল $1\cdot 2\cdot 3\cdot 4\cdot 5$‍ অথবা 120। (লক্ষ্য কর: আমরা উৎপাদকীয় ফাংশন নিয়ে আলোচনা করলে, সকল বিস্ময় সূচক চিহ্ন দিয়ে মূলত উৎপাদকীয় ফাংশনকে নির্দেশ করা হয়।)

আমরা কেন এত উৎপাদকীয় ফাংশন নিয়ে আলোচনা করছি? কারণ কোন বস্তু কতগুলো উপায়ে বিন্যস্ত রয়েছে অথবা আমরা কতগুলো উপায়ে সমন্বয় করতে পারি সেটা গণনা করার জন্য উৎপাদক খুবই উপকারি। উদাহরণস্বরূপ, আমরা $n$‍ বস্তুকে কতগুলো উপায়ে বিন্যস্ত করতে পারি? প্রথমেই $n$‍ বস্তু দেওয়া আছে। অর্থাৎ প্রত্যেকটি $n$‍ বস্তুর জন্য, আমাদের $n-1$‍ উপায় থাকে, যেন বিন্যাস অনুসারে প্রথম দুইটি বস্তুর জন্য $n\cdot (n-1)$‍ উপায় থাকে। এখন তৃতীয় বস্তুর জন্য $n-2$‍ উপায় রয়েছে, অর্থাৎ প্রথম তিনটি বস্তুর জন্য সুবিন্যস্তভাবে $n\cdot (n-1)\cdot (n-2)$‍ উপায়। এভাবেই চলতে থাকবে যেই পর্যন্ত শুধুমাত্র দুইটি বস্তু অবশিষ্ট না থাকে এবং তারপর একটি বস্তু অবশিষ্ট থাকবে। সুতরাং, আমরা $n$‍ বস্তুকে $n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$‍ উপায়ে বিন্যস্ত করতে পারি। ফলাফল হল শুধু $n!$‍ ($n$‍ এর উৎপাদক), কিন্তু গুণফলকে $n$‍ থেকে 1 পর্যন্ত লেখা হয়, 1 থেকে $n$‍ পর্যন্ত নয়।

উৎপাদকীয় ফাংশনের আরেকটি ব্যবহার হল কোন বস্তু সংগ্রহের মধ্য থেকে কয়েক উপায়ে বস্তু নির্বাচন গণনা করা। উদাহরণস্বরূপ, মনে কর, তুমি ভ্রমণে যাওয়ার জন্য টি-শার্ট নির্বাচন করছ। ধরি, তোমার $n$‍ সংখ্যক টি-শার্ট রয়েছে কিন্তু শুধুমাত্র $k$‍ সংখ্যক টি-শার্ট নেওয়া যাবে। তাহলে তুমি কতগুলো উপায়ে $n$‍ টি-শার্টের মধ্য থেকে $k$‍ টি-শার্ট নির্বাচন করতে পারবে? উত্তর হল (যা এখানে যাচাই করার দরকার নেই) $n!/(k!\cdot (n-k)!)$‍. এজন্য উৎপাদকীয় ফাংশন খুবই উপকারি। তুমি এখানে আরও বিন্যাস ও সমাবেশ সম্পর্কে জানতে পারবে, কিন্তু উৎপাদকীয় অ্যালগরিদম প্রয়োগ করার জন্য এগুলো বোঝার দরকার নেই।

উৎপাদকীয় ফাংশন সকল ধনাত্মক পূর্ণসংখ্যার জন্য সংজ্ঞায়িত, সাথে 0 রয়েছে। 0! এর কি মান হবে? এটি 1 থেকে বড় বা সমান এবং 0 থেকে ছোট বা সমান সকল পূর্ণসংখ্যার গুণফল। কিন্তু এমন কোন পূর্ণসংখ্যা নেই। সুতরাং, আমরা 0! কে 1 এর সমান বলে সংজ্ঞায়িত করি। (0! = 1 সংজ্ঞায়িত করা $n$‍ বস্তু থেকে $k$‍ বস্তু নির্বাচন করার সাথেও সামঞ্জস্যপূর্ণ। ধরি, আমরা $n$‍ বস্তু থেকে $n$‍ বস্তু নির্বাচন করার কতগুলো উপায় রয়েছে জানতে চাই। এটি সহজ, কারণ শুধুমাত্র একটি উপায় রয়েছে: সকল $n$‍ বস্তু নির্বাচন করা। আমরা জানি, সূত্র অনুযায়ী, $n!/(n!\cdot (n-n)!)$‍ সমান হল 1। কিন্তু $(n-n)!$‍ হল 0!, আমরা জানি যে, $n!/(n!\cdot 0!)$‍ হল 1 হওয়া উচিত। লব ও হর থেকে $n!$‍ বাদ দিলে, আমরা দেখি যে, $1/(0!)$‍ সমান হল 1 এটি হয় কারণ 0! সমান হল 1।)

এখন আমাদের $n!$‍ নিয়ে চিন্তা করতে হবে। এটি সমান 1 হয় যখন $n=0$‍ এবং $1\cdot 2\cdots (n-1)\cdot n$‍ যখন $n$‍ হল ধনাত্মক।

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।