KTH Matematik

5B1118 Diskret Matematik Lösningar till Kontrollskrivning 2 Måndagen den 1 22 Mars, 2004

(1) (3p) Bestäm talet x om

∑_{i=0}^{50} \binom{50}{i}8^{i} = x^{100}.

9^{50} = (1 + 8)^{50} = ∑_{i=0}^{50}(1)^{50−i}(8)^{i} = ∑_{i=0}^{50}(8)^{i} = x^{100}.

Så 9^{50} = (x^{2})^{50} och x^{2} = 9. Svaret är alttså x = ±3.

(2) (3p) Hur många arrangemang av bokstäverna i ordet ARRANGEMANG finns

det? Hur många av den har inga A intill varandra?

Det finns 11 bokstäver totalt med 3 stycken A, 2 stycken R, 2 stycken N och 2 stycken G. Antalet arrangemang är lika med den multinomialskoefficient

\binom{11}{3, 2, 2, 2} = \frac{11!}{6 · 8} = 831600

Om vi tar borta alla A har vi \binom{8}{2,2,2} = \frac{8!}{8} = 7! = 5040 många arrenemang av bostäverna RRNGEMNG. För att placera 3 stycken A sådan att inga är intill varandra måste vi lägga den mellan två bostäver i RRNGEMNG :

∗R ∗ R ∗ N ∗ G ∗ E ∗ M ∗ N ∗ G∗

Vi ska välja 3 stycken ∗ bland 9 (utan upprepning och utan ordning) så vi kan välja på \binom{9}{3} olika sätt.

Enligt multiplicationsprincipen är svaret:

5040 · \binom{9}{3} = 423360

(3) (3p) Bestäm antalet heltal lösningar till ekvationen:

x_{1} + x_{2} + x_{3} + x_{4} = 32

med x_{i} > 0 för i = 1, 2, x_{3} > 2 och x_{4} ≥ 3

Sätt y_{1} = x_{1} − 1 ≥ 0, y_{2} = x_{2} − 1 ≥ 0, y_{3} = x_{3} − 3 ≥ 0, y_{4} = x_{4} − 3 ≥ 0. Vi har att:

y_{1} + y_{2} + y_{3} + y_{4} = x_{1} + x_{2} + x_{3} + x_{4} − 8 = 24

Vi ska beräkna antalet icke-negativa lösningar till den här ekvation. Svaret är:

\binom{4 + 24 − 1}{24} = \frac{27 · 26 · 25}{3 · 2} = 2925