الف- آشنایی با توابع مولد
در مورد روابط چندجمله ای بازگشتی به دست آوردن رابطه ای صریح برای n امین جمله ی حاصل از رابطه در اغلب موارد کاری مشکل به نظر می رسد. به فرض این که ما یک تعداد ضریب a0,a1,…,an,… که در روابط بازگشتی تعریف شده اند داریم اما هیچ رابطه ی موثقی برای جمله ی n ام آن پیدا نکرده ایم.an می تواند یک عدد و یا یک الگوریتم حاصل از ورودی n باشد.تابع مولد این رشته به صورت سری توانی زیر تعریف می شود:
g(x)=∑n=0 to ∞ an x^n =a0+a1x+...+anx^n+…
نخست با ذکر یک مثال که به نوعی نشان دهنده چگونگی عملکرد توابع مولد است این مبحث را ادامه می دهیم:
مثال 1 # چه تعداد عدد صحیح برای تساوی c1+c2+c3+c4=25 ; ci≥0 ; 1≤i≤4 وجود دارد؟
این سوال قابل تعمیم به بسیاری از مسایل واقعی است. به عنوان مثال " 25 شکلات چگونه بین 4 کودک تقسیم می شود ؟".برای هر کودک امکان به دست آوردن 0 تا 25 شکلات وجود دارد یا :
x^0+x ^1+…+x^24+x^25
بنابر این جواب این مساله مجموع ضرایب حاصل از جملات دارایx^25 درf(x) است یعنی:
f(x)=(1+x+..+x^25)^4
جواب حتی از راه ضرایب x^25 در تابع مولد آن است:
g(x)=(1+x+…+x^25+x^26+…)^4
ب- روش های محاسبه
تعریف1# فرض کنید a0,a1,… یک رشته از اعداد حقیقی باشند. تابع مولد رشته مزبور به صورت زیر است:
F(x)=a0+a1x+a2x^2+...=∑i=1 to ∞ aix^i
مثال 2 # برای هر عددZ>0 n εداریم:
(1+x)^n = (n,0)+(n,1)x+…+(n,n) x^n
بنابراین (1+x)^n تابع مولد رشته ی (n,0),(n,1),..,(n,n),… است.
مثال 3#
الف) برای nεZ>0 داریم:
(1-x^(n+1))=(1-x)(1+x+x^2+…+x^n)
بنابراین : 1-x)) / (1-x^(n+1))
که این تابع مولد رشته ی 1و1و...و1و0و0و0و0و...است.
ب) با تعمیم الف داریم: 1=(1-x)/(1+x+x^2+…) بنابراین 1/(1-x) تابه مولد رشته ی 1و1و1و....و1 است.این سری برای مقادیر |x|<1 همگراست.
ج) اگر از رابطه 1/(1-x) = 1+x+x^2+… مشتق بگیریم داریم:
(1/(1-x))'=(1+x+x^2+…)'=>1/(1-x)^2 =1+2x+3x^2+…
که 1/(1-x)^2 تابع مولد 1و2و3و....وn است.
د) با ادامه مشتق بگیریم می توانیم تابع مولد دیگری نیز به دست بیاوریم:
(x/(1-x)^2)'=(x+2x^2+3x^3+..) => (x+1)/(1-x)^3 =1+4x+9x^2+…
که (x+1)/(1-x)^3 1^2,2^2,3^2,… و(x+1)/(1-x)^3 x 0^2,1^2,2^2,3^2,… را تولید می کنند.
| برای n , r εZ>0که n≥r>0 داریم: (n,r)= n! /(r! (n-r)!) =[n(n-1)(n-2)…(n-r+1)] / r! اگر n عضوی از اعداد مثبت صحیح نباشد می توان از از رابطه فوق باز استفاده کرد : (-n,r) = [(-n)(-n-1)(-n-2)…(-n-r+1)] /r! = ((-1)^r) [n(n+1)..(n+r-1)] / r!] =( (-1)^r)(n+r-1,r) ودر ضمن برای هر عدد طبیعی مانند n (n,0) = 1 ; تعریف می شود. برای هرaε R و Z>0 n ,m ε داریم: 1)(1+x)^n =(n,0)+(n,1)x+(n,2)x^2+…+(n,n)x^n 2)(1+a x) ^n=(n,0)+(n,1)ax+(n,2)(ax)^2+..+(n,n)(ax)^n 3)(1+x^m)^n=(n,0)+(n,1)x^m+(n,2)x^2m+…+(n,n)x^mn 4)1/(1-x)^n= 1+x+x^2+…=∑i=0 to ∞ x^i 5)(1-x^(n+1))/(1-x) =1+x+x^2+…+x^n 6)1/(1+x)^n=(-n,0)+(-n,1)x+…=∑i=0 to ∞ (-n,i) x^i =∑i=0 to ∞ (-1^i)[(n+i-1,i) x^i] 7)1/(1-x)^n =(-n,0)+(-n,1)(-x)+…=∑i=0 to ∞ (-n,i) (–x)^i =∑i=0 to ∞ (n+i-1,i) x^i] 8)if f(x)=∑i=0 to ∞ ai x^i , ,g(x)=∑i=0 to ∞ bi x^i , h(x)=f(x)g(x) => h(x)= ∑i=0 to ∞ci x^i => for any k≥0 ck=a.bk+a1.bk-1+…+ak-1.b1+ak.b0 |
جدول ( 1)
مثال 4 # ضریب x^15 را در f(x)=(x^2+x^3+…)^4 به دست آورید.
(x^2+x^3+x^3+…)^4 = (x^8)[1+x^2+x^3+…]^4
و چون 1+x+x^2+x^3+…=1 /(1-x) آنگاه ( x^8) / [1-x]^4 در حالی که x^8 در تمامی جملات / [1-x]^41 برای 0≤r≤n ضرب میشود بایستی ضرایب x^7 را در 1 / [1-x]^4 به دست آوریم(8+7=15) در نتیجه:
((-1)^7)(-4,7)= ((-1)^7) ((-1)^7)(4+7-1,7)=(10,7)=120
مثال5 # درستی رابطهi=0 to n (n,i)^2 (2n,n)=∑ را برای nεZ>0 بدست آورید.
از آنجایی که [(1+x)^n]^2=[1+x]^2n با قیاس ضرایب ( به مانند توانهای x) ضریب x^n باید در (1+x)^2n و[(1+x)^n]^2 برابر باشند:
[(1+x)^n]^2=[(n,0)+(n,1)x+…+(n,n)x^n]^2
که در ضریب x^n در آن از مجموع ضرایب x^n به دست می آید:
(n,0).(n,n)+(n,1).(n,n-1)+…+(n,n)(n,0)
که با وجود رابطه (n,n-r)=(n,r) برای 0≤r≤n به این می رسیم که(n,0)^2 +(n,1)^2+…+(n,n)^2=∑i=0 to n :
مثال 6 # با استفاده از توابع مولد تعداد مجموعه های چهارتایی حاصل از مجموعه S={ 1,2,…,14,15} که هیچ عدد صحیح متوالی وجود ندارد ,حساب کنید.
الف) یک مجموعه مثل 1,3,7,10 که می نویسیم 1≤1<3<7<10≤15 دیده می شود که اختلاف عدد های پشت سر هم به صورت زیر است:
1-1=0 ; 3-1=2 ; 7-3=4 ; 10-7=3 ; 15-10=5
و این اعداد در مجموع برابر با 14 است. مجموعه دیگری مثل 2و5و11و15 که: 1≤2<5<11<15≤15 که مجموع اختلاف های پشت سر هم در مجموع برابر 14 می شود.در دو نمونه مذکور بایستی c1+c2+c3+c4=14;c5,c1≥0;c3,c4,c2 که جواب همان ضرایب x^14 است:
F(x)=(1+x+x^2+…).[(x^2+x^3+…)^3].(1+x+x^2+…)=x^6.(1-x)^(-5)
با توجه به ضریب x^6 بایستی ضرایب x^8 را در (1-x)^(-5) به دست آوریم: (-5,8)(-1)^8 = (5+8-1) = (12,8) = 495
ب ) راه دیگر برای نگاه به این مساله به صورت زیر است. برای مجموعه 1,3,7,10 از نامساوی 0<1<3<7<10<16 استفاده می کنیم که اختلاف ها برابر با 0 و 1 و 3 و2 و 5 است .0 از آنجایی که هیچ عددی مابین 0 و 1 نیست و 1 از آنجایی که عدد صحیح 2 بین 1 و3 است و3 عدد از آنجایی که سه عدد 4 و5 و 6 بین 3 و7 و 5عدد از آنجایی که 5 عدد صحیح 11 و 12 و13 و14 و15 بین 10 و 16 است.که مجموع 0 و 1 و2 و 3 و5 برابر 11 است.برای مجموعه دیگری مثل 2و5و11و15 نامساوی 0<2<5<11<15<16 در نظر می گیریم که نتایج 1 و2 و5 و3 و0 مجموع 11 می شود.این نتایج از راه حل c1+c2+c3+c4=11;c5,c1≥0;c3,c4,c2≥1 که جواب همان مجموع ضرایب x^11 است.
g(x)=(1+x+x^2+…)(x+x^2+x^3+…)^3(1+x+x^2+…) = x^3 .[(1-x)^(-5)]
که با توجه به x^3 باید به دنبال مجموع ضرایب x^8 در[(1-x)^(-5)] برابر است: (-5,8).(-1)^8=495 که همانند جواب در قسمت الف است.
پ – کاربرد توابع مولد در افراز اعداد صحیح
در نظریه اعداد با افراز اعداد صحیح و مثبت به عوامل صحیح و مثبت برخورد داریم. از این افراز به p(n) یاد می شود.
P(1)=1
P(2)=2=1+1
P(3)=3=2+1=1+1+1 =>The order is not important
ما می خواهیم بدون نوشتن همه افراز ها به p(n) دسترسی داشته باشیم. باید ابزاری باشد که به ما این امکان را دهد.
اگر n ε Z >0 و برای شماره اول از 0 یا 1 یا 2 یا ... می توان استفاده کرد .سری حاصل 1+x+x^2+… حساب این اعداد را در بردارد .1+x^2+x^4+x^6+… برای دومین عدد در افراز p(n) است.برای مثال برای به دست آوردن p(10) ما باید ضریب x^10 در f(x) به دست آوریم:
f(x)=(1+x+x^2+…).(1+x^2+x^4+…)…….(1+x^10+x^20+…)=[1/(1-x)].[(1/(1-x^2)]=Пi=1 to 101/(1-x^i)
اگر عمل ضرب بالاتر از i=10 تعمیم پیدا کند ما p(x)=Пi=0 to ∞ 1/1-x^i که p(0) و p(1) و p(2) و.... را تولید میکند وما p(0)=1 را تعریف می کنیم.
به دلیل دشواری کار محاسبه p(n) استفاده از توابع مولد در این مورد کارایی بسیاری دارد.
مثال 7 # تابع مولد را برای pd(n) (تعداد افراز های مثبت وصحیح n به اعداد متفاوت ) بیابید.
1)1+1+1+1+1+1+1
2)1+1+1+1+2
3)1+1+1+3
4)1+1+4
5)1+1+2+2
6)1+5
7)1+2+3
8)2+2+2
9)2+4
10)3+3
11)6
افراز های شماره 6 و7 و 9 و 11 دارای اعدادی متفاوت اند پس pd(6)=4.در محاسبه pd(n) برای هر kεZ>0 دو گزینه موجود می بلشد : یا kبه عنوان یکی از افرازهای n است یا نیست که این دو گزینه در مجموع برابر 1+x^k است پس می توان نوشت:
pd(6)=(1+x).(1+x^2)(1+x^3)….=Пi=1 to ∞(1+x^i)
برای هر n ε Z>0 pd(n) برابر مجموع ضرایب x^n در Пi=1 to ∞(1+x^i) است.(تعریف: pd(0)=1 ) و وقتی n=6 مجموع ضرایب x^6 در
(1+x).(1+x^2)(1+x^3)….(1-x^6) برابر 4 است.
مثال 8 # با ملاحظه مثال 7 می بینیم که تعداد افراز عدد 6 به اعداد فرد نیز برابر 4 است. آیا این دو ارتباطی با هم دارند؟
فرض کنیم که po(n) نشانه افراز n به اعداد فرد است(تعریف: po(0)=1)تابع مولد برای رشته po(0), po(1), po(2),…. به صورت زیر است:
po(x)=(1+x+x^2+…).(1+x^3+x^6+…)(1+x^5+x^10+…)….=[1/(1-x)][1/(1-x^3)][1/(1-x^5)]…..
و نیز با توجه به این که: 1+x=(1-x^2)/(1-x) ,1-x^2=(1-x^4)/(1-x^2) ,…….
داریم: po(x)=(1+x)(1+x^2)(1+x^3)… => [(1-x^2)/(1-x)][ (1-x^4)/(1-x^2) ]…..= [1/(1-x)][1/(1-x^3)][1/(1-x^5)]…..=pd(x) po(x)=
از تساوی دو تابع مولد =pd(x) po(x) به دست می آید.
گراف فرر
این گراف از ردیف های نقطه ای برای نمایش قسمت بندی و افراز اعداد صحیح استفاده می کند که تعداد نقاط در هر ردیف از بالا به پایین کمتر می شود.در شکل (1) دو افراز برای عدد 14 : الف)4+3+3+2+1+1 و ب)6+4+3+1 وجود دارد. به گراف در شکل 1- ب ترانهاده ی گراف در شکل 1-الف گویند و بالعکس.
| oooooo oooo ooo o (ب) | oooo ooo ooo oo o o )الف) |
شکل 1
ااین گراف ها نتایجی در مورد افراز ها به ما می دهند. در شکل 1 به عنوان مثال دو افراز برای عدد 14 آمده است. به دلیل مشابهت یک به یک گراف فرر و ترانهاده اش این مثال یک نمونه را از نتیجه کلی نشان می دهد که افراز های n به m قسمت برابر است با تعداد افراز های n به قسمت برابر است با تعداد افراز های n به قسمت هایی که m بزرگ ترین قسمت آن است.
ت – توابع مولد توانی
وقتی که ترتیب اهمیت پیدا می کند به ابزار جدیدی برای یافتن راه حل نیاز است.برای هر n ε Z>0 داریم: (1+x)^n=∑i=0 to∞ (n,r)x^r
که (1+x)^nتابع مولد رشته ی (n,0),(n,1),(n,2),…,(n,n),0,0,0,… است.وقتی می نویسیم (n,r)=cn,r می خواهیم بر این امر تاکید کنیم که (n,r) تعدادترکیبیات n شی در r صورت در یک زمان 0≤r≤n است.
Cn,r=n!/[r!(n-r)!]=(1/r!).p(n,r)
هم چنین داریم
(1+x)^n : c(n,0) + c(n,1)x + … + c(n,n)x^n= p(n,0) + p(n,1) x + p(n,2)x^2/2! + … + p(n,n) x^n/n!
هم چنین اگر در (1+x)^r ما ضرایب x^r/r! را لحاظ کنیم، به p(n,r) دست می یابیم، بر این اساس به تعریف زیر میرسیم:
تعریف2# برای رشته ی a0, a1, a2, … در اعداد حقیقی
f(n) = a0 + a1x + a2x^2/2! + … = ∑i=0 to ∞ ai (x^i)/i!
به عنوان تابع مولد توانی رشته مزبور است.
مثال 9 # با بررس بسط e^x می یابیم که
بسط e^x
e^x = 1 + x + (x^2)/2! + …
e^x تابع مولد توانی برای رشته ی 1 و 1 و 1 و ... است.
مثال 10# در چند حالت 4 حرف از کلمه ی "بیابان" قابل چینش هستند؟
در جدول2 گزینه های محتمل در اندازه 4 از حروف واژه "بیابان" نوشته شده اند.
| ا ا ب ب 4!/(2!×2!) |
| ا ی ب ب 4!/2! |
| ا ن ب ب 4!/2! |
| ن ی ب ب 4!/2! |
| ا ا ی ب 4!/2! |
| ا ا ن ب 4!/2! |
| ا ا ن ی 4!/2! |
| ا ی ن ب 4! |
جدول 2
حال ما به جواب با استفاده از توابع مولد می رسیم. برای حرف(ب) از [1+x+(x^2)/2!] استفاده می کنیم از آنجایی که 0 1 یا 2 تا( ب) برای چینش می تواند وجود داشته باشد. شایان ذکر است که ضریب x^2/2! ‚1 می باشد. برای (الف) نیز همین حالت [1+x+(x^2)/2!] را داریم و برای (ن) و(ی) هم (1+x) مورد استفاده قرار می گیرد.پس تابع مولد توانی حاصل به صورت زیر می شود:
f(x)= [1+x+(x^2)/2!]^2.[1+x]^2
و جواب همان ضریب x^4 در f(x) است.در احتساب f(x) به ضرایب زیر برای x^4 بر می خوریم:
(x^4/2!2!+x^4/2!+ x^4/2!+ x^4/2!+ x^4/2!+ x^4/2!+ x^4/2!+x^4)
که با ضرب و تقسیم x^4 در همه ضرایب داریم:
[4!/2!2! +4!/2!+ 4!/2!+ 4!/2!+ 4!/2!+ 4!/2!+ 4!/2!+4!].(x^4/4!)
در آخر جواب برابر ضریب x^4/4!(102) می شود.
مثال 11 # کیسه ای حاوی 48 توپ است که به ترتیب 12 توپ از رنگ های سرخ و زرد و آبی و سبز تشکیل می شود.می خواهیم 12 توپ انتخاب کنیم چند نوع انتخاب وجود دارد که تعداد زوج توپ آبی و تعداد فرد توپ سبز برداشته شود؟
تابع مولد توانی به صورت :
f(x)=(1+x+x^2/2!+x^3/3!+…)^2(1+x^2/2!+x^4/4!+…).(x+x^3/3!+x^5/5!)
=> f(x)=(e^x)^2.((e^x+e^(-x))/2) .((e^x-e^(-x))/2)
=>f(x)=(1/4).e^2x.(e^2x – e^(-2x))=(1/4).(e^4x - 1)
=> f(x)=(1/4)[∑i=0 to ∞(4x)^i/i! ] – 1 =(1/4)[∑i=0 to ∞(4x)^i / i! ]
جواب مسِاله ضریب x^12/12! است که برابر با (1/4)(4^12)=4^11 می شود.
مثال 12 # شرکتی 11 کارمند جدید را استخدام کرده است.هر کدام از این ها بایستی در یکی از 4 اداره وابسته به این شرکت به کارگیری شوند و نیز هر یک از این شرکت ها باید حداقل یک کارمند جدید داشته باشند. راه های به کار گیری کارمندان تازه استخدام شده چند حالت دارد؟
فرض می کنیم 4 اداره وابسته A و B و C و D باشند حال می توان از راه حل چینش 4 حرف برای ساخت یک واژه 11 حرفی استفاده کرد. تابع مولد توانی به صورت زیر می شود :
f(x)=(x+x^2/2!+….)^4 =(e^x -1)^4=e^4x – 4e^3x +6e^2x – 4e^x +1
جواب مجموع ضرایب x^11/11! است:
4^11 -4.(3^11) +6.(2^11) – 4.(1^11) = ∑i=0 to 4 [(-1)^i].(4 –i)^11]
ث – نشانه عملگر جمع در توابع مولد
برای f(x)=a0+a1x+a2x^2+… تابع f(x)/(1-x) را داریم:
f(x)/(1-x) = [a0+a1x+a2x^2+…].[1+x+x^2+…]=a0 +(a0+a1)x +( a0+a1+a2)x^2+…
پس f(x)/(1-x) رشته مجموع ضرایب a0 و a0+a1 و.... را تولید می کند.
مثال 13 # رابطه ای را برای تولید رشته 0^2+1^2+2^2+3^2+…+n^2 بیابید.
داریم:
g(x)=1/1-x=1+x+x^2+x^3+…
سپس طبق قاعده مشتق گیری داریم:
g′(x)=[1/1-x]′=1/(1-x)^2 =1+2x+3x^2+…
پس h(x)=x/[(1-x)^2] رشته 0 و 1 و 2 و3 و4 و... را تولید می کند.
k(x)=x . h′(x)=x+(2^2)x^2+(3^2)x^3+…
پس تابع k(x) تابع مولد رشته 0^2+1^2+2^2+3^2 است.
k(x)/(1-x)=[x.(1+x)/(1-x)^3 .(1/(1-x)]= x.(1+x)/(1-x)^4
هم چنین x.(1+x)/(1-x)^4 رشته 0^2 و 0^2+1^2 و 0^2+1^2+2^2 و ... را تولید می کند.که همان ضرایب x^n یا i=0 to n i^2 ∑ است.
x.(1+x)/(1 –x)^4 =(x+x^2)(1-x)^(-4)=(x+x^2)[(-4,0)+(-4,1)(-x)+…]
که ضرایب x^n برابر تعداد زیر است:
(-4,n-1)(-1)^n-1 +(-4,n-2)(-1)^n-2 =[(-1)^(n-1)].(4+(n-1)-1,n-1). (-1)^(n-1) +(-1)^(n-2).(4+(n-2)-1,n-2)(-1)^(n-2) =(n+2,n-1)+(n+1,n-2)
=> Sum of coefficients=(n+2)!/3!(n-1)! + (n+1)!/3!(n-2)!=(1/6).[(n+2)(n+1)(n) +(n+1)(n)(n-1)]=(1/6).[n(n+1)(2n+1)]
ح – حل روابط بازگشتی با استفاده از توابع مولد
فرض بر این که رشته ای از اعداد مانند a0,a1,…,an,… داریم که به وسیله روابط بازگشتی تعریف شدند ولی ما نمی دانیم که رابطه حاصل از جمله n ام به صراحت چیست.
مثال 14 # رابطه بازگشتی زیر را با استفاده از تابع مولد حل کنید.
an- 9an-1+26an-2-24an-3=0 a0=0 ; a1=1 ;a2=10
A(x)=∑n=0 to ∞ an .x^n = x + 10x^2 +∑n=3 to ∞ [(9an-1 – 26an-2 + 24 an-3)(x^n)]
=> A(x) =x + 10x^2 +
9x(A(x) – a0 –a1x) -26 (x^2).[ A(x) –a0] +24 (x^3). A(x)
=>A(x)=[1- 9x +26 x^2 – 24 x^3 ] = x + x^2
=>A(x)=(x+x^2)/ [1- 9x +26 x^2 – 24 x^3 ] = a/(1-2x) + b/(1-3x) + c/(1-4x)
با استفاده از تجزیه روابط کسری داریم:a=3/2 و b=-4 و c=5/2
A(x)=(3/2)∑(2x)^n – 4 ∑(3x)^n + (5/2) ∑ (4x)^n
=>A(x)=(1/2).∑n=0 to ∞ [ 3×(5/2) - 8×(3^n) + 5 ×4^n ].(x^n)
=>a(n)=(1/2).[3×(2^n) – 8 ×(3)^n + 5×(4)^n]جمله n ام دنباله
مراجع :
Discrete and combinatorial Mathematics an applied introduction Ralph P Grimaldi
Parallel and sequential algorithms Berman – Paul
ساختمان های گسسته بهروز قلی زاده
Introduction to Discrete Mathematics James Bradly
جلوه هایی از ترکیبیات ویکتور برایانت ترجمه : عبّاس ثروتی – مهدی محمدی
ترکیبیات (جلد 1) علی رضا علی پور
