Ordinary generating functions और coefficients
उद्देश्य और पूर्वज्ञान
Sequence को formal power series में लिखना, sums/products/shifts का उपयोग, counting restrictions से factors बनाना, coefficients निकालना और linear recurrence को rational generating function में बदलना सीखें। पूर्वज्ञान: counting principles, binomial coefficients और recurrence relations। यहाँ ordinary generating functions या OGFs हैं; exponential generating functions, analytic convergence और asymptotic singularity methods अलग विषय हैं।
हर sequence index 0 से शुरू है। Rational या real coefficients वाली formal power series लेते हैं। x यहाँ हिसाब रखने वाला symbol है; किसी अनंत numerical sum का converge होना आवश्यक नहीं। Nonzero constant term वाला rational denominator, x=0 के आसपास formal series expansion देता है। अनंत formal identity में x=1 जैसी संख्या रखना अपने आप वैध नहीं; उसके लिए अतिरिक्त convergence reasoning चाहिए।
1. Coefficient एक sequence term रखता है
a₀,a₁,a₂,… के लिए A(x)=Σₙ≥₀aₙxⁿ=a₀+a₁x+a₂x²+… परिभाषित करें। [xⁿ]A(x) का अर्थ xⁿ का coefficient है, अर्थात aₙ। इसका अर्थ x की जगह n रखकर function का मान निकालना नहीं।
1,1,1,… का OGF है 1+x+x²+…=1/(1−x)। 1−x से गुणा करने पर हर positive-degree term कटती है और 1 बचता है; यह coefficient-दर-coefficient identity जाँचता है। सामान्यतः 1,c,c²,… का OGF 1/(1−cx) है।
0,1,1,1,… का OGF x/(1−x) है, 1/(1−x) नहीं, क्योंकि constant coefficient 0 है। 1,0,1,0,1,… का OGF 1/(1−x²) है। Index जाँचने के लिए पहली कुछ coefficients हमेशा देखें।
2. Addition और shifts
A में aₙ और B में bₙ हों तो αA+βB में αaₙ+βbₙ होंगे। Nonnegative integer k के लिए xᵏ से गुणा करने पर शुरुआत में k zeros आते हैं: n≥k पर [xⁿ]xᵏA(x)=aₙ₋ₖ और n<k पर 0। इससे coefficients shift होती हैं; nth coefficient को nᵏ से गुणा नहीं करते।
Initial term हटाते समय सावधानी रखें। Σₙ≥1aₙxⁿ=A(x)−a₀। साथ ही Σₙ≥1aₙ₋₁xⁿ=xA(x)। Sum n=2 से शुरू हो तो Σₙ≥2aₙ₋₁xⁿ=x(A(x)−a₀), जबकि Σₙ≥2aₙ₋₂xⁿ=x²A(x)। Recurrence solution के numerators इन्हीं lower limits से आते हैं।
जैसे A=1+3x+5x²+… हो तो x²A=x²+3x³+5x⁴+…। x⁴ का coefficient a₂=5 है, a₄ नहीं। Off-by-one गलती बहुत algebra करने पर भी बच सकती है; simplify करने से पहले दो-तीन terms लिखें।
3. Multiplication का अर्थ convolution
A(x)B(x) में xⁿ का coefficient Σₖ₌₀ⁿ aₖbₙ₋ₖ है। Total exponent n के लिए पहले factor से xᵏ और दूसरे से xⁿ⁻ᵏ लें, फिर सभी splits जोड़ें। यह convolution है, termwise multiplication aₙbₙ नहीं।
हल किया finite उदाहरण: (1+2x)(1+x+x²)=1+3x+3x²+2x³। x² का coefficient 1·1+2·1=3। Termwise product गलत रूप से 0 देगा, क्योंकि पहले polynomial में x² term नहीं।
1/(1−x) का square, ordered nonnegative pairs (u,v) को u+v से गिनता है। Total n पर pairs (0,n),(1,n−1),…,(n,0) हैं, इसलिए [xⁿ](1−x)⁻²=n+1। अतः 1/(1−x)² में 1,2,3,… आते हैं, जबकि x/(1−x)² में 0,1,2,…। अतिरिक्त x indexing बदलता है, केवल लिखावट नहीं।
4. हर स्वतंत्र choice का एक factor
u कोई भी nonnegative integer हो तो factor 1+x+x²+…। 0≤u≤m हो तो 1+x+…+xᵐ। u even होना चाहिए तो 1+x²+x⁴+…। u≥r हो तो xʳ/(1−x)। Exponent चुनी मात्रा रखता है; coefficient बताता है कि उस मात्रा के कितने distinguishable choices हैं।
स्वतंत्र labeled variables के factors गुणा करें। u+v=4, 0≤u≤2,v≥0 के लिए (1+x+x²)/(1−x)। x⁴ का coefficient 3 है, solutions (0,4),(1,3),(2,2)। 2! से भाग न दें: u,v नामित variables हैं; उनके मान बदलने से अलग solution बन सकता है।
दो अलग item types का allowed weight 1 हो तो उनके alternatives का योगदान 2x है, x नहीं। Generating function प्रश्न की वास्तविक distinguishability को model करती है; एक outcome का अर्थ स्पष्ट न हो तो algebra उसे ठीक नहीं कर सकता।
5. Nonnegative और bounded solutions
k labeled nonnegative integer variables का sum n हो तो OGF (1−x)⁻ᵏ है। Integers k≥1,n≥0 के लिए coefficient C(n+k−1,k−1)। Counting proof में n समान stars और k−1 separators लगाएँ। Separators के पहले, बीच और बाद के stars ordered variable values देते हैं। साथ-साथ separators zero बताते हैं; बिना बताए positivity की शर्त न जोड़ें।
Positive variables हों तो हर एक में से 1 घटाएँ या xᵏ से गुणा करें। u≥2,v≥1,w≥0 और u+v+w=7 हो तो अनिवार्य total 3 हटाएँ। बची तीन nonnegative quantities का sum 4 है, इसलिए C(6,2)=15 solutions। OGF x³/(1−x)³ है; उसका x⁷ coefficient भी यही है।
हल किया bounded उदाहरण: 0≤u,v,w≤2 और u+v+w=4। OGF (1+x+x²)³=(1−x³)³/(1−x)³। x⁴ के coefficient में numerator के केवल 1−3x³ terms काम करेंगे; आगे की degrees कम-से-कम 6 हैं। इसलिए count=C(6,2)−3C(3,2)=15−9=6।
सीधे जाँचें: (2,2,0) के permutations से 3 और (2,1,1) से 3, कुल 6। Inclusion–exclusion में 15 सभी nonnegative solutions हैं। Upper bound तोड़ने वाले हर variable का मान कम-से-कम 3 है; फिर total 1 बचता है और C(3,2)=3 solutions। दो violations के लिए total कम-से-कम 6 चाहिए, जो यहाँ असंभव है।
6. Recurrence से rational OGF निकालें
b₀=3,b₁=7 और bₙ=3bₙ₋₁−2bₙ₋₂, n≥2, लें। B(x)=Σₙ≥₀bₙxⁿ लिखें। Recurrence को xⁿ से गुणा करके केवल n≥2 पर sum लें:
B(x)−3−7x = 3x(B(x)−3)−2x²B(x)।
Terms इकट्ठा करने पर (1−3x+2x²)B(x)=3−2x, इसलिए
B(x)=(3−2x)/[(1−x)(1−2x)] = −1/(1−x)+4/(1−2x)।
अंतिम equality partial fractions है। दायाँ भाग जोड़ने पर numerator −(1−2x)+4(1−x)=3−2x। Coefficients से bₙ=−1+4·2ⁿ। b₀=3,b₁=7,b₂=15 जाँचें। Denominator recurrence बताता है, लेकिन initial values numerator तय करती हैं। उन्हें छोड़ने से दूसरी sequence बनेगी।
7. Repeated factors और forced recurrence
Convolution के परिणाम में x की जगह cx रखने पर [xⁿ](1−cx)⁻²=(n+1)cⁿ मिलता है। इसलिए denominator का repeated factor, n का polynomial factor देता है; यह recurrence के repeated-root व्यवहार से मेल खाता है।
e₀=1 और eₙ=2eₙ₋₁+2ⁿ, n≥1, लें। E(x)=Σₙ≥₀eₙxⁿ के लिए sum करने पर
E(x)−1=2xE(x)+2x/(1−2x)।
अतः (1−2x)E(x)=1+2x/(1−2x)=1/(1−2x), और E(x)=1/(1−2x)²। इसलिए eₙ=(n+1)2ⁿ, सही initial value सहित। यह पहले 2ⁿ से भाग देने वाली विधि को स्वतंत्र रूप से जाँचता है।
8. Counting recurrence और index की जाँच
लगातार दो 1 के बिना binary strings के लिए f₀=1,f₁=2 और fₙ=fₙ₋₁+fₙ₋₂, n≥2। Sum करने से F(x)−1−2x=x(F(x)−1)+x²F(x), इसलिए F(x)=(1+x)/(1−x−x²)।
इसके विपरीत standard Fibonacci F₀=0,F₁=1 का OGF x/(1−x−x²)। Denominators समान, numerators अलग: initial values अलग हैं। Binary-string count 1,2,3,5,8,… से शुरू है, 0,1,1,2,3,… से नहीं। केवल denominator देखकर sequences समान न मानें।
काम की जाँच-सूची
Counted objects और index-0 term स्पष्ट करें। Allowed choices से factors बनाएँ, केवल याद की शक्ल से नहीं। Products में exponents जोड़ें और सभी splits का sum लें। Recurrence sums में starting indices रखें तथा initial terms घटाएँ। माँगा coefficient निकालकर छोटी enumeration या direct recurrence से जाँचें। Numerical count पूछा हो तो पूरा generating function नहीं, exact coefficient उत्तर दें।
मौलिक अभ्यास: छह single-correct MCQ
मौलिक प्रश्न हैं, पिछले वर्षों के नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। दिए index, domain और graph conventions लागू रखें।
C01. [x⁴] x²/(1−x)² का मान क्या है?
A. 3 B. 5 C. 4 D. 10
उत्तर: A
A: x² factor से [x²](1−x)⁻² पूछते हैं, जिसका मान 2+1=3।
B: 5, शुरुआती x² shift के बिना [x⁴](1−x)⁻² है।
C: यह exponent को coefficient मानता है और shift तथा n+1 rule दोनों छोड़ता है।
D: Shifted series x²+2x³+3x⁴+… में माँगा coefficient 10 नहीं।
C02. (1+2x)(1+x+x²) में x² का coefficient क्या है?
A. 2 B. 0 C. 3 D. 1
उत्तर: C
A: यह केवल (2x)·x गिनता है और 1·x² छोड़ता है।
B: Coefficients का product convolution है, दोनों x² coefficients का सीधा गुणा नहीं।
C: योगदान 1·x² और (2x)·x हैं; 1+2=3।
D: यह केवल 1·x² गिनता है और (2x)·x छोड़ता है।
C03. कितनी labeled integer triples (u,v,w), u+v+w=4 तथा 0≤u,v,w≤2 पूरा करती हैं?
A. 15 B. 9 C. 3 D. 6
उत्तर: D
A: 15 upper bounds के बिना सभी nonnegative triples गिनता है।
B: 9 invalid triples हैं जिनका कोई coordinate कम-से-कम 3 है; valid नहीं।
C: (2,2,0) के तीन permutations के अलावा (2,1,1) के भी तीन हैं।
D: (1+x+x²)³ में x⁴ का coefficient 15−3·3=6; अलग types से 3+3 भी।
C04. u+v+w=7, u≥2,v≥1,w≥0 की कितनी labeled integer solutions हैं?
A. 21 B. 15 C. 10 D. 6
उत्तर: B
A: अनिवार्य lower bounds का total 3 है; 4 बचता है, 5 नहीं।
B: u′=u−2,v′=v−1 लें; तीन nonnegative variables का sum 4, इसलिए C(6,2)=15।
C: यह दूसरे variable को भी positive मानकर allowed zero cases हटाता है।
D: पिछले प्रश्न का upper bound 2 यहाँ नहीं; उसे साथ न ले आएँ।
C05. b₀=3,b₁=7 तथा bₙ=3bₙ₋₁−2bₙ₋₂ (n≥2) के लिए B(x)=N(x)/(1−3x+2x²) में सही numerator N(x) क्या है?
A. 3 B. 3+7x C. 3−2x D. 7−3x
उत्तर: C
A: इससे b₁=9 मिलेगा, आवश्यक 7 नहीं।
B: Shifted sum n=2 से शुरू होने पर आने वाला 3xb₀ contribution नहीं घटाया गया।
C: B−3−7x=3x(B−3)−2x²B से numerator 3+(7−9)x=3−2x।
D: Constant coefficient से b₀=3 के बजाय 7 होगा।
C06. f₀=1 सहित, लगातार दो 1 के बिना length-n binary strings की संख्या fₙ का OGF क्या है?
A. (1+x)/(1−x−x²) B. x/(1−x−x²) C. 1/(1−x−x²) D. (1−x)/(1−x−x²)
उत्तर: A
A: f₀=1,f₁=2 से numerator f₀+(f₁−f₀)x=1+x।
B: यह शुरुआती 0,1 वाला standard Fibonacci OGF है, आवश्यक 1,2 नहीं।
C: पहली coefficients 1,1 हैं; length-1 count गलत।
D: पहली coefficients 1,0 हैं; फिर f₁=2 गलत।
स्रोत और दायरा
यह मौलिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 1 में Discrete Mathematics के बताए विषय को विकसित करता है। इससे पूरा subject या syllabus समाप्त होने का दावा नहीं है। Syllabus प्रासंगिकता और संस्थागत course chapter आगे पढ़ने का स्रोत है। Worked examples, भाषा और अभ्यास मौलिक हैं।
स्रोत खोले और जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन