서로 다른 책 n권으로 두 가지 계획을 세우는 가상 독서 활동이에요. 첫째는 모든 책을 한 번씩 읽을 순서를 정하는 것이고, 둘째는 읽을 책만 고르고 순서는 정하지 않는 거예요. 둘째에서는 한 권도 고르지 않는 계획도 포함해요. 어떤 쪽의 가능한 계획이 더 많을까요?
전체 순서는 n!=1×2×…×n가지예요. 고르기에서는 각 책마다 선택 또는 제외의 두 가능성이 있으므로2ⁿ가지예요. 세 권이면6과8이라서 고르기가 더 많아요. 그런데 네 권에서는24와16으로 순서가 앞서요.
네 권만 확인했다고 그 뒤까지 단정할 수는 없어요. k≥4에서 k!>2ᵏ라고 가정하고 한 권을 더 넣어 볼까요? 모든 순서 수는 k+1배가 되고, 선택 수는2배가 돼요. k+1은5이상이어서 순서 쪽의 증가 배수가 더 커요.
오른쪽은2ᵏ⁺¹입니다. 따라서 네 권에서 시작한 부등식은 한 권을 늘릴 때마다 유지되고, 모든 정수 n≥4에서 순서를 정하는 방법이 더 많아요. 이것이 시작 사례와 전달 단계를 결합하는 귀납법이에요.
작은 수량에서는 고르기가 더 많고 이후에는 배열이 더 많을 수 있어요. 책이 하나 늘 때 두 계획이 각각 몇 배 늘어나는지 비교해야 해요. 책을 반복 사용하거나 읽는 순서를 무시한다면 첫째의 n! 계산부터 달라져요.
참고한 수학 개념: Mathigon · Axioms and Proofs.
이 글의 생활 상황과 계산 예시는 수학 이야기에서 새로 구성했습니다.