순열 수 $D,D,D,O,O,O,G,G,G$ 두 사람이 $D$ 인접하고 둘이 없다 $G$ 인접하다

Aug 19 2020

다음과 같은 문제가 있습니다. 이미 해결했지만 내 솔루션에 만족하지 않습니다. 나는 더 매끄러운 해결책을 원하며 누군가가 도움을 줄 수 있습니다. 별 / 막대 방법만으로이 문제를 해결할 수있는 방법이 있습니까?

모든 문자를 변경하는 방법의 수를 계산하십시오. $D,D,D,O,O,O,G,G,G$ 두 사람이 $D$ 인접하고 둘이 없다 $G$ 인접 해 있습니다.

내 시도.

에 대한 $k=2,3$, 허락하다 $\Delta_k$ 순열 집합을 나타냅니다. $k$ 의 $D$ 인접하고, $\Gamma_k$ 순열 집합을 나타냅니다. $k$ 의 $G$인접 해 있습니다. 허락하다$U$ 조건없이 모든 순열의 집합입니다.

그때 $$|U|=\frac{(3+3+3)!}{3!3!3!}=1680.$$ 우리는 $$|\Delta_3|=\frac{(1+3+3)!}{1!3!3!}=140$$ (같이 $\Delta_3$ 순열 집합입니다. $DDD,O,O,O,G,G,G$) 및 $$|\Delta_2|+2|\Delta_3|=\frac{(1+1+3+3)!}{1!1!3!3!}=1120$$ 이 숫자는 순열을 계산하기 때문에 $DD,D,O,O,O,G,G,G$. 따라서$$|\Delta_2|=1120-2(140)=840.$$ 비슷하게 $|\Gamma_3|=140$ 과 $|\Gamma_2|=840$.

우리는 찾고 싶다 $|\Delta_i\cap\Gamma_j|$. 이후$\Delta_3\cap\Gamma_3$ 순열 집합입니다. $DDD,O,O,O,GGG$, $$|\Delta_3\cap\Gamma_3|=\frac{(1+3+1)!}{1!3!1!}=20.$$ 이후 $|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|$ 순열을 계산 $DD,D,O,O,O,GGG$, 우리는 $$|\Delta_2\cap\Gamma_3|+2|\Delta_3\cap\Gamma_3|=\frac{(1+1+3+1)!}{1!1!3!1!}=120$$ 그래서 $$|\Delta_2\cap\Gamma_3|=120-2(20)=80.$$ 비슷하게 $|\Delta_3\cap\Gamma_2|=80$.

이제 우리는 $|\Delta_2\cap\Gamma_2|$. 이후$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|$ 순열의 수를 계산 $DD,D,O,O,O,GG,G$, 우리는 $$|\Delta_2\cap\Gamma_2|+2|\Delta_3\cap\Gamma_2|+2|\Delta_2\cap\Gamma_3|+4|\Delta_2\cap\Gamma_3|=\frac{(1+1+3+1+1)!}{1!1!3!1!1!}=840.$$ 그 후 $$|\Delta_2\cap\Gamma_2|=840-2(80)-2(80)-4(20)=440.$$

포함-제외 원칙에 따라 우리는 $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=\sum_{k=2}^3|\Delta_k|+\sum_{k=2}^3|\Gamma_k|-\sum_{i=2}^3\sum_{j=2}^3|\Delta_i\cap \Gamma_j|.$$ 따라서 $$|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=2(840)+2(140)-(440+80+80+20)=1340.$$ 질문은 크기를 묻습니다 $U\setminus(\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3)$, 즉 $$|U|-|\Delta_2\cup\Delta_3\cup\Gamma_2\cup\Gamma_3|=1680-1340=340.$$

답변

4 MathLover Aug 19 2020 at 12:56

이 작업을 수행하는 더 매끄러운 방법이 있는지는 모르겠지만 귀하의 접근 방식을 사용하더라도 더 간단 할 수 있습니다.

