List 5 of Problems. Topic 2.

1. How many permutations of the letters ‘ABCDEF’ contain the letters ‘DEF’ together in any order?

2. Let us consider the set Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

a) Calculate how many four-element strings of Σ the number 7 appears exactly once.
b) Calculate how many four-element strings of Σ 7 appears at most once.
c) Calculate how many four-element strings of Σ 7 appears at least once.

3. Let us consider the number 29 338 848 000 = 28 35 53 73 11

a) How many positive divisors does this number have?

b) How many are multiples of 99?
c) And of 39?

4. A bus with 32 seats (16 on the right and 16 on the left) transports 28 students of the E.T.S. Computer
Engineering on their final year trip. How many ways can they sit if three of them can only sit on the
right and five of them only on the left?

5. A robbery has taken place and the police question two witnesses about the number plate of the getaway
vehicle (four digits and two letters of an alphabet of 26).
The first witness claims that the second letter of the number plate was an O or a Q and that the last
digit was either a 3 or an 8.
The second witness states that the first letter was a C or a G and that the first digit was definitely a 7.

a) How many different plates will the police have to check?

b) If on further investigation the police also find that the number plate does not end in 53 and does
not begin in 78, how many checks will have to be made in this case?

6. A committee of six people A, B, C, D, E, F must choose a chairperson, a secretary and a treasurer. How
many ways can the choice be made? How many if the chairperson must be A or B? How many if E must
hold one of the offices? How many if A and F must hold one office?

7. From a group of 9 people you want to elect a committee with 4 members, but there are two people who
could not be on the committee together, how many ways can the committee be formed?

8. An exam consists of 10 questions. Find how many ways the test can be answered if

a) at least 6 questions must be answered.

b) at least 6 must be answered, of which two are compulsory from the first five and at least two must
be from the last five.

9. Find how many natural numbers between one thousand and one hundred thousand have the property
that the sum of their digits is 9 and they are all non-zero.

1
10. A large number of red, blue and green balls are available. How many ways can you select nine balls if you
must have at least one of each colour?

11. A class of 43 students votes to choose the date of an exam. Each student votes for one of the five possible
days. Determine how many results can be obtained in the vote in the following cases:

a) Every day gets at least one vote.

b) At least one day receives more than eight votes.

12. Out of a total of 20 persons, three commissions of 4, 5 and 6 persons respectively are to be elected.

a) In how many ways is it possible to form commissions?

b) And if each person can only belong to one commission.

13. Seven friends arrive at a hotel and only two double rooms and one triple room are available. How many
ways can they divide them up?

14. In the XY plane, paths are considered to move one step at a time (to the right or upwards).

a) How many different paths are there from (0, 0) to (7, 7)?
b) How many different paths are there from (2, 7) to (9, 14).
c) How many of these paths pass through (4, 10) ?

15. Consider the following numbers: -5, -4, -3, -2, -1, 1, 2, 3, 4. In how many ways can four numbers be
selected so that their product is positive?

16. A computer network consists of six computers. Each computer can be connected to several computers or
be disconnected. Show that there are at least two computers in the network that have the same number
of connections.

17. How many eight-bit strings are there? How many of them start with 101? How many of them start with
101 or have the fourth bit equal to 1?

18. Find how many integers not greater than 100 are prime.

19. Determine the number of positive integers less than 600 that are coprime with 600.

20. How many four-digit numbers have at least one digit that is 0, at least one digit that is 1 and at least
one digit that is 2?

21. (Maxima) Calculate the number of non-negative integer solutions to the equation

x1 + x2 + x3 + x4 = 29

How many of them satisfy 2 ≤ x1 ≤ 16, 0 ≤ x2 ≤ 7, 0 ≤ x3 ≤ 9, 1 ≤ x4 ≤ 15?

22. How many permutations of the PROGRAMMING letters do not have two consecutive letters that are
the same?

2
23. a) In how many orderings of the word NEWSPAPER do the N and A appear together?
b) In how many are all the vowels together?
c) In how many are there no two consecutive letters alike?

24. How many ways can the numbers 1, 2, · · · 10 be arranged so that none of them occupy their natural
position?

25. A researcher has 5 assistants and is involved in a project that requires the synthesis of 9 compounds.
In how many ways can the researcher assign these syntheses to the 5 assistants so that each of them
works on at least one?

