In order to continue enjoying our site, we ask that you confirm your identity as a human. Thank you very much for your cooperation. Show View Discussion Improve Article Save Article Like Article View Discussion Improve Article Save Article Like Article Prerequisite – Generalized PnC Set 1Combinatorial problems can be rephrased in several different ways, the most common of which is in terms of distributing balls into boxes. So we must become familiar with the terminology to be able to solve problems. The balls and boxes can be either distinguishable or indistinguishable and the distribution can take place either with or without exclusion. The term exclusion means that no box can contain more than one ball, and similarly, if the problem states the distribution is without exclusion it means that a box may contain more than one ball.Throughout this article consider that there are balls and boxes.1. Distinguishable balls and Distinguishable boxes –With Exclusion – In case of exclusion, distribution is the same as counting -permutations, as there are choices for the first ball, for the second and so on.Without Exclusion – When the distribution is without exclusion, i.e. there is no restriction on the minimum number of balls a box has to have, the number of ways – . This is because every ball has choices. Fixed number of balls – If the distribution is such that each box should only have a fixed number of balls then the number of ways is- where is the number of balls to be put in the box.
2. Indistinguishable balls and Distinguishable boxes –Counting the number of ways of placing indistinguishable balls into distinguishable boxes with exclusion is the same as counting -combinations without repetition of elements. But if the distribution is without exclusion then the problem is the same as counting the number of -combinations where elements can be repeated. Refer Generalized PnC Part-1 for more on this topic.3. Distinguishable balls and Indistinguishable boxes –There is no simple closed formula for counting the number of ways of distributing distinguishable balls into indistinguishable boxes, but there is a complex one involving Stirling number of the second kind. So the number of ways is- 4. Indistinguishable balls and Indistinguishable boxes –Counting the number of ways of distributing indistinguishable balls into indistinguishable objects is analogous to finding the number of partitions of a positive integer. No simple formula exists for finding the number of partitions of a positive integer. For both of the above cases, enumeration of all ways is sometimes easier than finding a closed formula which gives the same result.
GATE CS Corner Questions Practicing the following questions will help you test your knowledge. All questions have been asked in GATE in previous years or in GATE Mock Tests. It is highly recommended that you practice them.
References- Partition Number Theory – Wikipedia This article is contributed by Chirag Manwani. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above. |