"DD DGGGOO O"의 순열은 G가 인접하지만 D가 그렇지 않은 경우를 제외하고 인접 D 및 인접 G의 모든 경우를 포함합니다.

$i)$ "DD DGGGOO O"의 순열 $= \dfrac{8!}{3!3!} - \dfrac{7!}{3!3!} = 980$

[ 뺄셈은 서로 다른 것으로 간주되는 인접 DD D와 D DD를 처리하는 것입니다. 따라서 DDD 순열은 두 번 계산되며 한 번 제거해야합니다. ]

$ $

$ii)$ "GG GOO O"의 순열 및 배치 $3$ D' s in $3$ 인접하지 않은 $6$ 장소

$$= \dfrac{5!}{3!}.{^6}C_3 - \dfrac{4!}{3!}.{^5}C_3 = 360$$

[ 빼기는 인접한 GG G와 G GG가 다른 것으로 간주되는 것을 처리하는 것입니다. 그래서 GGG 순열과 D를$3$ 밖으로 $5$장소가 두 번 계산되었으며 한 번 계산되어야합니다. ]

$ $

그것은 당신에게 원하는 배열을 제공합니다 $= 1680 - 980 - 360 = 340$

1 DanielN Aug 20 2020 at 22:27

문제를 약간 수정하고 수정 한 다음이 새로운 형식으로 해결합니다. 초기 문제에 대한 통과는 표준입니다.

문제. 세트 고려$S=S(d+4)=\{x_1, x_2, x_3, y_1, y_2, y_3, z_1, \ldots, z_{d-2}\}$. 순열$S$ 불린다 $x,y$- 인접 자유 (및 이후 유형$(1,1)$) 두 개가 없으면 $x$의와 아니 2 $y$의 인접 해 있습니다. 수를 결정하십시오$x,y$-인접한 무료 순열.

