बंधित distributions और arrangements
उद्देश्य और model की शर्तें
Repetition वाले selections, bounds वाले integer distributions, repeated-symbol arrangements और circular arrangements को सही counted object के साथ गिनना सीखें। पूर्वज्ञान: sum/product rules, factorials और combinations। सभी counts finite हैं। अलग से न कहा हो तो boxes और positions labeled हैं, identical objects के अलग labels नहीं, और rotations को एक तभी मानते हैं जब प्रश्न स्पष्ट कहे।
Formula model का परिणाम है, उसका विकल्प नहीं। पहले पूछें: objects distinct हैं? Boxes distinct हैं? Position/order महत्वपूर्ण है? Box खाली हो सकता है? Capacity limits हैं? Rotations या mirror images को एक मानना है? एक शर्त बदलने से count बदल सकता है।
1. Labeled boxes में identical objects: stars and bars
n identical objects को k labeled boxes में बिना capacity limit, खाली boxes की अनुमति के साथ बाँटना, nonnegative integers में x₁+⋯+x_k=n हल करने के बराबर है। n≥0,k≥1 के लिए count C(n+k−1,k−1) है।
Objects को n stars की पंक्ति से और k boxes को अलग करने के लिए k−1 bars से दर्शाएँ। Bars साथ-साथ या दोनों सिरों पर हो सकती हैं, क्योंकि zero-size boxes allowed हैं। हर n stars और k−1 bars वाली string ठीक एक ordered k-tuple देती है और हर tuple ठीक एक string। कुल n+k−1 positions में से k−1 bars की positions चुनें।
पाँच identical objects और तीन labeled boxes में count C(7,2)=21। Tuple (0,2,3), (2,0,3) से अलग है, क्योंकि box labels महत्वपूर्ण हैं। लेकिन पाँच distinct objects को तीन labeled boxes में बाँटने पर 3⁵=243: हर object अपना box स्वतंत्र चुनता है। Stars and bars इस product rule की जगह नहीं ले सकता।
k types में से n items चुनना, unlimited repetition allowed और order महत्वहीन हो, तो यही nonnegative-tuple model है: x_i type i की चुनी मात्रा। इसलिए combinations with repetition का count C(n+k−1,n)। यह kⁿ नहीं, जो n type choices की ordered sequences गिनता है।
2. Lower bounds को bijection से हटाएँ
x_i≥l_i, integer l_i≥0 और sum x_i=n हो तो y_i=x_i−l_i रखें। हर y_i≥0 और उनका sum N=n−Σl_i। N<0 में कोई solution नहीं। N≥0 में count C(N+k−1,k−1)। Shift bijection है, इसलिए न कोई solution छूटता है, न दो बार गिना जाता है।
उदाहरण: नौ identical tokens चार labeled boxes में दें, जहाँ x₁≥1,x₂≥0,x₃≥2,x₄≥1। पहले 1+0+2+1=4 tokens reserve करें। बचे पाँच चार boxes में unrestricted हैं, इसलिए C(8,3)=56। C(12,3) लेने से reservations छूटते हैं; C(5,3) लेने से केवल stars और कुल stars-plus-bars positions में भ्रम होता है।
हर k box को कम-से-कम एक देना हो तो यही shift n≥k में C(n−1,k−1) देता है। n<k में count शून्य। Feasibility जाँचें; याद किए factorial formula में negative arguments न डालें।
3. Upper bounds में subtraction या generating factors चाहिए
Upper bound हटाने के लिए केवल objects की कुल संख्या कम करना सही नहीं। सभी nonnegative solutions गिनें, capacity तोड़ने वाले घटाएँ और overlaps का inclusion–exclusion से सुधार करें।
x₁+x₂+x₃=6 लें, जहाँ 0≤x₁≤3,0≤x₂≤2,x₃≥0। Upper bounds के बिना C(8,2)=28 solutions। Bad event A: x₁≥4; x₁ से 4 घटाने पर total 2 बचता है, इसलिए C(4,2)=6। Bad event B: x₂≥3; x₂ से 3 घटाने पर total 3, इसलिए C(5,2)=10। दोनों साथ नहीं हो सकते क्योंकि 4+3>6। उत्तर 28−6−10=12।
Direct check: x₁ के choices 0,1,2,3 और x₂ के 0,1,2। इन 4·3 pairs का sum अधिकतम 5 है और हर pair एक nonnegative x₃=6−x₁−x₂ तय करता है। स्वतंत्र तरीके से भी 12 मिलता है।
Bounds 0≤x_i≤u_i के लिए general inclusion–exclusion में S⊆{1,…,k} वाली term हर selected coordinate से u_i+1 घटाती है। Residual total n−Σ(i∈S)(u_i+1) है। (−1)^|S| के अनुसार nonnegative-solution count जोड़ें/घटाएँ; residual negative हो तो zero लें। +1 जरूरी है: x_i≤u_i का उल्लंघन x_i≥u_i+1 होता है।
इसी तरह ∏(1+x+⋯+x^{u_i}) में xⁿ का coefficient distributions गिनता है। इससे पहले ordinary-generating-function पाठ का संबंध बनता है; coefficients को probabilities नहीं मानते।
4. Repeated symbols: केवल वास्तविक symmetries का division
Multiset में n symbols हों, multiplicities n₁,…,n_k का sum n हो, तो distinct linear arrangements n!/(n₁!⋯n_k!) हैं। समान symbols पर temporary labels लगाएँ, सभी n! permutations गिनें, फिर labels भूल जाएँ। हर visible arrangement के ठीक n₁!⋯n_k! labeled versions हैं, इसलिए division उचित है।
तीन A, दो B और एक C की arrangements 6!/(3!2!)=60। Positions distinct हैं, एक ही letter की copies distinct नहीं। सभी छह symbols distinct मानने से overcount; letter counts को एक unordered selection मानने से positional differences छूटते हैं।
Restrictions से count बदलता है। उसी multiset में कोई दो A adjacent न हों: पहले दो B और एक C को 3!/2!=3 तरीकों से arrange करें। तीन symbols से चार gaps बनते हैं, दोनों सिरों सहित। तीन identical A को तीन अलग gaps में C(4,3)=4 तरीकों से रखें। उत्तर 3·4=12। हर gap में अधिकतम एक A से nonadjacency लागू है। A identical हैं, इसलिए अतिरिक्त 3! नहीं चाहिए।
Gap argument bijection है: valid arrangement से सभी A हटाएँ तो ठीक एक base arrangement और चुने gaps वापस मिलते हैं। उन्हीं तीन दूसरे symbols के बीच पाँच A रखने हों तो कोई valid arrangement नहीं, क्योंकि केवल चार gaps हैं।
5. Circular arrangements में equivalence rule स्पष्ट रखें
n≥1 distinct people को unlabeled round table के चारों ओर बैठाएँ, rotations एक माने जाएँ और reflections अलग, तो count (n−1)!। एक designated व्यक्ति को anchor मानें और बाकी n−1 का clockwise order तय करें। इससे हर rotational class एक बार गिनी जाती है और division की अस्पष्टता बचती है।
छह distinct people में 5!=120। छह seats पर अलग seat numbers हों तो rotations equivalent नहीं, इसलिए 6!=720। केवल table का गोल आकार counting rule तय नहीं करता।
Mirror images भी एक मानी जाएँ तो n≥3 distinct people में count (n−1)!/2। सब distinct हैं, इसलिए clockwise order उलटने से अलग rotational class बनती है और हर reflection-pair में ठीक दो members होते हैं। छह लोगों में 60। Repeated-symbol necklaces या n=1,2 पर यह division अपने आप न लगाएँ।
Repeated symbols के rotational periods अलग हो सकते हैं। A,A,B,B की छह linear arrangements को सीधे चार से divide नहीं कर सकते: 6/4 integer भी नहीं। Rotational classes के representatives AABB और ABAB हैं। पहले की चार distinct rotations, दूसरे की दो। Uniform division इसलिए गलत कि class sizes बराबर नहीं। General necklace counting को अतिरिक्त symmetry method चाहिए।
6. Circular adjacency में block, सही assumptions के साथ
छह distinct people A,B,C,D,E,F को unlabeled round table पर बैठाएँ; rotations एक और reflections अलग हैं। A और B adjacent हों तो कितनी arrangements? A,B को एक block बनाएँ। पाँच distinct circular objects हैं, इसलिए (5−1)!=24 arrangements और block के दो internal orders। Count 2·24=48।
कुल 120 हैं, इसलिए A,B nonadjacent arrangements 120−48=72। यहाँ block method सही है क्योंकि बाकी सभी people distinct और contraction के बाद कम-से-कम तीन circular objects हैं। जटिल overlapping adjacency शर्तों में blocks merge हो सकते हैं या constraints विरोधी; बिना जाँच independently multiply न करें।
हल की जाँच-सूची और आगे का दायरा
Counted object को tuple, word, function या equivalence class के रूप में लिखें। Lower bounds पहले shift करें और feasibility जाँचें। Upper bounds के bad events में capacity से एक अधिक threshold रखें और intersections गिनें। Repeated symbols में वही constant multiplicity पहचानें जो division को सही बनाती है। Circular प्रश्न में कौन-सी symmetries एक हैं, बताएँ। Unlabeled-box partitions, general necklace symmetry और advanced partition identities के लिए अन्य methods चाहिए; वे stars and bars में अपने आप शामिल नहीं।
मौलिक अभ्यास: छह single-correct MCQ
मौलिक प्रश्न हैं, पिछले वर्षों के नहीं। हर प्रश्न में ठीक एक विकल्प चुनें और labels, symmetry, domain तथा positivity की दी शर्तें रखें।
C01. पाँच identical objects को तीन labeled boxes में कितने तरीकों से बाँट सकते हैं, जहाँ खाली boxes allowed और upper bounds नहीं?
A. 243 B. 21 C. 10 D. 15
उत्तर: B
A: 3⁵ में पाँच distinct objects independently box चुनते हैं, identical नहीं।
B: x₁+x₂+x₃=5 के nonnegative solutions C(5+3−1,3−1)=C(7,2)=21।
C: C(5,2) केवल objects की positions में से चुनता है; combined representation की bars छूटती हैं।
D: यह संबंधित binomial count नहीं; ordered nonnegative triples गिनें या सात star/bar positions लें।
C02. x₁+x₂+x₃+x₄=9 में x₁≥1,x₂≥0,x₃≥2,x₄≥1 की कितनी integer solutions हैं?
A. 220 B. 20 C. 10 D. 56
उत्तर: D
A: C(12,3)=220 सभी lower bounds छोड़ता है।
B: यह पाँच residual objects को चारों labeled coordinates में सही नहीं बाँटता।
C: C(5,3)=10 केवल residual stars लेता है, तीन bars की positions नहीं।
D: Lower bounds का total 4 घटाएँ; residual 5 चार nonnegative coordinates में C(8,3)=56।
C03. कितनी nonnegative integer triples x₁+x₂+x₃=6, x₁≤3 और x₂≤2 पूरा करती हैं?
A. 12 B. 28 C. 18 D. 6
उत्तर: A
A: x₁ के 4 और x₂ के 3 choices में sum अधिकतम 5; हर pair valid x₃ तय करता है। या 28−6−10=12।
B: 28 दोनों upper bounds छोड़ता है।
C: केवल x₂≥3 की दस solutions घटाने पर x₁≤3 का उल्लंघन बचता है।
D: 6 unrestricted universe में bad event x₁≥4 गिनता है, valid triples नहीं।
C04. A,A,A,B,B,C की कितनी linear arrangements में दो A adjacent नहीं हैं?
A. 60 B. 24 C. 12 D. 72
उत्तर: C
A: 60 सभी multiset arrangements हैं, adjacent A वाली भी।
B: दो B copies distinct मानने से base arrangements दो गुनी हो जाती हैं।
C: B,B,C को 3!/2!=3 तरीकों से रखें; चार gaps में तीन चुनें: 3·C(4,3)=12।
D: Valid gap count को 3! से multiply करने पर identical A copies को गलत labels मिलते हैं।
C05. छह distinct people unlabeled round table पर बैठते हैं; rotations एक और reflections अलग हैं। निश्चित A,B nonadjacent हों तो कितनी arrangements?
A. 120 B. 72 C. 48 D. 360
उत्तर: B
A: 120, adjacent A,B हटाने से पहले का total।
B: कुल 5!=120; block से adjacent count 2·4!=48, इसलिए nonadjacent 72।
C: 48 adjacent arrangements गिनता है, माँगे set का complement।
D: सभी 6! linear arrangements को दो से divide करने से बताई rotational equivalence लागू नहीं होती।
C06. Multiset A,A,B,B की circular arrangements में rotations एक और reflections अलग हैं। Rotational classes कितनी हैं?
A. 6 B. 3 C. 1.5 D. 2
उत्तर: D
A: 6, rotations पहचानने से पहले linear arrangements हैं।
B: दो से uniform division rotational equivalence rule नहीं।
C: 6/4 गलत है क्योंकि rotational orbit sizes अलग हैं। Counts integer होने चाहिए।
D: Representatives AABB और ABAB दो classes देते हैं; उनकी distinct rotations क्रमशः चार और दो।
स्रोत और दायरा
यह मौलिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 में Discrete Mathematics के combinatorial counting भाग को गहरा करता है। आधिकारिक syllabus व्यापक विषय बताता है; MIT chapter counting methods का संस्थागत further-study स्रोत है। यहाँ examples, व्याख्या और अभ्यास मौलिक हैं। एक पाठ से पूरे subject में mastery का दावा नहीं।
स्रोत खोले और जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन