Constrained distributions and arrangements
Objectives and model contract
Count selections with repetition, integer distributions with bounds, repeated-symbol arrangements and circular arrangements without confusing the objects being counted. Prerequisite: sum/product rules, factorials and combinations. All counts are finite. Unless stated otherwise, boxes and positions are labeled, identical objects have no individual labels, and rotations are identified only when the problem explicitly says so.
A formula is a consequence of a model, not a substitute for it. Before calculating, ask: Are objects distinct? Are boxes distinct? Does position or order matter? Can a box be empty? Are there capacity limits? Are rotations or mirror images identified? Changing one answer can change the count.
1. Identical objects in labeled boxes: stars and bars
Distributing n identical objects into k labeled boxes with no capacity limit and emptiness allowed is equivalent to solving x₁+⋯+x_k=n in nonnegative integers. For n≥0 and k≥1, the count is C(n+k−1,k−1).
Represent the objects by n stars in a row and separate the k box counts using k−1 bars. Bars may be adjacent, or at either end, because zero-sized boxes are allowed. Every string of n stars and k−1 bars gives exactly one ordered k-tuple, and every such tuple gives one string. Choose the k−1 bar positions among n+k−1 positions.
For five identical objects and three labeled boxes, the count is C(7,2)=21. The tuple (0,2,3) differs from (2,0,3), because box labels matter. In contrast, distributing five distinct objects into three labeled boxes gives 3⁵=243: each object chooses a box independently. Stars and bars cannot replace that product rule.
Selecting n items from k types with unlimited repetition and no order is the same nonnegative-tuple model: x_i is the selected number of type i. Thus combinations with repetition have count C(n+k−1,n). This is not kⁿ, which counts ordered sequences of n type choices.
2. Lower bounds are removed by a bijection
For constraints x_i≥l_i with integer l_i≥0 and sum x_i=n, put y_i=x_i−l_i. Then every y_i≥0 and their sum is N=n−Σl_i. If N<0, there are no solutions. If N≥0, the count is C(N+k−1,k−1). The shift is a bijection, so it neither loses nor duplicates a solution.
Example: distribute nine identical tokens into four labeled boxes with x₁≥1,x₂≥0,x₃≥2,x₄≥1. Reserve 1+0+2+1=4 tokens. The remaining five are unrestricted among four boxes, giving C(8,3)=56. Counting C(12,3) would ignore the reservations; counting C(5,3) would confuse stars with the combined stars-and-bars positions.
If each of k boxes must receive at least one, the same shift gives C(n−1,k−1) when n≥k. For n<k the count is zero. Keep that feasibility check instead of substituting negative arguments into a memorized factorial formula.
3. Upper bounds need subtraction or generating factors
An upper bound is not removed by simply reducing the total number of objects. Count all nonnegative solutions and exclude those that exceed capacities, correcting overlaps by inclusion–exclusion.
Consider x₁+x₂+x₃=6, with 0≤x₁≤3, 0≤x₂≤2 and x₃≥0. Without upper bounds there are C(8,2)=28 solutions. Bad event A is x₁≥4; shifting x₁ down by 4 leaves total 2, giving C(4,2)=6. Bad event B is x₂≥3; shifting x₂ down by 3 leaves total 3, giving C(5,2)=10. Both cannot occur together because 4+3>6. Therefore the answer is 28−6−10=12.
Check directly: x₁ may be 0,1,2,3 and x₂ may be 0,1,2. Each of these 4·3 pairs has sum at most 5 and determines a unique nonnegative x₃=6−x₁−x₂. This independently gives 12.
For bounds 0≤x_i≤u_i, a general inclusion–exclusion term indexed by S⊆{1,…,k} shifts every selected coordinate by u_i+1. Its residual total is n−Σ(i∈S)(u_i+1). Add or subtract the nonnegative-solution count according to (−1)^|S|, and use zero if the residual total is negative. The +1 is essential: violating x_i≤u_i means x_i≥u_i+1.
Equivalently, the coefficient of xⁿ in ∏(1+x+⋯+x^{u_i}) counts these distributions. This connects to the earlier ordinary-generating-function lesson without treating coefficients as probabilities.
4. Repeated symbols: divide only genuine symmetries
If a multiset contains n symbols, with multiplicities n₁,…,n_k summing to n, its distinct linear arrangements number n!/(n₁!⋯n_k!). Temporarily label equal symbols, count all n! permutations, then forget those temporary labels. Every visible arrangement has exactly n₁!⋯n_k! labeled versions, so division is justified.
Example: three A's, two B's and one C have 6!/(3!2!)=60 arrangements. Positions are distinct, copies of the same letter are not. Treating all six symbols as distinct overcounts; treating the letter counts as a single unordered selection ignores positional differences.
Additional restrictions change the count. To arrange the same multiset with no two A's adjacent, first arrange the two B's and one C in 3!/2!=3 ways. These three symbols create four gaps, including both ends. Place the three identical A's into three distinct gaps, in C(4,3)=4 ways. The answer is 3·4=12. At most one A per gap enforces nonadjacency. No extra 3! is needed because the A's are identical.
This gap argument is a bijection: deleting all A's from a valid arrangement recovers exactly one base arrangement and the chosen gaps. If five A's had to fit among the same three other symbols, no valid arrangement would exist because only four gaps are available.
5. Circular arrangements require an equivalence rule
For n≥1 distinct people around an unlabeled round table, with rotations identified and reflections counted separately, the count is (n−1)!. Fix one designated person as an anchor and arrange the remaining n−1 clockwise. This avoids division ambiguities and counts each rotational class once.
For six distinct people the answer is 5!=120. If six seats carry distinct seat numbers, rotations are no longer equivalent and the count is 6!=720. The physical shape of the table alone does not decide the counting rule.
If mirror images are also identified, then for n≥3 distinct people the count becomes (n−1)!/2. With everyone distinct, reversing clockwise order gives a different rotational class, so each reflection-pair has exactly two members. For six people that gives 60. Do not extend this division automatically to repeated-symbol necklaces or to n=1,2.
Repeated symbols may have different rotational periods. For instance, the six linear arrangements of A,A,B,B cannot simply be divided by four: 6/4 is not even an integer. The rotational classes are represented by AABB and ABAB. The first has four distinct rotations; the second has two. A uniform division rule fails because class sizes differ. General necklace counting needs a symmetry method beyond this lesson.
6. Circular adjacency as a block, with assumptions
Among six distinct people A,B,C,D,E,F around an unlabeled round table, rotations are identified but reflections are distinct. Count arrangements where A and B sit adjacent. Combine A,B into one block. There are five distinct circular objects, giving (5−1)!=24 arrangements, and the block has two internal orders. The count is 2·24=48.
The total is 120, so nonadjacent A,B arrangements number 120−48=72. The block method works here because the other people are distinct and there are at least three circular objects after contraction. For more complicated overlapping adjacency requirements, blocks may merge or constraints may contradict; do not multiply independently without checking.
Solving checklist and remaining depth
Write the actual counted object as a tuple, word, function or equivalence class. Shift lower bounds first and check feasibility. For upper bounds, define bad events with the correct one-past-capacity threshold and account for intersections. For repeated symbols, identify the exact constant multiplicity that permits division. For a circular problem, state which symmetries are identified. Unlabeled-box partitions, general necklace symmetry and advanced partition identities require further methods; they are not secretly included in stars and bars.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option and retain all stated label, symmetry, domain and positivity assumptions.
C01. How many ways distribute five identical objects into three labeled boxes, allowing empty boxes and imposing no upper bounds?
A. 243 B. 21 C. 10 D. 15
Answer: B
A: 3⁵ counts five distinct objects making independent box choices, not identical objects.
B: Nonnegative solutions of x₁+x₂+x₃=5 number C(5+3−1,3−1)=C(7,2)=21.
C: C(5,2) chooses two object positions but omits the bars from the combined representation.
D: This is not the relevant binomial count; enumerate ordered nonnegative triples or use seven star/bar positions.
C02. How many integer solutions satisfy x₁+x₂+x₃+x₄=9 with x₁≥1,x₂≥0,x₃≥2,x₄≥1?
A. 220 B. 20 C. 10 D. 56
Answer: D
A: C(12,3)=220 ignores all lower bounds.
B: This does not distribute the five residual objects among all four labeled coordinates.
C: C(5,3)=10 uses only residual stars, omitting the three bar positions.
D: Subtract lower bounds totaling 4; residual total 5 across four nonnegative coordinates gives C(8,3)=56.
C03. How many nonnegative integer triples satisfy x₁+x₂+x₃=6, x₁≤3 and x₂≤2?
A. 12 B. 28 C. 18 D. 6
Answer: A
A: All 4 choices for x₁ and 3 for x₂ have sum at most 5 and determine a valid x₃. Equivalently 28−6−10=12.
B: 28 ignores both upper bounds.
C: Subtracting only the ten solutions with x₂≥3 leaves violations of x₁≤3.
D: 6 counts the bad event x₁≥4 in the unrestricted universe, not all valid triples.
C04. How many linear arrangements of A,A,A,B,B,C contain no adjacent A’s?
A. 60 B. 24 C. 12 D. 72
Answer: C
A: 60 counts all multiset arrangements, including adjacent A’s.
B: Treating the two B copies as distinct doubles the base arrangements.
C: Arrange B,B,C in 3!/2!=3 ways; select three of their four gaps for identical A’s: 3·C(4,3)=12.
D: Multiplying the valid gap count by 3! wrongly labels the identical A copies.
C05. Six distinct people sit around an unlabeled round table; rotations are identified and reflections are distinct. How many arrangements keep specified people A and B nonadjacent?
A. 120 B. 72 C. 48 D. 360
Answer: B
A: 120 is the total before excluding adjacent A,B arrangements.
B: Total 5!=120; adjacent count 2·4!=48 by a block, so nonadjacent count is 72.
C: 48 counts adjacent arrangements, the complement of the requested set.
D: Dividing all 6! linear arrangements by two does not implement the stated rotational equivalence.
C06. Rotations are identified for arrangements of the multiset A,A,B,B around a circle; reflections remain distinct. What is the number of rotational classes?
A. 6 B. 3 C. 1.5 D. 2
Answer: D
A: 6 counts linear arrangements before identifying rotations.
B: A uniform division by two is not the rotational equivalence rule.
C: 6/4 is invalid because different arrangements have different rotational orbit sizes. Counts must be integers.
D: Representatives AABB and ABAB give the two classes; their numbers of distinct rotations are four and two.
Sources and scope
This original lesson deepens combinatorial counting within Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. The official syllabus establishes the broad area; the MIT chapter provides institutional further-study support for counting methods. Examples, explanations and practice here are original. One lesson is not a claim of entire-subject mastery.
Sources opened and checked 2026-10-14.
Sign in to keep your progress. Sign in