요소는 $x_1$, $x_2$, 및 $x_3$ 별개의 요소로 간주됩니다 (그리고 $y$'에스).
문제 에서 초기 질문으로 의 통과 는 명백한 공식에 의해 주어집니다.$$ \frac{\text{number of $x, y$-adjacent free permutations of $에스$}} {3!\, 3!\, (d-2)!} $$ 우리가 취하는 $d=3$.

이 솔루션은 재귀 대수 계산 (모델이 파스칼의 삼각형 임)쪽으로 기울어집니다. 긍정적 인 측면에서 우리는 재귀 공식 (일반화, 다른 유사한 숫자의 계산 ...)에 만족할 수 있습니다. 부정적인 측면에서는 모든 방향으로 성가신 비행 지수가있을 것입니다.

솔루션의 표기법 및 설명. 허락하다$S^{a,b}\subset S$ 부분 집합 $$ S^{a,b} = \{ x_1,\ldots,x_a, y_1, \ldots, y_b, z_1, \ldots, z_{d-2}\} \subset S $$ 와 $1\leq a,b\leq3$. 그것은 가지고있다$d+a+b-2$집단. 표시$P_{(i,j)}^{a,b}$,와 함께 $i\leq a$ 과 $j\leq b$, 순열 집합 $S^{a,b}$ 정확히 $i$ 인접한 $x$'모래 $j$ 인접한 $y$의, 유형의 순열 이라고 함 $(i,j)$. 분명히 모든 순열의 집합$S^{a,b}$ 이다 $$ \bigcup_{\substack{1\leq i\leq a\\1\leq j\leq b}} P_{(i,j)}^{a,b}. $$ 우리는 계산하고 싶다 $N_{(1,1)}^{3,3}$, 추기경 $P_{(1,1)}^{3,3}$. 아이디어는 다음 필터링을 사용하여 재귀 적으로 계산을 수행하는 것입니다.$S^{3,3}$: $$ S^{1,1} \subset S^{2,1} \subset S^{3,1} \subset S^{3,2} \subset S^{3,3}. $$ 마다 $N_{(i,j)}^{a,b}$ 하위 집합에 해당 $S^{a,b}$ 여과에서 모든 정수 계수의 선형 조합으로 표현됩니다. $N$의 이전 하위 집합입니다. 이 모든 구절에 대해 계수가 결정되면 (구성의 조합을 사용하여) 문제가 해결됩니다.

계수 찾기. 우리가 찾고있는 것부터 시작합시다.$$ N_{(1,1)}^{3,3} = d\,N_{(1,1)}^{3,2} + N_{(2,1)}^{3,2}. $$이 경우 다른 계수는 모두 0입니다. 설명은$S^{3,3}$ 유형 $(1,1)$ 순열에서만 발급 될 수 있습니다. $S^{3,2}$ 어느 유형이든 $(1,1)$ 또는 유형 $(2,1)$. 전자의 경우 순열의 경우 정확히$d=d+4-4$ 위치 ( $d+4$) 어디 $y_3$ 삽입 될 수 있습니다 (둘 다 $y_1$ ...도 아니다 $y_2$). 후자의 경우에,$y_3$ 인접한 두 개 사이에 삽입해야합니다. $x$'에스.

우리는 다음을위한 공식을 추구합니다. $N_{(1,1)}^{3,2}$ 과 $N_{(2,1)}^{3,2}$ 구절을 사용하여 $S^{3,1}$ ...에 $S^{3,2}$우리 여과에서. 공식$N_{(1,1)}^{3,2}$ 이전 것과 거의 동일합니다. $$ N_{(1,1)}^{3,2} = (d+3-2)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1} = (d+1)\,N_{(1,1)}^{3,1} + N_{(2,1)}^{3,1}. $$ 공식 $N_{(2,1)}^{3,2}$까다 롭습니다. 읽습니다$$ N_{(2,1)}^{3,2} = 0\,N_{(1,1)}^{3,1} + (d+3-3)\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1} \\ = d\,N_{(2,1)}^{3,1} + 2N_{(3,1)}^{3,1}. $$ 계수 $d+3-3$ 다음과 같은 관찰이 이루어집니다. $(2,1)$ 순열 $S^{3,2}$ 형식으로 발행 $(2,1)$ 순열 $S^{3,1}$, 다음 $y_2$ 정확히 $d+3-3$ 삽입 가능한 위치 : $d+3$ 총 장소 수이며 $y_2$ 인접한 사이의 장소를 차지할 수 없습니다. $x$의 또는 인접한 두 장소 중 $y_1$.

마지막 두 가지 공식을 살펴보면 이제부터는 $N$의 나머지 여과 하위 집합에 해당합니다. 그러나 그들은 더 적고 공식을 이해하기가 더 쉽습니다. 우리는 다음을 연속적으로 얻습니다.

...에 대한 $S^{2,1}\subset S^{3,1}$ $$ N_{(1,1)}^{3,1} = (d+2-4)\,N_{(1,1)}^{2,1} + 0\,N_{(2,1)}^{2,1} $$ $$ N_{(2,1)}^{3,1} = 4\,N_{(1,1)}^{2,1} + (d+2-3)\,N_{(2,1)}^{2,1} $$ $$ N_{(3,1)}^{3,1} = 0\,N_{(1,1)}^{2,1} + 3\,N_{(2,1)}^{2,1} $$
...에 대한 $S^{1,1}\subset S^{2,1}$ $$ N_{(1,1)}^{2,1} = (d+1-2)\,N_{(1,1)}^{1,1} \quad\text{and}\quad N_{(2,1)}^{2,1} = 2\,N_{(1,1)}^{1,1}. $$

이제 계산 을 얻으려면$N_{(1,1)}^{3,3}$ 로 시작하여 뒤로 이동하는 것으로 충분합니다. $N_{(1,1)}^{1,1}=d!$. 알고리즘 특성을 강조하여 계산을 수행합시다. 아래 표기가 자명하기를 바랍니다.