이 강의는 세는 법을 다룹니다. 지금까지는 값을 구하는 계산이었다면 여기서는 "몇 가지가 있는가"를 묻습니다. 세는 일이 왜 수학의 한 분야가 되는지는 규모를 보면 알 수 있습니다. 카드 장을 늘어놓는 방법은 약 가지라 하나씩 세는 것이 불가능하므로, 세지 않고 개수를 구하는 방법이 필요합니다.
경우의 수는 확률의 바탕입니다. 121강 이후의 확률에서 "모든 경우가 똑같이 일어날 법할 때 확률은 원하는 경우의 수를 전체 경우의 수로 나눈 것"이라고 정의하는데, 그 두 수를 세는 도구가 이 강의에서 만들어집니다. 이 강의도 문제를 먼저 풀고 풀이에서 개념을 끌어냅니다.
문제. 서울에서 대전으로 가는 방법이 기차 가지와 버스 가지이고, 대전에서 부산으로 가는 방법이 기차 가지입니다. 서울에서 대전까지 가는 방법의 수와, 서울에서 대전을 거쳐 부산까지 가는 방법의 수를 각각 구하세요.
생각의 실마리. 두 질문의 구조가 다릅니다. 앞은 기차나 버스 중 하나를 고르는 것이고, 뒤는 앞 구간과 뒤 구간을 둘 다 정해야 합니다. "또는"인지 "그리고"인지 구분합니다.
풀이. 서울에서 대전까지는 기차를 타거나 버스를 타거나 둘 중 하나입니다. 두 방법이 겹치지 않으므로 더합니다.
서울에서 부산까지는 앞 구간을 정하고 그리고 뒤 구간도 정해야 합니다. 앞 구간 가지 각각에 대해 뒤 구간이 가지씩 있으므로 곱합니다.
이 문제에서 배우는 것: 합의 법칙과 곱의 법칙.
경우를 세는 두 가지 기본 규칙입니다.
두 법칙을 고르는 기준은 문제에 숨은 접속사입니다. "또는"이면 더하고 "그리고"면 곱합니다.
합의 법칙에는 조건이 하나 붙어 있습니다. 두 경우가 겹치지 않아야 합니다. 겹치면 중복해 세게 되므로 겹친 만큼 빼야 하고, 그것이 문제 5의 포함배제입니다.
곱의 법칙에도 조건이 있습니다. 앞의 선택이 무엇이든 뒤의 선택지 개수가 같아야 합니다. 앞의 결과에 따라 뒤의 개수가 달라지면 곱할 수 없고 경우를 나눠야 합니다.
바로 확인.
확인 1-1. (기초) 티셔츠 벌과 바지 벌로 만들 수 있는 옷차림의 수를 구하세요.
답. 가지
풀이. 티셔츠를 고르고 그리고 바지도 골라야 하므로 입니다.
확인 1-2. (표준) 부터 까지의 수 중 짝수이거나 보다 큰 수의 개수를 구하세요.
답. 개
풀이. 짝수는 의 개이고 보다 큰 수는 의 개인데 과 이 겹칩니다. 겹친 개를 빼면 입니다. 직접 세면 의 개로 맞습니다.
확인 1-3. (표준) 동전 하나와 주사위 하나를 던질 때 나올 수 있는 결과의 수를 구하세요.
답. 가지
풀이. 동전이 가지이고 각각에 대해 주사위가 가지이므로 입니다.
문제. 명 중 명을 뽑아 회장, 부회장, 총무를 정하는 방법의 수를 구하세요.
생각의 실마리. 자리를 하나씩 채워 갑니다. 회장을 먼저 정하면 남은 사람이 줄어들고, 부회장을 정하면 또 줄어듭니다. 각 단계의 선택지 수를 세어 곱합니다.
풀이. 회장은 명 중 아무나 될 수 있으므로 가지입니다. 회장이 정해지면 부회장은 남은 명 중에서 뽑으므로 가지입니다. 총무는 남은 명 중에서 뽑으므로 가지입니다.
여기서 곱의 법칙을 쓸 수 있는 이유를 확인합니다. 회장이 누구든 남은 사람이 항상 명이므로 뒤의 선택지 개수가 앞의 결과와 무관합니다.
이 문제에서 배우는 것: 계승과 순열.
개를 모두 늘어놓는 방법의 수를 계승이라 하고 으로 씁니다.
로 정하는 이유는 13강에서 을 정한 것과 같습니다. 뒤에 나올 공식들이 계속 성립하도록 강제된 값이며, "아무것도 늘어놓지 않는 방법이 한 가지"라고 읽어도 됩니다.
서로 다른 개에서 개를 골라 순서를 따져 늘어놓는 방법의 수를 순열이라 하고 다음과 같이 씁니다.
곱하는 인수가 개라는 점을 기억합니다. 문제 2에서 이라 세 개를 곱했습니다. 마지막 인수가 이지 이 아닌 것도 자주 틀리는 곳입니다.
이면 입니다. 공식으로 확인하면 이며, 여기서 이 필요했음이 드러납니다.
바로 확인.
확인 2-1. (기초) 을 계산하세요.
답.
풀이. 입니다.
확인 2-2. (기초) 를 계산하세요.
답.
풀이. 입니다. 인수가 두 개입니다.
확인 2-3. (표준) 명을 일렬로 세우되 특정 두 사람이 이웃하도록 하는 방법의 수를 구하세요.
답. 가지
풀이. 두 사람을 한 덩어리로 묶으면 개 단위를 늘어놓는 것이라 가지입니다. 덩어리 안에서 두 사람의 순서가 가지이므로 입니다.
문제. 명 중 명을 뽑아 청소 당번을 정하는 방법의 수를 구하세요.
생각의 실마리. 문제 2와 무엇이 다른지 봅니다. 회장, 부회장, 총무는 누가 어느 자리인지가 중요했지만 당번은 뽑히기만 하면 역할이 같습니다. 문제 2의 답에서 무엇을 나눠야 하는지 생각합니다.
풀이. 문제 2에서 가지를 셌습니다. 그런데 같은 세 사람 가 뽑힌 경우를 보면, 역할을 바꿔 배정한 가지가 모두 따로 세어져 있습니다. 당번에서는 이 가지가 모두 같은 결과입니다.
따라서 중복된 만큼 나눕니다.
이 문제에서 배우는 것: 조합.
서로 다른 개에서 개를 순서를 따지지 않고 고르는 방법의 수를 조합이라 하고 다음과 같이 씁니다.
순열을 로 나눈 것이 조합입니다. 고른 개를 늘어놓는 방법이 가지인데 조합에서는 그것들이 모두 같은 하나로 취급되기 때문입니다.
순열과 조합을 고르는 기준은 하나입니다. 순서가 결과를 바꾸는가.
| 상황 | 순서 | 도구 |
|---|---|---|
| 회장, 부회장 정하기 | 바뀝니다 | 순열 |
| 대표 명 뽑기 | 안 바뀝니다 | 조합 |
| 자리에 앉히기 | 바뀝니다 | 순열 |
| 팀 나누기 | 안 바뀝니다 | 조합 |
조합의 성질 두 가지를 기억해 두면 계산이 짧아집니다.
앞은 "개를 고르는 것과 남길 개를 고르는 것이 같다"는 뜻입니다. 을 계산할 때 으로 바꾸면 훨씬 빠릅니다. 뒤는 특정 원소를 고르는 경우와 고르지 않는 경우로 나눈 것이며, 파스칼의 삼각형을 만드는 규칙입니다. 20강에서 다시 쓰입니다.
바로 확인.
확인 3-1. (기초) 를 계산하세요.
답.
풀이. 입니다.
확인 3-2. (기초) 을 계산하세요.
답.
풀이. 입니다.
확인 3-3. (표준) 남자 명, 여자 명 중 남자 명과 여자 명을 뽑는 방법의 수를 구하세요.
답. 가지
풀이. 남자에서 가지, 여자에서 가지이고 둘을 모두 정해야 하므로 곱해서 입니다.
문제. 글자 를 일렬로 배열하는 방법의 수를 구하세요.
생각의 실마리. 여섯 글자가 모두 다르다면 입니다. 그런데 같은 글자끼리는 자리를 바꿔도 결과가 같습니다. 문제 3에서 중복을 나눈 방식을 그대로 적용합니다.
풀이. 여섯 글자에 임시로 번호를 붙여 모두 다르다고 하면 가지입니다.
이제 번호를 지웁니다. 같은 글자 두 개는 자리를 바꿔도 같은 배열이므로 가지가 하나로 뭉쳐집니다. 세 개는 가지가 하나로 뭉쳐집니다. 는 하나뿐이라 입니다.
이 문제에서 배우는 것: 같은 것이 있는 순열과 원순열.
개 중 같은 것이 각각 개, 개, 개씩 있을 때(단 ) 일렬로 배열하는 방법의 수는 다음과 같습니다.
원리는 하나입니다. 모두 다르다고 보고 센 뒤 중복해 센 만큼 나눕니다. 조합도 같은 원리였습니다. 실제로 은 "가 개, 가 개인 배열의 수" 과 같은 식입니다. 고르는 것과 표시를 배열하는 것이 같은 문제입니다.
원순열도 같은 사고로 처리합니다. 명을 원탁에 앉히는 경우, 일렬로 세운 가지 중에서 전체를 한 칸씩 돌린 가지가 모두 같은 배치입니다. 원탁에는 기준이 되는 자리가 없기 때문입니다.
한 사람을 기준으로 고정하고 나머지를 늘어놓는다고 봐도 같은 결과입니다.
중복순열은 반대로 나누지 않습니다. 같은 것을 여러 번 골라도 되는 경우, 예를 들어 개에서 중복을 허용해 개를 뽑아 나열하면 매 자리마다 가지씩이므로 입니다.
바로 확인.
확인 4-1. (기초) 글자 를 배열하는 방법의 수를 구하세요.
답. 가지
풀이. 입니다.
확인 4-2. (표준) 명을 원탁에 앉히는 방법의 수를 구하세요.
답. 가지
풀이. 입니다.
확인 4-3. (표준) 과 로 이루어진 길이 의 문자열의 개수를 구하세요.
답. 개
풀이. 각 자리마다 가지이므로 중복순열로 입니다.
문제. 명을 일렬로 세울 때 특정 두 사람 갑과 을이 이웃하지 않는 방법의 수를 구하세요.
생각의 실마리. 이웃하지 않는 배열을 직접 세려면 경우가 복잡합니다. 반대쪽인 "이웃하는" 경우는 확인 2-3에서 이미 세는 법을 익혔습니다. 전체에서 반대쪽을 빼는 방법을 생각합니다.
풀이. 전체 배열은 가지입니다.
이웃하는 경우는 두 사람을 묶어 개 단위를 늘어놓고 덩어리 안에서 순서를 정하므로 가지입니다.
이웃하지 않는 경우는 전체에서 이웃하는 경우를 뺍니다.
이 문제에서 배우는 것: 여사건과 포함배제.
"~하지 않는" 또는 "적어도 하나는 ~인" 조건은 직접 세면 경우가 갈라져 복잡합니다. 이럴 때 전체에서 반대쪽을 빼는 것이 표준 전략입니다.
"적어도 하나"의 반대는 "하나도 없다"로 단일한 조건이 되므로 세기 쉬워집니다. 이 사고는 121강 이후 확률에서 여사건으로 다시 나옵니다.
겹치는 경우를 다루는 포함배제 원리도 같은 계열입니다. 두 조건 중 적어도 하나를 만족하는 개수는 다음과 같습니다.
세 조건이면 두 개씩의 교집합을 빼고 세 개 모두의 교집합을 다시 더합니다.
이유는 중복해 센 만큼 걷어 내는 것입니다. 두 조건을 모두 만족하는 것은 앞의 두 항에서 두 번 세어졌으므로 한 번 빼고, 세 조건을 모두 만족하는 것은 세 번 더해지고 세 번 빠져 사라졌으므로 다시 한 번 더합니다.
한 가지 더 자주 쓰는 수법이 있습니다. 이웃하지 않게 배열할 때는 먼저 나머지를 배열하고 그 사이에 끼워 넣는 방법입니다. 확인 5-3에서 확인합니다.
바로 확인.
확인 5-1. (기초) 부터 까지 중 의 배수가 아닌 수의 개수를 구하세요.
답. 개
풀이. 의 배수는 의 개이므로 입니다.
확인 5-2. (표준) 부터 까지 중 또는 의 배수인 수의 개수를 구하세요.
답. 개
풀이. 의 배수 개, 의 배수 개, 의 배수 개입니다. 포함배제로 입니다.
확인 5-3. (표준) 남자 명과 여자 명을 일렬로 세울 때 여자끼리 이웃하지 않는 방법의 수를 구하세요.
답. 가지
풀이. 먼저 남자 명을 세우면 가지입니다. 남자들이 만드는 자리는 양 끝과 사이를 합해 곳이고, 그중 두 곳을 골라 여자를 넣으면 순서를 따지므로 가지입니다. 곱하면 입니다.
| 상황 | 도구 | 요령 |
|---|---|---|
| "또는"이며 겹치지 않음 | 합의 법칙 | 더합니다 |
| "그리고"로 잇달아 | 곱의 법칙 | 뒤의 선택지 개수가 일정한지 확인합니다 |
| 순서가 결과를 바꿈 | 순열 | 이며 인수가 개입니다 |
| 순서가 무관 | 조합 | \binom{n}{r}=\dfrac{{}_{n}P_{r}} |
| 이웃해야 함 | 묶기 | 덩어리로 묶고 안쪽 순서를 곱합니다 |
| 같은 것이 섞임 | 나누기 | 모두 다르다 보고 센 뒤 로 나눕니다 |
| 원탁 | 원순열 | 이며 한 사람을 고정합니다 |
| 중복 허용 | 중복순열 | 이며 나누지 않습니다 |
| "아니다", "적어도" | 여사건 | 전체에서 반대쪽을 뺍니다 |
| 조건이 겹침 | 포함배제 | 중복해 센 만큼 걷어 냅니다 |
| 이웃하지 않아야 함 | 사이에 끼우기 | 나머지를 먼저 세우고 빈자리를 고릅니다 |
핵심 습관은 이렇습니다. 세기 전에 순서가 중요한지 먼저 묻고, 같은 것이 있으면 나누고, "아니다"가 보이면 전체에서 빼는 쪽을 시도합니다.
문제 6. (기초) 을 계산하세요.
답.
풀이. 입니다.
문제 7. (기초) 을 계산하세요.
답.
풀이. 입니다.
문제 8. (기초) 을 계산하세요.
답.
풀이. 입니다.
문제 9. (표준) 명 중 명을 뽑아 일렬로 세우는 방법의 수를 구하세요.
답. 가지
풀이. 입니다.
문제 10. (표준) 글자 를 배열하는 방법의 수를 구하세요.
답. 가지
풀이. 가 개, 이 개, 가 개이므로 입니다.
문제 11. (표준) 명을 원탁에 앉히는 방법의 수를 구하세요.
답. 가지
풀이. 입니다.
문제 12. (표준) 에서 서로 다른 숫자로 세 자리 자연수를 만드는 방법의 수를 구하세요.
답. 개
풀이. 백의 자리는 을 뺀 가지입니다. 십의 자리는 을 포함해 남은 가지, 일의 자리는 남은 가지입니다. 입니다.
문제 13. (표준) 명 중 명을 뽑아 조를 만들 때 특정 인물 갑이 포함되는 경우의 수를 구하세요.
답. 가지
풀이. 갑을 이미 넣었다고 보고 나머지 명을 명 중에서 뽑으므로 입니다.
문제 14. (표준) 명을 일렬로 세울 때 특정 세 사람이 모두 이웃하는 방법의 수를 구하세요.
답. 가지
풀이. 세 사람을 한 덩어리로 묶으면 개 단위이므로 가지이고, 덩어리 안에서 가지입니다. 입니다.
문제 15. (표준) 부터 까지 중 의 배수도 의 배수도 아닌 수의 개수를 구하세요.
답. 개
풀이. 의 배수는 개, 의 배수는 개, 둘 다인 의 배수는 개입니다. 포함배제로 또는 의 배수는 개이므로 나머지는 개입니다.
문제 16. (심화) 서로 다른 명을 명씩 세 조로 나누는 방법의 수를 구하세요. 세 조는 구분하지 않습니다.
답. 가지
풀이. 순서를 매겨 뽑으면 입니다. 그런데 세 조의 순서 가지가 모두 같은 분할이므로 나눕니다. 입니다.
문제 17. (심화) 격자에서 부터 까지 오른쪽 또는 위로만 이동하는 최단경로의 수를 구하세요.
답. 가지
풀이. 오른쪽으로 번, 위로 번 이동해야 하므로 총 번의 이동입니다. 개의 자리 중 오른쪽 이동이 들어갈 자리를 고르면 경로가 정해지므로 입니다. 같은 것이 있는 순열로 보면 로 같은 식입니다.
문제 18. (심화) 명이 각자 자기 이름표를 무작위로 하나씩 집을 때 아무도 자기 이름표를 집지 않는 방법의 수를 구하세요.
답. 가지
풀이. 포함배제를 씁니다. 전체는 입니다. 특정 명이 자기 것을 집는 경우는 나머지를 자유롭게 배열해 가지이고, 그런 명을 고르는 방법이 가지입니다. 적어도 한 명이 자기 것을 집는 경우는 입니다. 따라서 아무도 집지 않는 경우는 입니다.
드릴에서는 공식을 골라 개수를 셌습니다. 이 절에서는 조합 공식이 왜 그런 꼴인지, 조합의 두 성질이 어떤 셈을 나타내는지를 확인합니다. 마지막 문항은 순열과 조합을 잘못 고르는 흔한 방식을 반례로 잡아냅니다.
심화 1. (조합 공식 유도) 을 두 가지 방법으로 유도하세요.
답. 순열을 로 나누거나, 같은 것이 있는 순열로 보면 됩니다.
풀이. 첫째 방법입니다. 개에서 개를 골라 늘어놓는 방법이 가지인데, 고른 개를 늘어놓는 방법이 가지이므로 순서를 무시하면 개씩 같은 것이 됩니다. 나누면 원하는 식입니다. 둘째 방법입니다. 개 각각에 "뽑음"과 "안 뽑음" 표를 붙인다고 봅니다. "뽑음"이 개, "안 뽑음"이 개인 표의 배열이 곧 하나의 선택에 대응하므로, 같은 것이 있는 순열로 입니다.
남는 것. 두 유도가 같은 답을 주는 것은 우연이 아닙니다. "고르기"와 "표시를 배열하기"가 같은 문제이기 때문이며, 문제 17의 격자 경로가 정확히 이 대응을 씁니다. 세는 문제에서 서로 다른 두 상황이 같은 답을 주면 대개 둘 사이에 일대일대응이 있습니다.
심화 2. (파스칼 항등식) 을 셈으로 설명하세요.
답. 특정 원소를 고르는 경우와 고르지 않는 경우로 나눈 것입니다.
풀이. 개 중 하나를 정해 라 부릅니다. 개를 고르는 모든 방법은 를 포함하는 경우와 포함하지 않는 경우로 정확히 둘로 갈립니다. 를 포함하면 나머지 개를 를 뺀 개에서 고르므로 가지입니다. 를 포함하지 않으면 개 모두를 개에서 고르므로 가지입니다. 두 경우가 겹치지 않고 빠짐없이 전체를 덮으므로 합의 법칙으로 더합니다.
남는 것. 식을 전개해 계산으로 확인할 수도 있지만 셈으로 설명하는 편이 훨씬 짧고 뜻이 분명합니다. 이렇게 개수를 두 가지 방법으로 세어 항등식을 증명하는 방식을 조합적 증명이라 하며, 20강의 이항정리에서도 계속 쓰입니다.
심화 3. (대칭성) 을 셈으로 설명하고, 이 성질이 계산을 어떻게 줄이는지 예를 드세요.
답. 고를 것을 정하는 것과 남길 것을 정하는 것이 같은 일이기 때문입니다.
풀이. 개에서 개를 고르면 나머지 개가 자동으로 정해집니다. 반대로 남길 개를 정하면 고를 개가 정해집니다. 두 방식이 서로를 정확히 하나씩 짝지으므로 개수가 같습니다. 계산 예로 을 봅니다. 그대로 계산하면 인수가 개지만 으로 바꾸면 세 개만 곱하면 됩니다.
남는 것. 이 보다 크면 언제나 작은 쪽으로 바꿔 계산합니다. 이 대칭성 때문에 조합의 값은 가운데에서 가장 크고 양 끝으로 갈수록 작아지는 종 모양이 되며, 그 모양이 20강의 파스칼 삼각형과 143강의 정규분포 근사로 이어집니다.
심화 4. (조 나누기의 나눗셈) 명을 명씩 세 조로 나누는 방법의 수를 구하고, 왜 로 나누는지 설명하세요. 조에 이름이 있으면 답이 어떻게 달라지는지도 말하세요.
답. 조에 이름이 없으면 가지이고 있으면 가지입니다.
풀이. 순서를 매겨 뽑으면 가지입니다. 이 셈에서는 같은 분할이라도 어느 조를 먼저 뽑았는지에 따라 다르게 세어졌습니다. 세 조의 순서가 가지이므로 나누면 입니다. 조에 조, 조, 조처럼 이름이 있으면 순서가 결과를 바꾸므로 나누지 않고 가지입니다.
남는 것. 나눌지 말지는 "구별되는가"로 정해집니다. 문제에 조 이름이 있는지, 사람이 앉을 자리가 구분되는지를 반드시 확인해야 합니다. 크기가 다른 조로 나눌 때는 조끼리 구별되므로 나누지 않는다는 점도 함께 기억합니다. 예를 들어 명을 명, 명, 명으로 나누면 크기로 구별되어 가지입니다.
심화 5. (여사건이 이기는 문제) 명을 일렬로 세울 때 특정 세 사람 중 어느 두 사람도 이웃하지 않는 방법의 수를 구하세요.
답. 가지
풀이. 여사건으로 세면 "적어도 두 사람이 이웃"이 여러 경우로 갈려 복잡합니다. 대신 사이에 끼우는 방법을 씁니다. 먼저 나머지 명을 일렬로 세우면 가지입니다. 이들이 만드는 자리는 양 끝과 사이를 합해 곳입니다. 이 중 세 곳을 골라 특정 세 사람을 한 명씩 넣으면 어느 둘도 이웃하지 않습니다. 자리를 고르고 순서를 정하는 것이므로 가지입니다. 곱하면 입니다.
남는 것. "이웃하지 않는다"는 조건은 여사건보다 끼워 넣기가 대개 짧습니다. 조건이 하나뿐이면 여사건이 편하고, 여러 쌍에 동시에 걸리면 끼워 넣기가 편합니다. 두 방법을 모두 알고 상황에 맞게 고르는 것이 요령입니다.
심화 6. (오해 깨기) "명 중 명을 뽑는 방법은 가지이다"와 "이다"라는 두 주장을 판단하세요.
답. 둘 다 거짓입니다. 각각 가지이고, 올바른 관계는 입니다.
풀이. 첫째 주장을 봅니다. "뽑는다"는 말에는 순서가 없으므로 조합입니다. 은 뽑아서 순서까지 정하는 경우이며, 같은 세 사람이 번씩 중복해 세어져 있습니다. 실제 답은 입니다. 둘째 주장을 봅니다. 값을 계산하면 왼쪽은 이고 오른쪽은 이라 명백히 다릅니다. 심화 2의 파스칼 항등식에서 두 조합을 더하면 위 첨자가 하나 늘고 아래 첨자는 큰 쪽을 따르므로 입니다. 첨자를 더하는 것이 아니라는 점이 핵심입니다.
남는 것. 세는 문제에서 가장 흔한 실수는 순서를 잘못 판단하는 것입니다. 문제 문장에 "정한다", "세운다", "앉힌다", "순서를 매긴다"가 있으면 순열이고, "뽑는다", "고른다", "나눈다"가 있으면 조합입니다. 애매하면 작은 수로 직접 나열해 확인하는 것이 가장 확실합니다.
경우의 수를 실제로 나열해 세어 공식과 대조합니다. 파이썬 표준 라이브러리의 조합 도구를 씁니다.
from itertools import permutations, combinations
from math import comb, factorial, perm
# 문제 9: 7명 중 4명을 뽑아 일렬로 세우기
print(perm(7, 4), len(list(permutations(range(7), 4)))) # 840 840
# 문제 8: C(9,3)
print(comb(9, 3), len(list(combinations(range(9), 3)))) # 84 84
# 문제 10: BANANA 배열
from collections import Counter
w = "BANANA"
f = factorial(len(w))
for c in Counter(w).values():
f //= factorial(c)
print(f, len(set(permutations(w)))) # 60 60
# 문제 18: 완전순열(교란순열)
n = 5
d = sum(1 for p in permutations(range(n)) if all(p[i] != i for i in range(n)))
print(d) # 44
# 심화 6: 순열과 조합은 다릅니다
print(perm(5, 3), comb(5, 3), comb(5, 2) + comb(5, 3), comb(6, 3)) # 60 10 20 20
각 줄에서 공식으로 구한 값과 실제로 나열해 센 값이 일치합니다. 마지막 줄은 심화 6의 두 주장을 한꺼번에 검증하며, 파스칼 항등식이 을 준다는 것도 확인됩니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 팩토리얼 | 개를 모두 늘어놓는 방법의 수 | |
| 공식이 성립하도록 정한 값입니다 | ||
| {}_{n}P_ | 개에서 개를 골라 늘어놓는 방법의 수 | |
| 또는 \binom{n} | 씨 | 개에서 개를 순서 없이 고르는 방법의 수 |
| 원순열 | 원순열 | 원형 배열이며 입니다 |
| 중복순열 | 중복순열 | 같은 것을 여러 번 골라도 되며 입니다 |
| 의 크기 | 집합 의 원소 개수 |