### The Problem

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation,

^{5}C_{3}= 10.In general, ,where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million:

^{23}C_{10}= 1144066.How many, not necessarily distinct, values of

^{n}C_{r}, for 1 ≤ n ≤ 100, are greater than one-million?

### The Solution

Thankfully, the problem definition has already given us the hard part of this problem.
That is, figuring out the number of combinations for ^{n}C_{r}.

The words "in general" in the problem definition made me nervous, but I couldn't think of any special cases that would apply here.

```
let rec fact n =
match n with
| 0 -> 1I
| 1 -> 1I
| _ -> bigint(n) * fact (n-1)
let rec numCombos n r =
fact n / ((fact r) * (fact (n - r)))
```

The `numCombos`

function returns the number of combinations for a given `n`

and `r`

.

Now we can solve the problem:

```
seq {
for n in 1..100 do
for r in 1..n do
yield (n,r)
}
|> Seq.map (fun (n,r) -> numCombos n r)
|> Seq.filter (fun n -> n > 1000000I)
|> Seq.length
```

The problem definition specifies 1 ≤ n ≤ 100. Therefore 1 ≤ r ≤ n because you can't take more from n than n.

We'll start by generating a sequence of all possible `n`

paired with the possible `r`

values for that `n`

.

Next, we generate the number of combinations for each `(n,r)`

pair.

Finally we filter out the values where the number of combos is more than one million and count them. That is the answer.

Other Posts in This Series