পুনরাবৃত্তিসহ সমাবেশ
পুনরাবৃত্তিসহ সমাবেশ সাধারণ সমাবেশের মতোই, পার্থক্য শুধু এই যে এখানে প্রদত্ত সেট M এর উপাদানগুলো একাধিকবার আসতে পারে।
সংজ্ঞা ও সূত্র
একটি মজার উদাহরণ দিয়ে শুরু করি: তুমি পিকনিকের জন্য দোকানে বারো প্যাকেট জুস কিনতে গেলে। তাকে মোট চার রকমের জুস আছে। জুস কেনার কয়েকটি উপায় আছে। যেমন কিনতে পার 5 টি আম, 2 টি কমলা, 1 টি লিচু ও 4 টি পেয়ারার জুস, অথবা প্রতিটি স্বাদের তিনটি করে। মোট বারো প্যাকেট হতে হলে জুস কেনার কতগুলো ভিন্ন উপায় আছে?
তাহলে আমাদের প্রদত্ত সেট M = {আম, কমলা, লিচু, পেয়ারা}, আর প্রশ্ন হলো: M সেটের উপাদান দিয়ে গঠিত এবং ক্রম গুরুত্বপূর্ণ নয় এমন k-টাপল কতগুলো আছে, যেখানে k = 12?
সূত্রের প্রতিপাদন বিন্যাস ও সমাবেশের অন্য সমস্যার চেয়ে একটু কঠিন। প্রথমে কেনাকাটাকে শূন্য ও একের একটি অনুক্রম হিসেবে কল্পনা করি: একের সংখ্যা হলো একটি স্বাদের কেনা প্যাকেটের সংখ্যা, আর শূন্য এক স্বাদকে অন্য স্বাদ থেকে আলাদা করে। তাহলে 111011101111101 মানে আমরা কিনেছি তিনটি আম (প্রথম তিনটি 1), তারপর তিনটি কমলা (0 হলো বিভাজক চিহ্ন, তারপর আরও তিনটি 1), তারপর পাঁচটি লিচু (বিভাজক 0, তারপর পাঁচটি 1) এবং শেষে একটি পেয়ারার জুস। পুরো নীতিটি নিচের চিত্রে দেখানো হলো:
যদি 6 টি আম, 4 টি কমলা, 2 টি পেয়ারার জুস কিনতাম এবং কোনো লিচু না কিনতাম, তাহলে অনুক্রমটি হতো এরকম:
লক্ষ করি, এই অনুক্রমের দৈর্ঘ্য সবসময় 15: মোট 12 প্যাকেট জুস কিনতে হলে এতে 12 টি এক থাকতেই হবে। আর চারটি ভিন্ন স্বাদ আলাদা করতে তিনটি বিভাজক থাকতে হবে। তাহলে বাকি থাকে এই হিসাব: 15 দৈর্ঘ্যের এমন কতগুলো অনুক্রম আছে, যাতে তিনটি শূন্য থাকে?
শুধু শূন্যগুলোর অবস্থান গুনলেই হবে: 12 টি একের মধ্যে 3 টি শূন্য বসালেই জুসের একটি বৈধ সমাবেশ পাই। অন্যভাবে বললে: মোট 15 টি অবস্থান আছে, তার 3 টিতে শূন্য বসাতে হবে। বাকি অবস্থানগুলোতে আপনাআপনি এক বসে যায়।
এটি এখন পুনরাবৃত্তিহীন সাধারণ সমাবেশের একটি সহজ সমস্যা। 15 টি অবস্থানকে {1, …, 15} সংখ্যা দিয়ে চিহ্নিত করি, তারপর এই সেট থেকে প্রতিবার তিনটি করে সংখ্যা বেছে নিই। এতে তিনটি অবস্থান পাই, যেখানে শূন্য বসবে। যেমন {2, 4, 7} সমাবেশ থেকে পাই অনুক্রম 101011011111111: দ্বিতীয়, চতুর্থ ও সপ্তম স্থানে শূন্য, বাকিগুলো এক। সুতরাং 15 টি অবস্থানে শূন্য বসানোর মোট
টি ভিন্ন উপায় আছে, ফলে চার রকমের জুস থেকে 12 প্যাকেট কেনারও 455 টি ভিন্ন উপায় আছে।
আগের যুক্তিকে সাধারণভাবে বলা যায়। n উপাদানের একটি সেট M থেকে আমরা k-টাপল বেছে নিলে এবং উপাদানগুলো পুনরাবৃত্ত হতে পারলে আমরা শূন্য ও একের n + k − 1 দৈর্ঘ্যের একটি অনুক্রম গঠন করি (k টি এক ও n − 1 টি শূন্য)। এরপর দেখি, n − 1 টি শূন্য কত উপায়ে বসানো যায়। তাই পুনরাবৃত্তিসহ সমাবেশের সংখ্যা, অর্থাৎ n − 1 টি শূন্য বসানোর উপায়ের সংখ্যা,
শেষ ধাপটি সম্ভব হয়েছে দ্বিপদী সহগের মৌলিক সম্পর্কের কারণে।
সমাধানকৃত উদাহরণ
- একটি নতুন নাটকের প্রথম প্রদর্শনীর 20 টি বিনামূল্যের টিকিট 10 জন অবসরপ্রাপ্ত শিক্ষিকার মধ্যে কত উপায়ে ভাগ করে দেওয়া যায়? এটি পুনরাবৃত্তিসহ সমাবেশের উদাহরণ, কারণ একজন শিক্ষিকা একাধিক টিকিট, এমনকি সবগুলো টিকিটও পেতে পারেন। শুধু ঠিকভাবে বুঝতে হবে, কোনটি n আর কোনটি k। আসলে আমরা 10 জন শিক্ষিকা থেকে প্রতিবার 20 টি নিয়ে সমাবেশ গঠন করছি। অন্যভাবে বললে, শূন্য ও একের এমন একটি অনুক্রম গঠন করছি, যার দৈর্ঘ্য 29 এবং যাতে 20 টি এক ও 9 টি শূন্য আছে। সুতরাং n = 10, k = 20। ফল পাই:
সূচিপত্র: বিন্যাস ও সমাবেশ, বিন্যাস (ⁿPₖ), সবগুলো জিনিসের বিন্যাস (n!), সমাবেশ (ⁿCₖ), পুনরাবৃত্তিসহ বিন্যাস (nᵏ), পুনরাবৃত্তিসহ সমাবেশ, কতগুলো ভিন্ন পিন হতে পারে