별과 막대 계산기
별과 막대 방법으로 중복조합과 정수해의 개수를 계산합니다. x1 + ... + xk = n에서 비음수, 양수, 하한, 상한 조건을 다룰 수 있습니다.
사용 방법(3단계)
- n(전체 개수)과 k(변수 또는 상자 수)를 입력합니다.
- 조건을 선택하세요: xi ≥ 0, xi ≥ 1, 또는 xi ≥ ai (선택사항: 제한됨).
- 동일한 상태를 재현하려면 공유 가능한 URL을 복사하세요.
참고: 이 계산기는 동일한 공. 공이 뚜렷하면 모델도 다릅니다.
비주얼 가이드
작은 입력의 경우 별표(*)와 막대(|)를 사용하여 인코딩하는 한 가지 예를 보여줍니다. “유일한 배열”이 아닌 예시입니다.
결과
단계(짧음)
추론을 보여주세요
예시(해결책)
작은 n,k의 해 표시
팁: 해 목록은 성능을 위해 제한됩니다. 입력이 크면 개수만 확인하세요.
수식 및 일반적인 실수
- 음수가 아닌 (xi≥0):
C(n+k−1, k−1) - 이는 "반복 조합"(다중 선택)과 같습니다.
k multichoose n = C(n+k−1, n). - 양수 (xi≥1):
C(n−1, k−1)(n<k이면0) - 하한 (xi≥ai):로 변환
n−Σai, 그러면C((n−Σai)+k−1, k−1)
일반적인 실수
- "서로 구별하지 않는 공"과 "구별 가능한 공"을 혼동하지 마세요. 이 계산기는 구별하지 않는 공의 정수해를 셉니다.
- xi≥1 조건에서는
n<k이면 해가0입니다. - 하한을 적용할 때는
Σai를 빼야 합니다. 모든 ai가 같을 때만 단일 a로 처리할 수 있습니다.
관련 계산기
올바른 별과 막대 설정을 선택하는 방법
이 계산기는 서로 구별하지 않는 항목을 상자나 변수에 나누어 넣는 경우를 셉니다. 순서가 중요하거나 항목이 서로 구별되면 다른 계산 모델을 사용하세요.
막대가 중요한 이유
고전적인 그림에서 각 별은 하나의 항목이고 각 막대는 상자 사이의 구분선입니다. n + k − 1개의 위치 중에서 k−1개의 막대 위치를 정하면 하나의 정수해가 완전히 정해집니다.
3단계로 사용하세요
- n에는 동일한 항목의 총개수를, k에는 상자 또는 변수의 수를 입력합니다.
- 문제 조건에 맞게 xi ≥ 0, xi ≥ 1, 하한, 상한 조건을 선택합니다.
- 먼저 개수를 확인한 뒤 짧은 단계와 예시로 모델 선택이 맞는지 점검하세요.
모드 선택 방법
- 빈 상자가 허용되면 xi ≥ 0을 사용합니다.
- 모든 상자에 최소 하나씩 들어가야 하면 xi ≥ 1을 사용합니다.
- 각 변수에 최소값이 있으면 xi ≥ ai를 사용합니다.
- 하한과 상한이 모두 조건에 포함될 때만 ai ≤ xi ≤ bi를 사용합니다.
비교 예시
빈 상자가 허용된 3개의 상자에 동일한 공 7개를 넣으면 개수는 C(9,2)입니다. 모든 상자에 최소 하나의 공이 있어야 하면 양수 조건으로 바꾸어 C(6,2)를 계산합니다. 이 차이를 먼저 확인하면 비음수 조건과 양수 조건을 혼동하는 실수를 줄일 수 있습니다.
피해야 할 일반적인 실수
- 순열, 다항 계수, 정수 구성으로 풀어야 하는 구별 가능한 항목 문제에 이 페이지를 사용하는 경우.
- 문제에서 각 상자에 최소 하나의 항목이 필요하다고 했는데 xi ≥ 0을 선택하는 경우.
- 하한 또는 상한을 입력한 뒤 합계가 여전히 n에 도달할 수 있는지 확인하지 않는 경우.
- 하나의 시각 예시를 가능한 해 전체로 오해하는 경우.
함께 보기
자주 묻는 질문
별과 막대 방법이란 무엇입니까?
n개의 동일한 항목을 k개의 상자에 배포하는 방법의 수를 계산합니다. 이는 xi≥0과 같은 조건에서 x1+…+xk=n에 대한 해의 수입니다.
음수가 아닌 경우가 C(n+k−1, k−1)가 되는 이유는 무엇입니까?
n개의 별과 k−1개의 막대를 한 줄에 놓습니다. 막대 위치를 고르면 각 상자에 들어가는 개수가 하나로 정해지므로 C(n+k−1, k−1)가 됩니다.
xi≥1일 때 공식은 어떻게 변합니까?
yi=xi−1이라고 하자. 그러면 yi≥0일 때 y1+…+yk=n−k이므로 n≥k일 때 개수는 C(n−1, k−1)이고, 그렇지 않으면 0입니다.
하한 xi≥ai는 어떻게 작동하나요?
yi=xi−ai로 두면 y1+…+yk=n−Σai이고 yi≥0입니다. n≥Σai이면 개수는 C((n−Σai)+k−1, k−1)이고, 그렇지 않으면 0입니다.
음수가 아닌 대신 언제 양수를 사용해야 합니까?
모든 변수나 상자가 최소한 하나의 항목을 받아야 하면 양수 조건을 사용합니다. 0이 허용되면 비음수 조건을 사용하세요. 이 한 단어 차이가 별과 막대 문제에서 오답을 만드는 가장 흔한 원인입니다.
공이 구별 가능하다면 어떨까요?
이 계산기는 서로 구별하지 않는 공을 가정합니다. 공이 구별 가능하면 모델이 k^n 또는 다항 계수처럼 달라지므로 문제에 맞는 다른 계산기를 사용하세요.