Examkin

Soru

Zorluk: Çok zorCounting with Restrictions and Repetitions

How many distinct 6-digit positive integers can be formed using all of the digits 1,1,2,2,3,1, 1, 2, 2, 3, and 44 such that no two identical digits are adjacent to each other?

  1. A
    36
  2. B
    60
  3. C
    72
  4. 84Cevap
  5. E
    96

Cevap

84
To find the number of 6-digit integers where no two identical digits are adjacent, apply complementary counting with the Principle of Inclusion-Exclusion. First, calculate the total distinct arrangements of the digits 1,1,2,2,3,41, 1, 2, 2, 3, 4, which is 6!2!2!=180\frac{6!}{2!2!} = 180. Next, count the forbidden outcomes. Treating the two 1s as a single block gives 5!2!=60\frac{5!}{2!} = 60 arrangements with adjacent 1s. Similarly, treating the two 2s as a single block gives 5!2!=60\frac{5!}{2!} = 60 arrangements with adjacent 2s. Arrangements where both the 1s are adjacent and the 2s are adjacent use two single blocks along with digits 3 and 4, giving 4!=244! = 24 arrangements. By Inclusion-Exclusion, the total number of forbidden arrangements is 60+60−24=9660 + 60 - 24 = 96. Subtracting these from the total unrestricted arrangements gives 180−96=84180 - 96 = 84.

Adım Adım Çözüm

1
Calculate the total number of unrestricted distinct 6-digit arrangements of the multiset {1, 1, 2, 2, 3, 4}.
Total arrangements = 6!2!×2!=7204=180\frac{6!}{2! \times 2!} = \frac{720}{4} = 180.
Dividing by 2!×2!2! \times 2! accounts for the indistinguishable repeated digits 1 and 2.
2
Define the forbidden events and calculate their individual counts.
Let AA be the set of arrangements with adjacent 1s, and BB be the set of arrangements with adjacent 2s.
For ∣A∣|A|, treat (11)(11) as a single block: elements are {(11),2,2,3,4}\{(11), 2, 2, 3, 4\}, so ∣A∣=5!2!=60|A| = \frac{5!}{2!} = 60.
For ∣B∣|B|, treat (22)(22) as a single block: elements are {1,1,(22),3,4}\{1, 1, (22), 3, 4\}, so ∣B∣=5!2!=60|B| = \frac{5!}{2!} = 60.
Grouping adjacent identical numbers into a single block simplifies counting restriction violations.
3
Calculate the intersection count ∣A∩B∣|A \cap B| where both pairs are adjacent.
Treating both (11)(11) and (22)(22) as single blocks yields elements {(11),(22),3,4}\{(11), (22), 3, 4\}, so ∣A∩B∣=4!=24|A \cap B| = 4! = 24.
Arrangements where both pairs of identical digits are adjacent are counted in both AA and BB and must be identified.
4
Apply the Principle of Inclusion-Exclusion to find the total forbidden arrangements and subtract from the total unrestricted arrangements.
∣A∪B∣=∣A∣+∣B∣−∣A∩B∣=60+60−24=96|A \cup B| = |A| + |B| - |A \cap B| = 60 + 60 - 24 = 96.
Valid arrangements = 180−96=84180 - 96 = 84.
Complementary counting yields the exact number of arrangements where no two identical digits are adjacent.

Anahtar Kavram

Permutations of Multisets with Restrictions via Inclusion-Exclusion
Bu soruyu puanla

Konular

Counting with Restrictions and Repetitions

Bu konudan daha fazla soru