1

Imagine you have this trivial problem:

How many ways can n people pick two flavours from a choice of k flavours (with no repetition on the flavours).

Suppose that you think the answer is ${k \choose 2}^n$

How do you write a formal proof to show this? Do you just state the steps? For example, would this be suffice:

Lemma: There are ${k \choose 2}^n$ ways for n people to pick two flavours from k flavours.

Proof. There are ${k \choose 2}$ ways for a person to pick two flavours. There are n people, so there are ${k \choose 2}^n$ ways.

I know this is a trivial example, but I am working on a more complex problem and I wanted some advice on how to formally state the proof.

S0rin
  • 421

1 Answers1

2

In combinatorics, you focus on the structure of the problem and then work out the formula. For example, when you say there are $k \choose 2$ ways to choose 2 flavors, that's the true number by definition even if you don't know the formula for $k \choose 2$. Some combinatorial quantities like Stirling numbers of the second kind don't even have any simple formulas, yet people prove combinatorial formulas that have Stirling numbers in them. There are some basic concepts in combinatorial reasoning, and you appealed to one of them to get ${k \choose 2}^n$, namely the multiplication principle in counting that if there are $N_1$ possible outcomes for one event, and $N_2$ possible outcomes for another event, then there are $N_1 \times N_2$ possible outcomes when the events are considered together as a joint event. There are other basic examples too, like the inclusion-exclusion principle. "Hard" combinatorial proofs rely on more than just applying basic counting rules though. They often prove a hard-to-see bijection (one-to-one correspondance) between one type of object that seems hard to count and another type of object that's easier to count. Then you know the formulas for counting the two types of objects are the same, so you can get a formula for the hard case.

user2566092
  • 26,142