Patterns and Combinatorics

0. Warm-up. Count the rows in Pascal’s triangle starting from 0. Recall that the number found on the -th horizontal row and -th slanted row is

the number of ways to choose a group of k objects from among n given objects.

For example, is located in the diagram below

Find the following numbers in Pascal’s triangle and verify the formula above for them:

1. In a Swiss-system tournament with 64 participants, there are several rounds. In each round players are divided into 32 pairs, each pair plays one game until a winner is decided. The winner gets 1 point and the loser 0 points for that round. In Round 1, players are paired randomly. In all the other rounds, the pairs are chosen so that the two opponents have the exact same overall score.

a) Construct a triangle as follows: write the total number of players on row 1. On row 2, write the numbers of people with a score of 1 and with a score of 0 after Round 1:

64

32 32

16 32 16

On row 3, write the numbers of people with a score of 2, with a score of 1, and with a score of 0 after Round 2. Continueuntil a winner emerges. How many games were played in total?

b) Compare your triangle with Pascal’s triangle. What do you notice? Can you explain?

2. In how many ways can a team of 10 people be formed out of 10 girls and 10 boys present, if each group must contain at least 3 boys and at least 3 girls?

3. At a party, Sorcha is asked to randomly select 3 people for a grand prize. She counts how many possible ways there are to do that. When suddenly 2 people leave the room, she realizes that she must adjust her count down by 81 possible triplets. How many people were in the room at the beginning?

4. a) Recall the formula . Can you find the result of the sum in Pascal’s triangle? Can you explain?

b) Calculate Can you find a formula for the sum of the first odd numbers?

5. a) Write down each of the numbers in the red line as for someand What can you say about their sum? Can you explain your result based on the properties of Pascal’s triangle?

b) Calculate . How is this related to the previous question?

c) Can you find a formula for ?

5. a) Write down each of the numbers in the yellow line as for someand What can you say about their sum? Can you explain?

b)Calculate How is this related to the sum in a)?

6. a) Based on the pattern below, can you write down a formula for

b) How about a formula for Can you prove it?