Combinatorics Problems: Problems with Solutions

Solution:
Each of the five students goes to exactly one of the three classes, independently of the others, and a distribution is completely determined by the class chosen for each student. By the multiplication principle the number of distributions is
[tex]3\times 3\times 3\times 3\times 3=3^5=243[/tex]

Solution:
The order of the players within each group does not matter, so we count combinations. The numbers of ways to choose the goalkeeper, the two defensemen and the three forwards are, respectively,
[tex]\binom{2}{1}=2,\qquad \binom{6}{2}=15,\qquad \binom{8}{3}=56[/tex]
These choices are independent, so by the multiplication principle the number of line-ups is
[tex]2\times 15\times 56=1680[/tex]

Solution:
The digit [tex]0[/tex] cannot occur: it would be the smallest digit, so it would have to stand in the first position, which is impossible for a seven-digit number. Hence all digits are among [tex]1,2,\dots,9[/tex].
Conversely, every choice of [tex]7[/tex] different digits from [tex]1,2,\dots,9[/tex] gives exactly one such number: the chosen digits written in increasing order. So the required count equals the number of ways to choose [tex]7[/tex] digits out of [tex]9[/tex]:
[tex]\binom{9}{7}=\binom{9}{2}=\frac{9\times 8}{2}=36[/tex]

Solution:
We split into cases according to the position of the only digit [tex]3[/tex]. If it is the hundreds digit, the tens and units digits can be any of the [tex]9[/tex] digits different from [tex]3[/tex]:
[tex]9\times 9=81[/tex]
If it is the tens digit, the hundreds digit cannot be [tex]0[/tex] or [tex]3[/tex] ([tex]8[/tex] choices) and the units digit is any digit except [tex]3[/tex] ([tex]9[/tex] choices):
[tex]8\times 9=72[/tex]
If it is the units digit, in the same way we get
[tex]8\times 9=72[/tex]
The cases do not overlap, so the number of such numbers is
[tex]81+72+72=225[/tex]

Solution:
The word has [tex]10[/tex] letters: M appears [tex]2[/tex] times, A appears [tex]3[/tex] times, T appears [tex]2[/tex] times, and E, I, K appear once each. If all ten letters were different, they could be arranged in [tex]10![/tex] ways.
Permuting equal letters among themselves does not change the word, so every word is counted exactly [tex]2!\times 3!\times 2!=24[/tex] times among these arrangements. Hence the number of different words is
[tex]\frac{10!}{2!\times 3!\times 2!}=\frac{3628800}{24}=151200[/tex]

Solution:
Three points are vertices of a triangle exactly when they are not collinear. Hence the three vertices cannot all lie on the same one of the given lines, i.e. a triangle has two vertices on one line and one vertex on the other. Conversely, every such triple of points gives a triangle, since the third point does not lie on the line through the other two (the lines are parallel and distinct).
Two vertices on the line with [tex]10[/tex] points and one on the other line:
[tex]\binom{10}{2}\times 20=45\times 20=900[/tex]
Two vertices on the line with [tex]20[/tex] points and one on the other line:
[tex]\binom{20}{2}\times 10=190\times 10=1900[/tex]
The two cases do not overlap, so the total number of triangles is
[tex]900+1900=2800[/tex]

Solution:
It matters who goes to which city, so we count ordered triples of different employees chosen out of all [tex]9[/tex] (arrangements). Without restrictions their number is
[tex]9\times 8\times 7=504[/tex]
The forbidden choices are those with no economist, i.e. when all three travellers are lawyers:
[tex]5\times 4\times 3=60[/tex]
Every other choice contains at least one economist, so the required number is
[tex]504-60=444[/tex]

Solution:
By the binomial theorem, the general term of the expansion is
[tex]T_{k+1}=\binom{7}{k}\left(2x^{4}\right)^{7-k}\left(\frac{1}{x^{3}}\right)^{k}=\binom{7}{k}\times 2^{7-k}\times x^{28-7k},\qquad k=0,1,\dots,7[/tex]
The term does not contain [tex]x[/tex] exactly when [tex]28-7k=0[/tex], i.e. [tex]k=4[/tex]. Hence the constant term is
[tex]T_{5}=\binom{7}{4}\times 2^{3}=35\times 8=280[/tex]

Solution:
There are [tex]2^4=16[/tex] expressions, but different expressions may have equal values, so we count the values directly. Let [tex]S[/tex] be the sum of the numbers that get a minus sign. Then the value of the expression is
[tex](2+4+6+8)-2S=20-2S[/tex]
Hence different values of [tex]S[/tex] give different values of the expression and vice versa. Write [tex]S=2T[/tex], where [tex]T[/tex] is the sum of some of the numbers [tex]1, 2, 3, 4[/tex] (possibly of none of them). Every integer from [tex]0[/tex] to [tex]10[/tex] is such a sum:
[tex]0, 1, 2, 3, 4, 5=1+4, 6=2+4, 7=3+4, 8=1+3+4, 9=2+3+4, 10=1+2+3+4[/tex]
No other values are possible, since [tex]0\le T\le 10[/tex]. Hence the value [tex]20-4T[/tex] of the expression takes exactly [tex]11[/tex] different values:
[tex]-20, -16, -12, \dots, 16, 20[/tex]

Solution:
First place the [tex]8[/tex] red pens in a row; since they are identical, this can be done in only one way. They create [tex]9[/tex] places for the blue pens: [tex]7[/tex] gaps between neighboring red pens and [tex]2[/tex] places at the two ends.
Two blue pens are adjacent exactly when they are put in the same place, so the blue pens must occupy [tex]4[/tex] different places out of these [tex]9[/tex]. The blue pens are identical, so only the set of chosen places matters, and every admissible arrangement is obtained exactly once:
[tex]\binom{9}{4}=\frac{9\times 8\times 7\times 6}{4!}=126[/tex]

Solution:
The piece has to move [tex]7[/tex] columns to the right and [tex]7[/tex] rows up. Each move changes either the column or the row by [tex]1[/tex], so at least [tex]14[/tex] moves are needed, and [tex]14[/tex] moves are enough.
A path of [tex]14[/tex] moves cannot contain a move left or down: such a move would have to be compensated by an extra move right or up, and the path would be longer than [tex]14[/tex] moves.
Hence the shortest paths are exactly the sequences of [tex]7[/tex] moves “right” and [tex]7[/tex] moves “up” in some order (each of them stays on the board). Such a sequence is determined by choosing which [tex]7[/tex] of the [tex]14[/tex] moves are “right”:
[tex]\binom{14}{7}=3432[/tex]