단어의 문자가 알파벳 순서로 나타나야하는 경우 A, B, C, D, E를 사용하여 8 자 단어를 구성합니다.
A, B, C, D, E를 사용하여 8 자 단어를 구성합니다. 여기서 각 문자는 여러 번 사용할 수 있습니다 . 단어의 문자가 알파벳 순서로 나타나야하는 경우 몇 개의 단어를 만들 수 있습니까?
예 : AABBDDDE허용됨, BBBACCCE허용되지 않음.
내가 이것을 계산할 수있는 유일한 방법은 각 문자의 발생 횟수를 표로 그린 다음 각 행의 문자 위치 순열을 계산하는 것입니다.
이 질문을 더 쉽게 해결할 수있는 방법이 있습니까?
답변
길이의 알파벳 단어를 세면 대답은 같습니다. $13$ 각 문자는 최소한 한 번만 나타나야합니다 (각 문자의 사본 하나를 추가 / 제거하여).
이것을 세기 위해, $13$문자를 보관할 슬롯 (일명 "별"). 단어를 지정하려면$4$ 에서 간격 $12$ 슬롯 사이의 내부 간격을 지정하여 $4$ 단어에서 문자가 변경되는 위치 (즉, "막대")입니다 (예 : A에서 B, B에서 C 등).
이것은에서 할 수 있습니다 $C(12,4) = 495$ 방법.
원하는 단어의 종류가 A, B, C, D, E의 숫자에 의해 일관되게 결정되는 것을 관찰하십시오. 그러면 문제는 8을 5 개의 숫자의 합으로 얼마나 많이 쓸 수 있는지 묻는 것과 같습니다. 정답은 ${12\choose 8}$, 그 이유를 아십니까?
생각할 필요가 거의없는 간단한 접근 방식 (Alex와 Alessandro Cigna의 답변에는 약간의 생각이 필요합니다).
허락하다$f(n,k)$ 원하는 문자열의 수 $n$ 글자 길이 $k$문자 허용. 우리는$$f(1,k)=k,\quad f(n,k)=\sum\limits_{i=0}^{k-1}f(n-1,k-i).$$
f (n, k)에 대한 표 n \ k | 1 | 2 | 3 | 4 | 5 --- + -------- + -------- + -------- + -------- + -------- 1 | 1 | 2 | 3 | 4 | 5 2 | 1 | 3 | 6 | 10 | 15 3 | 1 | 4 | 10 | 20 | 35 4 | 1 | 5 | 15 | 35 | 70 5 | 1 | 6 | 21 | 56 | 126 6 | 1 | 7 | 28 | 84 | 210 7 | 1 | 8 | 36 | 120 | 330 8 | | | | | 495
당신은 $8+5-1=12$ 선택해야하는 슬롯 $4$. 이러한 선택에 따라 각 문자가 반복되는 횟수가 결정됩니다. 예를 들어 슬롯 1 ~ 4를 선택하면 모든 E를 얻습니다. 여기서 처리 할 수 있습니까?