স্টার্স অ্যান্ড বার্স#
স্টার্স অ্যান্ড বার্স হলো নির্দিষ্ট কম্বিনেটরিক্স সমস্যা সমাধানের একটি গাণিতিক কৌশল। যখনই আপনি অভিন্ন অবজেক্ট গ্রুপ করার উপায়ের সংখ্যা গুনতে চান তখন এটি কাজে আসে।
উপপাদ্য#
$n$টি অভিন্ন অবজেক্টকে $k$টি লেবেলড বাক্সে রাখার উপায়ের সংখ্যা হলো
$$\binom{n + k - 1}{n}.$$প্রমাণটিতে অবজেক্টগুলোকে তারায় (স্টার) রূপান্তর করা হয় এবং বাক্সগুলোকে বার দ্বারা আলাদা করা হয় (তাই এই নাম)। যেমন, $\bigstar | \bigstar \bigstar |~| \bigstar \bigstar$ দ্বারা নিম্নলিখিত পরিস্থিতি উপস্থাপন করা যায়: প্রথম বাক্সে একটি অবজেক্ট, দ্বিতীয় বাক্সে দুটি অবজেক্ট, তৃতীয়টি খালি এবং শেষ বাক্সে দুটি অবজেক্ট। এটি ৫টি অবজেক্টকে ৪টি বাক্সে ভাগ করার একটি উপায়।
এটি বেশ স্পষ্ট যে প্রতিটি বিভাজন $n$টি স্টার এবং $k - 1$টি বার ব্যবহার করে উপস্থাপন করা যায় এবং $n$টি স্টার ও $k - 1$টি বার ব্যবহারকারী প্রতিটি স্টার্স অ্যান্ড বার্স পারমুটেশন একটি বিভাজন উপস্থাপন করে। তাই $n$টি অভিন্ন অবজেক্টকে $k$টি লেবেলড বাক্সে ভাগ করার উপায়ের সংখ্যা, $n$টি স্টার এবং $k - 1$টি বারের পারমুটেশনের সংখ্যার সমান। দ্বিপদী সহগ আমাদের কাঙ্ক্ষিত সূত্র দেয়।
অ-ঋণাত্মক পূর্ণসংখ্যা যোগফলের সংখ্যা#
এই সমস্যাটি উপপাদ্যের সরাসরি প্রয়োগ।
আপনি সমীকরণের সমাধানের সংখ্যা গুনতে চান
$$x_1 + x_2 + \dots + x_k = n$$যেখানে $x_i \ge 0$।
আবারও আমরা স্টার্স অ্যান্ড বার্স ব্যবহার করে একটি সমাধান উপস্থাপন করতে পারি। যেমন, $n = 4$, $k = 3$-এর জন্য $1 + 3 + 0 = 4$ সমাধানটি $\bigstar | \bigstar \bigstar \bigstar |$ ব্যবহার করে উপস্থাপন করা যায়।
সহজেই দেখা যায়, এটি ঠিক স্টার্স অ্যান্ড বার্স উপপাদ্য। তাই সমাধান হলো $\binom{n + k - 1}{n}$।
ধনাত্মক পূর্ণসংখ্যা যোগফলের সংখ্যা#
একটি দ্বিতীয় উপপাদ্য ধনাত্মক পূর্ণসংখ্যার জন্য একটি সুন্দর ব্যাখ্যা দেয়। বিবেচনা করুন
$$x_1 + x_2 + \dots + x_k = n$$যেখানে $x_i \ge 1$।
আমরা $n$টি স্টার বিবেচনা করতে পারি, কিন্তু এবার স্টারের মধ্যে সর্বোচ্চ একটি বার রাখা যায়, কারণ দুটি স্টারের মধ্যে দুটি বার $x_i=0$ উপস্থাপন করবে, অর্থাৎ একটি খালি বাক্স। $k-1$টি বার রাখার জন্য স্টারের মধ্যে $n-1$টি ফাঁক আছে, তাই সমাধান হলো $\binom{n-1}{k-1}$।
নিম্ন-সীমা যুক্ত পূর্ণসংখ্যা যোগফলের সংখ্যা#
এটি সহজেই বিভিন্ন নিম্ন সীমা সহ পূর্ণসংখ্যা যোগফলে সম্প্রসারিত করা যায়। অর্থাৎ, আমরা সমীকরণের সমাধানের সংখ্যা গুনতে চাই
$$x_1 + x_2 + \dots + x_k = n$$যেখানে $x_i \ge a_i$।
$x_i' := x_i - a_i$ প্রতিস্থাপন করলে আমরা পরিবর্তিত সমীকরণ পাই
$$(x_1' + a_i) + (x_2' + a_i) + \dots + (x_k' + a_k) = n$$$$\Leftrightarrow ~ ~ x_1' + x_2' + \dots + x_k' = n - a_1 - a_2 - \dots - a_k$$যেখানে $x_i' \ge 0$। তাই আমরা সমস্যাটিকে $x_i' \ge 0$ সহ সরলতর ক্ষেত্রে নামিয়ে এনেছি এবং আবার স্টার্স অ্যান্ড বার্স উপপাদ্য প্রয়োগ করতে পারি।
ঊর্ধ্ব-সীমা যুক্ত পূর্ণসংখ্যা যোগফলের সংখ্যা#
ইনক্লুশন-এক্সক্লুশন নীতি-র কিছু সাহায্যে, আপনি ঊর্ধ্ব সীমা দিয়েও পূর্ণসংখ্যা সীমাবদ্ধ করতে পারেন। সংশ্লিষ্ট নিবন্ধের ঊর্ধ্ব-সীমা যুক্ত পূর্ণসংখ্যা যোগফলের সংখ্যা সেকশন দেখুন।