26. A company hires eleven new employees for its four offices. How many ways is it possible to assign them?
What if each office must receive at least one new employee?

27. A first-year student is going to take four exams: MD, CC, FP and FF. He has seven days in a week during
which he will revise all the subjects, dedicating each day to the study of a single subject (without resting
any day).

a) How many different ways can you organise your study, if you consider the days indistinguishable?
b) What if we consider the days to be different?

28. Seven balls of different colours and four containers numbered I, II, III, IV are considered.

a) How many ways can the balls be distributed without leaving any empty containers?
b) If one of the balls is white, how many ways can we make the distribution so that there is no empty
container and the white ball is in container III?
c) If the numbering of the containers is removed so that it is not possible to differentiate them, in how
many ways can they be distributed, with the possibility of empty container(s)?

29. The Three Wise Men bring different toys to different children. On the way they decide to leave exactly
one child without a toy and distribute all the toys among the remaining children. How many ways can
they do this?

30. A company wants to distribute 100 memory sticks among its four offices so that each office receives at
least 5, but no more than 40. Knowing that they are delivered in packs of five, how many ways can the
distribution be done?

31. A telecommunications company wishes to install 210 mobile telephone antennas and 600 television satellite
dishes in Malaga. The city of Malaga is divided into 40 sectors. To ensure that there are no areas without
coverage, each sector must have a minimum of 10 television antennas and 4 telephone antennas. On the
other hand, municipal by-laws prevent the placement of more than 7 telephone antennas in each sector.
Determine the number of different ways of placing the antennas in compliance with the above restrictions,
knowing that television antennas are indistinguishable from each other and telephone antennas are also
indistinguishable from each other, but obviously one type of antenna can be distinguished from another.

32. Find an explicit formula for the following sequences:

3
 a) u0 = 1, u1 = 2 y un = −2un−1 + 3un−2 for all n ≥ 2.
b) u0 = 0, u1 = 1 y un − 5un−1 + 6un−2 = 0 for all n ≥ 2.
c) u0 = 1, u1 = 3 y un − 4un−1 + 4un−2 = 0 for all n ≥ 2.

33. It is known that the roots of the characteristic equation of a linear homogeneous recurrence are: −2
triple, −1 double and 3 single. Of what order is the recurrence? What form does the general solution
have? Justify your answers.

34. Find a homogeneous linear recurrence relation whose general term is

a) un = 3n+2 + n3n−2
b) un = 2n+1 + n2n−1

35. Find an explicit formula for the following sequences:

a) u0 = 0, un − 2un−1 = 1 for all n ≥ 1,

b) u0 = 0, u1 = 2 y un + 4un−1 + 4un−2 = n2 for all n ≥ 2.
c) u0 = 2 y un − un−1 = 3n2 for all n ≥ 1.
d ) u0 = 1 y un − 2un−1 = 2n−1 for all n ≥ 1.
e) u0 = 0, u1 = 1 y un + 3un−1 + 2un−2 = 3n−2 for all n ∈ N.
f ) u0 = 2 y un − 3un−1 = 5 · 7n for all n ≥ 1.
g) u0 = 3, u1 = −2 y un − 4un−1 + 4un−2 = (n − 2)2n−2 for all n ≥ 0.
h) u0 = 1, u1 = 0 y un + 6un−1 + 9un−2 = (n − 1)3n for all n ≥ 2

36. Pose and solve a recurrence equation to find the general term of the sequence
n
X
un = k · 2k = 1 · 21 + 2 · 22 + 3 · 23 + · · · + n · 2n
k=1

37. Consider the sequence qn of the number of strings of length n that can be formed from symbols of the
alphabet Σ = 0, 1 with the property that they do not have two consecutive zeros. Pose and solve a linear
recurrence for qn .

38. We want to cover a rectangular board of size 2 using pieces of size 1 and 2. Use a recursively defined
sequence to determine how many ways the board can be covered.

39. Motorbikes and passenger cars are parked in a row of spaces. Use a recurrence relation to determine the
number of ways to park these vehicles, knowing that all spaces must be filled and that each motorbike
occupies one space and each passenger car two. (Assume that all motorbikes are equal and all passenger
cars are equal).

40. A boy sets out to buy sweets from a vending machine. He likes popcorn, which costs 1 coin each, and two
kinds of cakes, which cost 2 coins each. How many ways can he get the sweets he chooses by spending
coins?