1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.
123, 124, 125, 134, 135, 145, 234, 235, 245, 345
조합론이라는 분야에서는 이것을 5C3 = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다.
nCr =
r!(n−r)!, 단 r ≤ n 이고, n! = n×(n−1)×…×3×2×1 이며 0! = 1. 이 값은 n = 23 에 이르러서야 23C10 = 1144066 으로 처음 1백만을 넘게 됩니다.
1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::NumSeq::Factorials; my $s = Math::NumSeq::Factorials->new; my $c = 0; for my $n (1..100) { for my $r (1..$n) { $c++ if (1000000 < $s->ith($n)/(($s->ith($r)*($s->ith($n-$r))))); } } say $c; |