Problem 53 "Combinatoric selections"

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, \( \binom{5}{3} = 10 \).

In general, \( \binom{n}{r} = \dfrac{n!}{r!(n-r)!} \), where \(r \le n \), \( n! = n \times (n-1) \times ... \times 3 \times 2 \times 1 \), and \(0! = 1\).

It is not until \(n = 23\), that a value exceeds one-million: \( \binom{23}{10} = 1144066 \).

How many, not necessarily distinct, values of \( \binom{n}{r} \) for\( 1 \le n \le 100 \), are greater than one-million?

問 53 「組み合わせ選択」

12345から3つ選ぶ選び方は10通りである.

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

組み合わせでは, 以下の記法を用いてこのことを表す: \( \binom{5}{3} = 10 \).

一般に, \(r \le n \) について \( \binom{n}{r} = \dfrac{n!}{r!(n-r)!} \) である.

ここで, \( n! = n \times (n-1) \times ... \times 3 \times 2 \times 1 \) と階乗を定義する.

n = 23 になるまで, これらの値が100万を超えることはない: \( \binom{23}{10} = 1144066 \).

1 ≤ n ≤ 100 について, 100万を超える \( \binom{n}{r} \) は何通りあるか?

const ONE_MILLION: u32 = 1_000_000;

fn main() {
    let mut count = 0u32;
    let mut prev = [0u32; 101];
    let mut line = [0u32; 101];
    prev[0] = 1;
    for _ in 0..100 {
        line[0] = 1;
        for (i, &v) in prev.iter().enumerate() {
            if v == 0 {
                break;
            }
            let binom = v + prev[i + 1];
            line[i + 1] = if binom > ONE_MILLION {
                count += 1;
                ONE_MILLION
            } else {
                binom
            }
        }
        prev.copy_from_slice(&line);
    }

    println!("{}", count);
    assert_eq!(count, 4075);
}