ÄÉÁÊÑÉÔÁ ÌÁÈÇÌÁÔÉÊÁ Ôá ÌáèçìáéêÜ çò ÅðéóÞìçò ùí Õðïëïãéóþí
ËåõÝñçò Ì. Êõñïýóçò ×ñÞóïò É. Ìðïýñáò áýëïò . ÓðõñÜêçò
2
åñéå÷üìåíá
1
Óïé÷åéþäçò ÓõíäõáóéêÞ
2
åííÞñéåò ÓõíáñÞóåéò
3
Ó÷Ýóåéò ÁíáäñïìÞò
4
Èåùñßá ÌÝñçóçò Polya
5
Åãêëåéóìüò - Áðïêëåéóìüò
1.1 1.2 1.3 1.4 1.5 1.6 1.7
2.1 2.2 2.3 2.4 2.5
ÅéóáãùãÞ . . . . . . . . . . . . . . . . . . Äéùíõìéêïß ÓõíåëåóÝò . . . . . . . . . . ÏìÜäåò Ìç ÄéáêåêñéìÝíùí ÁíéêåéìÝíùí . Óõíäõáóìïß êáé ÄéáÜîåéò ìå ÅðáíÜëçøç . Õðïóýíïëá . . . . . . . . . . . . . . . . . ÄéáíïìÝò ÁíéêåéìÝíùí óå Õðïäï÷Ýò . . . ÁóêÞóåéò . . . . . . . . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . . . .
. . . . .
. . . . .
. . . . . . .
. . . . .
. . . . .
. . . . . . .
. . . . .
. . . . .
. . . . . . .
. . . . .
. . . . .
. . . . . . .
. . . . . . .
1
. 1 . 2 . 5 . 7 . 8 . 9 . 11
. . . . . . . .
. . . . .
. . . . .
. . . . . . .
. . . . . . . .
. . . . .
. . . . .
. . . . . . .
3.1 ÅéóáãùãÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 ñáììéêÝò Ó÷Ýóåéò ÁíáäñïìÞò ìå óáèåñïýò óõíåëåóÝò . . . 3.2.1 Ëýóç ìå ç ìÝèïäï çò ÷áñáêçñéóéêÞò åîßóùóçò . . . 3.2.2 Ëýóç ìå ç ìÝèïäï ùí ãåííçñéþí óõíáñÞóåùí . . . 3.3 Ìç ãñáììéêÝò Ó÷Ýóåéò ÁíáäñïìÞò . . . . . . . . . . . . . . . 3.3.1 Ëýóç çò çëåóêïðéêÞò ó÷Ýóçò áíáäñïìÞò . . . . . . . 3.3.2 Ëýóç çò ó÷Ýóçò áíáäñïìÞò ðïõ ïñßæåáé ìå óõíÝëéîç . 3.4 ÁóêÞóåéò . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . . . .
. . . . .
. . . . .
. . . . .
. . . . . . .
. . . . .
ÅéóáãùãÞ . . . . . . . . . Éäéüçåò ÁíéìåáèÝóåùí Ôýðïò ïõ Burnside . . . Èåþñçìá Polya . . . . . . ÁóêÞóåéò . . . . . . . . .
. . . . .
. . . . . . .
. . . . .
4.1 4.2 4.3 4.4 4.5
ÅéóáãùãÞ . . . . . . . . . . . . . . . . . Éäéüçåò ùí åííçñéþí ÓõíáñÞóåùí . ÁðáñéèìçÝò . . . . . . . . . . . . . . . . ÅêèåéêÝò åííÞñéåò ÓõíáñÞóåéò . . . ÁóêÞóåéò . . . . . . . . . . . . . . . . .
. . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
13
13 14 24 28 32
35
35 36 36 39 42 42 44 47
51
51 54 54 57 60
63
5.1 ÅéóáãùãÞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Ç áñ÷Þ ïõ Åãêëåéóìïý - Áðïêëåéóìïý . . . . . . . . . . . . . . . 64 5.3 ÁóêÞóåéò . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3
4
ÅÑÉÅ×ÏÌÅÍÁ
6
Âéâëéïãñáößá
69
7
Ëßóá Óõìâüëùí
71
ÊåöÜëáéï 1 Óïé÷åéþäçò ÓõíäõáóéêÞ 1.1
ÅéóáãùãÞ
Óå áõü ï êåöÜëáéï èá ðåñéãñÜøïõìå ìåñéêïýò óïé÷åéþäåéò ñüðïõò íá ìåñÜìå ðåðåñáóìÝíá áíéêåßìåíá Þ ãåãïíüá. ¼áí ìåñÜìå ÷ñçóéìðïðïéïýìå ðïëý óõ÷íÜ, ó÷åäüí ðÜíá üìùò ÷ùñßò íá ï áíáöÝñïõìå ñçÜ, ïõò ðáñáêÜù äýï âáóéêïýò êáíüíåò: Áí Ýíá ãåãïíüò ìðïñåß íá óõìâåß êáÜ m ñüðïõò êáé Ýíá Üëëï ãåãïíüò ìðïñåß íá óõìâåß êáÜ n ñüðïõò, üå õðÜñ÷ïõí m + n ï ðëÞèïò ñüðïé êáÜ ïõò ïðïßïõò Ýíá áðü á äýï ãåãïíüá ìðïñåß íá óõìâåß. Êáíüíáò ïõ áèñïßóìáïò:
Áí Ýíá ãåãïíüò ìðïñåß íá óõìâåß êáÜ m ñüðïõò êáé Ýíá Üëëï ãåãïíüò ìðïñåß íá óõìâåß êáÜ n ñüðïõò, üå õðÜñ÷ïõí m · n ï ðëÞèïò ñüðïé êáÜ ïõò ïðïßïõò êáé á äýï ãåãïíüá ìðïñïýí íá óõìâïýí. Êáíüíáò ïõ ãéíïìÝíïõ:
áñÜäåéãìá 1.1: Áò õðïèÝóïõìå üé óï áíåðéóÞìéï õðÜñ÷ïõí 7 ìáèÞìáá ðñùúíÜ êáé 5 ìáèÞìáá áðïãåõìáéíÜ. üóåò åðéëïãÝò Ý÷åé Ýíáò óðïõäáóÞò ãéá íá ðÜñåé 1 ðñùúíü êáé 1 áðïãåõìáéíü ìÜèçìá; üóåò Ý÷åé Ýíáò Üëëïò óðïõäáóÞò ðïõ åíäéáöÝñåáé íá ðÜñåé Ýíá ìüíï ìÜèçìá (áäéáöïñþíáò ãéá áðüãåõìá Þ ðñùß);
ÕðÜñ÷ïõí 7 × 5 = 35 åðéëïãÝò ãéá Ýíá óðïõäáóÞ ðïõ èÝëåé íá ðÜñåé 1 ðñùéíü êáé 1 áðïãåõìáéíü ìÜèçìá. Åíþ ãéá Ýíá óðïõäáóÞ ðïõ èÝëåé íá ðÜñåé ìüíï 1 ìÜèçìá (áäéáöïñþíáò ãéá áðüãåõìá Þ ðñùß) õðÜñ÷ïõí 7 + 5 åðéëïãÝò.
Ëýóç.
Áí áðü ìßá óõëëïãÞ n áíéêåéìÝíùí èÝëïõìå íá åðéëÝîïõìå r ÷ùñßò íá Ý÷åé óçìáóßá ç óåéñÜ åðéëïãÞò, üå ï áñéèìüò ùí ñüðùí ðïõ åßíáé äõíáü íá ãßíåé áõü êáëåßáé áñéèìüò ùí óõíäõáóìþí r áíéêåéìÝíùí åðéëåãìÝíùí áðü n áíéêåßìåíá êáé óõìâïëßæåáé ìå C (n; r). ÅíáëëáêéêÜ ÷ñçóéìïðïéïýìå êáé ï óõìâïëéóìü nr (ðñïöÝñåáé: n áíÜ r Þ r áðü n), áíß ïõ C (n; r) : Áí ðÜëé áðü ìßá óõëëïãÞ n áíéêåéìÝíùí èÝëïõìå íá åðéëÝîïõìå r êáé íá á óïé÷ßóïõìå ï Ýíá êáüðéí ïõ Üëëïõ, üå ï áñéèìüò ùí ñüðùí ðïõ ìðïñåß íá ãßíåé áõü êáëåßáé áñéèìüò ùí äéáÜîåùí r áíéêåéìÝíùí åðéëåãìÝíùí áðü n áíéêåßìåíá êáé óõìâïëßæåáé ìå P (n; r). Åßíáé ó÷åéêÜ áðëü íá õðïëïãßóïõìå ï P (n; r). ÕðÜñ÷ïõí n äõíáïß ñüðïé 1
2
ÊÅÖÁËÁÉÏ 1.
ÓÔÏÉ×ÅÉÙÄÇÓ ÓÕÍÄÕÁÓÔÉÊÇ
íá åðéëåãåß ï ðñþï áðü á r áíéêåßìåíá, n − 1 ñüðïé íá åðéëåãåß ï äåýåñï, ê.ï.ê. Ýùò ï åëåõáßï, ãéá ï ïðïßï õðÜñ÷ïõí n − r + 1 ñüðïé íá åðéëåãåß. ÅðïìÝíùò ï óõíïëéêüò áñéèìüò ùí äéáÜîåùí åßíáé:
P (n; r) = n (n − 1) : : : (n − r + 1) =
n! : (n − r )!
(1.1)
¸íá Üìåóï óõìðÝñáóìá ïõ ýðïõ (1.1) åßíáé üé õðÜñ÷ïõí r! ñüðïé íá äéáÜîïõìå r áíéêåßìåíá, äçëáäÞ õðÜñ÷ïõí r! áíéìåáèÝóåéò r áíéêåéìÝíùí. Áò ðñï÷ùñÞóïõìå þñá êáé óïí õðïëïãéóìü ïõ C (n; r). áñáçñïýìå üé P (n; r) = P (r; r) · C (n; r). Ï ýðïò áõüò éó÷ýåé äéüé ïé äéáÜîåéò ðñïêýðïõí áðü ïõò óõíäõáóìïýò èåùñþíáò ãéá ïí êÜèå óõíäõáóìü ïõò äéáöïñåéêïýò ñüðïõò êáÜ ïõò ïðïßïõò ìðïñïýí íá áíéìåáåèïýí á áíéêåßìåíÜ ïõ. Ìå âÜóç ïí ýðï (1.1) þñá ðñïêýðåé:
C (n; r) =
n! r! (n − r)!
=
n (n − 1) : : : (n − r + 1) : r!
(1.2)
Ìå ðüóïõò ñüðïõò ìðïñïýí 3 åîåÜóåéò íá ðñïãñáììáéóïýí ìÝóá óå ìéá ðåñßïäï 5 çìåñþí, Ýóé þóå íá ìçí Ý÷ïõìå äõï åîåÜóåéò çí ßäéá çìÝñá; áñÜäåéãìá 1.2:
ÅðåéäÞ ðñüêåéáé ãéá óõãêåêñéìÝíåò åîåÜóåéò, åßíáé öáíåñü üé Ý÷åé óçìáóßá êáé ç óåéñÜ ðïõ èá ãßíïõí áõÝò. ¢ñá ç áðÜíçóç åßíáé P (5; 3) = 60. Ëýóç.
Ìå ðüóïõò ñüðïõò Ýíáò ìÜãåéñáò ìðïñåß íá ðñïãñáììáßóåé êáÜ ç äéÜñêåéá ìéáò åâäïìÜäáò 3 ãåýìáá ìå êñÝáò; áñÜäåéãìá 1.3:
ÅðåéäÞ äåí êáèïñßæïíáé á ãåýìáá êñÝáïò, ç áðÜíçóç åßíáé ï áñéèìüò ùí óõíäõáóìþí 3 çìåñþí áðü éò 7, äçëáäÞ C (7; 3) = 35.
Ëýóç.
1.2
Äéùíõìéêïß ÓõíåëåóÝò
Åßíáé öáíåñü üé ï (1 + x)n åßíáé Ýíá ðïëõþíõìï âáèìïý n. éá íá âñïýìå ï óõíåëåóÞ ïõ xr óï ðïëõþíõìï áõü áñêåß íá âñïýìå ïí áñéèìü ùí ñüðùí íá åðéëÝîïõìå r áðü ïõò n üñïõò x ðïõ åìöáíßæïíáé óï ãéíüìåíï (1 + x) : : : (1 + x) (n öïñÝò). ¼ðùò åßäáìå ï áñéèìüò áõüò åßíáé ï C (n; r). ÅðïìÝíùò ï óõíåëåóÞò ïõ xr óï ðïëõþíõìï (1 + x)n åßíáé ï C (n; r). éá ï ëüãï áõü ïé áñéèìïß C (n; r) êáëïýíáé äéùíõìéêïß óõíåëåóÝò. Ï ýðïò (1 + x) = n
n X
C (n; r) xr
(1.3)
r =0
êáëåßáé áíÜðõãìá ïõ äéùíýìïõ ïõ Newton. ÈÝïíáò x = s=t óïí ýðï (1.3) ðñïêýðåé, ìåÜ çí åêÝëåóç ùí ðñÜîåùí, ï ýðïò (s + t) = n
n X r =0
C (n; r) sr tn−r :
(1.4)
1.2.
3
ÄÉÙÍÕÌÉÊÏÉ ÓÕÍÔÅËÅÓÔÅÓ
áñÜäåéãìá 1.4: Ëýóç.
Íá õðïëïãéóèåß ï óáèåñüò üñïò óï áíÜðõãìá ïõ x2 + x1
Óýìöùíá ìå ïí (1.4) Ý÷ïõìå:
x2 +
1
x
12
=
12 X
C (12; r) x2
r =0
12−r 1
r
x
=
12 X
12
.
C (12; r) x3r−12 :
r =0
Ï óáèåñüò üñïò åßíáé ï óõíåëåóÞò ïõ x0 . ¢ñá èÝïõìå 3r − 12 = 0, äçëáäÞ r = 4 êáé åðïìÝíùò ï æçïýìåíïò óõíåëåóÞò åßíáé C (12; 4) = 495. Áðü ïí (1.2) ðñïêýðåé áìÝóùò üé
C (n; r) = C (n; n − r) :
(1.5)
C (n; r) = C (n − 1; r) + C (n − 1; r − 1) :
(1.6)
Åðßóçò ìðïñåß åýêïëá íá áðïäåé÷èåß áëãåâñéêÜ üé:
éá íá áðïäåßîïõìå ïí (1.6) ü÷é áëãåâñéêÜ, áëëÜ ìå óõíäõáóéêÜ åðé÷åéñÞìáá óêåöüìáóå ùò åîÞò: ãéá íá åðéëÝîïõìå r áíéêåßìåíá áðü n, óáèåñïðïéïýìå Ýíá áíéêåßìåíï êáé óç óõíÝ÷åéá åßå åðéëÝãïõìå r áíéêåßìåíá áðü á õðüëïéðá n − 1, åßå åðéëÝãïõìå r − 1 áíéêåßìåíá áðü á õðüëïéðá n − 1 êáé ðáßñíïõìå êáé áõü ðïõ Ý÷ïõìå óáèåñïðïéÞóåé. Ï ýðïò (1.6) ïäçãåß óçí êáÜóñùóç ùí ðñÜîåùí ãéá ïí õðïëïãéóìü ïõ C (n; r) ðïõ åßíáé ãíùóÞ ùò ñßãùíï ïõ Pas al. Óçí êáÜóñùóç áõÞ õðïëïãßæïõìå ïí áñéèìü ðïõ áíéóïé÷åß óå Ýíáí êüìâï ïõ ñéãþíïõ ðñïóèÝïíáò ïõò áñéèìïýò ùí äõï ðëçóéÝóåñùí áðü á ðÜíù êüìâùí ïõ ñéãþíïõ (Ó÷. 1.1). Ïé áêñáßïé êüìâïé ðáßñíïõí üëïé çí éìÞ 1: ÔÝëïò ìéá Üëëç ÷ñÞóéìç 0 0
1 0
2 0
3 0
@ @ @ @
@ @ @ @
@ @ @ @
1 1
@ @ @ @
2 1
3 1
@ @ @ @
2 2
3 2
@ @ @ @
Ó÷Þìá 1.1: Ôñßãùíï ïõ Pas al
3 3
éäéüçá ùí äéùíõìéêþí óõíåëåóþí åßíáé ç åîÞò:
n C (n; r) = C (n − 1; r − 1) : r
(1.7)
4
ÊÅÖÁËÁÉÏ 1.
ÓÔÏÉ×ÅÉÙÄÇÓ ÓÕÍÄÕÁÓÔÉÊÇ
éá íá áðïäåßîïõìå çí (1.7) ìå óõíäõáóéêÜ åðé÷åéñÞìáá óêåöüìáóå ùò åîÞò: ãéá íá åðéëÝîïõìå r áíéêåßìåíá, áñêåß íá åðéëÝîïõìå Ýíá êáé óç óõíÝ÷åéá íá åðéëÝîïõìå r − 1 áðü á n − 1. ÕðÜñ÷ïõí n ñüðïé ãéá çí åðéëïãÞ ïõ åíüò êáé C (n − 1; r − 1) ñüðïé ãéá çí åðéëïãÞ ùí r − 1. Êá' áõüí ïí ñüðï üìùò åßíáé óá íá £ìåñÜìå¤ êáé ðïéü åßíáé ï ðñþï áðü á r åðéëåãÝíá áíéêåßìåíá. Ï áñéèìüò üìùò C (n; r) äå ìåñÜ äéáÜîåéò. ¢ñá ãéá íá Ý÷ïõìå ï óùóü áðïÝëåóìá áñêåß íá äéáéñÝóïõìå ìå r. Áóöáëþò, ï ýðïò (1.7) ìðïñåß åýêïëá íá áðïäåé÷èåß áëãåâñéêÜ ìå âÜóç ïí (1.2). Åðßóçò, åðáíáëáìâÜíïíáò ïí (1.6), ðáßñíïõìå åýêïëá ïí ýðï:
n+r+1 r
r X n+k
=
(1.8)
k
k=0
ÔÝëïò áðü ïí (1.8) ìðïñïýìå íá áðïäåßîïõìå:
n+1 r+1
ñÜãìáé,
n+1 r +1
n+1 n−r
=
n+1 n−r
n X k
=
:
r
k =r
(1.9)
ìå âÜóç ïí (1.5). ÁëëÜ:
=
r + (n − r) + 1 n−r
=
n −r X k=0
r+k k
ìå âÜóç ïí (1.8). Ôþñá ï æçïýìåíï áðïäåéêíýåáé ðáñáçñþíáò üé: −r n X
k=0
r+k k
=
n −r X k=0
r+k r
=
n X k k =r
r
:
Ï ýðïò C (n; r) = n(n−1):::r!(n−r+1) áðïäåß÷èçêå ìå ïí ðåñéïñéóìü üé á n êáé r åßíáé öõóéêïß áñéèìïß êáé n ≥ r (óå áõÝò éò ðåñéðþóåéò Ý÷åé íüçìá íá ìéëÜìå ãéá åðéëïãÞ r áíéêåéìÝíùí áðü n). Åßíáé äõíáü üìùò íá ïñßóïõìå ïõò äéùíõìéêïýò óõíåëåóÝò êáé ãéá éò ðåñéðþóåéò üðïõ ï n åßíáé õ÷üí ðñáãìáéêüò. ÈÝïõìå ëïéðüí:
C (n; r) =
n (n − 1) : : : (n − r + 1) ; n ∈ R & r ∈ N: r!
(1.10)
Óï âéâëßï áõü, äå èá äþóïõìå ïñéóìü ãéá ï C (n; r) üáí r ∈= N. Åßíáé åýêïëï íá äéáðéóùèåß (Üóêçóç!) üé C (−1; r) = (−1)r êáé C (−2; r) = r (−1) (r + 1) : Åðßóçò, 1 −2
r
r − 21 − r + 1 (−1) · 2−r · 1 · 3 · : : : · (2r − 1) = = = r! r! (−1)r · 2−r · 2−r · (2r )! (−1)r · 2−2r · (2r )! = = 2 2 (r!) (r!) 2r r = (−1) · 2−2r · : − 21
:::
r
1.3.
5
ÏÌÁÄÅÓ ÌÇ ÄÉÁÊÅÊÑÉÌÅÍÙÍ ÁÍÔÉÊÅÉÌÅÍÙÍ
Áêüìç, üáí n < 0 éó÷ýåé üé (áðïäåßîå ï!):
n r
r
= (−1)
r−n−1 ; r ∈ N: r
(1.11)
Óç ÌáèçìáéêÞ ÁíÜëõóç áðïäåéêíýåáé üé áí n ∈ R êáé |x| < 1, ç óåéñÜ ∞ P C (n; r) xr óõãêëßíåé áðïëýùò óçí (1 + x)n . ¢ñá Ý÷ïõìå ï ãåíéêåõìÝíï r =0
äéùíõìéêü ýðï:
(1 + x) = n
∞ X
r =0
C (n; r) xr ; n ∈ R & |x| < 1:
(1.12)
Åðßóçò ïé ýðïé (1.5) { (1.8), êáèþò êáé Üëëïé áíßóïé÷ïé ìå áõïýò, éó÷ýïõí êáé óçí ðåñßðùóç n ∈ R. Áõü áðïäåéêíýåáé åýêïëá áí åñìçíåýóïõìå ïõò ýðïõò áõïýò óáí éóüçåò ðïëõùíýìùí âáèìïý r çò ìåáâëçÞò n, ïé ïðïßåò éó÷ýïõí ãéá éò Üðåéñåò éìÝò n = r; r + 1; : : : ñÜãìáé, ìßá éóüçá ðïëõùíýìùí âáèìïý r ðïõ åðáëçèåýåáé ãéá r + 1 Þ ðåñéóóüåñåò (äéáöïñåéêÝò) éìÝò éó÷ýåé ãéá êÜèå ðñáãìáéêÞ éìÞ. ñïïý êëåßóïõìå çí ðáñÜãñáöï áõÞ èá áíáöÝñïõìå ÷ùñßò áðüäåéîç ïí ýðï ïõ Stirling n! =1 lim √ (1.13) n n n→+∞
2n
üðïõ e ç âÜóç ùí öõóéêþí ëïãáñßèìùí.
e
√
n
ñÝðåé íá óçìåéþóïõìå üé ðáñÜ ï ãåãïíüò üé ç äéáöïñÜ n! − 2n ne √ n áðïêëßíåé óï Üðåéñï, ç Ýêöñáóç 2n ne åßíáé ìéá êáëÞ ðñïóÝããéóç ãéá ï n!, áêüìç êáé ãéá ìéêñÝò éìÝò ïõ n. Ï ßíáêáò 1.1 äåß÷íåé éò 10 ðéï âáóéêÝò áõüçåò ðïõ éó÷ýïõí óïõò äéùíõìéêïýò óõíåëåóÝò. Áðïäåßîå ìå óõíäõáóéêÜ åðé÷åéñÞìáá üóåò äåí Ý÷ïõí Þäç áðïäåé÷èåß.
1.3
ÏìÜäåò Ìç ÄéáêåêñéìÝíùí ÁíéêåéìÝíùí
¸óù üé Ý÷ïõìå n áíéêåßìåíá ðïõ áðïåëïýíáé áðü t ïìÜäåò ìå ðëçèõóìïýò q1 ; q2 ; : : : ; qr , áíßóïé÷á. Áò õðïèÝóïõìå üé á áíéêåßìåíá êÜèå ïìÜäáò äåí åßíáé äéáêåêñéìÝíá ìåáîý ïõò (óáí ìðßëéåò ïõ ßäéïõ ÷ñþìáïò). Ôüå õðÜñ÷ïõí
n! (1.14) q1 !q2 ! : : : qt ! ñüðïé íá á äéáÜîïõìå. ñÜãìáé, n! åßíáé üëïé ïé ñüðïé äéÜáîçò áí á
áíéêåßìåíá èåùñçèïýí äéáêåêñéìÝíá. Óçí ðåñßðùóç þñá ùí ïìÜäùí ìå ìç äéáêåêñéìÝíá óïé÷åßá ðñÝðåé íá äéáéñÝóïõìå ï n! ìå ïí áñéèìü ùí äéáöïñåéêþí äéáÜîåùí ðïõ äçìéïõñãïýíáé åî áéßáò çò õðïèÝóåùò üé á áíéêåßìåíá äåí åßíáé äéáêåêñéìÝíá. Ï áñéèìüò áõüò åßíáé q1 !; q2 !; : : : ; qr !. ïéü åßíáé ï ðëÞèïò ùí äéáöïñåéêþí äéáÜîåùí ãñáììÜùí ðïõ öéÜ÷íïíáé áðü á ãñÜììáá ðïõ ðåñéÝ÷ïíáé óç Ýêöñáóç £ìéá ðÜðéá ìá ðïéÜ ðÜðéá¤;
áñÜäåéãìá 1.5:
6
ÊÅÖÁËÁÉÏ 1.
ÓÔÏÉ×ÅÉÙÄÇÓ ÓÕÍÄÕÁÓÔÉÊÇ
n = n! r r!(n−r)! n = n r n−r n = n n−1 r r r−1 n = n−1 + n−1 r r r−1 n = (−1)r r−n−1 r r n m = n n−r m r r m−r n n P n r n−r (x + y ) = r xy r=0 ∞ P nxk n (1 + x) = k k=0 n n+ k n+r+1 = P k r k=0 n k n+1 = P r+1 r k=0 r n+m = P n m r k r−k k=0
áêÝñáéïé n ≥ r ≥ 0, áêÝñáéïé n ≥ r ≥ 0, áêÝñáéïò r > 0, ðñáãìáéêüò n, áêÝñáéïò r > 0, ðñáãìáéêüò n, áêÝñáéïò r ≥ 0, ðñáãìáéêüò n, áêÝñáéïé m ≥ r ≥ 0, ðñáãìáéêüò n, áêÝñáéïò n ≥ 0, ðñáãìáéêïß x; y ,
ðñáãìáéêïß n; x, |x| < 1;
áêÝñáéïé r; n ≥ 0,
áêÝñáéïé r; n ≥ 0,
áêÝñáéïò r ≥ 0, ðñáãìáéêïß n; m,
ßíáêáò 1.1: ÂáóéêÝò áõüçåò ùí äéùíõìéêþí óõíåëåóþí
áñáçñïýìå üé: õðÜñ÷ïõí q1 = 2 ãñÜììáá åßäïõò \ì", " q2 = 4 " " \é" , " q3 = 7 " " \á", " q4 = 5 " " \ð" , " q5 = 1 " " \ï".
Ëýóç.
1.4.
ÓÕÍÄÕÁÓÌÏÉ ÊÁÉ ÄÉÁÔÁÎÅÉÓ ÌÅ ÅÁÍÁËÇØÇ
7
¢ñá óõíïëéêÜ õðÜñ÷ïõí 19! = 4:190:266:080 2!4!7!5!1!
äéáÜîåéò ãñáììÜùí. áñÜäåéãìá 1.6:
Íá áðïäåé÷èåß üé ï (k !)! äéáéñåßáé áêñéâþò áðü ï (k !)(k−1)! .
Èåùñïýìå k ! áíéêåßìåíá êáé á ÷ùñßæïõìå óå (k − 1)! ïìÜäåò ìå k ìç äéáêåêñéìÝíá óïé÷åßá ç êÜèå ìßá. Ôï ðëÞèïò ùí óõíäõáóìþí ùí áíéêåéìÝíùí áõþí åßíáé (k!)(k(k!)!−1)! . Ï áñéèìüò üìùò áõüò ðñÝðåé íá åßíáé áêÝñáéïò. Ëýóç.
1.4
Óõíäõáóìïß êáé ÄéáÜîåéò ìå ÅðáíÜëçøç
ÕðÜñ÷ïõí nr äéáÜîåéò r áíéêåéìÝíùí áðü n áíéêåßìåíá üáí åðéñÝðïíáé åðáíáëçðéêÝò åìöáíßóåéò ùí áíéêåéìÝíùí. ñÜãìáé, Ý÷ïõìå n åðéëïãÝò ãéá ï ðñþï áíéêåßìåíï, ïìïßùò n ãéá ï äåýåñï, ê.ï.ê. ìÝ÷ñé ï r-ïóü áíéêåßìåíï. áñÜäåéãìá 1.7:
ï øçößï 1.
Íá õðïëïãéóåß ðüóïé áñéèìïß ìåáîý 1 êáé 1010 ðåñéÝ÷ïõí
Ëýóç. ÅðåéäÞ á äéÜöïñá ïõ 1 øçößá åßíáé 9, ìå âÜóç çí ðñïçãïýìåíç ðáñÜãñáöï ïé áñéèìïß ìåáîý 0 êáé 9.999.999.999 ðïõ äåí ðåñéÝ÷ïõí ï øçößï 1 åßíáé 910 . ¢ñá ìåáîý 1 êáé 1010 õðÜñ÷ïõí 910 − 1 áñéèìïß ðïõ äåí ðåñéÝ÷ïõí ï øçößï 1. ÅðïìÝíùò, óï ßäéï äéÜóçìá, õðÜñ÷ïõí 1010 − 910 + 1 áñéèìïß ðïõ ðåñéÝ÷ïõí ï øçößï 1.
åñéóóüåñï åíäéáöÝñïõóá åßíáé ç ðåñßðùóç ùí óõíäõáóìþí r áíéêåéìÝíùí áðü n áíéêåßìåíá ìå åðáíÜëçøç. áñáçñÞóå üé äéáéñþíáò áðëþò ï nr (ðïõ åßíáé ï áñéèìüò ùí óõíäõáóìþí) ìå r! äåí ðáßñíïõìå ïí áñéèìü ùí äéáÜîåùí êáé áõü äéüé åðéñÝðåáé Ýíáò áðñïóäéüñéóïò áñéèìüò åðáíáëÞøåùí ïõ ßäéïõ áíéêåéìÝíïõ. éá íá õðïëïãßóïõìå ïí áñéèìü ùí óõíäõáóìþí ìå åðáíÜëçøç èåùñïýìå üé ï óýíïëï ùí áíéêåéìÝíùí áðü üðïõ ãßíåáé ç åðéëïãÞ ïõ óõíäõáóìïý åßíáé ïé áñéèìïß {1; : : : ; n} êáé óêåöüìáóå ùò åîÞò: Ýíáò óõíäõáóìüò r áíéêåéìÝíùí áðü n ìå åðáíÜëçøç åßíáé ìßá áêïëïõèßá x1 ; : : : ; xr üðïõ 1 ≤ xi ≤ n êáé xi ≤ xj üáí 1 ≤ i ≤ j ≤ r. Ç áðåéêüíéóç üìùò (x1 ; x2 ; : : : ; xr ) → (x1 + 0; x2 + 1; : : : ; xr + r − 1)
åßíáé ìéá 1-1 êáé åðß áðåéêüíéóç áðü ï óýíïëï ùí ìç öèßíïõóùí áêïëïõèéþí ìå r üñïõò áðü ï {1; : : : ; n} óï óýíïëï ùí ãíçóßùò áõîïõóþí áêïëïõèéþí ìå üñïõò áðü ï {1; : : : ; n + r − 1}. Ôï óýíïëï üìùò ùí ãíçóßùò áõîïõóþí áêïëïõèéþí r üñùí áðü ï {1; : : : ; n + r − 1} Ý÷åé ðëçèéêü áñéèìü ßóï ìå ïí áñéèìü ùí óõíäõáóìþí ÷ùñßò åðáíÜëçøç r áíéêåéìÝíùí áðü n + r − 1 áíéêåßìåíá. Óõìðåñáßíïõìå ëïéðüí åëéêÜ üé ï áñéèìüò ùí óõíäõáóìþí r áíéêåéìÝíùí áðü n áíéêåßìåíá ìå åðáíÜëçøç åßíáé C (n + r − 1; r). áñÜäåéãìá 1.8:
üóåò æáñéÝò õðÜñ÷ïõí óï Üâëé;
8
ÊÅÖÁËÁÉÏ 1.
ÓÔÏÉ×ÅÉÙÄÇÓ ÓÕÍÄÕÁÓÔÉÊÇ
Ëýóç. Ï áñéèìüò ùí æáñéþí óï Üâëé åßíáé ï óõíäõáóìüò (åðåéäÞ äåí åíäéáöÝñåé ç óåéñÜ ðïõ ðÝöïõí á æÜñéá) 2 áíéêåéìÝíùí áðü 6, äçëáäÞ
C (6 + 2 − 1; 2) = C (7; 2) = 21: áñÜäåéãìá 1.9: üóåò öïñÝò èá åêåëåóåß ç åíïëÞ writeln óï ðéï êÜù ìÞìá åíüò ðñïãñÜììáïò Pas al;
For i := 1 to 20 do For j := 1 to i do For k := 1 to j do writeln (i*j+k); Óõìðåñáßíïõìå áðü ïõò óõíáêéêïýò êáíüíåò çò åíïëÞò For üé êÜèå öïñÜ ðïõ èá åêåëåßáé ç åíïëÞ writeln éó÷ýåé ç óõíèÞêç 1 ≤ k ≤ j ≤ i ≤ 20. ÆçÜìå ëïéðüí íá âñïýìå ïí áñéèìü ùí ñüðùí íá óõíäõÜóïõìå á i; j; k , åðéñÝðïíáò åðáíáëÞøåéò, ìå éìÝò áðü 1; 2; : : : ; 20. Áõüò åßíáé 20+3−1 = 1540. ÅðïìÝíùò ç åíïëÞ writeln èá åêåëåóåß 1540 3 öïñÝò. Ëýóç.
1.5
Õðïóýíïëá
ÕðÜñ÷ïõí 2n − 1 ñüðïé íá åðéëÝîïõìå Ýíá Þ ðåñéóóüåñá áíéêåßìåíá áðü n áíéêåßìåíá, ÷ùñßò åðáíÜëçøç êáé ÷ùñßò íá £ìåñÜåé¤ ç äéÜáîç. ñÜãìáé, õðÜñ÷ïõí äýï åðéëïãÝò ãéá ï ðñþï áíéêåßìåíï: íá ï äéáëÝîïõìå Þ ü÷é. Äýï åðßóçò åðéëïãÝò ãéá ï äåýåñï, ê.ï.ê. ìÝ÷ñé ï åëåõáßï. Ï üñïò −1 åìöáíßæåáé ãéá íá áðïêëåßóïõìå çí ðåñßðùóç üðïõ êáíÝíá áíéêåßìåíï äåí åðéëÝãåáé. Åðßóçò, åðåéäÞ õðÜñ÷ïõí C (n; k ) ñüðïé ãéá íá åðéëÝîïõìå k áíéêåßìåíá áðü n, ìå âÜóç á ðñïçãïýìåíá êááëÞãïõìå óï üé: 2n − 1 =
Þ áëëéþò 2n =
n X
C (n; k);
k=1
n X
C (n; k):
(1.15)
k=0
Ï ðáñáðÜíù ýðïò áðïäåéêíýåáé åýêïëá êáé áëëéþò: áí óïí (1.3) èÝóù x = 1. Áí þñá á áíéêåßìåíá áðïåëïýíáé áðü t ïìÜäåò, ìå ìç äéáêåêñéìÝíá óïé÷åßá ç êÜèå ìßá, ïé ïðïßåò áðïåëïýíáé áðü q1 ; : : : ; qt óïé÷åßá, áíßóïé÷á, üå ï áñéèìüò ùí óõíäõáóìþí åíüò Þ ðåñéóóüåñùí áíéêåéìÝíùí éóïýáé ìå (q1 + 1) (q2 + 1) : : : (qt + 1) − 1:
(1.16)
ñÜãìáé, õðÜñ÷ïõí q +1 ñüðïé íá äéáëÝîïõìå áíéêåßìåíá áðü çí ðñþç ïìÜäá: íá äéáëÝîïõìå 1 Þ 2 Þ ... Þ q1 Þ êáíÝíá. Ôï åðé÷åßñçìá óõíå÷ßæåáé üðùò êáé óïí õðïëïãéóìü ïõ 2n .
1.6.
ÄÉÁÍÏÌÅÓ ÁÍÔÉÊÅÉÌÅÍÙÍ ÓÅ ÕÏÄÏ×ÅÓ
áñÜäåéãìá 1.10: Ëýóç.
9
Íá âñåèåß ï áñéèìüò ùí äéáéñåþí ïõ 180.
180 = 22 · 32 · 5. ñïöáíþò ïé äéáéñÝåò ó÷çìáßæïíáé áðü óõíäõáóìïýò
áðü éò åîÞò ïìÜäåò:
1ç ïìÜäá : 2ç ïìÜäá : 3ç ïìÜäá :
{2,2} {3,3} {5}
¢ñá ï áñéèìüò ùí äéáéñåþí åßíáé (2 + 1) · (2 + 1) · (1 + 1) = 18 (ï üñïò −1 äåí åìöáíßæåáé äéüé áíéóïé÷åß óï óõíäõáóìü 20 30 50 = 1 êáé ï 1 åßíáé äéáéñÝçò ïõ 180). 1.6
ÄéáíïìÝò ÁíéêåéìÝíùí óå Õðïäï÷Ýò
Áò õðïèÝóïõìå üé ïðïèåïýìå r äéáêåêñéìÝíá áíéêåßìåíá êáé n äéáêåêñéìÝíåò õðïäï÷Ýò. Ï áñéèìüò ùí ñüðùí íá êááíåßìïõìå á áíéêåßìåíá óéò õðïäï÷Ýò åßíáé nr . ñÜãìáé, áí èåùñÞóïõìå üé ç ïðïèÝçóç ïõ ðñþïõ áíéêåéìÝíïõ éóïäõíáìåß ìå åðéëïãÞ çò áíßóïé÷çò õðïäï÷Þò, âëÝðïõìå üé ï æçïýìåíïò áñéèìüò éóïýáé ìå ïí áñéèìü ùí äéáÜîåùí ìå åðáíÜëçøç r áíéêåéìÝíùí áðü n, ï ïðïßïò ãíùñßæïõìå üé éóïýáé ìå nr . áñáçñÞóå üé óçí ðáñáðÜíù áñßèìçóç äå ìåñÜåé ç óåéñÜ ìå çí ïðïßá á áíéêåßìåíá åìöáíßæïíáé óçí êÜèå õðïäï÷Þ. éá íá õðïëïãßóïõìå þñá ïí áñéèìü ùí äéáíïìþí üáí ìåñÜåé ç óåéñÜ ïðïèÝçóçò ùí áíéêåéìÝíùí óå êÜèå õðïäï÷Þ óêåöüìáóå éò n õðïäï÷Ýò óáí n äéáóÞìáá áíÜìåóá óå n + 1 äéáäï÷éêÜ óçìåßá óå ìéá åõèåßá üðïõ èá ðñÝðåé íá ïðïèåçèïýí á r áíéêåßìåíá. Ôï ðñþï áðü áõÜ á óçìåßá ðñÝðåé ðÜíá íá ïðïèåçèåß óçí áñ÷Þ êáé ï åëåõáßï óï Ýëïò. ¢ñá åßíáé á õðüëïéðá n − 1 óçìåßá ðïõ èá ðñÝðåé íá äéá÷ùñßóïõí á r áíéêåßìåíá á ïðïßá åßíáé äéáêåêñéìÝíá. Ôá n − 1 óçìåßá ðïõ ïñßæïõí éò õðïäï÷Ýò åßíáé ìç äéáêåêñéìÝíá, ÓõíïëéêÜ ëïéðüí õðÜñ÷ïõí n − 1 + r áíéêåßìåíá ðïõ ðñÝðåé íá ìåñÞóïõìå éò äéáÜîåéò ïõò. Ìå âÜóç ïí (1.14) ï æçïýìåíïò áñéèìüò åßíáé (n + r − 1)! = (n + r − 1) (n + r − 2) : : : n: (n − 1)!
(1.17)
ÕðÜñ÷åé êáé Üëëïò ñüðïò íá êááëÞîïõìå óï ßäéï áðïÝëåóìá: ÕðÜñ÷ïõí n õðïøÞöéåò õðïäï÷Ýò ãéá ï ðñþï áíéêåßìåíï. Áò öáíáóïýìå þñá üé ç ïðïèÝçóç ïõ ðñþïõ áíéêåéìÝíïõ äéáéñåß çí áíßóïé÷ç õðïäï÷Þ óå äõï äéáöïñåéêÜ ìåáîý ïõò ìÝñç. Ï áñéèìüò ùí õðïøÞöéùí õðïäï÷þí ãéá ï äåýåñï áíéêåßìåíï áõîÜíåáé Ýóé óå n + 1. Óõíå÷ßæïõìå ìå áõü ïí ñüðï ìÝ÷ñé ï r-ïóü áíéêåßìåíï ãéá ï ïðïßï õðÜñ÷ïõí n + r −1 õðïøÞöéåò õðïäï÷Ýò. Áò åîåÜóïõìå þñá çí ðåñßðùóç üðïõ á r áíéêåßìåíá åßíáé ìç äéáêåêñéìÝíá. ÕðÜñ÷ïõí áñêåïß ñüðïé ãéá íá õðïëïãßóïõìå ïí áñéèìü ùí ñüðùí ïðïèÝçóçò ùí áíéêåéìÝíùí óå n õðïäï÷Ýò. Ï ðéï áðëüò åßíáé íá äéáéñÝóïõìå ïí ýðï ðïõ äßíåé ïí áñéèìü ùí äéáíïìþí ãéá r äéáêåêñéìÝíá áíéêåßìåíá ìå r!. ¸óé ðáßñíïõìå ïí áñéèìü (n + r − 1)! = (n − 1)!r!
n+r−1 : r
(1.18)
10
ÊÅÖÁËÁÉÏ 1.
ÓÔÏÉ×ÅÉÙÄÇÓ ÓÕÍÄÕÁÓÔÉÊÇ
¸íáò Üëëïò ñüðïò ãéá íá êááëÞîïõìå óïí ßäéï ýðï åßíáé íá ìéìçèïýìå çí ðñþç áðüäåéîç ðïõ äþóáìå ãéá çí ðåñßðùóç ùí r äéáêåêñéìÝíùí áíéêåéìÝíùí, ìå çí åðéðëÝïí ðáñáÞñçóç üé þñá ü÷é ìüíïí á n − 1 óçìåßá ðïõ ïñßæïõí éò õðïäï÷Ýò åßíáé ìéá ïìÜäá áðü ìç äéáêåêñéìÝíá áíéêåßìåíá, áëëÜ åðßóçò êáé á r áíéêåßìåíá ðñïò ïðïèÝçóç åßíáé ìç äéáêåêñéìÝíá. ×ñçóéìïðïéþíáò ïí (1.14) Ý÷ïõìå üé ï æçïýìåíïò áñéèìüò åßíáé (n + r − 1)! (n − 1)!r!
(1.19)
ÔÝëïò, Ýíáò áêüìç ñüðïò åßíáé íá ðáñáçñÞóïõìå üé ï æçïýìåíïò áñéèìüò éóïýáé ìå ïí áñéèìü ùí óõíäõáóìþí ìå åðáíÜëçøç r áíéêåéìÝíùí áðü n áíéêåßìåíá (äçëáäÞ éò õðïäï÷Ýò). Íá õðïëïãéóåß ï áñéèìüò ùí ñüðùí ðïõ r ìç äéáêåêñéìÝíá áíéêåßìåíá ìðïñïýí íá ïðïèåçèïýí óå n õðïäï÷Ýò, ìå ïí ðåñéïñéóìü üé üëåò ïé õðïäï÷Ýò èá äå÷èïýí ïõëÜ÷éóïí Ýíá áíéêåßìåíï (r ≥ n ≥ 1). ïéüò åßíáé ï áñéèìüò áõüò áí áðáéÞóïõìå áêñéâþò ìßá õðïäï÷Þ íá åßíáé êåíÞ (r ≥ n −1 ≥ 1); áñÜäåéãìá 1.11:
Ëýóç.
ñþá ïðïèåïýìå Ýíá áíéêåßìåíï óå êÜèå õðïäï÷Þ êáé ìáò ìÝíïõí
r − n áíéêåßìåíá. Ï áñéèìüò ùí ñüðùí íá äéáíåìçèïýí áõÜ óéò õðïäï÷Ýò åßíáé
n + (r − n) − 1 r−n
=
r−1 r−n
=
r−1 n−1
¢ñá C (r − 1; n − 1) åßíáé ï áñéèìüò ùí ñüðùí íá äéáíåßìïõìå á áíéêåßìåíá ÷ùñßò íá áöÞóïõìå êåíÞ õðïäï÷Þ. éá çí ðåñßðùóç þñá çò áêñéâþò ìßáò Üäåéáò õðïäï÷Þò, áñêåß íá åðéëÝîïõìå çí Üäåéá õðïäï÷Þ êáé íá êááíåßìïõìå á áíéêåßìåíá óéò åíáðïìÝíïõóåò n − 1 õðïäï÷Ýò, öñïíßæïíáò áõÝò üëåò íá äå÷èïýí ïõëÜ÷éóïí Ýíá áíéêåßìåíï. ¢ñá ç áðÜíçóç ãéá çí ðåñßðùóç çò áêñéâþò ìßáò êåíÞò õðïäï÷Þò åßíáé nC (r − 1; n − 2). Ï ßíáêáò 1.2 äåß÷íåé üëïõò ïõò ýðïõò ãéá éò äéáíïìÝò áíéêåéìÝíùí óå õðïäï÷Ýò êÜù áðü äéáöïñåéêÝò ðáñáäï÷Ýò. áñáäï÷Ýò
n äéáêåêñéìÝíåò õðïäï÷Ýò r äéáêåêñéìÝíá áíéêåßìåíá
Áñéèìüò ñüðùí (ìå äõíáüçá êåíþí õðïäï÷þí)
nr
äå ìåñÜåé ç óåéñÜ óéò õðïäï÷Ýò
n äéáêåêñéìÝíåò õðïäï÷Ýò r äéáêåêñéìÝíá áíéêåßìåíá
(n + r − 1)! (n − 1)!
n äéáêåêñéìÝíåò õðïäï÷Ýò
ìåñÜåé ç óåéñÜ óéò õðïäï÷Ýò ìç äéáêåêñéìÝíá áíéêåßìåíá
n+r−1 r
ßíáêáò 1.2: Ôõðïëüãéï ãéá ç äéáíïìÞ áíéêåéìÝíùí óå õðïäï÷Ýò
1.7.
1.7
11
ÁÓÊÇÓÅÉÓ
ÁóêÞóåéò
1.1 ÊáÜ ðüóïõò ñüðïõò 3 áñéèìïß ìðïñïýí íá åðéëåãïýí áðü ïõò áñéèìïýò 1{300 Ýóé þóå ï Üèñïéóìá ïõò íá åßíáé äéáéñåü ìå ï 3 (äåí åíäéáöÝñåé ç óåéñÜ ùí áñéèìþí); 1.2 Íá âñåèåß ï áñéèìüò ùí åñáøÞöéùí áñéèìþí ïõ äåêáäéêïý óõóÞìáïò ðïõ äåí Ý÷ïõí äýï ßäéá øçößá. 1.3 Ìå ðüóïõò ñüðïõò ìðïñïýí íá âáöïýí 12 ãñáöåßá Ýóé þóå 3 áðü áõÜ íá åßíáé êüêêéíá, 2 ñïæ, 2 ëåõêÜ êáé á õðüëïéðá ðñÜóéíá; 1.4 üóïõò äéáéñÝåò Ý÷åé ï áñéèìüò 1400; 1.5 Áðü Ýíá ìåãÜëï áñéèìü áðü êÝñìáá (áðü ìïíüëåðá Ýùò äßåõñá (äßöñáãêá)), ìå ðüóïõò ñüðïõò ìðïñïýí íá åðéëåãïýí 6 êÝñìáá; 1.6 Íá áðïäåé÷èåß üé ïé áñéèìïß
(3n)! (2n 3n )
n2 ! êáé (n(!)n)+1 åßíáé áêÝñáéïé.
1.7 Íá õðïëïãéóèåß ï óõíåëåóÞò ïõ x23 óï 1 + x5 + x9
100
.
1.8 ÊáÜ ðüóïõò ñüðïõò ìðïñïýí r üìïéåò ìðÜëåò íá ïðïèåçèïýí óå n äéáêåêñéìÝíá êïõéÜ, Ýóé þóå êÜèå êïõß íá ðåñéÝ÷åé ïõëÜ÷éóïí 9 ìðÜëåò; 1.9 Íá âñåèåß ï áñéèìüò ùí ñüðùí ðïõ ìðïñïýìå íá ïðïèåÞóïõìå 2t + 1 ìç äéáêåêñéìÝíåò ìðÜëåò óå 3 äéáêåêñéìÝíá êïõéÜ Ýóé þóå êÜèå 2 êïõéÜ ìáæß íá ðåñéÝ÷ïõí ðåñéóóüåñåò ìðÜëåò áðü üé ï Üëëï Ýíá. 1.10 Ìåáîý 2n áíéêåéìÝíùí á n åßíáé ßäéá. Âñåßå ïí áñéèìü ùí åðéëïãþí n áíéêåéìÝíùí áðü áõÜ á 2n áíéêåßìåíá. 1.11 Ìåáîý 3n+1 áíéêåéìÝíùí á n åßíáé ßäéá. Âñåßå ïí áñéèìü ùí åðéëïãþí n áíéêåéìÝíùí áðü áõÜ á 3n + 1 áíéêåßìåíá. 1.12 Íá âñåèåß ï áñéèìüò ùí ñüðùí ðïõ r äéáêåêñéìÝíåò óçìáßåò ìðïñïýí íá ïðïèåçèïýí óå n äéáêåêñéìÝíïõò éóïýò, äåäïìÝíïõ üé Ý÷åé óçìáóßá ç óåéñÜ ìå çí ïðïßá ïé óçìáßåò åìöáíßæïíáé óïõò éóïýò êáé äåäïìÝíïõ üé êáíÝíáò éóüò äåí ðñÝðåé íá ìåßíåé êåíüò (r ≥ n). 1.13 Íá âñåèåß ï áñéèìüò ùí ñüðùí ðïõ r äéáêåêñéìÝíá áõïêßíçá ìðïñïýí íá ðåñÜóïõí áðü n äéáêåêñéìÝíïõò óáèìïýò äéïäßùí, äåäïìÝíïõ üé ìßá ï ðïëý äéáäñïìÞ åðéñÝðåáé íá ìç äå÷èåß áõïêßíçï (r ≥ n − 1 êáé n ≥ 2).
12
ÊÅÖÁËÁÉÏ 1.
ÓÔÏÉ×ÅÉÙÄÇÓ ÓÕÍÄÕÁÓÔÉÊÇ
1.14 Íá õðïëïãéóèåß ï Üèñïéóìá 12 + 22 + : : : + n2 . 1.15 Íá áðïäåé÷èåß üé (á)
n P
k=0
k
(−1)
C (r; k) = (−1)n C (r − 1; n)
(â) C (r; m) C (m; k ) = C (r; k ) C (r − k; m − k ) (ã)
n P
k=0
C (r; k) C (s; n − k) = C (r + s; n)
ÊåöÜëáéï 2 åííÞñéåò ÓõíáñÞóåéò 2.1
ÅéóáãùãÞ
¸óù a0 ; a1 ; : : : ìéá áêïëïõèßá ðñáãìáéêþí áñéèìþí. Óü÷ïò ìáò åßíáé íá £êùäéêïðïéÞóïõìå¤ çí áêïëïõèßá ìå ìßá ìüíï óõíÜñçóç êáÜ Ýïéï ñüðï þóå íá ìðïñïýìå åýêïëá íá áíáðáñáãÜãïõìå çí áêïëïõèßá áðü ç óõíÜñçóç ðïõ çí êùäéêïðïéåß. ¸íáò ñüðïò ðïõ åðéõã÷Üíåáé áõü åßíáé ìÝóù åíüò ìåáó÷çìáéóìïý ï ïðïßïò áíéóïé÷ßæåé óçí áêïëïõèßá ìßá äõíáìïóåéñÜ (äçëáäÞ óåéñÜ äõíÜìåùí çò ìåáâëçÞò x) óýìöùíá ìå ïí ýðï:
A (x) =
∞ X
ar xr :
r =0
Ç äõíáìïóåéñÜ, ç ïðïßá ïñßæåé ðñïöáíþò ìßá óõíÜñçóç ìßáò ìåáâëçÞò óï ðåäßï óýãêëéóÞò çò, êáëåßáé óõíÞèùò ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò. Èá áðïöýãïõìå íá õðåéóÝëèïõìå óå ëåðïìÝñåéåò ó÷åéêÜ ìå ç óýãêëéóç ùí äõíáìïóåéñþí, åðåéäÞ åßíáé ãíùóü üé óõãêëßíïõí ìå £éó÷õñü¤ ñüðï óå êÜðïéï äéÜóçìá ìå êÝíñï ï 0. Ôï äéÜóçìá áõü åßíáé äõíáü íá åßíáé êåíü (äçëáäÞ íá Ý÷åé ìÞêïò 0), áëëÜ óéò åöáñìïãÝò ðïõ èá åîåÜóïõìå áõü äå óõìâáßíåé. áñáèÝïõìå ðáñáêÜù ðïëý óõíïðéêÜ éò âáóéêÝò éäéüçåò óýãêëéóçò ùí äõíáìïóåéñþí, ïé ïðïßåò ìáò åðéñÝðïõí íá éò ÷åéñéæüìáóå óáí íá åðñüêåéï ãéá ðåðåñáóìÝíá áèñïßóìáá (õðÜñ÷åé ðëçèþñá ó÷åéêþí âéâëßùí ãéá ïí áíáãíþóç ðïõ åíäéáöÝñåáé íá ìÜèåé ðåñéóóüåñá ãéá ç èåìåëßùóç ùí äõíáìïóåéñþí). ÓõãêåêñéìÝíá: á. Áí ìéá äõíáìïóåéñÜ
A (x) =
∞ X
ar xr
r =0
óõãêëßíåé ãéá ìéá éìÞ ïõ x = x0 , üå óõãêëßíåé ãéá êÜèå x ìå |x| < |x0 |. Káëïýìå áêßíá óýãêëéóçò R çò äõíáìïóåéñÜò ïí áñéèìü (
sup |x| :
∞ X
)
ar x óõãêëßíåé :
r =0
r
Ôüå ç äõíáìïóåéñÜ óõãêëßíåé ãéá êÜèå x ìå |x| < R (ç éìÞ ïõ R ìðïñåß íá åßíáé +∞ Þ 0). 13
14
ÊÅÖÁËÁÉÏ 2.
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
Ç áêßíá óýãêëéóçò õðïëïãßæåáé ìå Ýíáí áðü ïõò ýðïõò: 1
R Þ 1
R
= lim sup
p r |ar |
ar+1 : = lim sup
ar
Ç óýãêëéóç çò óåéñÜò åßíáé ïìïéüìïñöç óå êÜèå äéÜóçìá çò ìïñöÞò {x : |x| ≤ r }, üðïõ r < R.
â. Óï åóùåñéêü ïõ äéáóÞìáïò óýãêëéóçò çò äõíáìïóåéñÜò (äçëáäÞ, ïõ äéáóÞìáïò ìå êÝíñï çí áñ÷Þ ùí áîüíùí êáé áêßíá çí áêßíá óýãêëéóçò), ç óõíÜñçóç
A (x) =
∞ X
ar xr
r =0
åßíáé Üðåéñá ðáñáãùãßóéìç êáé ïé ðáñÜãùãïß çò õðïëïãßæïíáé ðáñáãùãßæïíáò õðéêÜ ç óåéñÜ ùò ðåðåñáóìÝíï Üèñïéóìá, äçëáäÞ:
A (x) = ′
∞ X
rar xr−1 :
(2.1)
r =1
Ïé áêßíåò óýãêëéóçò ùí äõíáìïóåéñþí ðïõ ëáìâÜíïíáé ìå çí ðáñáãþãéóç ðáñáìÝíïõí üëåò ßóåò ìå çí áêßíá óýãêëéóçò çò áñ÷éêÞò äõíáìïóåéñÜò. ã. éá êÜèå äéÜóçìá [0; x] ðïõ ðåñéÝ÷åáé óï äéÜóçìá óýãêëéóçò çò äõíáìïóåéñÜò, ç óõíÜñçóç A åßíáé ïëïêëçñþóéìç êáé ç éìÞ ïõ ïëïêëçñþìáüò çò õðïëïãßæåáé ïëïêëçñþíïíáò õðéêÜ ç óåéñÜ ùò ðåðåñáóìÝíï Üèñïéóìá, äçëáäÞ: ! Z
0
x
∞ X
ar t
r
r =0
dt =
∞ X ar−1
r =1
r
xr :
(2.2)
Ç áêßíá óýãêëéóçò çò íÝáò äõíáìïóåéñÜò ðáñáìÝíåé áìåÜâëçç. ÓõìðåñáóìáéêÜ, åßíáé áóöáëÝò íá ÷åéñéæüìáóå éò äõíáìïóåéñÝò ùò ðåðåñáóìÝíá áèñïßóìáá. H óçìáíéêüåñç üìùò éäéüçá ùí äõíáìïóåéñþí åßíáé üé ïé óõíåëåóÝò ar çò A ìðïñïýí íá õðïëïãéóïýí áðü ïí ýðï 1
ar = A(r) (0) : r!
(2.3)
Ï ðáñáðÜíù ýðïò äéêáéïëïãåß ç èåþñçóç ìéáò ãåííÞñéáò óõíÜñçóçò ùò êùäéêïðïßçóç çò áíßóïé÷çò áêïëïõèßáò. 2.2
Éäéüçåò ùí åííçñéþí ÓõíáñÞóåùí
Óçí ðáñÜãñáöï áõÞ ðáñáèÝïõìå éäéüçåò ïé ïðïßåò ìáò åðéñÝðïõí íá õðïëïãßæïõìå ç ãåííÞñéá óõíÜñçóç ìßáò äåäïìÝíçò áêïëïõèßáò êáé áíßóñïöá, äåäïìÝíçò ìéáò ãåííÞñéáò óõíÜñçóçò íá âñßóêïõìå çí áíßóïé÷ç áêïëïõèßá.
2.2.
ÉÄÉÏÔÇÔÅÓ ÔÙÍ ÅÍÍÇÔÑÉÙÍ ÓÕÍÁÑÔÇÓÅÙÍ
15
1. ñáììéêÞ éäéüçá
Áí k , l åßíáé óáèåñÝò êáé
A (x)
∞ X
=
ar xr ;
r =0
B (x)
∞ X
=
br xr ;
r =0
üå ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò
dr = kar + lbr åßíáé ç
D (x) = kA (x) + lB (x) :
Ç áðüäåéîç çò éäéüçáò åßíáé åýêïëç. 2. Éäéüçá çò êëßìáêáò
Áí A(x) åßíáé ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò a0 ; a1 ; a2 ; : : : üå ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò
br åßíáé ç
=
r ar
A (x) :
Ç áðüäåéîç êáé áõÞò çò éäéüçáò åßíáé åýêïëç. 3. Éäéüçá çò ïëßóèçóçò
Áí A(x) åßíáé ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò a0 ; a1 ; a2 ; : : : üå ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò
br br
= 0; ãéá r = 0; 1; : : : ; n − 1 êáé = ar−n ; ãéá r = n; n + 1; : : :
åßíáé ç
xn A (x) :
¼ìïéá, ç áêïëïõèßá ðïõ ïñßæåáé ùò
dr = ar+n ; r = 0; 1; 2; : : : Ý÷åé ãåííÞñéá óõíÜñçóç çí
A (x) −
nP −1 r =0 n
x
ar xr
:
16
ÊÅÖÁËÁÉÏ 2.
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
Óç óõíÝ÷åéá èá áðïäåßîïõìå ï ðñþï ìÝñïò çò éäéüçáò (ï äåýåñï ìÝñïò åðáößåáé ùò Üóêçóç). Åßíáé
B (x) B (x)
∞ X
=
r =0 n −1 X
=
br xr ⇒ br xr +
r =n
r =0
B (x)
=
0+
∞ X
∞ X
br xr ⇒
ar−n xr :
r =n
ÈÝù r − n = k , ïðüå:
B (x)
=
∞ X
k=0
ak xn+k ⇒
∞ X
B (x)
=
xn
B (x)
=
xn A (x) :
k=0
ak xk ⇒
4. Éäéüçá ìåñéêþí áèñïéóìÜùí
ÅÜí
bk =
k X
ar ; k = 0; 1; 2; : : : ;
r =0
üå ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò bk , áí ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò ar åßíáé A(x), åßíáé
B (x) =
A (x) : 1−x
Èá áðïäåßîïõìå áõÞ çí éäéüçá. áñáçñïýìå üé: ∞ X
ak
=
ak xk
=
k=0
bk − bk−1 ⇒ ∞ X
k=0
bk xk −
∞ X
bk−1 xk :
k=0
×ñçóéìïðïéþíáò çí éäéüçá çò ïëßóèçóçò Ý÷ïõìå: ¢ñá
A (x) = B (x) − xB (x) : B (x) =
A (x) 1−x
5. Éäéüçá óõìðëçñùìáéêþí ìåñéêþí áèñïéóìÜùí
Áí ç áêßíá óýãêëéóçò çò ãåííÞñéáò óõíÜñçóçò A(x) åßíáé ìåãáëýåñç çò ìïíÜäáò êáé ïñßóïõìå
bk =
∞ X
r =k
ar ; k = 0; 1; 2; : : : ;
2.2.
17
ÉÄÉÏÔÇÔÅÓ ÔÙÍ ÅÍÍÇÔÑÉÙÍ ÓÕÍÁÑÔÇÓÅÙÍ
üå ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò bk åßíáé
B (x) =
A (1) − xA (x) : 1−x
éá íá áðïäåßîïõìå áõÞ çí éäéüçá ðáñáçñïýìå üé
bk
∞ X
=
r =0
bk ∞ X
A (1) −
=
bk x
k
ar −
∞ X
=
k=0
k −1 X
ar ⇒
r =0
k −1 X
ar ⇒
r =0
A (1) x
k
k=0
−
∞ k −1 X X
k=0
r =0
!
ar xk ⇒
(óýìöùíá ìå éò éäéüçåò çò ïëßóèçóçò êáé ùí ìåñéêþí áèñïéóìÜùí)
B (x)
=
A (1) − xA (x) : 1−x
6. Éäéüçåò çò ðáñáãþãïõ êáé ïõ ïëïêëçñþìáïò
Ç áêïëïõèßá br = rar ; r = 0; 1; 2; : : : Ý÷åé ãåííÞñéá óõíÜñçóç:
B (x) = xA′ (x) ; åíþ ç áêïëïõèßá dr =
ar r +1
Ý÷åé ãåííÞñéá óõíÜñçóç:
D (x) =
1
x
Z
x
0
A (t) dt:
Ïé ðáñáðÜíù ó÷Ýóåéò áðïäåéêíýïíáé åýêïëá áðü ïõò ýðïõò (2.1,2.2). 7. Éäéüçá çò óõíÝëéîçò
Ç áêïëïõèßá
dk =
k X
ar bk−r ; k = 0; 1; 2; : : :
r =0
ðïõ êáëåßáé óõíÝëéîç ùí áêïëïõèéþí ar ; br (óõìâïëéóìüò dr = ar ∗ br ) Ý÷åé ãåííÞñéá óõíÜñçóç
D (x) = A (x) B (x)
üðïõ A(x) ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò ar êáé B (x) ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò br . Èá áðïäåßîïõìå áõÞ çí éäéüçá ùò åîÞò:
A (x) B (x)
= = =
a0 + a1 x + a2 x2 + : : : b0 + b1x + b2 x2 + : : : = (a0 b0 ) + (a0 b1 + a1 b0 ) x + (a0 b2 + a1 b1 + a2 b0 ) x2 + : : : =
∞ X
k=0
dk xk :
18
ÊÅÖÁËÁÉÏ 2.
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
¢ñá A (x) B (x) = D (x). Ïé ðáñáðÜíù éäéüçåò ÷ñçóéìïðïéïýíáé ãéá ïí õðïëïãéóìü áèñïéóìÜùí á ïðïßá åßíáé äýóêïëï íá õðïëïãéóèïýí ìå Üëëåò ìåèüäïõò. Íá õðïëïãéóåß ï
áñÜäåéãìá 2.1:
t X n−i
Ëýóç
. ÈÝù
:
j
i=1
n−i : j éá êÜèå óáèåñÜ éìÞ ïõ i, èåùñïýìå ï aij ùò áêïëïõèßá ìå äåßêç ï j . Ç
aij =
áíßóïé÷ç ãåííÞñéá óõíÜñçóç åßíáé:
Ai (x) = (1 + x)n−i : ÅìÜò üìùò ìáò åíäéáöÝñåé ç áêïëïõèßá bj ç ïðïßá ïñßæåáé ùò åîÞò:
bj =
t X
aij :
i=1
Ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò bj åßíáé
B ( x) =
t X
Ai (x) =
i=1
Ï üñïò
t P
i=1
1 1+x
i
t X
(1 + x)
n−i
= (1 + x)
n
i=1
t X i=1
1 (1 + x)
i
:
åßíáé ï Üèñïéóìá ãåùìåñéêÞò ðñïüäïõ. ¢ñá åßíáé ßóïò ìå 1 − (1 + x)−t
x
ÔåëéêÜ:
B (x) =
(1 + x)
n
:
(1 + x)
n−t
−
x
x
áñáçñïýìå áðü ïí ßíáêá 2.1 üé ç áêïëïõèßá ar = nr Ý÷åé ãåííÞñéá n n óõíÜñçóç (1 + x)n . ¢ñá ç áêïëïõèßá r+1 Ý÷åé ãåííÞñéá óõíÜñçóç (1+xx) −1 (1+x)n−t −1 (éäéüçá ïëßóèçóçò). ¼ìïéá ç óõíÜñçóç åßíáé ãåííÞñéá çò áêïëïõèßáò x n−t r +1 . Åäþ åßíáé r = j . ¢ñá:
bj =
t X n−i i=1
j
=
n
j+1
−
n−t : j +1
Óï ðñïçãïýìåíï ðáñÜäåéãìá ÷ñçóéìïðïéþíáò ãåííÞñéåò óõíáñÞóåéò ìðïñÝóáìå êáé õðïëïãßóáìå Ýíá Üèñïéóìá, ï ïðïßï åßíáé áñêåÜ äýóêïëï íá õðïëïãéóåß äéáöïñåéêÜ. Óçí ðáñÜãñáöï 2.3 èá äïýìå ðþò ÷ñçóéìïðïéïýíáé ïé ãåííÞñéåò óõíáñÞóåéò óå óõíäõáóéêÜ ðñïâëÞìáá. Óï ÊåöÜëáéï 3 èá ÷ñçóéìïðïéÞóïõìå ãåííÞñéåò óõíáñÞóåéò ãéá íá ëýóïõìå ó÷Ýóåéò áíáäñïìÞò.
2.2.
ÉÄÉÏÔÇÔÅÓ ÔÙÍ ÅÍÍÇÔÑÉÙÍ ÓÕÍÁÑÔÇÓÅÙÍ
19
Ç ãåíéêÞ éäÝá ðÜíùò ðïõ áêïëïõèåßáé óå ðïëëÝò ðåñéðþóåéò üðïõ èÝëïõìå íá áðïäåßîïõìå éäéüçåò £äéáêñéïý¤ ÷áñáêÞñá ðïõ áíáöÝñïíáé óå ìßá áêïëïõèßá åßíáé íá èåùñÞóïõìå ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò êáé íá âñïýìå êÜðïéá £áíáëõéêÞ¤ Þ £óõíå÷Þ¤ éäéüçá çò åëåõáßáò ðïõ áðïåëåß £ìåÜöñáóç¤ çò áñ÷éêÞò £äéáêñéÞò¤ éäéüçáò. Ç áíáëõéêÞ éäéüçá óõíÞèùò áðïäåéêíýåáé åõêïëüåñá áðü ç äéáêñéÞ. Áöïý çí áðïäåßîïõìå, åðéóñÝöïõìå óçí áñ÷éêÞ áêïëïõèßá. Ç ìåÜâáóç áðü ï ÷þñï ùí áêïëïõèéþí óï ÷þñï ùí ãåííçñéþí óõíáñÞóåùí êáé ç åðéóñïöÞ ãßíåáé ìå ÷ñÞóç ïõ ßíáêá 2.1. ïëëÝò öïñÝò üìùò, üðùò äåß÷íïõí êáé á ðáñáêÜù ðáñáäåßãìáá, ç £áíáëëáãÞ¤ áêïëïõèéþí ìå ãåííÞñéåò óõíáñÞóåéò äåí åßíáé åíåëþò Üìåóç. áñÜäåéãìá 2.2: 2r r
Íá äåé÷åß üé ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò ar =
; r = 0; 1; 2; : : : åßíáé ç A (x) = (1 − 4x)1=2 .
. Áðü ï äéùíõìéêü áíÜðõãìá Ý÷ïõìå üé
Ëýóç
(1 + x)
n
=
1+
∞ X n (n − 1) (n − 2) : : : (n − r + 1)
r!
r =1
(1 − 4x)
−1=2
=
1+
∞ X − 21
r =1
=
1+
∞ X 4r
1 2
r =1
=
1+
− 12 − 1
=
1+ 1+ 1+
r =1 ∞ X
r!
:::
r!
r!r!
2
xr
xr
r!r!
xr
∞ X 2r
=
1+
=
∞ X 2r
r
r =1
r
xr
(2 · 4 · 6 · : : : · 2r ) (1 · 3 · 5 · : : : · (2r − 1)) r x r!r!
∞ X (2r)!
r =1
r =0
5 2
∞ X 2r r! (1 · 3 · 5 · : : : · (2r − 1))
r =1
=
− 21 − 2 : : : − 12 − r + 1 (−4x)r r! 2r −1
∞ X 2r (1 · 3 · 5 · : : : · (2r − 1))
r =1
=
3 2
xr ⇒
xr :
xr
20
ÊÅÖÁËÁÉÏ 2.
Áêïëïõèßá
åííÞñéá óõíÜñçóç
ar ; r = 0; 1; 2; : : : ar
=
1
ar
=
r+1
a0 ar
=
0 1
a0 ar
=
=
=
ar
=
ar
=
ar
=
ar ar
r
0 1
r
1
r
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
A (x)
1 1−x 1 (1 − x)
2
;r ≥ 1
ln
1 1−x
ln (1 + x)
; r æõãüò ; r > 0 êáé ìïíüò n ; n∈R r
(1 + x)n
r!
1
ex
=
nr ; n∈R r!
enx
−
ar−1
(1 − x) A (x)
ßíáêáò 2.1: åííÞñéåò óõíáñÞóåéò êáé áêïëïõèßåò ÄçëáäÞ, (1 − 4x)
−1=2
=
∞ X 2r
r =0
r
xr :
¢ñá ç áêïëïõèßá ar = ; r = 0; 1; 2; : : : ; r Ý÷åé ãåííÞñéá óõíÜñçóç çí 1=2 A (x) = (1 − 4x) . ñéí ï äåýåñï ðáñÜäåéãìá êñßíïõìå óêüðéìï íá õðåíèõìßóïõìå óõíïðéêÜ çí å÷íéêÞ çò ìåñéêÞò êëáóìáéêÞò áíÜëõóçò. Óü÷ïò çò å÷íéêÞò áõÞò åßíáé íá ãñáöåß ìßá ñçÞ óõíÜñçóç F (x), äçëáäÞ ìßá óõíÜñçóç ðïõ ãñÜöåáé ùò ðçëßêïí P (x)=Q(x) äýï ðïëõùíýìùí P (x) êáé Q(x), ùò Üèñïéóìá êëáóìÜùí 2r r
2.2.
21
ÉÄÉÏÔÇÔÅÓ ÔÙÍ ÅÍÍÇÔÑÉÙÍ ÓÕÍÁÑÔÇÓÅÙÍ
áðëïýóåñçò ìïñöÞò. Äå÷üìáóå ÷ùñßò âëÜâç çò ãåíéêüçáò üé ï âáèìüò ïõ ðïëõùíýìïõ P (x) åßíáé ãíçóßùò ìéêñüåñïò ïõ âáèìïý ïõ ðïëõùíýìïõ Q(x) (áëëéþò äéáéñïýìå á ðïëõþíõìá). Áêüìç, ãéá íá áðïöýãïõìå ï äýó÷ñçóï óõìâïëéóìü çò ãåíéêÞò ðåñßðùóçò, èá èåùñÞóïõìå ìßá åéäéêÞ ðåñßðùóç ãéá ï ðïëõþíõìï Q(x). Ìåëåþíáò çí åéäéêÞ áõÞ ðåñßðùóç ï áíáãíþóçò èá ìðïñåß åýêïëá íá áíéìåùðßóåé ïðïéáäÞðïå ðåñßðùóç (ðåñéóóüåñåò ëåðïìÝñåéåò ìðïñåß íá âñåé ï áíáãíþóçò óå ïðïéïäÞðïå âéâëßï Áðåéñïóéêïý Ëïãéóìïý Þ åéóáãùãéêÞò ÁíÜëõóçò). ¸óù ëïéðüí üé ï Q(x) Ý÷åé ìßá ðñáãìáéêÞ ñßæá x1 ðïëëáðëüçáò 1, ìßá ðñáãìáéêÞ ñßæá x2 ðïëëáðëüçáò 3 êáé éò äýï óõæõãåßò öáíáóéêÝò ñßæåò ±i çí êÜèå ìßá ìå ðïëëáðëüçá 2. ÅðïìÝíùò ï âáèìüò ïõ Q(x) åßíáé 8 êáé ï âáèìüò ïõ P (x) |óýìöùíá ìå çí õðüèåóç ìáò| åßíáé ï ðïëý 7. Åðßóçò éó÷ýåé üé:
Q(x) = (x − x1 )(x − x2 )3 (x2 + 1)2 :
Íá óçìåéþóïõìå åäþ üé ãåíéêÜ äåí åßíáé åýêïëï, êáé ðïëëÝò öïñÝò åßíáé áäýíáï, íá âñïýìå éò ñßæåò åíüò ðïëõùíýìïõ üáí äåí éò ãíùñßæïõìå. Ç óõíçèÝóåñç áêéêÞ ãéá ïí õðïëïãéóìü ïõò åßíáé íá ðñïóðáèÞóïõìå íá áíáëýóïõìå ï ðïëõþíõìï óå ãéíüìåíï ðáñáãüíùí (üáí ï âáèìüò ïõ åßíáé ìåãáëýåñïò ïõ 2). Èá ãñÜøïõìå ç óõíÜñçóç F (x) = P (x)=Q(x) ùò:
F (x) = +
A
(x − x1 )
B
C
D
+ + (x − x2 )3 (x − x2 )2 (x − x2 ) Ex + F Gx + H + 2 + 2 (x + 1)2 (x + 1)
(2.4)
êáé èá õðïëïãßóïõìå ïõò óõíåëåóÝò A; B; C; D; E; F; G; H . éá ïí õðïëïãéóìü ïõ óõíåëåóÞ A, ðïëëáðëáóéÜæïõìå êáé á äýï ìÝëç çò åîßóùóçò (2.4) ìå (x − x1 ), äéáãñÜöïõìå ïí ðáñÜãïíá (x − x1 ) áð' üðïõ åßíáé äõíáü íá äéáãñáöåß êáé èÝïõìå x = x1 . ÔåëéêÜ ðñïêýðåé üé:
A = F (x)(x − x1 )|x=x
=
1
P (x1 ) : (x1 − x2 )3 (x21 + 1)2
éá ïí õðïëïãéóìü ïõ óõíåëåóÞ B , åðéóñÝöïõìå óçí åîßóùóç (2.4), ðïëëáðëáóéÜæïõìå êáé á äýï ìÝëç çò ìå (x − x2 )3 , äéáãñÜöïõìå ïí ðáñÜãïíá (x−x2 ) áð' üðïõ åßíáé äõíáü íá äéáãñáöåß êáé èÝïõìå x = x2 . ÔåëéêÜ ðñïêýðåé üé:
P (x2 ) : (x2 − x1 )(x22 + 1)2 éá ïí õðïëïãéóìü ïõ óõíåëåóÞ C , ðñéí èÝóïõìå x = x2 , B = F (x)(x − x2 )3 x=x
ðñþá êáé á äýï ìÝëç çò åîßóùóçò
ðñïêýðåé üé:
C=
d F (x)(x − x2 )3 dx
2
=
ðáñáãùãßæïõìå
êáé èÝïõìå óç óõíÝ÷åéá x = x2 . ÔåëéêÜ
x=x2
=
P (x) (x − x1 )(x2 + 1)2
′
: x=x2
22
ÊÅÖÁËÁÉÏ 2.
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
Ï õðïëïãéóìüò ïõ óõíåëåóÞ D ãßíåáé ðáñáãùãßæïíáò äýï öïñÝò ðñßí èÝóïõìå x = x2 . éá ïí õðïëïãéóìü ùí óõíåëåóþí F; G, åðéóñÝöïõìå óç åîßóùóç (2.4), ðïëëáðëáóéÜæïõìå êáé á äýï ìÝëç çò ìå (x2 + 1), äéáãñÜöïõìå ïí ðáñÜãïíá (x2 + 1)2 áð' üðïõ åßíáé äõíáü íá äéáãñáöåß êáé èÝïõìå x = i. Åîéóþíïíáò á ðñáãìáéêÜ êáé öáíáóéêÜ ìÝñç çò åîßóùóçò ðïõ ðñïêýðåé, ðáßñíïõìå Ýíá ãñáììéêü óýóçìá äýï åîéóþóåùí ìå áãíþóïõò ïõò óõíåëåóÝò F; G, ï ïðïßï åðéëýïõìå. ÔÝëïò ãéá ïí õðïëïãéóìü ùí óõíåëåóþí H; D, ðñéí èÝóïõìå x = i, ðáñáãùãßæïõìå äýï öïñÝò. áñÜäåéãìá 2.3:
ïéÜ áêïëïõèßá Ý÷åé ãåííÞñéá óõíÜñçóç çí
F (x) = Ëýóç
. Åßíáé
4x2 (1 − 8x)
2;
(1 − 4x) (1 − 2x)
F (x) = 4x
2
(1 − 8x)
(1 − 4x) (1 − 2x)
2
!
:
áñáçñÞóå üé áñêåß âñïýìå ðñþá ç ãåííÞñéá óõíÜñçóç ïõ ðáñÜãïíá G(x) = (1 − 8x) =((1 − 4x) (1 − 2x)2 ). Ï ðáñïíïìáóÞò Ý÷åé äýï ñßæåò, ç x1 = 1=4 ðïëëáðëüçáò 1 êáé çí x2 = 1=2, ðïëëáðëüçáò 2. ÅðïìÝíùò èÝù:
G (x) =
A
(1 − 4x)
+
B
(1 − 2x)
2
+
C
(1 − 2x)
:
áñáçñÞóå üé ãéá íá áðïöýãïõìå ðïëýðëïêåò êëáóìáéêÝò åêöñÜóåéò, ãñÜøáìå ïõò ðáñïíïìáóÝò ùí áðëþí êëáóìÜùí ëßãï äéáöïñåéêÜ óå óýãêñéóç ìå çí ðåñßðùóç ðïõ áíáëýóáìå ðñïçãïýìåíá. ¸÷ïõìå þñá:
A
=
B
=
C
=
ÅðïìÝíùò
(1 − 8x)
(1 − 4x) 2 (1 − 4x) (1 − 2x)
x=1=4
= : : : = −4;
(1 − 8x)
(1 − 2x) = : : : = 3; 2 (1 − 4x) (1 − 2x) x=1=2 " !# 1 d (1 − 8x) 2 − (1 − 2x) = : : : = 2: 2 2 dx (1 − 4x) (1 − 2x) x=12 2
G (x) =
−4 3 2 + + : 2 (1 − 4x) (1 − 2x) (1 − 2x)
ñïêýðåé þñá üé ç áêïëïõèßá ðïõ áíéóïé÷åß óç ãåííÞñéá óõíÜñçóç G(x) åßíáé ç:
ar = −4 · 4r + 3 (r + 1) 2r + 2 · 2r ; r = 0; 1; 2; : : : ¢ñá ç F (x) = 4x2 G(x) åßíáé ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò 4ar−2 . ÅðïìÝíùò ç æçïýìåíç áêïëïõèßá åßíáé ç
ar =
0; r < 2 (3r − 1) 2r − 4r ;
r = 2; 3; 4; : : :
2.2.
23
ÉÄÉÏÔÇÔÅÓ ÔÙÍ ÅÍÍÇÔÑÉÙÍ ÓÕÍÁÑÔÇÓÅÙÍ
Íá âñåèåß êëåéóüò ýðïò ãéá ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò ar = r2 ; r = 0; 1; 2; : : : êáé óç óõíÝ÷åéá íá õðïëïãéóåß ï Üèñïéóìá 12 + 22 + 32 + : : : + r 2 . áñÜäåéãìá 2.4:
. Åßíáé ãíùóü üé
Ëýóç
1 = 1 + x + x2 + x3 + : : : + xr + : : : 1−x
áñáãùãßæïíáò êáé á äýï ìÝñç çò ðáñáðÜíù åîßóùóçò ðñïêýðåé: 1
= 1 + 2x + 3x2 + 4x3 + : : : + rxr−1 + : : :
(1 − x)
2
ïëëáðëáóéÜæïíáò åðß x ðñïêýðåé:
x
= 1x + 2x2 + 3x3 + 4x4 + : : : + rxr + : : : ;
(1 − x)2
ðáñáãùãßæïíáò îáíÜ:
x d dx (1 − x)2
= 12 + 22 x + 33 x2 + 42 x3 + : : : + r2 xr−1 + : : : ;
êáé Ýëïò ðïëëáðëáóéÜæïíáò ðÜëé åðß x:
x
x d dx (1 − x)2
= 02 + 12 x + 22 x2 + 33 x3 + : : : + r2 xr + : : :
ÄçëáäÞ ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò ar = r2 ; r = 0; 1; 2; : : : åßíáé ç:
f (x) =
x (1 + x) 3 : (1 − x)
Áðü çí éäéüçá ùí ìåñéêþí áèñïéóìÜùí Ý÷ïõìå üé ç
g (x) =
x (1 + x) 3 (1 − x) (1 − x)
=
åßíáé ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò
f (x) (1 − x)
02 ; 02 + 12 ; 02 + 12 + 22 ; 02 + 12 + 22 + 32 ; : : : ; 02 + 12 + 22 + 32 + : : : + r 2 ; : : :
Óýìöùíá ìå ï äéùíõìéêü áíÜðõãìá Ý÷ïõìå üé ï óõíåëåóÞò ïõ xr óï 1 åßíáé (1−x)4 (−4) (−4 − 1) (−4 − 2) : : : (−4 − r + 1) r (−1) r!
= =
ÅðïìÝíùò ï óõíåëåóÞò ïõ xr óçí Ýêöñáóç
r (r + 1) (r + 2) ÅðïìÝíùò
1·2·3
+
x(1+x) (1−x)4
(r − 1) r (r + 1) = 1·2·3
12 + 22 + 32 + : : : + r 2 =
4 · 5 · 6 · : : : · (r + 3) r! (r + 1) (r + 2) (r + 3) : 1·2·3
åßíáé
r (r + 1) (2r + 1) 6
r (r + 1) (2r + 1) 6
:
:
24
ÊÅÖÁËÁÉÏ 2.
2.3
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
ÁðáñéèìçÝò
Áí ïé üñïé ìéáò áêïëïõèßáò ar ; r = 0; 1; 2; : : : äßíïõí ï ðëÞèïò åíüò óõíüëïõ óõíäõáóéêþí áíéêåéìÝíùí ðïõ åîáñÜáé áðü çí ðáñÜìåñï r, üå ç ãåííÞñéá óõíÜñçóç
A (x) =
∞ X
ar xr
r =0
êáëåßáé áðáñéèìçÞò ïõ óõíüëïõ. éá ðáñÜäåéãìá, ç ãåííÞñéá óõíÜñçóç n X n r =0
r
xr
åßíáé ï áðáñéèìçÞò ùí óõíäõáóìþí (÷ùñßò åðáíÜëçøç) r áíéêåéìÝíùí åðéëåãìÝíùí áðü n áíéêåßìåíá (óï ðáñÜäåéãìá áõü ï óýíïëï ùí óõíäõáóéêþí áíéêåéìÝíùí ðáñáìåñïðïéåßáé áðü ï r, åíþ ï n èåùñåßáé ùò óáèåñÜ). Ïé áðáñéèìçÝò ÷ñçóéìïðïéïýíáé ãéá íá õðïëïãßóïõìå ï ðëÞèïò óõíüëùí áíéêåéìÝíùí ðïõ äßíïíáé ìå óõíäõáóéêÞ ðåñéãñáöÞ êáé åîáñþíáé áðü ìßá ðáñÜìåñï. ÊáÜ çí åöáñìïãÞ çò ìåèüäïõ áõÞò, âñßóêïõìå ðñþá Ýíáí êëåéóü (äçë. óõìðçãìÝíï) ýðï ãéá ïí áðáñéèìçÞ £ìåáöñÜæïíáò¤ ç óõíäõáóéêÞ ðåñéãñáöÞ ïõ óõíüëïõ óå áëãåâñéêÝò ðñÜîåéò. Óç óõíÝ÷åéá ãñÜöïõìå ïí áðáñéèìçÞ óå ìïñöÞ äõíáìïóåéñÜò. Ïé óõíåëåóÝò çò äõíáìïóåéñÜò ìáò äßíïõí ï ðëÞèïò ùí áíéêåéìÝíùí ïõ óõíüëïõ, ãéá êÜèå éìÞ çò ðáñáìÝñïõ. áñÜäåéãìá 2.5:
¸óù üé èÝëïõìå íá õðïëïãßóïõìå ïí áñéèìü ùí åðéëïãþí
r áíéêåéìÝíùí (÷ùñßò åðáíÜëçøç) áðü n áíéêåßìåíá.
. Åßíáé åýêïëï íá äéáðéóþóïõìå áí óêåöïýìå ïí ñüðï ðïõ ðïëëáðëáóéÜæïõìå ðïëõþíõìá üé ï áñéèìüò áõüò ðñÝðåé íá åßíáé ï óõíåëåóÞò ïõ xr óç óõíÜñçóç n n (1 + x) . Áíáðýóóïíáò þñá ï (1 + x) óå äõíáìïóåéñÜ (÷ñçóéìïðïéþíáò ï äéùíõìéêü ýðï) êááëÞãïõìå óï óõìðÝñáóìá üé ï æçïýìåíïò áñéèìüò åßíáé Ëýóç
n (n − 1) : : : (n − r + 1) : r! Áò åîåÜóïõìå þñá é èá ãßíåé áí åðéñÝøïõìå åðáíÜëçøç ùí áíéêåéìÝíùí. ¸óù üé Ý÷ïõìå ìüíï ñßá áíéêåßìåíá êáé èÝëïõìå íá âñïýìå ïõò äõíáïýò ñüðïõò íá êááóêåõÜóïõìå óõíäõáóìïýò áðü áõÜ ìå ïí ðåñéïñéóìü üé i-ïóü áíéêåßìåíï ìðïñåß íá åðáíáëçöèåß óï óõíäõáóìü Ýùò mi öïñÝò, üðïõ mi ; i = 1; 2; 3 äåäïìÝíïé öõóéêïß áñéèìïß. áñáçñþíáò ðÜëé ðþò ðïëëáðëáóéÜæïõìå ðïëõþíõìá, êááëÞãïõìå óï óõìðÝñáóìá üé ï æçïýìåíïò áñéèìüò åßíáé ï óõíåëåóÞò ïõ xr óï áíÜðõãìá ïõ ðïëõùíýìïõ 1 + x + x2 + : : : + xm1
1 + x + x2 + : : : + xm2
1 + x + x2 + : : : + xm3
:
Áí þñá åðéñÝðïõìå áðåñéüñéóç åðáíÜëçøç ùí áíéêåéìÝíùí, ï æçïýìåíïò áñéèìüò åßíáé ï óõíåëåóÞò ïõ xr óï: ÅðåéäÞ üìùò
3 1 + x + x2 + : : : : 1 + x + x2 + : : : =
1 (ãéá |x| < 1) ; 1−x
2.3.
25
ÁÁÑÉÈÌÇÔÅÓ
ï æçïýìåíïò áñéèìüò åßíáé ï óõíåëåóÞò ïõ xr óï: (1 − x)
−3
=
∞ X
r
(−1)
r =0
¢ñá ï æçïýìåíïò áñéèìüò åßíáé (−1)
r
−3
r
=
−3
xr :
r
r+2 r
Åßíáé ðëÝïí åñéììÝíï íá áðïäåßîïõìå üé áí Ý÷ïõìå n áíéêåßìåíá êáé èÝëïõìå íá åðéëÝîïõìå r áðü áõÜ ìå åðáíÜëçøç, õðÜñ÷ïõí
n+r−1 r
ñüðïé íá ï êÜíïõìå. Ìå Üëëá ëüãéá, õðÜñ÷ïõí
n+r−1 r
ïðïèåÞóåéò r ìç äéáêåêñéìÝíùí áíéêåéìÝíùí óå n äéáêåêñéìÝíåò õðïäï÷Ýò. Óá ßäéá óõìðåñÜóìáá åß÷áìå êááëÞîåé ìå äéáöïñåéêïýò ñüðïõò êáé óï ðñïçãïýìåíï êåöÜëáéï. Ôþñá üìùò Ý÷ïõìå óá ÷Ýñéá ìáò Ýíá éó÷õñü åñãáëåßï ðïõ ìáò åðéñÝðåé íá ëýóïõìå äõóêïëüåñá ðñïâëÞìáá. ¸óù üé Ý÷ïõìå ïí ðåñéïñéóìü üé üëåò ïé õðïäï÷Ýò ðñÝðåé íá Ý÷ïõí Ýíá ïõëÜ÷éóïí áíéêåßìåíï. áñÜäåéãìá 2.6:
. Åßíáé þñá åýêïëï íá äéáðéóþóåé êáíåßò üé ï áðáñéèìçÞò åßíáé
Ëýóç
n
x + x2 + : : :
=
xn (1 − x)n
¢ñá ï æçïýìåíïò áñéèìüò åßíáé r
(−1)
= xn
∞ X
r
(−1)
r =0
−n r−1 = : r−n r−n
−n
r
xr :
ïéü åßíáé ï ðëÞèïò ùí óõíäõáóìþí r áíéêåéìÝíùí áðü n áíéêåßìåíá, ìå åðáíÜëçøç áëëÜ ìå ïí ðåñéïñéóìü üé êÜèå áíéêåßìåíï ðñÝðåé íá åìöáíéóåß Üñéï áñéèìü öïñþí; Óçìåéþóå üé ï ðéï ðÜíù ðñüâëçìá åßíáé ï ßäéï ìå ï åîÞò: £Íá âñåèåß ï áñéèìüò ùí ñüðùí ðïõ r ìç äéáêåêñéìÝíá áíéêåßìåíá ìðïñïýí íá ïðïèåçèïýí óå n õðïäï÷Ýò äéáêåêñéìÝíåò, ìå ïí ðåñéïñéóìü üé êÜèå õðïäï÷Þ èá äå÷åß Üñéï áñéèìü áíéêåéìÝíùí¤. áñÜäåéãìá 2.7:
. Ç ãåííÞñéá óõíÜñçóç/áðáñéèìçÞò åßíáé
Ëýóç
n
1 + x2 + x4 + : : :
Åßíáé ãíùóü üé
:
1 = 1 + x2 + x4 + : : : 1 − x2
26
ÊÅÖÁËÁÉÏ 2.
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
ÅðïìÝíùò: n
1 + x + x + ::: 2
4
= 1−x
¢ñá, üðùò áíáìÝíåáé, ç áðÜíçóç åßíáé Óçìåéþóå üé 1 − x2
2 −n
−n
=
∞ X n+r−1
r
r =0
x2r :
n+r=2−1 r=2
.
= (1 − x)−n (1 + x)−n :
×ñçóéìïðïéþíáò éò ðáñáðÜíù ó÷Ýóåéò êáé çí éäéüçá çò óõíÝëéîçò êááëÞãïõìå óï óõìðÝñáóìá üé ç Ýêöñáóç:
n+r−1 n+r−2 n+r−3 n+1 − n+ − ::: 2 r r−1 r−2 n+k−1 k n + (r − k ) − 1 r n+r−1 + : : : + (−1) + (−1) r−k k r
åßíáé ßóç ìå 0 ãéá r ðåñéü, êáé åßíáé ßóç ìå
n+s−1 ãéá Üñéï r = 2s: s
¢ñá êááëÞãïõìå óïí ýðï
n+s−1 s
=
2s X n + 2s − k − 1 n + k − 1
k=0
2s − k
k
k
(−1)
:
Íá âñåèåß ï áñéèìüò ùí ñüðùí ðïõ Ýíáò áêÝñáéïò èåéêüò áñéèìüò n ìðïñåß íá ãñáöåß ùò Üèñïéóìá èåéêþí áêåñáßùí áñéèìþí, ÷ùñßò íá ìáò åíäéáöÝñåé ç óåéñÜ ùí üñùí óá áèñïßóìáá. Ï áñéèìüò áõüò óõìâïëßæåáé ìå d(n). éá ðáñÜäåéãìá: áñÜäåéãìá 2.8 (äéáìåñßóåéò áêåñáßùí):
d (1) = 1 d (2) = 2 d (3) = 3 d (4) = 5 Ëýóç.
: 1 : 2=1+1 : 3=2+1=1+1+1 : 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1:
Ìðïñïýìå íá èåùñÞóïõìå üé ïé åêèÝåò ïõ x óç äõíáìïóåéñÜ
1 + x + x1+1 + x1+1+1 + x1+1+1+1 + · · · = 1 + x + x2 + x3 + x4 + · · ·
áíéóïé÷ïýí óéò öïñÝò èá ÷ñçóéìïðïéÞóïõìå ï 1 óå ìßá äéáìÝñéóç ïõ n. ¼ìïéá ïé åêèÝåò ïõ x óç äõíáìïóåéñÜ 1 + x2 + x2+2 + x2+2+2 + · · · = 1 + x2 + x4 + x6 + · · ·
áíéóïé÷ïýí óéò öïñÝò ðïõ èá ÷ñçóéìïðïéÞóïõìå ï 2 óå ìßá äéáìÝñéóç ïõ n. ÅÜí èÝëïõìå ëïéðüí íá õðïëïãßóïõìå, ãéá ðáñÜäåéãìá, ï d(10) áñêåß íá âñïýìå ï óõíåëåóÞ ïõ x10 óï ãéíüìåíï:
f (x) =
1 + x + x2 + x3 + · · · 1 + x2 + x4 + x6 + · · · · · · 1 + x10 + x20 + x30 + · · · :
2.3.
27
ÁÁÑÉÈÌÇÔÅÓ
áñáçñÞóå þñá üé:
f (x) =
10
Y 1 1 1 1 · · · = : 2 10 (1 − x) (1 − x ) (1 − x ) i=1 (1 − xi )
åíéêåýïíáò á ðáñáðÜíù, êááëÞãïõìå óï üé óõíÜñçóç:
D (x) =
∞ Y
1 (1 − xi )
i=1
åßíáé ç ãåííÞñéá óõíÜñçóç (áðáñéèìçÞò) ãéá çí áêïëïõèßá d(n); n = 0; 1; : : :, üðïõ ïñßæïõìå d(0) = 1. Áí êáé ï D(x) åßíáé èåùñçéêÜ ðëÞñùò ïñéóìÝíï, åßíáé áñêåÜ äýóêïëï íá äïõëåýïõìå ìå ãéíüìåíá Üðåéñùí üñùí. ÅÜí üìùò èåùñÞóïõìå ìüíï ï r Y
1 ; ãéá êÜðïéï óáèåñü (1 − xi ) i=1
r;
üå ï óõíåëåóÞò ïõ xn åßíáé ï áñéèìüò ùí äéáìåñßóåùí ïõ n óå áèñïßóìáá ùí ïðïßùí ïé üñïé äåí õðåñâáßíïõí ï r. Íá âñåèåß ç ãåííÞñéá óõíÜñçóç ãéá ï dÆ (n), üðïõ dÆ (n) åßíáé ï áñéèìüò ùí äéáìåñßóåùí åíüò èåéêïý áêÝñáéïõ n óå áèñïßóìáá ðïõ ðåñéÝ÷ïõí äéáöïñåéêïýò èåéêïýò áêÝñáéïõò.
áñÜäåéãìá 2.9:
. éá ðáñÜäåéãìá, åíþ üëåò ïé äõíáÝò äéáìåñßóåéò ïõ áêÝñáéïõ 6 (ü÷é êá' áíÜãêç óå äéáöïñåéêïýò áêÝñáéïõò åßíáé ïé:
Ëýóç
(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) ðåñéÝ÷ïõí äéáöïñåéêïýò áêÝñáéïõò. ÅðïìÝíùò dÆ (6) = 4. áñáçñïýìå þñá üé ãéá ïí õðïëïãéóìü ïõ dÆ (n) Ý÷ïõìå äýï åðéëïãÝò ãéá êÜèå áêÝñáéï k: (á) ï k íá ìç ÷ñçóéìïðïéçèåß óç äéáìÝñéóç Þ (â) ï k íá ÷ñçóéìïðïéçèåß ìüíï ìéá öïñÜ. ÅðïìÝíùò ðñïêýðåé üé ç ãåííÞñéá óõíÜñçóç ãéá ï dÆ (n) åßíáé ç
DÆ (x) = (1 + x)
1 + x2
1 + x3
¢ñá ï dÆ (n) åßíáé ï óõíåëåóÞò ïõ x óï n
(1 + x) 1 + x2
::: =
i=1
: : : (1 + xn ) :
Ïñßæïõìå üé dÆ (0) = 1. éá n = 6, ï óõíåëåóÞò ïõ x6 óï
(1 + x) 1 + x2
åßíáé 4.
:::
1 + x6
∞ Y
1 − xi
28
ÊÅÖÁËÁÉÏ 2.
2.4
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
ÅêèåéêÝò åííÞñéåò ÓõíáñÞóåéò
Äõóõ÷þò ïé ãåííÞñéåò óõíáñÞóåéò ðïõ ìÜèáìå ìÝ÷ñé þñá äåí ìðïñïýí íá ÷ñçóéìïðïéçèïýí ãéá ç ìÝñçóç äéáÜîåùí, Þ ãéá çí åýñåóç ïõ ðëÞèïõò óõíüëùí áðü óõíäõáóéêÜ áíéêåßìåíá á ïðïßá åîáñþíáé áðü ðáñÜìåñï ðïõ áíáöÝñåáé óå äéáêåêñéìÝíá áíéêåßìåíá. Ôïýï äéüé ï ðïëëáðëáóéáóìüò åßíáé áíéìåáèåéêÞ ðñÜîç, Üñá ðïëëáðëáóéÜæïíáò ðïëõþíõìá Þ óåéñÝò äåí ìðïñïýìå íá £áðåéêïíßóïõìå¤ áëãåâñéêÜ çí Ýííïéá ùí äéáÜîåùí Þ ùí ðáñáìåñïðïéÞóåùí ðïõ áíáöÝñïíáé óå äéáêåêñéìÝíá áíéêåßìåíá. Ìðïñïýìå üìùò íá îåöýãïõìå áðü áõü ï áäéÝîïäï. Áò ðáñáçñÞóïõìå ðñþá üé (1 + x) = n
∞ X
P (n; r)
r =0
r
xr ; r!
äçëáäÞ ï óõíåëåóÞò ïõ xr! óï áíÜðõãìá ïõ (1 + x)n åßíáé ï áñéèìüò ùí äéáÜîåùí r áíéêåéìÝíùí åðéëåãìÝíùí áðü n áíéêåßìåíá. Áõü ìáò ïäçãåß íá ïñßóïõìå ùò åêèåéêÞ ãåííÞñéá óõíÜñçóç ìéáò áêïëïõèßáò a0 ; a1 ; : : : ç óåéñÜ ∞ ∞ P P k xr ar xr!r (ç ïñïëïãßá ïöåßëåáé óï üé ex = r ! ). r =0
r =0
Áò êïéÜîïõìå þñá ðñïóåêéêÜ Ýíá ãéíüìåíï çò ìïñöÞò: 1+
x 1!
+
x2 2!
+
x3 3!
Áí áíáðýîïõìå ï ãéíüìåíï áõü óå óåéñÜ ùí q1 +q2
n
+ :::
xr r!
:
; ï óõíåëåóÞò ïõ
xr r!
åßíáé
r! ; q ! q ! : : : qn ! +:::+qn =r 1 2 X
üðïõ ï Üèñïéóìá êõìáßíåáé ðÜíù áðü üëåò éò äõíáÝò áíáëýóåéò ïõ r óå Üèñïéóìá n ìç áñíçéêþí üñùí (äéáöïñåéêÝò èåùñïýíáé äýï áíáëýóåéò åÜí Ý÷ïõí äéáöïñåéêÜ óýíïëá üñùí, Þ åÜí Ý÷ïõí ï ßäéï óýíïëï üñùí áëëÜ ìå äéáöïñåéêÞ óåéñÜ). ÁëëÜ üìùò ç Ýêöñáóç
r! q1 !q2 ! : : : qn ! äßíåé ïí áñéèìü ùí ìåáèÝóåùí r áíéêåéìÝíùí ðïõ åßíáé ÷ùñéóìÝíá óå n ïìÜäåò ìå qi (1 ≤ i ≤ n) ìç äéáêåêñéìÝíá óïé÷åßá ç êÜèå ìßá. ÅðïìÝíùò ç Ýêöñáóç q1
r! q : : : qn ! ! 1 +:::+qn =r X
(2.5)
äßíåé ïí áñéèìü ùí ìåáèÝóåùí ìå åðáíÜëçøç r áíéêåéìÝíùí åðéëåãìÝíùí áðü n áíéêåßìåíá (ç Ýêöñáóç áõÞ åðïìÝíùò éóïýáé ìå nr ). Äåí åßíáé þñá äýóêïëï íá ãåíéêåýóïõìå éò ðáñáðÜíù éäÝåò: áñÜäåéãìá 2.10:
Íá õðïëïãéóèåß ï áñéèìüò ùí ñüðùí íá êááíåìçèïýí
r äéáêåêñéìÝíá áíéêåßìåíá óå n äéáêåêñéìÝíåò (Þ ìç äéáêåêñéìÝíåò) õðïäï÷Ýò, üáí êÜèå õðïäï÷Þ ðñÝðåé íá äå÷èåß Ýíá ïõëÜ÷éóïí áíéêåßìåíï.
2.4.
29
ÅÊÈÅÔÉÊÅÓ ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
. Èåùñïýìå ùò ðáñÜìåñï ïõ ðñïâëÞìáïò ïí áñéèìü r ùí áíéêåéìÝíùí êáé ùò óáèåñÜ ïí áñéèìü n ùí õðïäï÷þí. ¢ñá áêüìç êáé åÜí ïé õðïäï÷Ýò åßíáé ìç äéáêåêñéìÝíåò, èá ÷ñçóéìïðïéÞóïõìå åêèåéêÝò ãåííÞñéåò óõíáñÞóåéò. Áò åîåÜóïõìå ðñþá çí ðåñßðùóç üðïõ ïé õðïäï÷Ýò åßíáé äéáêåêñéìÝíåò. Ï åêèåéêüò áðáñéèìçÞò åßíáé Ëýóç
x+
x2
+
2!
n
x3
+ :::
3!
= (ex − 1)n :
Óçìåßùóç: Ôï ðñüâëçìá ùí ïðïèåÞóåùí óå áõÞ çí ðåñßðùóç åßíáé éóïäýíáìï ìå çí åýñåóç ïõ áñéèìïý ùí äéáÜîåùí r áíéêåéìÝíùí åðéëåãìÝíùí áðü n áíéêåßìåíá, ìå åðáíÜëçøç, áëëÜ êáé ìå ïí åðéðëÝïí ðåñéïñéóìü üé üëá á n áíéêåßìåíá ðñÝðåé íá åìöáíéóèïýí óç äéÜáîç ïõëÜ÷éóïí ìßá öïñÜ. áñáçñïýìå þñá üé: (ex − 1)
n
n X n
=
i=0 n X
=
i
n i
i=0
∞ X xr
=
r =0
r!
e
i (n−i)x
(−1)
∞ X 1 r (n − i) xr r ! r =0 n X i n r (−1) (n − i) :
i
(−1)
i
i=0
ÅðïìÝíùò, ï áñéèìüò ùí ñüðùí íá ïðïèåÞóïõìå r äéáêåêñéìÝíá áíéêåßìåíá óå n äéáêåêñéìÝíåò õðïäï÷Ýò, ÷ùñßò íá áöÞóïõìå Üäåéåò õðïäï÷Ýò, åßíáé n X
i
(−1)
i=0
üðïõ
S (r; n) =
n i
(n − i) = n!S (r; n) ;
n
r
1 X i (−1) n! i=0
n i
(n − i)
r
:
(2.6)
Ïé S (r; n) êáëïýíáé áñéèìïß Stirling 2ïõ åßäïõò. Óõìâïëßæïíáé åðßóçò êáé ìå r
. éá çí ðåñßðùóç þñá ðïõ ïé õðïäï÷Ýò åßíáé ìç äéáêåêñéìÝíåò, áñêåß íá äéáéñÝóïõìå ïí ýðï ãéá äéáêåêñéìÝíåò õðïäï÷Ýò ìå n! ãéá íá êááëÞîïõìå óï óõìðÝñáóìá üé ï áñéèìüò ùí ñüðùí íá ïðïèåÞóïõìå r äéáêåêñéìÝíá áíéêåßìåíá óå n ìç äéáêåêñéìÝíåò õðïäï÷Ýò, ÷ùñßò íá áöÞóïõìå Üäåéåò õðïäï÷Ýò, åßíáé S (r; n). áñáçñÞóå üé óçí ðåñßðùóç áõÞ ï ðñüâëçìá åßíáé éóïäýíáìï ìå ïí õðïëïãéóìü ïõ áñéèìïý ùí ñüðùí ðïõ Ýíá óýíïëï ìå r óïé÷åßá ìðïñåß íá äéáìåñéóèåß óå n ìç êåíÜ õðïóýíïëá, îÝíá áíÜ äýï ìåáîý ïõò. Ï åêèåéêüò áðáñéèìçÞò ùí áñéèìþí áõþí (èåùñþíáò ùò ðáñÜìåñï ï r êáé ï n ùò óáèåñÜ) åßíáé (ex − 1)n =n!. ×ñçóéìïðïéþíáò çí ðáñáðÜíù åñìçíåßá ïõ áñéèìïý ùí äéáìåñßóåùí ãéá ïõò áñéèìïýò Stirling 2ïõ åßäïõò åßíáé åýêïëï íá êááëÞîåé êáíåßò óïí áêüëïõèï áíáãùãéêü ýðï: n
S (r + 1; n + 1) = (n + 1)S (r; n + 1) + S (r; n):
(2.7)
ñÜãìáé, äåäïìÝíùí r + 1 äéáêåêñéìÝíùí áíéêåéìÝíùí, Ýóù ùí {1; : : : ; r; r + 1}, îå÷ùñßæù Ýíá áðü áõÜ, Ýóù ï åëåõáßï, ï r + 1. éá íá êááóêåõÜóù
30
ÊÅÖÁËÁÉÏ 2.
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
þñá ìßá ïðïéáäÞðïå äéáìÝñéóç ùí áíéêåéìÝíùí {1; : : : ; r; r + 1} õðÜñ÷ïõí äýï åðéëïãÝò: (á) íá êááóêåõÜóù ìßá äéáìÝñéóç ùí r áíéêåéìÝíùí {1; : : : ; r} ðïõ Ý÷åé n +1 õðïóýíïëá êáé íá ðñïóèÝóù ï áíéêåßìåíï r +1 óå êÜðïéï áðü á n +1 õðïóýíïëá Þ (â) íá êááóêåõÜóù ìßá äéáìÝñéóç ùí r áíéêåéìÝíùí {1; : : : ; r} ðïõ Ý÷åé n õðïóýíïëá êáé íá èåùñÞóù üé ï ìïíïóýíïëï {r + 1} áðïåëåß ï (n + 1)-ïóü õðïóýíïëï çò äéáìÝñéóçò. Áñêåß þñá íá ðáñáçñÞóïõìå üé ç åðéëïãÞ (á) ìðïñåß íá õëïðïéçèåß êáÜ n + 1 ñüðïõò, åíþ ç åðéëïãÞ (â) êáÜ Ýíá ñüðï. Óïí ßíáêá 2.2 õðÜñ÷ïõí ìåñéêïß áñéèìïß Stirling 2ïõ åßäïõò, õðïëïãéóìÝíïé ìå ÷ñÞóç ïõ ýðïõ 2.7.
r=n 1 2
3
4
5
6
7
8
9
10
1 2 3 4 5 6 7 8 9 10
1 6 25 90 301 966 3025 9330
1 10 65 350 1701 1770 34105
1 15 140 1050 6951 42525
1 21 266 2646 22827
1 28 462 5880
1 36 750
1 45
1
1 1 1 1 1 1 1 1 1 1
1 3 7 15 31 63 127 255 511
ßíáêáò 2.2: Áñéèìïß Stirling 2ïõ åßäïõò, S (r; n) Óå áõü ï óçìåßo íá áíáöÝñïõìå üé õðÜñ÷ïõí êáé áñéèìïß Stirling 1ïõ åßäïõò, ðïõ óõìâïëßæïíáé s(r; n) (Þ åðßóçò êáé ìå nr ) êáé äßíïõí ïí áñéèìü ùí ñüðùí íá êááóêåõÜóïõìå Ýíá óýíïëï áðü n ðåñéäÝñáéá ÷ñçóéìïðïéþíáò r äéáêåêñéìÝíåò ÷Üíñåò (êÜèå ðåñéäÝñáéï ðñÝðåé íá ðåñéÝ÷åé ïõëÜ÷éóïí ìßá ÷Üíñá). Ï áíáãùãéêüò ýðïò ãéá ïõò áñéèìïýò Stirling 1ïõ åßäïõò åßíáé (Üóêçóç):
s(r + 1; n + 1) = rs(r; n + 1) + s(r; n):
(2.8)
Óïí ßíáêá 2.3 õðÜñ÷ïõí ìåñéêïß áñéèìïß Stirling 1ïõ åßäïõò, õðïëïãéóìÝíïé ìå ÷ñÞóç ïõ ýðïõ 2.8. Íá âñåèåß ï åêèåéêüò áðáñéèìçÞò ïõ áñéèìïý ùí ñüðùí íá äéáìåñßóïõìå Ýíá óýíïëï áðü r óïé÷åßá óå ìç êåíÜ, îÝíá áíÜ äýï õðïóýíïëá ÷ùñßò ðåñéïñéóìü óïí áñéèìü ùí õðïóõíüëùí. Ïé áñéèìïß áõïß êáëïýíáé áñéèìïß Bell êáé óõìâïëßæïíáé ìå Br .
áñÜäåéãìá 2.11:
Ëýóç. ÅðåéäÞ ìßá äéáìÝñéóç èá áðïåëåßáé áðü Ýíá Þ äýï Þ ñßá êë õðïóýíïëá, åßíáé åýêïëï íá äéáðéóþóåé êÜðïéïò üé:
Br =
∞ X
i=1
S (r; i):
2.4.
31
ÅÊÈÅÔÉÊÅÓ ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
r=n 1
2
3
4
5
6
7
8
1 2 3 4 5 6 7 8
1 3 11 50 274 1764 13068
1 6 35 255 1624 13132
1 10 85 735 6769
1 15 175 1960
1 21 322
1 28
1
1 1 2 6 24 120 720 5040
ßíáêáò 2.3: Áñéèìïß Stirling 1ïõ åßäïõò s(r; n) ÎÝñïõìå üé ï åêèåéêüò áðáñéèìçÞò ùí S (r; n) åßíáé (ex − 1)n =n!. ÅðïìÝíùò, ï åêèåéêüò áðáñéèìçÞò ùí áñéèìþí Bell Br åßíáé ∞ x X (e − 1)i
i!
i=1
x −1
= ee
− 1:
Íá âñåèåß ï áñéèìüò ùí ñüðùí íá åêõðùèïýí 25 äéáöïñåéêÜ ðñïãñÜììáá áðü ïõò 3 äéáöïñåéêïýò åêõðùÝò ðïõ äéáèÝåé Ýíá õðïëïãéóéêü êÝíñï, ìå ïí ðåñéïñéóìü üé êÜèå åêõðùÞò ðñÝðåé íá åêõðþóåé Ýíá ïõëÜ÷éóïí ðñüãñáììá. áñÜäåéãìá 2.12:
. Èá ÷ñçóéìïðïéÞóïõìå åêèåéêÞ ãåííÞñéá óõíÜñçóç. ÁõÞ åßíáé ç åîÞò:
Ëýóç
x+
x2 2!
+
x3 3!
+ :::
3
= (ex − 1)3
Ï áñéèìüò ùí ñüðùí ðïõ ìðïñïýí íá ãßíïõí ïé åêõðþóåéò åßíáé ï óõíåëåóÞò ïõ x25 =25! óï (ex − 1)3 . ¸÷ïõìå üé (ex − 1)
3
= = =
e3x − 3e2x + 3ex − 1 ∞ ∞ X X xr xr 3r −3 2r r! r! r =0 r =0 ∞ X
r =0
(3r − 3 · 2r + 3)
xr r!
+3
∞ X xr
r =0
r!
− 1:
ÅðïìÝíùò ï óõíåëåóÞò ïõ x25 =25! åßíáé 325 − 3 · 225 + 3.
−1
32 2.5
ÊÅÖÁËÁÉÏ 2.
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
ÁóêÞóåéò
2.1 ïéÜ áêïëïõèßá Ý÷åé ãåííÞñéá óõíÜñçóç çí: x−x −x , A (x) = 1+2 1+x−x −x x−6x , (â) A (x) = 2+31+2 x 2 (ã) A (x) = 1−4x . 2
(á)
3
2
3
2
2
2.2 ïéÜ åßíáé ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò: (á) 2; 5; 13; 35; : : : = 2n + 3n , (â) 1; 2; 3; : : : ; r; : : : 2.3 Íá áðïäåé÷èïýí ïé éäéüçåò ùí ìåñéêþí áèñïéóìÜùí ÷ñçóéìïðïéþíáò çí éäéüçá çò óõíÝëéîçò. 2.4 Íá õðïëïãéóåß ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò ar = (r + 1) r (r − 1). Óç óõíÝ÷åéá íá õðïëïãéóåß ï Üèñïéóìá 3 · 2 · 1 + 4 · 3 · 2 + : : : + (n + 1) n (n − 1). 2.5 éá äïóìÝíï t, íá õðïëïãéóåß ï Üèñïéóìá
t X 2i 2t − 2i i=0
i
t−i
:
2.6 Íá õðïëïãéóïýí á áèñïßóìáá: (á) (â)
nP −1 k=1 r P
i=0
−1 (n − k )2 nn− k ,
r! . (r −i+1)!(i+1)!
2.7 ¸óù x ìéá õ÷áßá ìåáâëçÞ ðïõP ðáßñíåé éò éìÝò 0; 1; 2; : : : ìå ðéèáíüçá áíßóïé÷á x0 ; x1 ; : : : (xi ≥ 0 êáé xi = 1). ¸óù
x (s) =
∞ X
xk sk
k=0
ç ëåãüìåíç £ãåííÞñéá óõíÜñçóç ðéèáíïÞùí¤. ¸óù y ç õ÷áßá ìåáâëçÞ ðïõ ðáßñíïõìå áí ðñïóèÝóïõìå n áíåîÜñçá äåßãìáá çò x. ¸óù y0 ; y1 ; : : : ïé ðéèáíüçåò ç y íá ðáßñíåé éò éìÝò 0; 1; 2; : : :, áíßóïé÷á. Íá áðïäåßîåå üé ç ãåííÞñéá óõíÜñçóç ðéèáíïÞùí
y (s) =
∞ X
k=0
éóïýáé ìå (X (s))n .
yk sk
2.5.
ÁÓÊÇÓÅÉÓ
33
2.8 Âñåßå ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò a0 ; a1 ; a2 ; : : : üðïõ ar åßíáé ï áñéèìüò ùí ñüðùí íá ó÷çìáßóïõìå óõíäõáóìü (ìå åðáíáëÞøåéò) åðéëÝãïíáò r ãñÜììáá áðü ï áëöÜâçï {0; 1; 2} ìå ïí ðåñéïñéóìü ï ãñÜììá 0 íá åìöáíéóåß Üñéåò öïñÝò. Ìå âÜóç ç ãåííÞñéá óõíÜñçóç, õðïëïãßóå ï ar . 2.9 Äßíåáé ç ãåííÞñéá óõíÜñçóç ãéá çí áêïëïõèßá a0 ; a1 ; a2 ; : : :. Íá âñåèïýí: (á) ç ãåííÞñéá óõíÜñçóç ãéá çí õðáêïëïõèßá ùí üñùí ìå Üñéï äåßêç, äçë. a0 ; a2 ; a4 ; : : :, (â) ç ãåííÞñéá óõíÜñçóç çò õðáêïëïõèßáò a1 ; a4 ; a7 ; : : : (Õðüäåéîç: Áí w = e2i =3 , üå w0 + w1 + w2 = 0). 2.10 Íá âñåèåß ï áñéèìüò ùí äéáìåñßóåùí ïõ 2n ìå üñïõò ùí áèñïéóìÜùí ïõò áñéèìïýò 1,2 êáé 4. 2.11 Íá âñåèåß ï áñéèìüò ùí ñüðùí ðïõ 2t + 1 ìç äéáêåêñéìÝíá áíéêåßìåíá ìðïñïýí íá ïðïèåçèïýí óå 3 äéáêåêñéìÝíá êïõéÜ, Ýóé þóå êÜèå êïõß íá ìçí ðåñéÝ÷åé ðåñéóóüåñá áðü t áíéêåßìåíá. 2.12 ¸÷ïõìå 2 åßäç áíéêåéìÝíùí. Ôï åßäïò 1 Ý÷åé p ìç äéáêåêñéìÝíá áíéêåßìåíá êáé ï åßäïò 2 Ý÷åé q ìç äéáêåêñéìÝíá áíéêåßìåíá. ÊáÜ ðüóïõò ñüðïõò ìðïñïýìå íá ó÷çìáßóïõìå óõíäõáóìü åðéëÝãïíáò r áíéêåßìåíá; 2.13 Íá âñåèåß ï åêèåéêüò áðáñéèìçÞò ãéá ïí áñéèìü ùí ñüðùí ðïõ ìðïñïýìå íá äéáëÝîïõìå r Þ ëéãüåñá áíéêåßìåíá áðü r äéáêåêñéìÝíá áíéêåßìåíá êáé íá á êááíåßìïõìå óå n äéáêåêñéìÝíåò õðïäï÷Ýò, ìå á áíéêåßìåíá ìÝóá óå êÜèå õðïäï÷Þ áîéíïìçìÝíá. 2.14 Íá õðïëïãéóèåß ï áñéèìüò ùí ñüðùí ðïõ ìðïñïýìå íá ìåáñÝøïõìå óå øéëÜ íüìéóìá ïõ åíüò åõñþ.
34
ÊÅÖÁËÁÉÏ 2.
ÅÍÍÇÔÑÉÅÓ ÓÕÍÁÑÔÇÓÅÉÓ
ÊåöÜëáéï 3 Ó÷Ýóåéò ÁíáäñïìÞò 3.1
ÅéóáãùãÞ
ýñù óá 1200 ì. ×. ï Leonardo da Pisa, ðéï ãíùóüò óáí Fibona
i, áíáêÜëõøå êáé ìåëÝçóå çí áêïëïõèßá áñéèìþí Fibona
i. Ï Fibona
i ðáñïõóßáæå áõÞí çí áêïëïõèßá áñéèìþí ëÝãïíáò çí ðéï êÜù éóïñßá: £Óå Ýíá íçóß õðÜñ÷åé áñ÷éêÜ Ýíá æåõãÜñé áðü êïõíÝëéá. ÊÜèå æåýãïò êïõíåëéþí Ý÷åé ç äõíáüçá ìåÜ áðü Ýíá ìÞíá æùÞò íá áíáðáñÜãåé Ýíá Üëëï æåýãïò áðü êïõíÝëéá ìÝóá óå Ýíá ìÞíá. Áõü ìáò ëÝåé üé ï êïõíÝëé ãéá íá ãåííÞóåé ðñÝðåé íá åíçëéêéùèåß, äçëáäÞ íá ãßíåé åíüò ìçíüò.
åííÞóåéò óõìâáßíïõí êÜèå ìÞíá.
Ôá êïõíÝëéá
. Áò ðñïóðáèÞóïõìå íá äþóïõìå ìéá ëýóç óï ðñüâëçìá ïõ õðïëïãéóìïý ïõ áñéèìïý ùí êïõíåëéþí ìåÜ áðü Ýíá äåäïìÝíï äéÜóçìá. Áò åßíáé an ï áñéèìüò ùí æåõãáñéþí ùí êïõíåëéþí ìåÜ áðü n ìÞíåò. Áò åßíáé Nn á íåïãåííçèÝíá æåõãÜñéá (äçëáäÞ áõÜ ðïõ ãåííÞèçêáí óï ìÞíá n) êáé On á ðáëéÜ æåõãÜñéá (äçëáäÞ áõÜ ðïõ ãåííÞèçêáí óïõò ìÞíåò 1; : : : ; n −1). ÅðïìÝíùò åßíáé ðïÝ äåí ðåèáßíïõí êáé ðïÝ äåí óáìáÜíå íá áíáðáñÜãïõí¤
an = Nn + On
Ïé êáíüíåò çò éóïñßáò ìáò ëÝíå üé ïí åðüìåíï ìÞíá èá óõìâïýí á åîÞò ãåãïíüá: On+1 = On + Nn = an - á ðáëéÜ æåõãÜñéá ç ÷ñïíéêÞ óéãìÞ (n + 1) Ý÷ïõí áõîçèåß ìå áõÜ ðïõ ãåííÞèçêáí ç ÷ñïíéêÞ óéãìÞ n. Nn+1 = On - êÜèå ðáëéü æåõãÜñé óç ÷ñïíéêÞ óéãìÞ n ðáñÜãåé Ýíá íåïãÝííçï æåõãÜñé ç ÷ñïíéêÞ óéãìÞ n + 1. ÊáÜ ç äéÜñêåéá ïõ åðüìåíïõ ìÞíá Ý÷ïõìå:
On+2 Nn+2
= =
On+1 + Nn+1 = an+1 On+1
ÓõíäõÜæïíáò éò ðéï ðÜíù åîéóþóåéò Ý÷ïõìå
an+2 = On+2 + Nn+2 = (On+1 + Nn+1 ) + (On + Nn ) = an+1 + an Ç ðéï ðÜíù ó÷Ýóç åßíáé ìéá ó÷Ýóç áíáäñïìÞò. Ïé áñ÷éêÝò óõíèÞêåò ÷ñåéÜæïíáé, áëëÜ äåí Ý÷ïõí êáé ìåãÜëç óçìáóßá. éá ïõò áñéèìïýò Fibona
i óõíÞèùò åßíáé a0 = 0; a1 = 1; Þ a0 = a1 = 1. 35
36
ÊÅÖÁËÁÉÏ 3.
Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
Óéò åðüìåíåò ðáñáãñÜöïõò èá äþóïõìå êÜðïéïõò ïñéóìïýò êáé èá ðåñéãñÜøïõìå ñüðïõò ãéá ç ëýóç ó÷Ýóåùí áíáäñïìÞò, äçëáäÞ ãéá çí åýñåóç êëåéóïý ýðïõ ãéá ï ãåíéêü üñï çò áêïëïõèßáò ðïõ ïñßæåáé ìå ç ó÷Ýóç áíáäñïìÞò. 3.2
ñáììéêÝò Ó÷Ýóåéò ÁíáäñïìÞò ìå óáèåñïýò óõíåëåóÝò
Ìéá ó÷Ýóç áíáäñïìÞò ðïõ Ý÷åé çí åîÞò ìïñöÞ
0 an + 1 an−1 + 2 an−2 + : : : + r an−r = f (n)
(3.1)
ìå 0 ; 1 ; : : : ; r óáèåñïýò áñéèìïýò ïíïìÜæåáé ãñáììéêÞ ó÷Ýóç áíáäñïìÞò ìå óáèåñïýò óõíåëåóÝò, r-Üîçò Þ r-âáèìïý. Ïé éìÝò çò áêïëïõèßáò a0 ; a1 ; : : : ; ar−1 ïíïìÜæïíáé áñ÷éêÝò óõíèÞêåò çò ó÷Ýóçò áíáäñïìÞò. Ç an+2 − an+1 − an = 0 åßíáé ìéá Ýïéá ó÷Ýóç áíáäñïìÞò. Ç óõíÜñçóç f (n) ïíïìÜæåáé ïäçãüò óõíÜñçóç. Áí ç f (n) = 0, üå ç ó÷Ýóç áíáäñïìÞò ëÝãåáé ïìïãåíÞò. Óçí ðåñßðùóç ðïõ f (n) 6= 0 ëÝãåáé ìç ïìïãåíÞò. Óç óõíÝ÷åéá èá äþóïõìå äõï ñüðïõò åðßëõóçò ãñáììéêþí ó÷Ýóåùí áíáäñïìÞò ìå óáèåñïýò óõíåëåóÝò. 3.2.1
Ëýóç ìå ç ìÝèïäï çò ÷áñáêçñéóéêÞò åîßóùóçò
Åßíáé åýêïëï íá äéáðéóþóåé êáíåßò üé ç ãåíéêÞ ëýóç ìéáò ãñáììéêÞò ó÷Ýóçò áíáäñïìÞò ìå óáèåñïýò óõíåëåóÝò ìðïñåß íá ãñáöåß óáí Üèñïéóìá äýï ìåñþí: çò ãåíéêÞò ëýóçò çò áíßóïé÷çò ïìïãåíïýò ó÷Ýóçò êáé ìéáò ìåñéêÞò ëýóçò çò äåäïìÝíçò ìç ïìïãåíïýò ó÷Ýóçò. ¢ñá ï ðñüâëçìá çò åýñåóçò çò ãåíéêÞò ëýóçò çò ó÷Ýóçò áíáäñïìÞò áíÜãåáé óï ðñüâëçìá çò åýñåóçò çò ãåíéêÞò ëýóçò çò ïìïãåíïýò êáé ìéáò ìåñéêÞò ëýóçò çò äåäïìÝíçò ìç ïìïãåíïýò. Áò åßíáé a(nh) ç ëýóç çò ãåíéêÞò ïìïãåíïýò êáé a(np) ìéá ìåñéêÞ ëýóç çò ìç ïìïãåíïýò. Åßíáé ) (h)
0 a(nh) + 1 a(nh−1 + : : : + r an−r ) (p)
0 a(np) + 1 a(np−1 + : : : + r an−r
=
0
=
f (n)
ÅðïìÝíùò
0 a(nh) + a(np)
+ 1
) (p) a(nh−1 + an−1
+ : : : + r
a(nh−)r + a(np−) r
= f (n)
(3.2)
ñïöáíþò ç ðëÞñçò ëýóç, an = a(nh) + a(np) , éêáíïðïéåß ç ó÷Ýóç áíáäñïìÞò.
£Ï
óêïðüò èá åßíáé íá îåöýãïõìå áðü ç ó÷Ýóç áíáäñïìÞò êáé íá êááëÞîïõìå óå Ýíá êëåéóü ýðï ðïõ ìáò äßíåé ï
an
óõíáñÞóåé ïõ
n¤.
(Á) Åýñåóç ïìïãåíïýò ëýóçò: ÄïêéìÜæïõìå ìéá ëýóç çò ìïñöÞò a(nh) = Axn , üðïõ x ïíïìÜæåáé ÷áñáêçñéóéêÞ ñßæá êáé Á åßíáé ìéá óáèåñÜ ðïõ èá õðïëïãéóåß áðü éò áñ÷éêÝò óõíèÞêåò. Áíéêáèéóþíáò áõÞ ç ëýóç óç ó÷Ýóç áíáäñïìÞò ðáßñíïõìå
0 Axn + 1 Axn−1 + 2 Axn−2 + : : : + r Axn−r = 0 ⇔
0 xn + 1 xn−1 + 2 xn−2 + : : : + r xn−r = 0
(3.3)
3.2. ÑÁÌÌÉÊÅÓ Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ ÌÅ ÓÔÁÈÅÑÏÕÓ ÓÕÍÔÅËÅÓÔÅÓ
Ç (3.3) ïíïìÜæåáé ÷áñáêçñéóéêÞ åîßóùóç çò ó÷Ýóçò áíáäñïìÞò. ¸óù üé Ý÷åé äéáöïñåéêÝò ðñáãìáéêÝò ñßæåò éò x1 ; x2 ; : : : ; xr . Ôüå áðïäåéêíýåáé üé ç ãåíéêÞ ëýóç çò ïìïãåíïýò åßíáé
a(nh) = A1 xn1 + A2 xn2 + : : : + Ar xnr Ôá A1 ; A2 ; : : : ; Ar èá õðïëïãéóïýí áðü éò áñ÷éêÝò óõíèÞêåò. áñÜäåéãìá 3.1:
Ç ó÷Ýóç áíáäñïìÞò ãéá ïõò áñéèìïýò Fibona
i åßíáé
an+2 = an+1 + an Þ
an = an−1 + an−2 Ëýóç. ¸óù üé ïé áñ÷éêÝò óõíèÞêåò åßíáé a0 = a1 åîßóùóç åßíáé
= 1. Ç ÷áñáêçñéóéêÞ
x2 − x − 1 = 0
ïé ñßæåò åßíáé
x1 Ï áñéèìüò
√ √ 1+ 5 1− 5 = ; x2 = 2 2
√ 1+ 5 Φ= ≈ 1; 16803 2
åßíáé ï ëåãüìåíïò £÷ñõóüò ëüãïò¤. (Áíáëïãßá ìåãåèþí ðïõ Ý÷åé ÷ñçóéìïðïéçèåß áðü çí åðï÷Þ ïõ Öåéäßá óçí êëáóéêÞ Ý÷íç. ËÝãåáé üé åõ÷áñéóåß éò áéóèÞóåéò). Óå áõÞ çí ðåñßðùóç ç ïìïãåíÞò ëýóç åßíáé êáé ç ðëÞñçò ëýóç êáé äßíåáé áðü ïí ýðï:
an = a
(h) n
= A1
√ !n 1+ 5 + A2 2
√ !n 1− 5 2
Ïé äõï óáèåñÝò A1 ; A2 õðïëïãßæïíáé áðü éò áñ÷éêÝò óõíèÞêåò a0 = a1 = 1 éò äõï åîéóþóåéò
a0 = A1 + A2 = 1; a1 êáé
A1
√ 1 1+ 5 = √ ; 2 5
ÅðïìÝíùò,
an
√ √ 1+ 5 1− 5 = A1 + A2 2 2
1 = √ 5
A2
√ 1 1− 5 = −√ 2 5
√ !n+1 1+ 5 1 −√ 2 5
√ !n+1 1− 5 2
èá áíáöåñèïýìå þñá óçí ðåñßðùóç êáÜ çí ïðïßá ìåñéêÝò ñßæåò çò ÷áñáêçñéóéêÞò åîßóùóçò åßíáé ìéãáäéêïß áñéèìïß. ÅðåéäÞ ïé óõíåëåóÝò çò ÷áñáêçñéóéêÞò åîßóùóçò åßíáé ðñáãìáéêïß, áí ç ÷áñáêçñéóéêÞ åîßóùóç Ý÷åé ñßæá Ýíá ìéãáäéêü, üå Ý÷åé êáé ï óõæõãÞ ïõ. Áò åßíáé x1 = a + ib êáé x2 = a − ib ï æåõãÜñé ùí ìéãáäéêþí ñéæþí.
37
38
ÊÅÖÁËÁÉÏ 3.
Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
Ç áíßóïé÷ç ïìïãåíÞò ëýóç åßíáé
A1 (X1 )n + A2 (X2 )n = A1 (a + ib)n + A2 (a − ib)n = B1 pn cos (n#) + B2 pn sin (n#) üðïõ
p=
êáé
a2 + b2
p
# = tan−1 (b=a) ; B1 = (A1 + A2 ) ; B2 = i (A1 − A2 )
Ìáò ìÝíåé ç ðåñßðùóç íá Ý÷ïõìå ðïëëáðëÝò ñßæåò ãéá ç ÷áñáêçñéóéêÞ åîßóùóç. Áò åßíáé X1 k -ðïëëáðëüçáò ñßæá çò ÷áñáêçñéóéêÞò åîßóùóçò. Ôüå áðïäåéêíýåáé üé ç ïìïãåíÞò ëýóç åßíáé
A1 nk−1 + A2 nk−2 + : : : + Ak−2 n2 + Ak−1 n + Ak X1n áñÜäåéãìá 3.2:
Íá ëõèåß ç ó÷Ýóç áíáäñïìÞò 4an − 20an−1 + 17an−2 − 4an−3 = 0
Ëýóç
. Ç ÷áñáêçñéóéêÞ åîßóùóç, åßíáé 4x3 − 20x2 + 17x − 4 = 0
êáé ïé ñßæåò
x1 = x2 = 1=2; x3 = 4
¢ñá ç ïìïãåíÞò ëýóç, ðïõ óå áõÞ çí ðåñßðùóç åßíáé êáé ðëÞñçò ëýóç, åßíáé
a(nh) = (A1 n + A2 ) (1=2)n + A3 4n Ôá A1 ; A2 ; êáé A3 õðïëïãßæïíáé áðü éò áñ÷éêÝò óõíèÞêåò. (Â) Åýñåóç ìéáò ìåñéêÞò ëýóçò: Äåí õðÜñ÷åé ãåíéêüò êáíüíáò. Ìðïñïýìå üìùò íá ðïýìå ðùò ç ìåñéêÞ ëýóç £ìïéÜæåé¤ ìå çí ïäçãü óõíÜñçóç. ÄçëáäÞ, áíÜëïãá ìå ï é åßíáé ç ïäçãüò óõíÜñçóç äïêéìÜæïõìå êáé ìéá ìåñéêÞ ëýóç. Ï ðéï êÜù ðßíáêáò äßíåé ìåñéêÜ ðáñáäåßãìáá ÌïñöÞ f (n) k, óáèåñÜ ðïëõþíõìï kn ; k; óáèåñÝò
ÌïñöÞ ìåñéêÞò ëýóçò C , óáèåñÜ ðïëõþíõìï ßäéïõ âáèìïý áëëÜ ðëÞñåò
n ; ; óáèåñÝò
Ïé óáèåñÝò çò ìåñéêÞò ëýóçò õðïëïãßæïíáé áíéêáèéóþíáò çí õðïøÞöéá ëýóç óçí ìç ïìïãåíÞ ó÷Ýóç áíáäñïìÞò. áñÜäåéãìá 3.3:
Íá ëõèåß ç ó÷Ýóç áíáäñïìÞò
6an − 5an−1 + an−2 = 6 (1=5)n
a0 = 0; a1 = 6=5 Ëýóç
.
n = 2; 3; 4; : : :
3.2. ÑÁÌÌÉÊÅÓ Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ ÌÅ ÓÔÁÈÅÑÏÕÓ ÓÕÍÔÅËÅÓÔÅÓ
(á)
ÏìïãåíÞò ëýóç
×áñáêçñéóéêÞ åîßóùóç, 6x2 − 5x + 1 = 0 ïé ñßæåò åßíáé, x1 = 1=2; x2 = 1=3 ¢ñá ç ïìïãåíÞò ëýóç åßíáé
a(nh) = A1 (1=2)n + A2 (1=3)n (â)
ÌåñéêÞ ëýóç
Ç ìïñöÞ çò ïäçãïý óõíÜñçóçò f (n), ìáò åðéâÜëëåé íá äïêéìÜóïõìå ìéá ìåñéêÞ ëýóç çò ìïñöÞò a(np) =  (1=5)n . ÄçëáäÞ + B (1=5) 6B (1=5) − 5B (1=5) (6=25) B − B + B = 6=25 ⇒ B = 1 n
n−1
n−2
= 6 (1=5) ⇒ n
¢ñá ç ðëÞñçò ëýóç åßíáé
an = a(np) + a(nh) = A1 (1=2)n + A2 (1=3)n + (1=5)n Áðü éò áñ÷éêÝò óõíèÞêåò Ý÷ïõìå
a0
=
a1
=
0 0 0 1 1 1 + A2 + =0 2 3 5 1 1 1 1 1 1 6 A1 + A2 + = 2 3 5 5 A1 = 8 êáé A2 = −9
A1
A1 + A2 = −1 A1 2
+
A2 3
=1
¢ñá ç ðëÞñçò ëýóç åßíáé
an = (1=2)n−2 − (1=3)n−2 + (1=5)n ; n = 0; 1; 2; 3; : : : 3.2.2
Ëýóç ìå ç ìÝèïäï ùí ãåííçñéþí óõíáñÞóåùí
Áò åßíáé A(x) ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò (a0 ; a1 ; a2 ; : : : ; an ; : : :)
äçëáäÞ
A (x) =
∞ X
aL xL
L=0
¸óù üé Ý÷ïõìå çí åîÞò ó÷Ýóç áíáäñïìÞò
0 an + 1 an−1 + : : : + r an−r = f (n)
(3.4)
ç ïðïßá Ý÷åé öõóéêÞ óçìáóßá êáé éó÷ýåé ìüíï ãéá åêåßíá á n á ïðïßá åßíáé ìåãáëýåñá Þ ßóá áðü êÜðïéï áêÝñáéï k . Åíäéáöåñüìáóå íá ðñïóäéïñßóïõìå éò éìÝò åêåßíùí ùí an ãéá á ïðïßá n > k − r êáé áõü ãéáß ìüíï áõÜ á an ó÷åßæïíáé ìå ç ó÷Ýóç áíáäñïìÞò. Áðü áõÜ á an á ak−r ; ak−r+1 ; : : : ; ak−1 åßíáé ïé áñ÷éêÝò óõíèÞêåò ïõ ðñïâëÞìáïò.
39
40
ÊÅÖÁËÁÉÏ 3.
Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
Áðü çí (3.4), ðïëëáðëáóéÜæïíáò ìå xn êáé áèñïßæïíáò Ý÷ïõìå ∞ X
( 0 an + 1 an−1 + : : : + r an−r ) xn =
n=k
∞ X
f (n) xn
(3.5)
n=k
Áðü çí éäéüçá çò ïëßóèçóçò ùí ãåííçñéþí óõíáñÞóåùí Ý÷ïõìå ∞ X
0 an xn
=
0 A (x) − a0 − a1 x − a2 x2 − : : : − ak−1 xk−1
1 an−1 xn
=
1 x A (x) − a0 − a1 x − a2 x2 − : : : − ak−2 xk−2 :::
r an−r xn
=
r xr A (x) − a0 − a1 x − a2 x2 − : : : − ak−r−1 xk−r−1
n=k ∞ X
n= k ∞ X
n= k
Ëýíïíáò çí (3.5) ùò ðñïò A(x) êáé êÜíïíáò éò áíéêááóÜóåéò Ý÷ïõìå üé
A (x) = a0 + a1 x + : : : + ak−r−1 xk−r−1 1 +
0 + 1 x + : : : + r xr + 1
áñÜäåéãìá 3.4:
óõíáñÞóåùí. . ¸÷ïõìå
∞ P
Íá ëõèåß ï áñÜäåéãìá 3.3 ìå ç ìÝèïäï ùí ãåííçñéþí
Ëýóç
ÅðïìÝíùò ∞ X
n=2
6an − 5an−1 + an−2 = 6 (1=5)
6an xn −
∞ X
5an−1 xn +
n=2
∞ X
n=2
n
; a0 = 0; a1 = 6=5
an−2 xn =
∞ X
6 (1=5)
n=2
6 [A (x) − a0 − a1 x] − 5x [A (x) − a0 ] + x2 A (x) =
A (x) = (1=5) A (x) =
n
xn
6 (1=5) x2 ⇒ 1 − (1=5) x
x (6 − x) [1 − (1=3) x] [1 − (1=2) x] [1 − (1=5) x]
2
⇒
−9 8 1 + + ⇒ 1 − (1=3) x 1 − (1=2) x 1 − (1=5) x
an = (1=2)n−2 − (1=3)n−2 + (1=5)n ; n = 0; 1; 2; : : : áñÜäåéãìá 3.5:
ìåáîý ïõò
Äßíïíáé ïé 2 ðáñáêÜù ó÷Ýóåéò áíáäñïìÞò ðïõ ó÷åßæïíáé
ìå
f (n) xn + 0 ak−r xk−r + : : : + ak−1 xk−1 n=k ak−r xk−r+1 + : : : + ak−2 xk−1 + : : : + r−1 ak−r xk−1
ar = 3ar−1 + 2br−1 br = ar−1 + br−1 a0 = 1; b0 = 0
3.2. ÑÁÌÌÉÊÅÓ Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ ÌÅ ÓÔÁÈÅÑÏÕÓ ÓÕÍÔÅËÅÓÔÅÓ
. Èá âñïýìå êëåéóü ýðï ãéá á ar ; br ìå ç âïÞèåéá ùí ãåííçñéþí óõíáñÞóåùí. Áðü éò ðáñáðÜíù ó÷Ýóåéò Ý÷ïõìå Ëýóç
∞ X
ar xr =
r =1
∞ X
3ar−1 xr +
r =1
br xr =
r =1
ìå
∞ X
A (x) =
∞ X
2br−1 xr
r =1
ar−1 xr +
r =1
∞ X
∞ X
∞ X
br−1 xr
r =1 ∞ X
ar xr ; B (x) =
r =0
br xr
r =0
Ý÷ïõìå áðü éò éäéüçåò ùí ãåííçñéþí óõíáñÞóåùí
A (x) − 1 = 3xA (x) + 2xB (x) B (x) = xA (x) + xB (x) Ëýíïíáò ùò ðñïò A(x); B (x) âñßóêïõìå üé √ √ 3 + 3 =6 3 − 3 =6 1−x √ + √ A (x) = = 1 − 4x + x2 1− 2+ 3 x 1− 2− 3 x
êáé óç óõíÝ÷åéá ìå ìåñéêÞ êëáóìáéêÞ áíÜëõóç
an
=
bn
=
√ √ √ n 3 − 3 √ n 3+ 3 2+ 3 + 2− 3 √ 6 √ 6 √ n √ n 3 3 2+ 3 − 2− 3 6 6
ïëëÝò öïñÝò åßíáé ÷ñÞóéìï íá åöáñìüóïõìå êÜðïéáò ìïñöÞò ìåáó÷çìáéóìü óçí áêïëïõèßá, ãéá íá çí åìöáíßóïõìå óå ìéá ðéï êáÜëëçëç ìïñöÞ. Áò äïýìå Ýíá Ýïéï ðáñÜäåéãìá. áñÜäåéãìá 3.6:
Íá ëõèåß ç ó÷Ýóç áíáäñïìÞò
an = 3a2n−1; n ≥ 1; a0 = 1 Ëýóç. ÁõÞ ç ó÷Ýóç áíáäñïìÞò äåí ìðïñåß íá ëõèåß ìå êáìéÜ áðü éò ìåèüäïõò ðïõ Ý÷ïõìå óõæçÞóåé ìÝ÷ñé þñá. Áí üìùò èåùñÞóïõìå ìéá íÝá áêïëïõèßá bn çò ìïñöÞò bn = log an (üðïõ log äçëþíåé ëïãÜñéèìï ìå âÜóç ï 2). Ôüå ç ó÷Ýóç áíáäñïìÞò ìðïñåß íá îáíáãñáöåß ùò åîÞò
bn = 2bn−1 + log 3; b0 = 0 ÁõÞ ç ó÷Ýóç áíáäñïìÞò ìðïñåß íá ëõèåß åýêïëá ìå éò ìåèüäïõò ðïõ Ý÷ïõìå óõæçÞóåé. Áí ç ëýóïõìå âñßóêïõìå üé n −1) log 3
bn = (2n − 1) log 3 Þ an = 2(2
n −1
= 32
41
42 3.3
ÊÅÖÁËÁÉÏ 3.
Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
Ìç ãñáììéêÝò Ó÷Ýóåéò ÁíáäñïìÞò
Ïé ó÷Ýóåéò áíáäñïìÞò ïé ïðïßåò äåí åßíáé ãñáììéêÝò êáé Ý÷ïõí óáèåñïýò óõíåëåóÝò, äåí Ý÷ïõí ãåíéêÝò å÷íéêÝò ëýóçò ðáñüìïéåò ìå áõÝò çò áñáãñÜöïõ 3.2. ÓõíÞèùò êááöåýãïõìå óå åéäéêÝò ìåèüäïõò. ¢ëëïå ðÜëé ãéá åéäéêÝò êáçãïñßåò ìðïñïýìå íá äþóïõìå ãåíéêÞ ëýóç Þ íá ìåëåÞóïõìå çí áóõìðùéêÞ óõìðåñéöïñÜ çò ëýóçò çò ó÷Ýóçò áíáäñïìÞò. ïëëÝò öïñÝò £ìáíåýïõìå¤ ìéá ëýóç êáé ç äïêéìÜæïõìå áí äïõëåýåé. ¢ëëåò öïñÝò ðÜëé êÜíïõìå äéÜöïñïõò ìåáó÷çìáéóìïýò. 3.3.1
Ëýóç çò çëåóêïðéêÞò ó÷Ýóçò áíáäñïìÞò
Ç ãåíéêÞ ìïñöÞ çò çëåóêïðéêÞò ó÷Ýóçò áíáäñïìÞò åßíáé ç åîÞò
T (1) T (n)
= 1 = aT (n=b) + d (n)
(3.6)
Ç óõíÜñçóç d(n) ëÝãåáé ïäçãüò óõíÜñçóç. Óçìåéþíåáé üé ç (3.6) Ý÷åé íüçìá üáí ï n åßíáé áêÝñáéá äýíáìç ïõ b. ÁëëÜ åÜí õðïèÝóïõìå üé ç Ô (n) åßíáé ëåßá (äçëáäÞ Ý÷åé ðáñáãþãïõò êÜèå Üîçò) êáé ðÜñïõìå Ýíá êáëü Üíù üñéï ãéá çí Ô (n), áõÝò ïé éìÝò ïõ n ìáò äßíïõí ðëçñïöïñßá ãéá ï ñõèìü áýîçóçò çò óõíÜñçóçò Ô (n). éá íá ìéëÞóïõìå ãéá ïõò ñõèìïýò ðïõ áõîÜíïõí ïé óõíáñÞóåéò èá ÷ñçóéìïðïéÞóïõìå ï óõìâïëéóìü £êåöáëáßï üìéêñïí¤ (big-oh). éá ðáñÜäåéãìá üáí èá ëÝìå üé ç Ô (n) åßíáé Ï (n2 ), èá åííïïýìå üé õðÜñ÷ïõí èåéêÝò óáèåñÝò êáé n0 Ýïéåò þóå ãéá n ßóï Þ ìåãáëýåñï áðü ï n0 , Ý÷ïõìå üé T (n) ≤ n2 . Áò åßíáé T (n) = (n + 1)2 . áñáçñïýìå üé ç Ô (n) åßíáé Ï (n2 ). ñÜãìáé áñêåß íá ðÜñïõìå n0 = 1 êáé = 4. Áõü óõìâáßíåé ãéáß ãéá n ≥ 1 éó÷ýåé üé 2 (n + 1) ≤ 4n2 . Ìå Üëëá ëüãéá, üáí ëÝìå üé ç Ô (n) åßíáé O (f (n)), áõü óçìáßíåé üé ç f (n) åßíáé Ýíá ðÜíù üñéï óï ñõèìü áýîçóçò çò Ô (n). éá íá ëýóïõìå çí (3.6) êÜíïõìå äéáäï÷éêÝò áíéêááóÜóåéò óï äåîéü ìÝñïò ãéá i = 1; 2 êáé Ý÷ïõìå = =
=
T (n) = aT (n=b) + d (n) h n n i n n a aT 2 + d + d (n) = a2 T 2 + ad + d (n) b h b n b n i n b n n n a2 aT 3 + d 2 + ad + d (n) = a3 T 3 + a2 d 2 + ad + d (n) b b b b b b ::: i−1 n X n ai T i + aj d j b b j =0
ÅÜí þñá õðïèÝóïõìå üé n = bk ìðïñïýìå íá ÷ñçóéìïðïéÞóïõìå ï ãåãïíüò üé n T bk = T (1) = 1 êáé íá ðÜñïõìå, ìå i = k ç ó÷Ýóç
T (n) = ak +
k −1 X
aj d bk−j
j =0
Åßíáé k = logb n, Üñá
T (n) = alogb n +
k −1 X j =0
aj d bk−j
(3.7)
3.3.
43
ÌÇ ÑÁÌÌÉÊÅÓ Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
Åßíáé áñêåÜ åíäéáöÝñïí íá äïýìå ïõò äéáöïñåéêïýò ñüëïõò ðïõ ðáßæïõí ïé äýï üñïé óçí (3.7). Ï ðñþïò üñïò, ï alogb n , ïíïìÜæåáé ïìïãåíÞò ëýóç óå áíáëïãßá ìå çí ïñïëïãßá ðïõ ÷ñçóéìïðïéÞóáìå óéò ãñáììéêÝò ó÷Ýóçò áíáäñïìÞò ìå óáèåñïýò óõíåëåóÝò. ñïöáíþò áí ç ïäçãüò óõíÜñçóç d(n) åßíáé 0, üå ç ïìïãåíÞò ëýóç åßíáé ç áêñéâÞò ëýóç ãéá çí çëåóêïðéêÞ ó÷Ýóç áíáäñïìÞò. Ï äåýåñïò üñïò ïíïìÜæåáé ìåñéêÞ ëýóç êáé åßíáé äýóêïëï íá õðïëïãéóåß áêüìá êáé áí îÝñïõìå áêñéâþò çí ïäçãü óõíÜñçóç d(n). ÕðÜñ÷ïõí ëïéðüí ïäçãïß óõíáñÞóåéò d(n) ãéá éò ïðïßåò ìðïñïýìå íá ëýóïõìå çí (3.7) áêñéâþò êáé õðÜñ÷ïõí êáé Üëëåò ãéá éò ïðïßåò ìðïñïýìå íá ðÜñïõìå Ýíá êáëü Üíù üñéï. ËÝìå üé ìéá óõíÜñçóç f ùí áêÝñáéùí åßíáé ðïëëáðëáóéáóéêÞ åÜí f (xy ) = f (x)f (y) ãéá üëïõò ïõò èåéêïýò áêÝñáéïõò x êáé y. Áí ç d(n) åßíáé ðïëëáðëáóéáóéêÞ üå
d bk−j ¢ñá ç ìåñéêÞ ëýóç åßíáé
X
=
k −1 X
= (d (b))
k −j
aj (d (b))k−j
j =0
= (d (b))k
= (d (b))
k
X
a
k
=
k −1 X j =0
a d (b)
k
a d(b) a d(b) k
− (d (b)) a d(b) − 1
j
−1
−1
(3.8)
ÕðÜñ÷ïõí 3 ðåñéðþóåéò ðïõ ðñÝðåé íá ìåëåçèïýí (á) ÅÜí a > d(b), üå ç ó÷Ýóç (3.8) åßíáé O(ak ) Þ O(nlogb a ) áöïý k = logb n. Óå áõÞ çí ðåñßðùóç ç ìåñéêÞ êáé ç ïìïãåíÞò ëýóç åßíáé ßóåò óå Üîç ìåãÝèïõò êáé åîáñþíáé ìüíï áðü á a; b êáé ü÷é áðü çí ïäçãü óõíÜñçóç d(n). T (n) = O ak = O nlogb a (3.9)
(â) ÅÜí a < d(b), üå ç ó÷Ýóç (3.8) åßíáé O d (b)k Þ O nlogb d(b) . Óå áõÞ çí ðåñßðùóç ç ìåñéêÞ ëýóç õðåñâáßíåé óå Üîç ìåãÝèïõò çí ïìïãåíÞ ëýóç. ¢ñá áí èÝëïõìå íá êÜíïõìå âåëéþóåéò ðñÝðåé íá êïéÜîïõìå åêüò áðü á a; b êáé çí ïäçãü óõíÜñçóç d(n). (Óçí åéäéêÞ ðåñßðùóç ðïõ d(n) = na , Ý÷ïõìå d(b) = ba êáé logb (ba ) = a. ¢ñá ç T (n) = O(na ) = O (d (n)). Óå áõÞ çí ðåñßðùóç éó÷ýåé üé
T (n) = O (d (b))k
= O (na )
(3.10)
44
ÊÅÖÁËÁÉÏ 3.
Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
(ã) ÅÜí a = d(b) üå
X
k−1 X
=
aj (d (b))k−j
j =0
=
(d (b))
= =
(d (b))
k
k −1 X j =0
k
n
a d (b)
j
k
logb d(b)
logb n
Áöïý a = d(b), ðáñáçñïýìå üé ç ìåñéêÞ ëýóç åßíáé êáÜ logb n Üîç ìåãÝèïõò öïñÝò ç ïìïãåíÞò ëýóç. ¢ñá ç ìåñéêÞ ëýóç õðåñâáßíåé êáé ðÜëé çí ïìïãåíÞ ëýóç. ËÝìå ëïéðüí üé
T (n) = O nlogb d(b) logb n
áñÜäåéãìá 3.7:
(3.11)
Íá ìåëåçèïýí ïé ðéï êÜù ó÷Ýóåéò áíáäñïìÞò
1. T (n) = 4T (n=2) + n 2. T (n) = 4T (n=2) + n2 3. T (n) = 4T (n=2) + n3 óå üëåò éò ðéï ðÜíù åßíáé Ô (1) = 1. . Óå êÜèå ìéá áðü éò ðéï ðÜíù Ý÷ïõìå ãéá çí ïìïãåíÞ ëýóç a = 4; b = 2 Üñá ç ïìïãåíÞò ëýóç åßíáé n2 . Ëýóç
(1) Åßíáé d(n) = n ⇒ d(b) = d(2) = 2 êáé a = 4 ⇒ d(b) = 2. ¢ñá êáé ç ìåñéêÞ ëýóç åßíáé n2 . ÅðïìÝíùò Ô (n) = Ï (n2 ). (2) Åßíáé d(b) = 4 = a Üñá ç ìåñéêÞ ëýóç êáé åðïìÝíùò êáé ç Ô (n) åßíáé O(n2 log n). (3) Åßíáé d(n) = n3 ⇒ d(b) = d(2) = 8 êáé a < d(b). ÅðïìÝíùò ç ìåñéêÞ ëýóç êáé åðïìÝíùò êáé ç Ô (n) åßíáé O nlogb d(b) = O n3 . 3.3.2
Ëýóç çò ó÷Ýóçò áíáäñïìÞò ðïõ ïñßæåáé ìå óõíÝëéîç
¸óù ç ó÷Ýóç áíáäñïìÞò
an = an−r a0 + an−r−1 a1 + : : : + a0 ar Þ
an =
n −r X
an−r−l al
(3.12)
l=0
ç ïðïßá éó÷ýåé ãéá n ≥ k , üðïõ k êÜðïéïò áêÝñáéïò. ¼ðùò êáé óçí ðáñÜãñáöï (3.2.2) èá äå÷èïýìå üé k ≥ r.
3.3.
ÌÇ ÑÁÌÌÉÊÅÓ Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
45
Åßíáé ðñïöáíÝò üé ç éìÞ ïõ an ãéá n ≥ k ìðïñåß íá õðïëïãéóåß áíáäñïìéêÜ üáí ïé éìÝò ùí a0 ; a1 ; : : : ; ak−1 åßíáé ãíùóÝò. ÁõÝò ïé éìÝò ùí a0 ; a1 ; : : : ; ak−1 åßíáé ïé áñ÷éêÝò óõíèÞêåò. ïëëáðëáóéÜæïíáò êáé á äýï ìÝñç çò (3.12) ìå xn êáé ðáßñíïíáò ï Üèñïéóìá áðü n = k ìÝ÷ñé n = ∞ Ý÷ïõìå ∞ X
an xn =
n=k
∞ X
(an−r a0 + an−r−1 a1 + : : : + a0 an−r ) xn
n= k
Ìå ç âïÞèåéá ùí éäéïÞùí çò óõíÝëéîçò êáé çò ïëßóèçóçò Ý÷ïõìå
A (x) − a0 − a1 x − : : : − ak−1 xk−1 = xr A (x) A (x) − a20 − (a1 a0 + a0 a1 ) x− : : : − (ak−r−1 a0 + ak−r−2 a1 + : : : + a0 ak−r−1 ) xk−r−1 (3.13)
Ç (3.13) åßíáé ìéá áëãåâñéêÞ åîßóùóç 2ïõ âáèìïý ùò ðñïò A(x), ç ïðïßá ìðïñåß íá ëõèåß. Ç A(x) åßíáé ç óõíÞèçò ãåííÞñéá óõíÜñçóç êáé Üñá ìðïñïýìå íá âñïýìå ðïéá áêïëïõèßá Ý÷åé çí A(x) ãåííÞñéá óõíÜñçóç.
Íá âñåèåß ï áñéèìüò ùí ñüðùí ðïõ ìðïñïýìå íá âÜëïõìå ðáñåíèÝóåéò óçí Ýêöñáóç
áñÜäåéãìá 3.8:
1 + 2 + : : : + n−1 + n Ýóé þóå ìüíï 2 üñïé íá ðñïóßèåíáé êÜèå öïñÜ. Ëýóç. Áò åßíáé ai ï áñéèìüò ùí ñüðùí ðïõ ìðïñïýìå íá âÜëïõìå ðáñåíèÝóåéò óå ìéá Ýêöñáóç ìå i üñïõò.
Èåùñïýìå éò 2 õðïåêöñÜóåéò
1 + 2 + : : : + n−r n−r+1 + n−r+2 + : : : + n ¢ñá õðÜñ÷ïõí an−r ñüðïé íá âÜëïõìå ðáñåíèÝóåéò óçí ðñþç Ýêöñáóç êáé ar ñüðïé íá âÜëïõìå ðáñåíèÝóåéò óçí äåýåñç Ýêöñáóç. Áõü óçìáßíåé üé õðÜñ÷ïõí an−r ar ñüðïé íá âÜëïõìå ðáñåíèÝóåéò óå üëç çí Ýêöñáóç. ÄçëáäÞ
an
=
an
=
an−1 a1 + an−2 a2 + : : : + a2 an−2 + a1 an−1 ⇒ n −1 X k=1
ñïöáíþò a1 = 1.
an−k ak ãéá n ≥ 2
ÈÝù a0 = 0 êáé ç ðéï ðÜíù ó÷Ýóç ìðïñåß íá îáíáãñáöåß ùò åîÞò
an
=
an
=
an a0 + an−1 a1 + : : : + a1 an−1 + a0 an ; n ≥ 2 n X
k=0
an−k ak
46
ÊÅÖÁËÁÉÏ 3.
Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
ïëëáðëáóéÜæïíáò ìå xn êáé áèñïßæïíáò áðü n = 2 Ýùò n = ∞ Ý÷ïõìå ∞ X
an xn =
n=2
∞ X
(an a0 + an−1 a1 + : : : + a1 an−1 + a0 an ) xn
n=2
A (x) − a1 x − a0 = [A (x)]2 − a20 − (a1 a0 + a0 a1 ) x ⇒ [A (x)]2 − A (x) + x = 0 ⇒ √ 1 ± 1 − 4x A (x) = 2
Áí êáé õðÜñ÷ïõí äõï ëýóåéò ãéá çí A(x), èá ðÜñïõìå áõÞ ç ëýóç ðïõ ìáò åîáóöáëßæåé ìéá áêïëïõèßá èåéêþí áñéèìþí. Åßíáé ãíùóü (áí ü÷é áðïäåßîå ï) üé ç óõíÜñçóç (1 − 4x)1=2 åßíáé ç ãåííÞñéá óõíÜñçóç çò áêïëïõèßáò
an = − ¢ñá èá åðéëÝîïõìå ç ëýóç
2 2n − 2 n n−1
n = 1; 2; 3; : : :
A (x) = 1=2 − 1=2
√ 1 − 4x
ãéá íá åîáóöáëßóïõìå áêïëïõèßá èåéêþí áñéèìþí. Ç áêïëïõèßá
an =
0
1 2n−2 n n−1
n=0 n = 1; 2; 3; : : : √
Ý÷åé ãåííÞñéá óõíÜñçóç çí A (x) = 1=2 − 1=2 1 − 4x (áò ï áðïäåßîåé ï áíáãíþóçò). Åðåêåßíïíáò çí ðéï ðÜíù ðåñßðùóç ìðïñïýìå íá ëýóïõìå ìéá ìåãáëýåñç êëÜóç ðñïâëçìÜùí. Áò èåùñÞóïõìå þñá çí åîÞò ó÷Ýóç áíáäñïìÞò
bn = an−r b0 + an−r−1b1 + : : : + a0 bn−r Þ
bn =
n −r X
an−r−k bk
k=0
ç ïðïßá éó÷ýåé ãéá n ≥ k , üðïõ k êÜðïéïò áêÝñáéïò, êáé k ≥ r. ïëëáðëáóéÜæïíáò êáé á äýï ìÝñç ìå xn êáé áèñïßæïíáò áðü n = k ìÝ÷ñé n = ∞, Ý÷ïõìå ∞ X
n=k
bn xn =
∞ X
n=k
(an−r b0 + an−r−1 b1 + : : : + a0 bn−r ) xn ⇒
B (x) − b0 − b1 x − : : : − bk−1 xk−1 = = xr [A (x) B (x) − a0 b0 − (a1 b0 + a0 b1 ) x − : : : − (ak−r−1 b0 + ak−r−2 b1 + : : : + a0 bk−r−1 ) xk−r−1
ÅÜí þñá ç A(x) Þ ç B (x) åßíáé ãíùóÞ ìáæß ìå éò êáÜëëçëåò áñ÷éêÝò óõíèÞêåò (êáé áõÝò ãíùóÝò), üå ìðïñïýìå íá õðïëïãßóïõìå åßå çí Á(x) åßå çí  (x).
3.4.
3.4
47
ÁÓÊÇÓÅÉÓ
ÁóêÞóåéò
3.1 Íá ëõèïýí ïé ó÷Ýóåéò áíáäñïìÞò êáé ìå ïõò äýï ñüðïõò (á) (â) (ã) (ä) (å) (ó)
an + an−1 + 1=4an−2 = 0; a0 = 0; a1 = 1 an − 4an−1 + 4an−2 = n + 2; a0 = 6; a1 = 7 an = 2an−1 + 1; a0 = 1 an = 2an−1 + n; a1 = 1 an + 6an−1 + 12an−2 + 8an−3 = 0; a0 = 0; a1 = −2; a2 = 8 an + 2an−1 + an−2 = 2n ; a0 = 1; a1 = 1
3.2 Íá õðïëïãéóïýí ïé ðéï êÜù (n × n) ïñßæïõóåò, ìå ç âïÞèåéá ùí ó÷Ýóåùí áíáäñïìÞò (á)
(â)
(ã)
0 0 0 1
0 0 0 0
::: ::: ::: :::
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0
::: ::: :::
0 0 0
1 1 0 1 0 0
1 1 1
2 1 0 0
1 2 1 0
0 0 1 2
0 0 0 1
0 0 0 0
::: ::: ::: :::
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0
::: ::: :::
0 0 0
1 2 0 1 0 0
1 2 1
1 + 2 0 .. . 0 0
1 1 0 0
1 1 1 0
0 0 0
.. .
.. .
0 1 1 1
0 1 2 1
0 0 1 1
1 + 2
::: ::: :::
0 0
0 0
0 0
1 + 2
0
0 0
::: :::
0 0 0 1 + 2
0 1 1 0 0 0 0
0 1 2 0 0 0 0
0 0 0
1 + 2
48
ÊÅÖÁËÁÉÏ 3.
Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
3.3 Óï ðéï êÜù êýêëùìá íá õðïëïãéóåß ç Üóç V (n). Äßíåáé V (0) = 1. V(n)
V(n-1) 2
V
V(n-2)
V(i)
V(2)
2 1
V(1) 2
1
1
1
V(0) 2
1
1
3.4 ¸óù üé óñßâïõìå Ýíá íüìéóìá n öïñÝò. ÕðÜñ÷ïõí ðñïöáíþò 2n áêïëïõèßåò ðéèáíþí áðïåëåóìÜùí. ïéïò åßíáé ï áñéèìüò ùí áêïëïõèéþí ùí áðïåëåóìÜùí óéò ïðïßåò ðïÝ äåí åìöáíßæåáé £êåöáëÞ¤ óå äéáäï÷éêÜ óñéøßìáá; 3.5 Íá ëõèïýí ïé ó÷Ýóåéò áíáäñïìÞò (á) T (n) = 8T (n=2) + n3 ;
T (1) = 1
(â) T (n) = T (n=2) + 1; (ã) (ä) (å) (ó)
T (1) = 1 T (n) = 2T (n=2) + n; T (1) = 1 T (n) = 3T (n=2) + 2n1:5 ; T (1) = 1 T (n) = 2T (n=2) + n log n; T (1) = 1 T (n) = 2T (n=2) + log n; T (1) = 1
3.6 ¸óù ar íá åßíáé ï áñéèìüò ùí ñüðùí íá åðéëÝîïõìå (ìå åðáíáëÞøåéò) r ãñÜììáá áðü ï áëöÜâçï {0; 1; 2}, ìå ðåñéïñéóìü üé ï ãñÜììá 0 èá åðéëåãåß æõãÝò öïñÝò. Âñåßå ìéá ó÷Ýóç áíáäñïìÞò ãéá ï ðñüâëçìá êáé ëýóå ç (Ýíáò Üëëïò ñüðïò åßíáé íá ÷ñçóéìïðïéÞóåå ãåííÞñéåò óõíáñÞóåéò). 3.7 ¸íáò ðáÝñáò äßíåé óï ãéï ïõ n ÷éëéÜñéêá. Ï ãéïò ìðïñåß íá îïäÝøåé á ëåöÜ ìå ïí åîÞò ñüðï: ÊÜèå ìÝñá ìðïñåß íá êÜíåé ìéá áðü éò áêüëïõèåò áãïñÝò (á) Ýíá âéâëßï (éìÞ: 1000 äñ÷.) (â) 10 äéóêÝåò 51/4 (éìÞ: 2000 äñ÷.) (ã) 1 èÞêç (éìÞ: 1000 äñ÷.) ïéïò åßíáé ï áñéèìüò ùí äõíáþí ñüðùí íá îïäÝøåé á ÷ñÞìáá; Åßíáé åýêïëï íá ëõèåß ï ðñüâëçìá ìå ìéá ó÷Ýóç áíáäñïìÞò 2ïõ âáèìïý. ñïóðáèÞóå üìùò íá âñåßå êáé ìéá ó÷Ýóç áíáäñïìÞò 1ïõ âáèìïý, ç ïðïßá íá ëýíåé ï ðñüâëçìá. 3.8 ïéïò åßíáé ï áñéèìüò ùí ñüðùí íá áíÝâïõìå n óêáëéÜ, åÜí åìåßò êÜèå óéãìÞ áíåâáßíïõìå Ýíá Þ äýï óêáëéÜ;
3.4.
49
ÁÓÊÇÓÅÉÓ
3.9 ¸íá äõáäéêü äÝíñï n êïñõöþí åßíáé åßå Üäåéï áí n = 0 åßå ìéá ñéÜäá (Ti ; r; Tn−i−1 ) üðïõ r åßíáé Ýíáò äéáêåêñéìÝíïò êüìâïò (n ñßæá), Ti åßíáé Ýíá äõáäéêü äÝíñï i êïñõöþí êáé Tn−i−1 åßíáé Ýíá äõáäéêü äÝíñï n − i −1 êïñõöþí (áñéóåñü êáé äåîéü õðïäÝíñï). üóá äõáäéêÜ äÝíñá n êïñõöþí õðÜñ÷ïõí; 3.10 üóåò áêïëïõèßåò ìÞêïõò n ìðïñïýí íá ó÷çìáéóïýí áðü á a; b; ; d ìå Ýïéï ñüðï þóå á a êáé b íá ìçí åßíáé ðïÝ ãåéïíéêÜ; 3.11 Ìå ðüóïõò ñüðïõò an , ìðïñïýìå íá ïðïèåÞóïõìå ðáñåíèÝóåéò óï ãéíüìåíï x1 ; x2 ; x3 ; : : : ; xn âÜæïíáò ðáñÝíèåóç óå êÜèå 2 üñïõò ïõ ãéíïìÝíïõ, Ýóé þóå íá ðïëëáðëáóéÜæïíáé 2 üñïé êÜèå öïñÜ; 3.12 Íá âñåèåß ï áñéèìüò dn ùí ñéãùíéóìþí åíüò êõñïý n-ãþíïõ. Ôñéãùíéóìüò åßíáé Ýíá óýíïëï áðü n − 3 äéáãþíéåò ìå êÜèå äõï áðü áõÝò íá ìçí Ýìíïíáé óï åóùåñéêü ïõ n-ãþíïõ. 3.13 (á) üóåò áêïëïõèßåò n øçößùí áðü á øçößá 0,1,2,3 Ý÷ïõí ìïíü áñéèìü áðü 0; (â) Íá âñåèåß ï áñéèìüò ùí áêïëïõèéþí n øçößùí áðü á 0,1, óéò ïðïßåò ï äåßãìá 010 åìöáíßæåáé óï n øçößï. 3.14 Íá âñåèåß ï áñéèìüò ùí áêïëïõèéþí n øçößùí áðü á 0,1, óéò ïðïßåò ìéá åìöÜíéóç ïõ äåßãìáïò 010 áêïëïõèåßáé áðü çí åìöÜíéóç ïõ äåßãìáïò 110. 3.15 Íá ëõèåß ç ó÷Ýóç áíáäñïìÞò an = 10a2n−1 ;
n ≥ 1; a0 = 1
50
ÊÅÖÁËÁÉÏ 3.
Ó×ÅÓÅÉÓ ÁÍÁÄÑÏÌÇÓ
ÊåöÜëáéï 4 Èåùñßá ÌÝñçóçò Polya 4.1
ÅéóáãùãÞ
Óå áõü ï êåöÜëáéï èá áó÷ïëçèïýìå ìå ìéá åéäéêÞ êáçãïñßá ðñïâëçìÜùí ìÝñçóçò. Óá ðñïâëÞìáá áõÜ, Þ ïõëÜ÷éóïí óéò áðëïýóåñÝò ïõò ìïñöÝò, óü÷ïò åßíáé íá ìåñÞóïõìå á äéáöïñåéêÜ åßäç ìéáò ïñéóìÝíçò êáçãïñßáò äïìþí, üáí üìùò èåùñïýìå ùò éóïäýíáìåò äïìÝò ðïõ åßíáé ãåùìåñéêÜ óõììåñéêÝò. ÔÝïéá ðñïâëÞìáá ðñïóðÜèçóå íá ëýóåé, ìå åðéõ÷ßá, ï G. Polya1 üáí èÝëçóå íá ìåñÞóåé á éóïìåñÞ óå äéÜöïñåò ÷çìéêÝò áíéäñÜóåéò. Èá îåêéíÞóïõìå ìå Ýíá áðëü ðáñÜäåéãìá. Áò õðïèÝóïõìå üé ìáò äßíåáé Ýíá ðëÞñåò äõáäéêü äÝíäñï âÜèïõò 2, üðùò óï Ó÷Þìá 4.1, êáé ìáò æçåßáé íá âñïýìå ìå ðüóïõò äéáöïñåéêïýò ñüðïõò ìðïñïýìå íá ÷ñùìáßóïõìå éò êïñõöÝò ïõ ìå äýï ÷ñþìáá: Üóðñï êáé ìáýñï. Ç áðÜíçóç åßíáé åñéììÝíç:
•
@ @ @ @
•
•
@ @ @ @
•
@ @ @ @
•
•
•
Ó÷Þìá 4.1: ëÞñåò äõáäéêü äÝíäñï 27 , äéüé ï äÝíäñï Ý÷åé 7 êïñõöÝò. Áí üìùò èåëÞóïõìå íá ìåñÞóïõìå ïõò
÷ñùìáéóìïýò, üáí èåùñÞóïõìå üé ç áñéóåñÞ êáé ç äåîéÜ êáåýèõíóç (ïõ åðéðÝäïõ óï ïðïßï êåßáé ï äÝíäñï) åßíáé ìç äéáêåêñéìÝíåò, üå á ðñÜãìáá äõóêïëåýïõí áñêåÜ. Êá' áñ÷Þí üìùò áò êÜíïõìå êááíïçü ìå ðáñáäåßãìáá, ÷ùñßò õðéêü ïñéóìü, é åííïïýìå üáí ëÝìå üé ç áñéóåñÞ êáé ç äåîéÜ êáåýèõíóç åßíáé ìç äéáêåêñéìÝíåò. Óï Ó÷Þìá 4.2 äßíïíáé ìåñéêïß ÷ñùìáéóìïß ðïõ üëïé 1 G. Polya - Ïýããñïò Ìáèçìáéêüò ïõ 20ïõ áéþíá.
51
52
ÊÅÖÁËÁÉÏ 4.
ÈÅÙÑÉÁ ÌÅÔÑÇÓÇÓ POLYA
åßíáé éóïäýíáìïé üáí ïé äýï êáåõèýíóåéò ïõ åðéðÝäïõ åßíáé ìç äéáêåêñéìÝíåò, åðïìÝíùò ïé ÷ñùìáéóìïß áõïß èåùñïýíáé áõüóçìïé. Áíßèåá, óï Ó÷Þìá 4.3 äßíïíáé ìåñéêïß ÷ñùìáéóìïß ðïõ áíÜ äýï åßíáé ìç éóïäýíáìïé, Ýóù êáé åÜí ïé äýï êáåõèýíóåéò ïõ åðéðÝäïõ åßíáé ìç äéáêåêñéìÝíåò, åðïìÝíùò ïé ÷ñùìáéóìïß áõïß èåùñïýíáé áíÜ äýï äéáöïñåéêïß. Ìå Üëëá ëüãéá, áõü ðïõ èÝëïõìå
M
M @ @
A @ @
M M
A @ @ A
M
A @ @
A @ @
A M
M @ @ M
M
M @ @
A @ @
M A
A @ @ M
Ó÷Þìá 4.2: Éóïäýíáìïé ÷ñùìáéóìïß M
M
M @ @
M
@ @
M
M A @ @ A
M
A @ @
M
@ @
M
M M @ @
A
M
M @ @
M
@ @
A
Ó÷Þìá 4.3: ÁíÜ äýï ìç éóïäýíáìïé ÷ñùìáéóìïß íá õðïëïãßóïõìå óï óõãêåêñéìÝíï ðáñÜäåéãìá åßíáé ï áñéèìüò ùí êëÜóåùí éóïäõíáìßáò ùí ÷ñùìáéóìþí ùí êïñõöþí ïõ äÝíäñïõ ùò ðñïò ìßá ó÷Ýóç éóïäõíáìßáò ðïõ ðñïêýðåé üáí áõßæïõìå ç äåîéÜ ìå çí áñéóåñÞ êáåýèõíóç óï åðßðåäï. Áò ïðïèåÞóïõìå üìùò ï ðñüâëçìá óå Ýíá ðéï ãåíéêü ðëáßóéï. ¸óù V Ýíá ìç êåíü, ðåðåñáóìÝíï óýíïëï (ð.÷. ï óýíïëï ùí êïñõöþí ïõ ðëÞñïõò äõáäéêïý äÝíäñïõ âÜèïõò 2) êáé C Ýíá ìç êåíü, ðåðåñáóìÝíï óýíïëï ÷ñùìÜùí (óï ðáñÜäåéãìá ìáò C = {M; A}). Ôï óýíïëï C ìðïñåß íá èåùñçèåß êáé ùò áëöÜâçï, ïðüå á óïé÷åßá ïõ ïíïìÜæïíáé ãñÜììáá. Êáëïýìå ÷ñùìáéóìü ìßá ïðïéáäÞðïå óõíÜñçóç f : V → C . ¸óù áêüìç Ýíá óýíïëï G áíéìåáèÝóåùí ïõ V . Áí 1 êáé 2 åßíáé äýï óïé÷åßá ïõ G, üå ìå 1 2 óõìâïëßæïõìå ç óýíèåóç ùí äýï áíéìåáèÝóåùí, äçëáäÞ çí áíéìåÜèåóç ðïõ ïñßæåáé ùò åîÞò:
1 2 (v) = 1 (2 (v)); ∀v ∈ V:
Åðßóçò, ìå 1−1 óõìâïëßæïõìå çí áíßóñïöç çò 1 , äçëáäÞ çí áíéìåÜèåóç ãéá çí ïðïßá éó÷ýåé:
1−1 (v) = v′ ⇔ 1 (v′ ) = v; ∀v ∈ V:
ÔÝëïò ìå e óõìâïëßæïõìå çí áõïéêÞ áíéìåÜèåóç, äçëáäÞ çí áíéìåÜèåóç ãéá çí ïðïßá éó÷ýåé:
e(v) = v; ∀v ∈ V:
ÕðïèÝïõìå óå üëá á åðüìåíá üé ï óýíïëï G ùí áíéìåáèÝóåùí ïõ V áðïåëåß ïìÜäá ùò ðñïò ç óýíèåóç, äçëáäÞ, ðåñéÝ÷åé çí áõïéêÞ áíéìåÜèåóç
A @ @ A
4.1.
53
ÅÉÓÁ Ù Ç
e êáé áí 1 ; 2
∈ G. ÄéáéóèçéêÜ, ï G ÷áñáêçñßæåé éò áõïðïéÞóåéò ðïõ èÝëïõìå íá åéóáãÜãïõìå. Ôá óïé÷åßá ïõ G êáëïýíáé óõììåñßåò. Åßíáé ðñïöáíÝò üé ï óýíïëï üëùí ùí áíéìåáèÝóåùí ïõ V áðïåëåß ïìÜäá. ÓõíÞèùò óá óõãêåêñéìÝíá ðñïâëÞìáá ðïõ áíéìåùðßæïõìå ï óýíïëï G åßíáé ìßá ðïëý ìéêñüåñç óå ðëÞèïò õðïïìÜäá çò ïìÜäáò üëùí ùí áíéìåáèÝóåùí. Óï ðáñÜäåéãìá ìå ï ðëÞñåò äõáäéêü äÝíäñï âÜèïõò 2, áí ∈
G, üå 1 2
G êáé åðßóçò 1−1
∈
v1 @ @ @ @
v2 @ @
v3 @ @ @ @
@ @
v4
v5
v6
v7
Ó÷Þìá 4.4: Áñßèìçóç ùí êïñõöþí êáÜ âÜèïò
V
= {v1 ; v2 ; : : : ; v7 } åßíáé ïé êïñõöÝò áñéèìçìÝíåò üðùò óï Ó÷Þìá 4.4, üå ç G åßíáé ç åëÜ÷éóç (ùò ðñïò ç ó÷Ýóç ïõ ðåñéÝ÷åóèáé óå óýíïëá) ïìÜäá áíéìåáèÝóåùí ðïõ ðåñéÝ÷åé éò áêüëïõèåò áíéìåáèÝóåéò (âë. áñÜäåéãìá 4.1):
v1 v1 2 = vv1 1
1 =
v2 v3 v2 v2
v3 v2 v3 v3
v4 v6 v4 v5
v5 v7 v5 v4
v6 v4 v6 v6
v7 v5 v7 v7
; :
Óéò ðáñáðÜíù éóüçåò, êÜù áðü êÜèå êïñõöÞ ãñÜöåáé ç åéêüíá çò ùò ðñïò çí áíéìåÜèåóç. Ç åëÜ÷éóç (ùò ðñïò ç ó÷Ýóç ïõ ðåñéÝ÷åóèáé) ïìÜäá áíéìåáèÝóåùí ðïõ ðåñéÝ÷åé êÜðïéåò äåäïìÝíåò áíéìåáèÝóåéò ïíïìÜæåáé ïìÜäá ðïõ ðáñÜãåáé áðü éò äåäïìÝíåò áíéìåáèÝóåéò. ñïêýðåé áí óõíäõÜóïõìå åðáíáëçðéêÜ ìÝóù çò äéìåñïýò ðñÜîçò çò óýíèåóçò éò äåäïìÝíåò áíéìåáèÝóåéò êáé éò áíßóñïöÝò ïõò êáÜ üëïõò ïõò äõíáïýò ñüðïõò. Áí þñá f åßíáé Ýíáò ÷ñùìáéóìüò êáé ∈ G, üå (f ) åßíáé Ýíáò íÝïò ÷ñùìáéóìüò ðïõ ïñßæåáé áðü ïí ýðï:
(f ) (v) = f ( (v)) ; ∀v ∈ V:
(4.1)
f ≡G g ⇔ (∃ ∈ G) ( (f ) = g)
(4.2)
ÄéáéóèçéêÜ, (v ) åßíáé ç êïñõöÞ ðïõ áíéêáèéóÜ çí v üáí ç óõììåñßá óï V . ËÝìå üé ç êïñõöÞ (v ) åßíáé ç óõììåñéêÞ çò v . Åðßóçò (f ) åßíáé ï ÷ñùìáéóìüò ðïõ ðñïêýðåé üáí üëåò ïé êïñõöÝò áíéêááóáèïýí áðü éò óõììåñéêÝò ïõò. ¸óù þñá × Ýíá óýíïëï ÷ñùìáéóìþí ðïõ åßíáé êëåéóü ùò ðñïò éò äñÜóåéò ùí óïé÷åßùí ïõ G, äçëáäÞ áí f ∈ × êáé ∈ G, üå (f ) ∈ × . ÅéóÜãïõìå óï × çí áêüëïõèç ó÷Ýóç éóïäõíáìßáò: äñÜóåé
Åßíáé åýêïëï íá áðïäåé÷èåß üé ðñüêåéáé ðñÜãìáé ãéá ó÷Ýóç éóïäõíáìßáò. ¸óù þñá X=G ï óýíïëï ùí êëÜóåùí éóïäõíáìßáò ïõ × ùò ðñïò çí ≡G . To
54
ÊÅÖÁËÁÉÏ 4.
ÈÅÙÑÉÁ ÌÅÔÑÇÓÇÓ POLYA
ãåíéêü ðñüâëçìá ðïõ èá åðéëýóïõìå åßíáé íá âñåèåß ï ðëçèÜñéèìïò ïõ X=G, äçëáäÞ ï áñéèìüò ùí ìç éóïäýíáìùí ÷ñùìáéóìþí ùò ðñïò çí éóïäõíáìßá ðïõ êáèïñßæåáé áðü ç äñÜóç çò ïìÜäáò G ðÜíù óï × . 4.2
Éäéüçåò ÁíéìåáèÝóåùí
Ç ðáñÜãñáöïò áõÞ áðïåëåß ìßá ðáñÝíèåóç ãéá íá áíáðýîïõìå ïñéóìÝíåò ÷ñÞóéìåò éäéüçåò ùí áíéìåáèÝóåùí. Èá åñãáóèïýìå ìå Ýíá óõãêåêñéìÝíï ðáñÜäåéãìá: ¸óù üé Ý÷ïõìå ï óýíïëï V ìå ïêþ óïé÷åßá {v1 ; v2 ; : : : ; v7 ; v8 } êáé çí áíéìåÜèåóç ïõ :
1 =
v1 v2 v3 v4 v5 v6 v7 v8 v4 v3 v2 v6 v5 v7 v1 v8
:
Áò ó÷çìáßóïõìå ìßá áêïëïõèßá îåêéíþíáò áðü ï ðñþï óïé÷åßï v1 ïõ V êáé ãñÜöïíáò óç óõíÝ÷åéá äéáäï÷éêÜ éò åéêüíåò (v ); ( (v )); : : : Ýùò üïõ îáíáðÜñïõìå ï óïé÷åßï áðü üðïõ îåêéíÞóáìå, óï óõãêåêñéìÝíï ðáñÜäåéãìá ï v1 . Ç áêïëïõèßá ðïõ ðñïêýðåé, ÷ùñßò íá îáíáãñÜøïõìå ï v1 , åßíáé ç (v1 ; v4 ; v6 ; v7 ). Ç áêïëïõèßá áõÞ ìðïñåß íá èåùñçèåß ùò ç áíéìåÜèåóç:
′
=
v1 v4 v6 v7 v4 v6 v7 v1
ìå ðåäßï ïñéóìïý ï óýíïëï {v1 ; v4 ; v6 ; v7 }. ÁíéìåáèÝóåéò üðùò ç ′ , ãéá éò ïðïßåò ç áêïëïõèßá (v; ′ (v ); ′ ( ′ (v )); : : :) êáëýðåé üëï ï ðåäßï ïñéóìïý ïõò ãéá ïðïéïäÞðïå óïé÷åßï v êáëïýíáé êõêëéêÝò áíéìåáèÝóåéò Þ áðëþò êýêëïé. ÅðéóñÝöïõìå þñá óçí áñ÷éêÞ áíéìåÜèåóç êáé áò èåùñÞóïõìå ï ðñþï óïé÷åßï ïõ V ðïõ äåí êáëýöèçêå áðü ïõò üñïõò çò áêïëïõèßáò (v1 ; v4 ; v6 ; v7 ), äçëáäÞ ï v2 . Áò ó÷çìáßóïõìå ìå ïí ßäéï üðùò ðñïçãïõìÝíùò ñüðï çí áêïëïõèßá (v2 ; v3 ). ÅðáíáëáìâÜíïíáò á ßäéá ãéá Üëëåò äýï öïñÝò ðáßñíïõìå éò äýï áêïëïõèßåò (v5 ) êáé (v8 ), ðïõ Ý÷ïõí áðü Ýíá üñï ç êÜèå ìßá. Ïé áêïëïõèßåò áõÝò áíéóïé÷ïýí åðßóçò óå êõêëéêÝò áíéìåáèÝóåéò. Ìå çí ðáñáðÜíù äéáäéêáóßá ëÝìå üé áíáëýóáìå çí áñ÷éêÞ áíéìåÜèåóç óå ãéíüìåíï êõêëéêþí áíéìåáèÝóåùí îÝíùí ìåáîý ïõò êáé ãñÜöïõìå:
= (v1 ; v4 ; v6 ; v7 )(v2 ; v3 )(v5 )(v8 ): Ïé êõêëéêÝò áíéìåáèÝóåéò óï äåîß ìÝëïò ïõ ðáñáðÜíù ýðïõ ÷áñáêçñßæïíáé ùò îÝíåò ìåáîý ïõò äéüé á ðåäßá ïñéóìïý ïõò åßíáé îÝíá óýíïëá áíÜ äýï. Åßíáé ðñïöáíÝò üé ìå çí ðáñáðÜíù äéáäéêáóßá ïðïéáäÞðïå áíéìåÜèåóç ìðïñåß íá áíáëõèåß óå ãéíüìåíï îÝíùí ìåáîý ïõò êýêëùí. Ìðïñåß íá áðïäåé÷èåß üé ìéá Ýïéá áíÜëõóç ìðïñåß íá ãßíåé êáÜ ìïíáäéêü ñüðï. 4.3
Ôýðïò ïõ Burnside
Óçí ðáñÜãñáöï áõÞ èá äþóïõìå êáé èá áðïäåßîïõìå Ýíáí ýðï ãéá ïí ðëçèÜñéèìï ïõ óõíüëïõ X=G. Ï ýðïò üìùò áõüò, ãíùóüò óáí ýðïò ïõ Burnside, äåí åßíáé ðÜíïå åýêïëï íá åöáñìïóèåß óçí ðñÜîç. é' áõü óçí åðüìåíç ðáñÜãñáöï èá ðáñïõóéÜóïõìå ìßá óõíÝðåéá ïõ ýðïõ ïõ Burnside, ãíùóÞ ùò Èåþñçìá ïõ Polya, ðïõ èá åðéñÝøåé íá õðïëïãßæïõìå ï |X=G| ðéï åýêïëá.
4.3.
55
ÔÕÏÓ ÔÏÕ BURNSIDE
Êá' áñ÷Þí ìåñéêïß ïñéóìïß êáé óõìâïëéóìïß. ¸óù f ∈ X Ýíáò ÷ñùìáéóìüò êáé ∈ G ìßá óõììåñßá. Ï ÷ñùìáéóìüò f êáëåßáé áíáëëïßùïò ùò ðñïò çí áí (f ) = f . Ìå É () óõìâïëßæïõìå ï áêüëïõèï óýíïëï:
I () = {f ∈ X | (f ) = f }
(4.3)
J (f ) = { ∈ G| (f ) = f } :
(4.4)
êáé ìå J (f ) ï óýíïëï Åðßóçò [f ] óõìâïëßæåé çí êëÜóç éóïäõíáìßáò çò f ùò ðñïò ≡G . Ï ýðïò ïõ Burnside åßíáé ï áêüëïõèïò: 1 X |I ( )|: |G|
|X=G| =
(4.5)
∈G
Èá äþóïõìå þñá óçí áðüäåéîç ïõ ðáñáðÜíù ýðïõ. Óçí áñ÷Þ èá áðïäåßîïõìå üé: X X |I ( )| = |J (f )|: (4.6) ∈G
f ∈X
éá çí áðüäåéîç çò (4.6) êááóêåõÜæïõìå Ýíáí ðßíáêá Á = (af ); f ∈ X; ∈ G ðïõ ïé ãñáììÝò ïõ áíéóïé÷ïýí óå ÷ñùìáéóìïýò ïõ × êáé ïé óÞëåò ïõ óå óõììåñßåò ïõ G êáé üðïõ
af =
1 áí 0 áí
(f ) = f; (f ) 6= f:
áñáçñïýìå þñá üé êáé á äýï ìÝëç çò (4.6) ìáò äßíïõí ï Üèñïéóìá üëùí ùí óïé÷åßùí ïõ Á. ñÜãìáé, ï áñéóåñü ìÝëïò çò (4.6) ðñïêýðåé áí áèñïßóïõìå á óïé÷åßá êÜèå óÞëçò ïõ A êáé óç óõíÝ÷åéá áèñïßóïõìå á ìåñéêÜ áèñïßóìáá ùí óçëþí (Üèñïéóç êáÜ óÞëåò), åíþ ï äåîéü ìÝëïò çò (4.6) ðñïêýðåé áí áèñïßóïõìå á óïé÷åßá êÜèå ãñáììÞò ïõ A êáé óç óõíÝ÷åéá áèñïßóïõìå á ìåñéêÜ áèñïßóìáá ùí ãñáììþí (Üèñïéóç êáÜ ãñáììÝò). Áõü áðïäåéêíýåé çí (4.6). Óç óõíÝ÷åéá ðáñáçñïýìå üé X
f ∈X
|J (f )| =
X
X
[f ]∈X=G g ∈[f ]
|J (g )|:
(4.7)
Ç ó÷Ýóç (4.7) ðñïêýðåé áðëþò ïìáäïðïéþíáò ï Üèñïéóìá ïõ áñéóåñïý çò ìÝëïõò. Áí þñá f; g ∈ × , ïñßæïõìå
E (f; g) = { ∈ G| (f ) = g} : Éó÷õñéæüìáóå üé áí f ≡G g üå |J (g )| = |E (f; g )|. ñÜãìáé Ýóù 0 ∈ E (f; g). (ÕðÜñ÷åé Ýïéá 0 , äéüé f ≡G g). Ç áðåéêüíéóç → 0 , üðùò ìðïñåß åýêïëá íá åëåã÷èåß, áðïåëåß ìßá 1-1 êáé åðß áðåéêüíéóç áðü J (g ) óï E (f; g ). ¢ñá |J (g )| = |E (f; g )|. Áðü çí (4.7) ëïéðüí ðñïêýðåé X
f ∈X
|J (f )| =
X
X
[f ]∈X=G g ∈[f ]
|E (f; g ) |:
(4.8)
56
ÊÅÖÁËÁÉÏ 4.
ÁëëÜ üìùò
G=
[
ÈÅÙÑÉÁ ÌÅÔÑÇÓÇÓ POLYA
E (f; g)
(4.9)
g ∈[f ]
êáé åðéðëÝïí áí g1 6= g2 üå
E (f; g1 ) Áðü éò (4.9) êáé (4.10) Ý÷ïõìå: |G| =
\
E (f; g2 ) = ∅:
(4.10)
|E (f; g ) |:
(4.11)
X
g ∈[f ]
ÔÝëïò áðü éò (4.8) êáé (4.11) ðñïêýðåé üé: X
f ∈X
|J (f )| =
X
[f ]∈X=G
|G| = |X=G| |G| :
(4.12)
Áðü çí åëåõáßá ó÷Ýóç êáé ç ó÷Ýóç (4.7) áðïäåéêíýåáé ï ýðïò Burnside. Ìå ÷ñÞóç ïõ ýðïõ ïõ Burnside íá ëõèåß ï ðñüâëçìá ïõ ÷ñùìáéóìïý ùí êüìâùí åíüò ðëÞñïõò äõáäéêïý äÝíäñïõ âÜèïõò 2 (üáí ç äåîéÜ êáé áñéóåñÞ êáåýèõíóç åßíáé ìç äéáêåêñéìÝíåò). áñÜäåéãìá 4.1:
. Ç ïìÜäá ùí áíéìåáèÝóåùí G ðïõ áíéóïé÷åß óç äéáéóèçéêÞ Ýííïéá çò ìç äéáêñéóçò çò äåîéÜò êáåýèõíóçò áðü çí áñéóåñÞ ðáñÜãåáé áðü éò ðáñáêÜù áíéìåáèÝóåéò: Ëýóç
ÁíéìåáèÝóåéò
ÁíÜëõóç óå êýêëïõò
1
1
@ @
1 :
@ @
2
3
@ @
@ @
4
5
6
7
→
2
@ @
@ @
6
7
1
4
5
@ @
2
3
@ @
@ @ 5
4 1
@ @
2 :
(1)(23)(46)(57)
3
6
7
→ 5
(1)(2)(3)(45)(6)(7)
2
2
@ @
@ @ 4
6
7
ÄçëáäÞ, üáí ïé áíéìåáèÝóåéò 1 ; 2 êáé ïé áíßóñïöÝò ïõò óõíäõáóèïýí åðáíáëçðéêÜ ìå üëïõò ïõò äõíáïýò ñüðïõò, ðáñÜãåáé ç ïìÜäá G. Ï ßíáêáò 4.3 äßíåé óçí åëåõáßá óÞëç ïõ ãéá êÜèå áíéìåÜèåóç ï ðëÞèïò ùí ÷ñùìáéóìþí ðïõ ðáñáìÝíïõí áíáëëïßùïé ùò ðñïò áõÞí. Ôï ðëÞèïò áõü ï õðïëïãßæïõìå ùò åîÞò: Ýóù üé ìßá áíéìåÜèåóç, üðùò ç 1 2 , ç ïðïßá áíáëýåáé óå ãéíüìåíï ñéþí îÝíùí ìåáîý ïõò êýêëùí. Åßíáé öáíåñü üé Ýíáò ÷ñùìáéóìüò f ðáñáìÝíåé áíáëëïßùïò áðü çí áíéìåÜèåóç 1 2 áí êáé ìüíïí áí ïé êïñõöÝò ïõ êÜèå êýêëïõ óçí áíÜëõóç çò 1 2 ðáßñíïõí ï ßäéï ÷ñþìá. Áöïý ç 1 2 Ý÷åé ñåéò êýêëïõò êáé ãéá éò êïñõöÝò ïõ êÜèå åíüò êýêëïõ Ý÷ïõìå äýï åðéëïãÝò åíüò êïéíïý ÷ñþìáïò ãéá íá éò ÷ñùìáßóïõìå Ýóé
4.4.
57
ÈÅÙÑÇÌÁ POLYA
ÁíéìåÜèåóç
ÁíÜëõóç óå êýêëïõò
e áõïéêÞ 1 2 1 2 1 1 2 1 2 1 2 2 1 2 1 2
(1)(2)(3)(4)(5)(6)(7) (1)(23)(46)(57) (1)(2)(3)(45)(6)(7) (1)(2)(3)(4)(5)(67) (1)(2)(3)(45)(67) (1)(23)(4657) (1)(23)(4756) (1)(23)(47)(56)
É(ð) = áñéèìüò ùí ÷ñùìáéóìÝíùí äÝíäñùí ðïõ ðáñáìÝíïõí áíáëëïßùá
27 = 128 24 = 16 26 = 64 26 = 64 25 = 32 23 = 8 23 = 8 4 2P = 16 ∈G |I ( )| = 336
ßíáêáò 4.1: ÏìÜäá G ùí áíéìåáèÝóåùí ðïõ ðáñÜãåáé áðü éò 1 ; 2 . þóå íá ðñïêýøåé ÷ñùìáéóìüò ðïõ ðáñáìÝíåé áíáëëïßùïò ùò ðñïò çí 1 2 , óõìðåñáßíïõìå üé |I (1 2 )| = 23 . Ìå ïí ßäéï ñüðï õðïëïãßæïõìå ï |I ( )| ãéá üëá á ∈ G. Åöáñìüæïíáò þñá ïí ýðï ïõ Burnside ðáßñíïõìå: |X=G| =
4.4
1X |I ( )| = 42: 8 ∈G
Èåþñçìá Polya
Óï êåöÜëáéï 2 åßäáìå ðþò ìðïñïýìå íá ÷ñçóéìïðïéÞóïõìå ãåííÞñéåò óõíáñÞóåéò ìéáò ìåáâëçÞò ãéá íá õðïëïãßóïõìå ïõò üñïõò ìßáò áêïëïõèßáò ak ; k = 1; 2; : : : çò ïðïßáò ïé üñïé äßíïõí ïí ðëçèÜñéèìï ìéáò êëÜóçò óõíäõáóéêþí áíéêåéìÝíùí ðïõ åîáñÜáé áðü ìßá ðáñÜìåñï, çí k . éá íá âñïýìå ï ðëÞèïò êëÜóåùí ðïõ áíáöÝñïíáé óï óýíïëï ÷ñùìáéóìþí ìå r ÷ñþìáá èá ÷ñçóéìïðïéÞóïõìå ãåííÞñéåò óõíáñÞóåéò ìå r ìåáâëçÝò, äçëáäÞ èá åéóáãÜãïõìå üóåò äéáöïñåéêÝò ìåáâëçÝò üóá åßíáé êáé á ÷ñþìáá. Åßíáé âïëéêü íá èåùñÞóïõìå üé ï óýíïëï C ùí ÷ñùìÜùí áõßæåáé ìå óýíïëï {x1 ; : : : ; xr } ùí ìåáâëçþí. ¸íáò öõóéêüò ñüðïò íá ðáñáóÞóïõìå Ýíáí ÷ñùìáéóìü f : V = {v1 ; :::vn } → C åßíáé ï ìïíþíõìï xf (v1 ) xf (v2 ) : : : xf (vr ) . Ôï ìïíþíõìï áõü óõìâïëßæåáé ìå mf . Åßíáé åýêïëï íá äéáðéóùèåß üé Ý÷åé âáèìü n = |V |. ¸óù áêüìç Ì ï óýíïëï üëùí ùí ìïíùíýìùí âáèìïý |V | óéò ìåáâëçÝò {x1 ; : : : ; xr }. Åßíáé åðßóçò åýêïëï íá äéáðéóùèåß üé äýï ÷ñùìáéóìïß ðïõ åßíáé éóïäýíáìïé ùò ðñïò ìßá óõììåñßá , Ý÷ïõí ßóá ìïíþíõìá. ÄçëáäÞ áí (f ) = g üå mf = mg . To áíßóñïöï üìùò äåí éó÷ýåé êá' áíÜãêç. áñéóÜíïõìå ìå am ïí áñéèìü ùí äéáöïñåéêþí êëÜóåùí éóïäõíáìßáò (ùò ðñïò ≡G ) ÷ñùìáéóìþí ðïõ Ý÷ïõí ï ßäéï ìïíþíõìï m ∈ Ì . Åßíáé üå öáíåñü üé X
f ∈X=G
mf
=
X
am m:
(4.13)
m∈M
Áí þñá èÝóïõìå Im ( ) = {f ∈ × | (f ) = f êáé mf = m} üå ìå âÜóç ïí ýðï ïõ Burnside Ý÷ïõìå
am =
1 X |Im ( )|: |G| ∈G
(4.14)
58
ÊÅÖÁËÁÉÏ 4.
ÈÅÙÑÉÁ ÌÅÔÑÇÓÇÓ POLYA
ÅðïìÝíùò áðü ïõò ýðïõò (4.13) êáé (4.14) ðñïêýðåé üé
mf
X
X
=
am m =
m∈M
f ∈X=G
=
X
m∈ M
1 X |Im ( )|m |G| ∈G
1 X X |Im ( )| m: |G|
(4.15)
∈G m∈M
ÁíáäéáÜóóïíáò üìùò áèñïßóìáá ðñïêýðåé üé: X
m∈M
|Im ( )| m =
mf :
X
(4.16)
f ∈I ( )
Áðü (4.15) êáé (4.16) ðñïêýðåé üé
mf
X
f ∈X=G
=
1 X X |G|
mf :
(4.17)
∈ G f ∈ I ( )
Óç óõíÝ÷åéá èá äþóïõìå óï Üèñïéóìá f ∈I () mf ìéá ðéï åý÷ñçóç ìïñöÞ. ¸óù üé áíáëýïíáò çí áíéìåÜèåóç óå ãéíüìåíï îÝíùí ìåáîý ïõò êýêëùí, èá ðñïêýøïõí bi êýêëïé ìÞêïõò i, üðïõ 1 ≤ i ≤ |V | = n. Åßíáé öáíåñü üé áí f ∈ I (), äçëáäÞ áí (f ) = f , üå ï ÷ñùìáéóìüò f ðáßñíåéPçí ßäéá éìÞ óå üëá á óïé÷åßá åíüò êýêëïõ. ÅðïìÝíùò, åðåéäÞ ï Üèñïéóìá f ∈I () mf åßíáé ï Üèñïéóìá ùí ìïíùíýìùí ãéá üëïõò ïõò ÷ñùìáéóìïýò f ∈ I ( ), ðñïêýðåé üé: P
X
mf
= (x1 + : : : + xr )
b1
x21 + : : : + x2r
f ∈I ( )
b2
: : : (xn1 + : : : + xnr )bn : (4.18)
éá íá äþóïõìå þñá ïí åëéêü ýðï, áðïìÝíåé ìüíïí íá äþóïõìå Ýíáí åðéðëÝïí ïñéóìü ðïõ áðëþò áðëïðïéåß ï óõìâïëéóìü. Êáëïýìå äåßêñéá óõíÜñçóç ãéá ç óõììåñßá ∈ G ç óõíÜñçóç
Æ (y1 ; : : : ; yn) = y1b : : : ynbn : 1
Áðü éò ó÷Ýóåéò (4.17) êáé (4.18) Ý÷ïõìå þñá üé X
mf
=
f ∈ I ( )
1 X Æ (x1 + : : : + xr ; : : : ; x1n + : : : + xnr ): |G|
(4.19)
∈G
Ç ó÷Ýóç (4.19) åßíáé ãíùóÞ ùò èåþñçìá ïõ Polya. Áí êáé èá äéáöáíåß êáëýåñá óá ðáñáäåßãìáá, ðáñáçñÞóå üé ï õðïëïãéóìüò ïõ äåîéïý ìÝñïõò ïõ ýðïõ åßíáé ó÷åéêÜ áðëüò, åðåéäÞ ç äåßêñéá óõíÜñçóç ìéáò óõììåñßáò õðïëïãßæåáé åýêïëá. ÈÝïíáò x1 = x2 = : : : = xr = 1 óç ó÷Ýóç (4.19) ðáßñíïõìå çí ðéï êÜù ó÷Ýóç ðïõ ëýíåé ï ðñüâëçìá ðïõ èÝóáìå óçí áñ÷Þ ïõ êåöáëáßïõ. |X=G| = áñÜäåéãìá 4.2:
4.1 .
1 X Æ (|V | ; : : : ; |V |): |G|
(4.20)
∈G
×ñçóéìïðïéþíáò ï èåþñçìá Polya íá ëõèåß ï áñÜäåéãìá
4.4.
59
ÈÅÙÑÇÌÁ POLYA
.
Ëýóç
ÁíéìåÜèåóç
ÊõêëéêÞ ÁíáðáñÜóáóç
e 1 2 1 2 1 1 2 1 2 1 2 2 1 2 1 2
(1)(2)(3)(4)(5)(6)(7) (1)(23)(46)(57) (1)(2)(3)(45)(6)(7) (1)(2)(3)(4)(5)(67) (1)(2)(3)(45)(67) (1)(23)(4657) (1)(23)(4756) (1)(23)(47)(56)
Äåßêñéá ÓõíÜñçóç
y17 y1 y23 y15 y2 y15 y2 y13 y22 y1 y2 y4 y1 y2 y4 y1 y23
Å÷ïõìå ëïéðüí üé
mf
X
=
1 X 1 Æ (y1 ; : : : ; y7 = |G| 8
y17 + 2y1 y23 + 2y15 y2 + 2y1y2 y4 + y13 y22 :
∈G
f ∈X=G
Ôá ÷ñþìáá åßíáé 2: x1 ; x2 , Üñá X
mf
=
1 8
f ∈X=G
h 7 (x1 + x2 ) + 2 (x1 + x2 )
+ 2 (x1 + x2 ) +
x21 + x22 x41 + x42
Áíéêáèéóþ x1 = x2 = 1 êáé ðáßñíù X
f ∈X=G
mf
=
x21 + x22
3
+ 2 (x1 + x2 )
5
+ (x1 + x2 )
3
x21 + x22
x21 + x22
2 i
:
1 7 2 + 2 · 2 · 23 + 2 · 25 · 2 + 2 · 2 · 2 · 2 + 23 · 22 = 42: 8
áñáÞñçóç: Áí ìáò Ýâáæáí óáí ðåñéïñéóìü üé ðñÝðåé íá ÷ñçóéìïðïéÞóïõìå ï ðñþï ÷ñþìá ïõëÜ÷éóïí 4 öïñÝò, üå èá Ýðñåðå íá áíáðýîïõìå o ðáñáðÜíù ðïëõþíõìï ùí x1 ; x2 êáé íá ðñïóèÝóïõìå ïõò óõíåëåóÝò ùí ìïíùíýìùí xi1 x2j ìå i ≥ 4, Þ áëëéþò íá èÝóïõìå x2 = 1 êáé íá âñïýìå ï óõíåëåóÞ ïõ x41 .
60 4.5
ÊÅÖÁËÁÉÏ 4.
ÈÅÙÑÉÁ ÌÅÔÑÇÓÇÓ POLYA
ÁóêÞóåéò
4.1 Íá âñåèåß ï áñéèìüò ùí äéáöïñåéêþí êïëéÝ ðïõ ìðïñïýí íá öéá÷ïýí áðü ðÝíå ÷Üíñåò. Íá ÷ñçóéìïðïéçèïýí á ÷ñþìáá êßñéíï, ìðëå êáé êüêêéíï. 4.2 ÈÝëïõìå íá õðþóïõìå üëïõò ïõò ðåíáøÞöéïõò áñéèìïýò óå öýëëá ÷áñéïý, ìå Ýíáí áñéèìü óå êÜèå öýëëï. üóá öýëëá ÷áñéïý ÷ñåéÜæïíáé; 4.3 Íá âñåèåß ï áñéèìüò ùí ñüðùí ðïõ ìðïñïýìå íá âÜøïõìå éò Ýóóåñéò ðëåõñÝò á,â,ã,ä ìéáò êáíïíéêÞò ñéãùíéêÞò ðõñáìßäáò ÷ñçóéìïðïéþíáò äýï ÷ñþìáá. 4.4 Íá õðïëïãéóèåß êáÜ ðüóïõò ñüðïõò ìðïñïýìå íá ÷ñùìáßóïõìå éò êïñõöÝò åíüò êáíïíéêïý ðåíáãþíïõ ìå ñßá ÷ñþìáá Ýóé þóå íá ÷ñçóéìïðïéÞóïõìå ï ðñþï ÷ñþìá ïõëÜ÷éóïí äýï öïñÝò. 4.5 Íá âñåèåß ï áñéèìüò ùí ñüðùí ãéá íá âÜøïõìå éò ïêþ êïñõöÝò åíüò êýâïõ ÷ñçóéìïðïéþíáò äýï ÷ñþìáá. 4.6 Óï ó÷Þìá Ý÷ïõìå Ýóóåñéò ÷Üíñåò óå ãñáììéêÞ äéÜáîç. Ìðïñïýìå íá
âÜøïõìå çí êÜèå ÷Üíñá ðñÜóéíç Þ êüêêéíç. Ôá äýï Üêñá çò äéÜáîçò äåí îå÷ùñßæïõí ìåáîý ïõò (äçëáäÞ ç ãñáììéêÞ äéÜáîç ìðïñåß íá ðåñéóñÝöåáé êáÜ 180◦ ãýñù áðü ï ìÝóï çò). Âñåßå ðüóåò îå÷ùñéóÝò äéáÜîåéò ìðïñïýìå íá Ý÷ïõìå. 4.7 ¸íá ñáðÝæé êõêëéêü Ý÷åé ðÝíå èÝóåéò. Áíéðñüóùðïé ñéþí ðïëééêþí êïììÜùí Á,Â, èá êáèßóïõí óï ñáðÝæé (ïõëÜ÷éóïí Ýíáò áðü êÜèå êüììá). üóïé äéáöïñåéêïß ñüðïé íá êáèßóïõí õðÜñ÷ïõí; (Äýï ñüðïé êáèßóìáïò åßíáé éóïäýíáìïé áí ç ðåñéóñïöÞ ïõ åíüò äßíåé ïí Üëëï.) 4.8 Ïêþ Üíèñùðïé ó÷åäéÜæïõí íá êÜíïõí äéáêïðÝò ìáæß. ¸÷ïõí õð' üøç ïõò ñåéò ðüëåéò. ÁíÜìåóá óïõò ïêþ áíèñþðïõò õðÜñ÷ïõí ðÝíå ðïõ áíÞêïõí óå ìéá ïéêïãÝíåéá êáé Üëëïé ñåéò ðïõ áíÞêïõí óå Üëëç ïéêïãÝíåéá. ÅÜí ïé Üíèñùðïé çò ßäéáò ïéêïãÝíåéáò ðñÝðåé íá ðÜíå ìáæß, íá âñåèåß ï áñéèìüò ùí ñüðùí ðïõ ìðïñïýí áõïß ïé ïêþ Üíèñùðïé íá ó÷åäéÜóïõí á áîßäéá ïõò. 4.9 Âñåßå üëïõò ïõò äõíáïýò ñüðïõò ãéá íá âÜøïõìå ñåéò ìðÜëåò üáí Ý÷ïõìå ñßá ÷ñþìáá. 4.10 Íá äåé÷åß üé ï áêÝñáéïò n8 + 17n4 + 6n2 äéáéñåßáé áðü ïí 24, ãéá êÜèå áêÝñáéï n. Õðüäåéîç: Âñåßå ïõò ñüðïõò ðïõ ìðïñïýìå íá ÷ñùìáßóïõìå éò áêìÝò åíüò êýâïõ ìå n ÷ñþìáá. 4.11 Íá ðåñéãñáöåß ðñïóåêéêÜ ç ïìÜäá óõììåñéþí ïõ åñáãþíïõ êáé íá õðïëïãéóèïýí ïé äåßêñéåò óõíáñÞóåéò ùí óõììåñéþí.
4.5.
ÁÓÊÇÓÅÉÓ
61
4.12 Äéáéñïýìå çí ðáñÜðëåõñç åðéöÜíåéá åíüò êõëßíäñïõ óå Ýóóåñéò ëùñßäåò êáé ÷ñçóéìïðïéïýìå äýï ÷ñþìáá ãéá íá âÜøïõìå éò ëùñßäåò, Ýóé þóå êÜèå ìéá íá âáöåß ìå ï ßäéï ÷ñþìá. üóïé äéáöïñåéêïß ÷ñùìáéóìïß õðÜñ÷ïõí; 4.13 Íá õðïëïãéóèåß ï áñéèìüò ùí ñüðùí ðïõ ïé êïñõöÝò åíüò åñáãþíïõ ìðïñïýí íá âáöïýí ìå ñßá ÷ñþìáá x1 ; x2 ; x3 ìå çí ðáñáäï÷Þ üé äýï ÷ñùìáéóìïß åßíáé éóïäýíáìïé üáí (á) ï Ýíáò ðñïêýðåé áðü ïí Üëëï ðåñéóñÝöïíáò ï åñÜãùíï ãýñù áðü êÜðïéï Üîïíá Þ (â) ï Ýíáò ðñïêýðåé áðü ïí Üëëï áíéìåáèÝïíáò á ÷ñþìáá. 4.14 Ìå ðüóïõò äéáöïñåéêïýò ñüðïõò ìðïñïýìå íá ÷ñùìáßóïõìå ìå Ýóóåñá ÷ñþìáá éò êïñõöÝò åíüò êáíïíéêïý åîÜãùíïõ, ï ïðïßï åßíáé åëåýèåñï íá êéíåßáé óï ÷þñï; 4.15 Õðïëïãßóå ìå ðüóïõò ñüðïõò ìðïñïýìå íá ÷ñùìáßóïõìå éò êïñõöÝò åíüò éóüðëåõñïõ ñéãþíïõ ìå ñßá ÷ñþìáá, Ýóé þóå áêñéâþò äýï êïñõöÝò íá Ý÷ïõí ï ßäéï ÷ñþìá.
62
ÊÅÖÁËÁÉÏ 4.
ÈÅÙÑÉÁ ÌÅÔÑÇÓÇÓ POLYA
ÊåöÜëáéï 5 Åãêëåéóìüò - Áðïêëåéóìüò 5.1
ÅéóáãùãÞ
Óå áõü ï êåöÜëáéï èá óõæçÞóïõìå ìéá óõíïëï-èåùñçéêÞ ìÝèïäï, ç ïðïßá èá ìáò åðéñÝøåé íá ëýóïõìå ìéá ìåãÜëç êáçãïñßá ðñïâëçìÜùí ìÝñçóçò. Ç ìÝèïäïò áõÞ ëÝãåáé áñ÷Þ ïõ Åãêëåéóìïý - Áðïêëåéóìïý. ñéí óõæçÞóïõìå áõÞ ç ìÝèïäï èá äþóïõìå ìåñéêïýò ïñéóìïýò êáé óõìâïëéóìïýò, ïé ïðïßïé èá ìáò åßíáé ÷ñÞóéìïé ãéá ç óõíÝ÷åéá. Áò åßíáé S Ýíá óýíïëï ìå ðëçèéêü áñéèìü N , äçëáäÞ N = |S |. ¸óù
1 ; 2 ; : : : ; t ìéá óõëëïãÞ áðü óõíèÞêåò, ïé ïðïßåò éêáíïðïéïýíáé áðü ìåñéêÜ Þ üëá á óïé÷åßá ïõ S . Åßíáé äõíáüí ìåñéêÜ óïé÷åßá ïõ S íá éêáíïðïéïýí ðåñéóóüåñåò áðü ìéá óõíèÞêåò, åíþ ìðïñåß êÜðïéá Üëëá óïé÷åßá íá ìçí éêáíïðïéïýí êáìéÜ óõíèÞêç. éá êÜèå i, 1 ≤ i ≤ t, ï áñéèìüò N ( i ) èá äçëþíåé ïí áñéèìü ùí óïé÷åßùí ïõ S , ðïõ éêáíïðïéïýí ç óõíèÞêç i . Åßíáé Üìåóï óõìðÝñáóìá üé ãéá êÜèå i, 1 ≤ i ≤ t, ï áñéèìüò N ( i ) = Í − N ( i ) ìåñÜ ïí áñéèìü ùí óïé÷åßùí ïõ S , á ïðïßá äåí éêáíïðïéïýí ç óõíèÞêç i . Óå ìéá Üîç õðÜñ÷ïõí 100 ìáèçÝò, ïé ïðïßïé ðáñáêïëïõèïýí ï ìÜèçìá £ÄéáêñéÜ ÌáèçìáéêÜ É¤. Áðü áõïýò ïé 30 Ý÷ïõí ï ìÜèçìá óáí åðéëïãÞ. ïéïò åßíáé ï áñéèìüò ùí ìáèçþí ðïõ ï Ý÷ïõí õðï÷ñåùéêü;
áñÜäåéãìá 5.1:
. Åäþ ç éäéüçá åßíáé, üé êÜðïéïò ìáèçÞò Ý÷åé óáí åðéëïãÞ ï ìÜèçìá £ÄéáêñéÜ ÌáèçìáéêÜ É¤. ¢ñá ï áñéèìüò ùí ìáèçþí ðïõ ï Ý÷ïõí õðï÷ñåùéêü åßíáé Ëýóç
N (ü÷é åðéëïãÞ, áëëÜ õðï÷ñåùéêü) = N − N (åðéëïãÞ) N (ü÷é åðéëïãÞ, áëëÜ õðï÷ñåùéêü) = 100 − 30 = 70 Óç óõíÝ÷åéá èá óõæçÞóïõìå ãéá 2 óõíèÞêåò ìáæß. éá êÜèå i; j ∈ {1; 2; 3; : : : ; t}, ìå i 6= j ï áñéèìüò N ( i j ) äçëþíåé ïí áñéèìü ùí óïé÷åßùí ïõ S , á ïðïßá éêáíïðïéïýí êáé éò äõï óõíèÞêåò i ; j (êáé ðéèáíþò êáé êÜðïéåò Üëëåò). Ôþñá ãéá êÜèå i; j , ìå 1 ≤ i; j ≤ t êáé i 6= j , ï áñéèìüò N ( i j ) ìåñÜ ïí áñéèìü ùí óïé÷åßùí ïõ S á ïðïßá äåí éêáíïðïéïýí åßå ç óõíèÞêç i Þ çí j . ñïóï÷Þ ï áñéèìüò N ( i j ) äåí åßíáé ßäéïò ìå ïí áñéèìü N ( i j ). ×ñçóéìïðïéþíáò ï äéÜãñáììá Venn ðáßñíïõìå ç ðéï êÜù åéêüíá. Áðü ï Ó÷. 5.1 63
64
ÊÅÖÁËÁÉÏ 5.
Å ÊËÅÉÓÌÏÓ - ÁÏÊËÅÉÓÌÏÓ
N ci c j N ci
N cj
N ci c j
Ó÷Þìá 5.1: ÄéÜãñáììá Venn Ý÷ïõìå üé:
N ( i j ) = N − [N ( i ) + N ( j )] + N ( i j )
Åßíáé åýêïëï íá ðÜñïõìå ç ðéï ðÜíù ó÷Ýóç, áí ÷ñçóéìïðïéÞóïõìå ï Íüìï ïõ de Morgan. áñÜäåéãìá 5.2: Óå Ýíá ó÷ïëåßï õðÜñ÷ïõí 100 ìáèçÝò êáé áðü áõïýò ïé 50 ìéëÜíå áëëéêÜ, ïé 40 ËáéíéêÜ êáé 20 ìéëÜíå êáé éò 2 ãëþóóåò. üóïé ìáèçÝò äåí ìéëÜíå êáìéÜ ãëþóóá. Ëýóç
: Ïé éäéüçåò åßíáé 2.
Éäéüçá F , ï ìáèçÞò ìéëÜ áëëéêÜ êáé ç éäéüçá L, ï ìáèçÞò ìéëÜ ËáéíéêÜ. Ôá äåäïìÝíá ìáò åßíáé á ðéï êÜù:
N
= 100;
N (F ) = 50; N (L) = 40; N (F L) = 20
Åäþ ï æçïýìåíï åßíáé ï áñéèìüò N (F L). Áðü ï Ó÷. 5.1 Ý÷ïõìå:
N FL
= N − (N (F ) N (L)) + N (F L) = 30
Óçí åðüìåíç ðáñÜãñáöï èá ãåíéêåýóïõìå ç ìÝèïäï ðïõ ÷ñçóéìïðïéÞóáìå óï ðéï ðÜíù ðáñÜäåéãìá. 5.2
Ç áñ÷Þ ïõ Åãêëåéóìïý - Áðïêëåéóìïý
Èá äþóïõìå Ýíá èåþñçìá êáé çí áðüäåéîç ïõ. Èåþñçìá: Áò èåùñÞóïõìå Ýíá óýíïëï S , ìå ðëçèéêü áñéèìü |S | = N êáé éò óõíèÞêåò i , 1 ≤ i ≤ t, ïé ïðïßåò éêáíïðïéïýíáé áðü ìåñéêÜ óïé÷åßá ïõ S . Ï áñéèìüò ùí óïé÷åßùí ïõ S , á ïðïßá äåí éêáíïðïéïýí êáìßá áðü éò óõíèÞêåò
5.2.
65
Ç ÁÑ×Ç ÔÏÕ Å ÊËÅÉÓÌÏÕ - ÁÏÊËÅÉÓÌÏÕ
i , 1 ≤ i ≤ t, åßíáé: N = N ( 1 2 3 : : : t ) üðïõ N = N − [N ( 1 ) + N ( 2 ) + N ( 3 ) + : : : + N ( t )] + [N ( 1 2 ) + N ( 1 3 ) + : : : + N ( 1 t ) + N ( 2 3 ) + : : : + N ( t−1 t )] − [N ( 1 2 3 ) + N ( 1 2 4 ) + : : : + N ( 1 2 t ) + N ( 1 3 4 ) + : : : t + N ( 1 3 t ) + : : : + N ( t−2 t−1 t )] + : : : + (−1) N ( 1 2 3 : : : t )(5.1) Þ
N
N−
=
X
N ( i ) +
1≤i≤t
+ (−1)
t
X
1≤i<j ≤t
N ( i j ) −
N ( 1 2 3 : : : t )
X
N ( i j k ) + : : :
1≤i<j
(5.2)
Áðüäåéîç: Åßíáé åýêïëï íá áðïäåé÷èåß ï èåþñçìá ìå åðáãùãÞ óï t. Åìåßò üìùò èá äþóïõìå ìéá óõíäõáóéêÞ áðüäåéîç. Èá äåßîïõìå üé ãéá êÜèå x ∈ S , ðùò áõü óõììåÝ÷åé ï ßäéï, åßå 0 Þ 1, óå êÜèå ìÝñïò çò (5.1). ÅÜí ï x äåí éêáíïðïéåß êáìéÜ áðü éò óõíèÞêåò, üå ï x ðñïóìåñéÝáé ìéá öïñÜ óï N êáé ìéá öïñÜ óï N , áëëÜ êáìéÜ öïñÜ óå êÜèå Üëëï üñï çò (5.1). ÅðïìÝíùò, ï x óõììåÝ÷åé ìéá öïñÜ ìå 1 óå êÜèå ìÝñïò çò ó÷Ýóçò. Ç Üëëç ðåñßðùóç åßíáé ï x íá éêáíïðïéåß áêñéâþò r áðü éò óõíèÞêåò, ìå 1 ≤ r ≤ t. Óå áõÞ ç ðåñßðùóç ï x äåí óõììåÝ÷åé óï N . ÁëëÜ óï äåîéü ìÝñïò çò (5.1), ï x ðñïóìåñéÝáé. 1. Ìéá öïñÜ óï N . 2. r öïñÝò óï 3.
r 2
P
1≤i≤t
ÖïñÝò óï
r 3
öïñÝò óï
N ( i ) (Ìéá öïñÜ ãéá êÜèå ìßá áðü éò r óõíèÞêåò).
P
1≤i<j ≤t
N ( i j ) (Ìéá öïñÜ ãéá êÜèå æåýãïò óõíèçêþí ðïõ
åðéëÝãåáé áðü éò r óõíèÞêåò, éò ïðïßåò éêáíïðïéåß). 4.
:::
P
1≤i<j
N ( i j k ).
N ( i i : : : ir ). ¢ñá óï äåîéü ìÝñïò çò (5.2), ï x ðñïóìåñéÝáé. r r r r r 1−r+ − + : : : + (−1) = [1 + (−1)] = 0r = 0 öïñÝò 2 3 r ÅðïìÝíùò, á 2 ìÝñç çò ó÷Ýóçò ìåñïýí á ßäéá óïé÷åßá ïõ S êáé Üñá ç éóüçá r+1.
r r
= 1 öïñÜ óï
P
1
2
éêáíïðïéåßáé. ÓõìðÝñáóìá: Óýìöùíá ìå éò õðïèÝóåéò ïõ èåùñÞìáïò, ï áñéèìüò ùí óïé÷åßùí ïõ S á ïðïßá éêáíïðïéïýí ïõëÜ÷éóïí ìéá áðü éò óõíèÞêåò i , 1 ≤ i ≤ t, åßíáé: N ( 1 Þ 2 Þ 3 Þ : : : Þ t ) = N − N ñéí ðñï÷ùñÞóïõìå óå ðáñáäåßãìáá, èá äþóïõìå ìéá óõíïìïãñáößá. Áò åßíáé:
S0 S1 S2
= = =
N [N ( 1 ) + N ( 2 ) + N ( 3 ) + : : : + N ( t )] [N ( 1 2 ) + N ( 1 3 ) + : : : + N ( 1 t ) + N ( 2 3 ) + : : : + N ( t−1 t )]
66
ÊÅÖÁËÁÉÏ 5.
Å ÊËÅÉÓÌÏÓ - ÁÏÊËÅÉÓÌÏÓ
êáé åðïìÝíùò ãåíéêÜ
Sk =
X
N ( i i : : : ik ); 1
2
1≤k≤t
Ôá áèñïßóìáá ðáßñíïíáé ðÜíù óå üëåò éò åðéëïãÝò ìåãÝèïõò k áðü ç óõëëïãÞ ùí t óõíèçêþí. ¢ñá ï Sk Ý÷åé kt üñïõò. áñÜäåéãìá 5.3: Ìå ðüóïõò ñüðïõò ìðïñïýí á 26 ãñÜììáá ïõ áããëéêïý áëöÜâçïõ íá áíéìåáåèïýí Ýóé þóå êáíÝíá áðü á ðáñáêÜù äåßãìáá íá ìçí åìöáíéóïýí. Ôá äåßãìáá åßíáé ar, dog, pun, byte.
: ¸óù S ï óýíïëï üëùí ùí áíéìåáèÝóåùí ùí 26 ãñáììÜùí. ñïöáíþò S ëÝìå üé éêáíïðïéåß ç óõíèÞêç i , åÜí ç áíéìåÜèåóç ðåñéÝ÷åé á äåßãìáá ar Þ dog Þ pun Þ byte.
Ëýóç
|S | = 26!. éá êÜèå i, 1 ≤ i ≤ 4, ìéá áíéìåÜèåóç óï
Åßíáé:
N ( ðåñéÝ÷åé ï äåßãìá ar ) N ( ðåñéÝ÷åé ï äåßãìá dog ) N ( ðåñéÝ÷åé ï äåßãìá pun ) N ( ðåñéÝ÷åé ï äåßãìá byte )
= = = =
N ( 1 ) = 24! N ( 2 ) = 24! N ( 3 ) = 24! N ( 4 ) = 23!
Áêüìá Ý÷ïõìå üé:
N ( 1 2 ) = N ( 1 3 ) = N ( 2 3 ) = 22! N ( i 4 ) = 21!; i 6= 4 êáé
N ( 1 2 3 ) = 20!; N ( i j 4 ) = 19!; N ( 1 2 3 4 ) = 17!
1≤i<j
<3
ÅðïìÝíùò
N ( 1 2 3 4 ) = 26! − [3 (24!) + 23!] + [3 (22!) + 3 (21!)] − [20! + 3 (19!)] + 17!
éá n ∈ Æ + , áò åßíáé (n) ï áñéèìüò ùí èåéêþí áêåñáßùí m, üðïõ 1 ≤ m < n êáé (m; n) = 1, äçëáäÞ m; n åßíáé ó÷åéêÜ ðñþïé. ÁõÞ ç óõíÜñçóç åßíáé ãíùóÞ óáí óõíÜñçóç ïõ Euler1 . Åßíáé åýêïëï íá äéáðéóþóïõìå üé (2) = 1; (3) = 2; (4) = 2; (5) = 2 êáé (6) = 2. éá êÜèå ðñþï áñéèìü p åßíáé (p) = p − 1. Íá âñåèåß Ýíáò ýðïò ðïõ íá ìáò äßíåé ï (n). áñÜäåéãìá 5.4:
. éá êÜèå n ≤ 2 ìðïñïýìå íá ãñÜøïõìå ï n óáí n = p1e1 p2e2 : : : pet t üðïõ p1 ; p2 ; : : : ; pt åßíáé äéáêåêñéìÝíïé ðñþïé áñéèìïß êáé ei ≥ 1; 1 ≤ i ≤ t. éá åõêïëßá óéò ðñÜîåéò èá èåùñÞóïõìå t = 4 êáé óç óõíÝ÷åéá åßíáé åýêïëï íá ãåíéêåõèåß ï ýðïò. Åßíáé S = {l; 2; 3; : : : ; n}, N = |S | = n êáé ãéá 1 ≤ i ≤ 4 ëÝìå üé k ∈ S êáé éêáíïðïéåß ç óõíèÞêç i , åÜí ï k åßíáé äéáéñÝóéìï áðü ï pi . éá 1 ≤ k ≤ n, Ëýóç
1 L. Euler Åëâåüò Ìáèçìáéêüò ïõ 18ïõ áéþíá áðü ïõò ìåãáëýåñïõò óçí éóïñßá.
5.2.
67
Ç ÁÑ×Ç ÔÏÕ Å ÊËÅÉÓÌÏÕ - ÁÏÊËÅÉÓÌÏÕ
(k; n) = 1, åÜí
åßíáé:
k äåí åßíáé äéáéñåü áðü êáíÝíá ðñþï pi , 1 ≤ i ≤ 4. ÅðïìÝíùò
(n) = N ( 1 2 3 4 ) éá 1 ≤ i ≤ 4; N ( i ) = n=pi ; N ( i j ) = n=(pi pj ); 1 ≤ i < j ≤ 4. Åðßóçò åßíáé:
N ( i j k ) = n= (pi pj pk ) ;
êáé
1≤i<j
N ( 1 2 3 4 ) = n= (p1 p2 p3 p4 )
ÅðïìÝíùò
(n)
= =
=
=
= =
S0 − S1 + S2 − S3 + S4 = n n n n n n− + :::+ + + + :::+ p1 p4 p1 p2 p1 p3 p3 p4 n n n − + :::+ + = p1 p2 p3 p2 p3 p4 p1 p2 p3 p4 n
1−
1
p1
+ :::+
1
+
1
1
p1 p2
+
1
p1 p3
+ :::+
1
p3 p4 n − + :::+ + = p1 p2 p3 p2 p3 p4 p1 p2 p3 p4 n [p p p p − (p2 p3 p4 + p1 p3 p4 + p1 p2 p4 + p1 p2 p3 ) p1 p2 p3 p4 1 2 3 4 + (p3 p4 + p2 p4 + p2 p3 + p1 p4 + p1 p3 + p1 p2 ) − (p4 + p3 + p2 + p1 ) + 1] = n [(p − 1) (p2 − 1) (p3 − 1) (p4 − 1)] = p1 p2 p3 p4 1 4 Y p1 − 1 p2 − 1 p3 − 1 p4 − 1 1 n 1− =n p1 p2 p3 p4 pi i=1 1
p4
Åßíáé åýêïëï íá ãåíéêåýóïõìå êáé íá êááëÞîïõìå üé: (n) = n
Q
p=n
1−
üðïõ ï ãéíüìåíï ðáßñíåáé ðÜíù óå üëïõò ïõò ðñþïõò ðïõ äéáéñïýí ï n. áñÜäåéãìá 5.5:
1 p
,
üóïé åßíáé ïé ñüðïé ìå ïõò ïðïßïõò ìðïñïýìå íá äéáíåßìïõìå
r äéáêåêñéìÝíá áíéêåßìåíá óå 5 (äéáêåêñéìÝíá) êïõéÜ Ýóé þóå Ýíá ïõëÜ÷éóïí êïõß íá 'íáé Üäåéï;
. Áò åßíáé Ái ç éäéüçá üé ï êïõß i ìÝíåé Üäåéï óå êÜðïéá äéáíïìÞ Þ äéáíïìÝò. Áõü ðïõ æçÜìå åìåßò åßíáé ï N (A1 Þ Á2 Þ : : : Þ Á5 ). ÁëëÜ áõü ìå âÜóç ï óõìðÝñáóìá åßíáé: Ëýóç
N (A1 Þ A2 Þ : : : Þ A5 )
= =
N − N = N − N A1 A2 A3 A4 A5 N − (N − S1 + S2 − S3 + S4 )
üðïõ Si ï áñéèìüò ùí ñüðùí íá äéáíåßìïõìå á áíéêåßìåíá þóå ïõëÜ÷éóïí i óï ðëÞèïò êïõéÜ Üäåéá
N (A1 Þ A2 Þ : : : Þ A5 ) =
5 r 5 r 5 r 5 r 4 − 3 + 2 − 1 1 2 3 4
68 5.3
ÊÅÖÁËÁÉÏ 5.
Å ÊËÅÉÓÌÏÓ - ÁÏÊËÅÉÓÌÏÓ
ÁóêÞóåéò
5.1 üóåò ïðïèåÞóåéò ùí øçößùí 0; 1; 2; : : : ; 9 õðÜñ÷ïõí óéò ïðïßåò ï ðñþï øçößï íá 'íáé ìåãáëýåñï áðü ï 1 êáé ï åëåõáßï øçößï íá 'íáé ìéêñüåñï áðü ï 8; 5.2 üóïé áêÝñáéïé ìéêñüåñïé ïõ 70 åßíáé ó÷åéêÜ ðñþïé ìå ï 70 (Ó÷åéêÜ ðñþïé óçìáßíåé üé äåí Ý÷ïõí êïéíïýò äéáéñÝåò); 5.3 üóåò ëÝîåéò n-øçößùí áðü ï áëöÜâçï {0; 1; 2} õðÜñ÷ïõí ìå Ýíá ïõëÜ÷éóïí 0, ìå Ýíá ïõëÜ÷éóïí 1 êáé ìå Ýíá ïõëÜ÷éóïí 2; 5.4 Óå Ýíá ó÷ïëåßï õðÜñ÷ïõí 1.000 ìáèçÝò. Áðü áõïýò ïé 400 ìéëÜíå áëëéêÜ, ïé 300 ÉáëéêÜ êáé 200 ìéëÜíå åñìáíéêÜ. ÅÜí õðÜñ÷ïõí 200 ìáèçÝò ðïõ ìéëÜíå ïðïéåóäÞðïå 2 ãëþóóåò êáé 100 ìáèçÝò ðïõ ìéëÜíå êáé éò 3 ãëþóóåò, ðüóïé åßíáé ïé ìáèçÝò ðïõ äåí ìéëÜíå êáìéÜ ãëþóóá; 5.5 Íá ëõèåß ï áñ. 5.4 óç ãåíéêÞ ðåñßðùóç. 5.6 Íá âñåèåß ï áñéèìüò ùí èåéêþí áêåñáßùí n; 1 ≤ n ≤ 100 êáé n ìç äéáéñÝóéìïò ìå 2,3 êáé 5. 5.7 ¸íáò öïéçÞò èÝëåé íá öéÜîåé Ýíá ðñüãñáììá ãéá ìéá ÷ñïíéêÞ ðåñßïäï 7 çìåñþí Ýóé þóå êÜèå ìÝñá íá ìåëåÜ Ýíá ìüíï ìÜèçìá. Ôá ìáèÞìáá åßíáé: ìáèçìáéêÜ, öõóéêÞ, ÷çìåßá êáé ïéêïíïìßá. Íá âñåèåß ï áñéèìüò áõþí ùí ðñïãñáììÜùí. 5.8 üóåò äéáöïñåéêÝò áêÝñáéåò ëýóåéò õðÜñ÷ïõí ãéá çí åîßóùóç
x1 + x2 + x3 + x4 + x5 + x6 = 20;
0 ≤ xi ≤ 8
5.9 Íá âñåèåß ï áñéèìüò ùí áíéìåáèÝóåùí ùí ãñáììÜùí ïõ ëáéíéêïý áëöáâÞïõ a,b, ,...,x,y,z, óéò ïðïßåò äåí åìöáíßæïíáé á äåßãìáá spin, game, path êáé net. 5.10 ¸óù á ðåðåñáóìÝíá óýíïëá Á;  ìå |Á| = m; |B | = n êáé m ≥ n. Áò åßíáé Á = {a1 ; a2 ; : : : ; am };  = {b1 ; b2 ; : : : ; bn } êáé S = ï óýíïëï üëùí ùí óõíáñÞóåùí f : A →  . ñïöáíþò N = |S | = nm . éá 1 ≤ i ≤ n, áò åßíáé i ç óõíèÞêç óï S ðïõ éêáíïðïéåßáé, üáí ç óõíÜñçóç f : Á →  äåí Ý÷åé óï ðåäßï éìþí çò ï bi . Ôüå N ( i ) åßíáé ï áñéèìüò ùí óõíáñÞóåùí óï S , ïé ïðïßåò Ý÷ïõí óï ðåäßï éìþí ïõò ï bi . Íá âñåèåß ï áñéèìüò N .
6 Âéâëéïãñáößá 1. Aho Á., Hop roft J., Ullman J., "The design and analysis of omputer algorithms", Addison-Wesley 1974. 2. Aho Á., Hop roft J., Ullman J., "Data stru tures and algorithms", AddisonWesley 1983. 3. Behzad M., Chartrand G., Lesniak-Foster L., "Graphs and Digraphs", Wadsworth International Group 1981. 4. DeBruijn N., "Polya's Theory of Counting", In Applied Combinatorial Mathemati s, ed. Be kenba h, John Wiley 1964. 5. Feller W., "An Introdu tion to Probability Theory and its Appli ation", Vol. I. 3rd ed., John Willey 1968. 6. Harary F., "Graph Theory", Addison-Wesley 1972. 7. Graham R., Knuth D., Patashnik O., "Con rete Mathemati s", AddisonWesley 1989. 8. Grimaldi R., "Dis rete and Combinatorial Mathemati s An Applied introdu tion", Se ond Edition, Addison-Wesley 1984. 9. Liu C, "Elements of Dis rete Mathemati s", Se ond Edition, M Graw-Hill 1985. 10. Liu C, "Introdu tion to Combinatorial Mathemati s", M Graw-Hill 1968. 11. Lovasz L., "Combinatorial Problems and Exer ises", North-Holland 1979. 12. Lueker G., "Some Te hniques for Solving Re urren es", Computing Surveys, Vol. 12, No. 4, De ember 1980. 13. J Marshall H., "Combinatorial Theory", Se ond Edition, John Wiley and Sons, 1986. 14. Polya G., "Kombinatoris he Anzahlbestimmungen fur Gruppen, Graphen und Chemishe Verbindungen", A ta Informati a 68, 1937, pp. 145-254. 69
70
6.
ÂÉÂËÉÏ ÑÁÖÉÁ
15. Read R., "Polya's Theorem and its Progeny", Mathemati s Magazine 60, No. 5, De ember 1987, pp. 275-282. 16. Reingold M., Nievergelt J., Deo N., "Combinatorial Algorithms: Theory and Pra ti e", Englewood Clis 1977. 17. Riordan J., "An Introdu tion to Combinatorial Analysis", John Wiley 1958. 18. Ross K.A., C.R.B Wright, "Dis rete Mathemati s", Prenti e Hall, 1985. 19. Tomes u I. and Melter R., "Problems in Combinatori s and Graph Theory", John Wiley and Sons, 1985. 20. Townsend M., "Dis rete Mathemati s: Applied Combinatori s and Graph Theory", Benjamin/Cummings Publishiny Company, 1987. 21. Tu ker Á., "Applied Combinatori s", Se ond Edition, John Wiley and Sons 1984. 22. "Topi s in Combinatorial Mathemati s", Mathemati al Asso iation of Ameri a, 1972.
7 Ëßóá Óõìâüëùí Óýìâïëï
n!
C (n; r) Ñ (n; r) S (r; n) s (r; n) X=G N ( i )
Óçìáóßá
áñáãïíéêü Óõíäõáóìïß n áíÜ r ÄéáÜîåéò n áíÜ r Áñéèìïß Stirling 2ïõ åßäïõò Áñéèìïß Stirling 1ïõ åßäïõò Óýíïëï êëÜóåùí éóïäõíáìßáò ïõ óõíüëïõ × ùò ðñïò çí =G Áñéèìüò óïé÷åßùí åíüò óõíüëïõ S ðïõ éêáíïðïéïýí çí óõíèÞêç i
71