May 4, 2019

# Combinatorics. Intro (with solutions)

I. Imagine you visit an apparel store. After some time you put your eye on 3 different shirts and 5 different trousers.

You like all of them, but you have money to buy only one piece of clothing. How many options do you have?

Solution: There are the total of 3+5=8 pieces of closing. You may choose only one. Obviously, there are only 8 ways you can do this.

II. A friend of yours comes by. You have similar tastes, so she likes the same 3 shirts and 5 trousers as you do. She too has money to buy only one thing.

How many ways do you have to buy a piece of clothing for each one of you? (You may choose independently of each other)

Solution: You have 8 options to choose. Let's call them A, B, C, D, E, F, G and H. Suppose you choose A. Then your friend can choose one of those same 8 options, and your choosings may look like this: AA, AB, AC, AD, AE, AF, AG, AH. If you choose B, your friend still has the same 8 options, so your choosings may look like this: BA, BB, BC, BD, BE, BF, BG, BH. By continuing the argument, we get the following table of possible combinations:

```friend: A   B   C   D   E   F   G   H
you:
A      AA  AB  AC  AD  AE  AF  AG  AH
B      BA  BB  BC  BD  BE  BF  BG  BH
C      CA  CB  CC  CD  CE  CF  CG  CH
D      DA  DB  DC  DD  DE  DF  DG  DH
E      EA  EB  EC  ED  EE  EF  EG  EH
F      FA  FB  FC  FD  FE  FF  FG  FH
G      GA  GB  GC  GD  GE  GF  GG  GH
H      HA  HB  HC  HD  HE  HF  HG  HH
```

So you have 8 options; for each of your options there are 8 options for your friend. Thus there are 8+8+8+8+8+8+8+8=8*8=64 options for two of you to choose your clothing.

III. After some fitting you realise that you don't want to wear the same things.

How many ways do you have to buy a piece of clothing for each one of you? (You are not allowed to buy the same shirt or the same trousers)

Solution: If you choose A, then your friend is left with options B, C, D, E, F, G and H - 7 in total. If you choose B, then your friend is left with options A, C, D, E, F, G and H - still 7 options. If we continue the argument, we get the following table of combinations:

```friend: A   B   C   D   E   F   G   H
you:
A      --  AB  AC  AD  AE  AF  AG  AH
B      BA  --  BC  BD  BE  BF  BG  BH
C      CA  CB  --  CD  CE  CF  CG  CH
D      DA  DB  DC  --  DE  DF  DG  DH
E      EA  EB  EC  ED  --  EF  EG  EH
F      FA  FB  FC  FD  FE  --  FG  FH
G      GA  GB  GC  GD  GE  GF  --  GH
H      HA  HB  HC  HD  HE  HF  HG  --
```

So you have 8 options; for each of your options there are 7 options for your friend. Thus there are 7+7+7+7+7+7+7+7=8*7=56 options.

IV. A manager comes to you and says they have a special offer today. You may buy a shirt and get trousers for free.

How many options are there to pick a pair "shirt-trousers"?

Solution: Let A, B, C be the shirts, the rest are trousers. If you choose a shirt A, then you may choose D, E, F, G or H - 5 options to choose trousers. The same if you choose B or C. Thus the table of combinations looks like this:

```trousers:  D   E   F   G   H
shirt:
A       AD  AE  AF  AG  AH
B       BD  BE  BF  BG  BH
C       CD  CE  CF  CG  CH
```

So you may choose one of 3 shirts, for each of each you have 5 options to choose trousers; so there are in total 5+5+5 =3*5 =15 options to choose a pair "shirt-trousers".

V. You and your friend decide to use the offer, but you still don't want to wear the same shirt or trousers. So you have to choose different shirts and different trousers.

How many options do you have?

Solution: Suppose you get to choose first. Let's say you choose the shirt A and the trousers D. Then your friend is left with 2 options for shirts and 4 options for trousers. In total she has 2*4=8 options to choose her pair "shirt-trousers". Even if you choose another shirt or another trousers, your friend still has 8 options. You have 15 ways to choose your pair, for each of which there are 8 choices for her, so there are 8+8+8+8+8+8+8+8+8+8+8+8+8+8+8 =15*8 =130 possible combinations.