Xin hướng xử lý bài tổ hợp này ạ

[Trinity]

Có bao nhiêu hoán vị của các chữ cái trong từ INTERPRETATION thỏa điều kiện không có 2 nguyên âm nào đúng cạnh nhau ?

hướng của em thế này :
em sẽ tính hoán vị của trường hợp tổng rồi sau đó tính hoán vị của các trường hợp mà 2 nguyên âm đứng cạnh nhau , rồi sau đó trừ 2 cái cho nhau
ta thấy có 6 nguyên âm trong chuỗi trên nên sẽ có các trường hợp sau nguyên 2 nguyên âm sẽ đứng cạnh nhau :
xét 6 nguyên âm đứng cạnh nhau , các vị trí còn lại ta lấy hoán vị
xét 5 nguyên âm đứng cạnh nhau , các vị trí còn lại ta lấy hoán vị
xét 4 nguyên âm đứng cạnh nhau , các vị trí còn lại ta lấy hoán vị
xét 3 nguyên âm đứng cạnh nhau , các vị trí còn lại ta lấy hoán vị

đáp án thì làm rất gọn :
nó tính hoán vị của các ký tự không nguyên âm , rồi sau đó lấy tổ chợp chập của các nguyên âm :
kq : 3.360 * tổ hợp chập 6 của 3.361

1.cho em hỏi cách em làm có khả thi không
2.ở cái đáp án em không hiểu đoạn tổ hợp chập 6 của 3.361 có ý nghĩa gì luôn , cái 3.360 là các hoán vị của ký tự không nguyên âm thì em hiểu …

[hungaya (Hung)]

INTERPRETATION có tổng cộng 14 chữ cái (characters), trong đó có 8 phụ âm (consonants) và 6 nguyên âm (vowels).

Nếu xếp liên tiếp phụ âm riêng hoặc nguyên âm riêng:
Thông tin phụ âm

N	R	P	T	Tổng (sum)
2	2	1	3	8

=> Số hoán vị (permutation) phụ âm = 8! / (2! . 2! . 1!. 3!) = 1680

Thông tin nguyên âm

A	E	I	O	Tổng
1	2	2	1	6

=> Số hoán vị nguyên âm = 6! / (1! . 2! . 2!. 1!) = 180

Cách tạo hoán vị gồm 3 bước:
Bước 1:
Lập dãy phụ âm liên tiếp (consonant sequence), được 1680 cách.

Bước 2:
Nếu kí hiệu phụ âm là | (bar) và nguyên âm là * (star)

 1 2 3 4 5 6 7 8
*|*| |*| |*| |*|*

Dãy có 8 bar nên có 9 khoảng trống: 7 giữa 2 bars bất kì, 1 trước bar (1), 1 sau bar (8)

Vì đề bài yêu cầu không có 2 nguyên âm kế tiếp nhau (consecutive), nên khoảng trống (empty box) chỉ nhiều nhất 1 star. Từ đó, số cách sắp xếp star vào bar bằng số cách chọn 6 khoảng trống trong 9 khoảng trống để đặt 6 stars, hay 9C6 = 84 cách.

Vậy bước 2 có 84 cách.

Bước 3:
Tương ứng với mỗi star được chọn từ bước 2, chọn 1 hoán vị từ dãy nguyên âm đặt vào vị trí star, số cách đặt bằng số nguyên âm (ở trên), hay 180.

Áp dụng quy tắc nhân (multiplication rule) cho 3 bước: 1680 . 84 . 180 = 25,401,600

---

Hên xui trúng đáp số

[noname00 (HK boy)]

Trong INTERPRETATION có 6 nguyên âm.

Coi các nguyên âm có các kí tự |. Đặt 1 số lượng các phụ âm quanh các kí tự | mà giữa | luôn có ít nhất 1 phụ âm (có thể có phụ âm ở đầu và cuối).

... | ... | ... | ... | ... | ... | ...

Bài toán trở thành tìm số nghiệm dương của phương trình x₁ + … + x_n = 8 (n = số nghiệm, 8 = số phụ âm)

Chia làm 3 TH:

• TH1: có phụ âm ở đầu, không có phụ âm ở cuối: n = 6, có (8-1)C(6-1) = 21 (công thức theo bài toán chia kẹo) nghiệm
• TH2: không có phụ âm ở đầu, có phụ âm ở cuối: tương tự TH1, kết quả là 21.
• TH3: có phụ âm ở đầu và cuối: n = 7, có (8-1)C(7-1) = 7 nghiệm
• UPD: TH4: không có phụ âm ở đầu: (8-1)C(5-1) = 35

Ở 6 vị trí nguyên âm có các hoán vị các kí tự, 8 vị trí phụ âm có hoán vị các kí tự. Kết quả có

(UPD)

Đáp số ở trên ảo quá nhỉ, còn lớn hơn cả 14! (số hoán vị của từ) nữa kìa…

---

P/s: Thanks @hungsteve vì đã chỉ mình chỗ sai

[hungaya (Hung)]

Thiếu 1 trường hợp kìa: không có phụ âm đầu lẫn phụ âm cuối, có (8-1)C(5-1) = 35.
4 trường hợp thì phải cộng lại, không phải nhân: 21 + 21 + 7 + 35 = 84 (như mình )

[rogp10]

Sao số 3361 lại ở đây, mà dù sao thì 361 = 19^2
Hi vọng là đáp án có kèm lời giải.

[Trinity]

hix cái này là 1 bài tập em tìm được của trường khtn trong đó chỉ có cái đề và đáp án thôi , chắc chạy lên trường hỏi thầy quá nhiều khi đọc đáp án mà ko hiểu làm sao nó ra đc đáp án nữa

còn 1 bài nữa cũng ra đáp án khó hiểu @@

tiệm bán sơn có 12 màu sơn khác nhau , 1 khách hàng muốn mua 15 hộp sơn hỏi có bao nhiêu cách chọn để ?
a> mỗi màu ít nhất 1 hộp (đáp án 3C14)
b>gồm đúng 8 màu khác nhau ( 8C12*15C22 )

em suy luận câu a:
chọn ra 12 hộp với 12 màu khác nhau => có 1 cách
chọn ra 12 vị trí trong 15 vị trí để đặt 12 hộp trên vào => tổ hợp chập 12 của 15 ( 12C15 )
chọn ra 3 hộp với 12 màu bất kì ( trùng hoặc không trùng ) => tổ hợp chập 3 của 14 ( 3C14)
chọn ra 3 vị trí trong 3 vi trí còn lại để đặt 3 hộp trên vào => 3C3
kq : 12C15 * 3C14 * 3C3

[rogp10]

chọn ra 12 vị trí trong 15 vị trí để đặt 12 hộp trên vào => tổ hợp chập 12 của 15 ( 12C15 )

Sao lại có vị trí trong này

[hungaya (Hung)]

Bạn nên tham khảo dạng bài toán

Stars and bars (combinatorics)

[Trinity]

thì em coi bài toán như là cho 12 số tư nhiên chọn ra 15 số trong 12 số , thì mỗi số sẽ được chọn em xem như 1 vị trí để đặt số 15 số là 15 vị trí

[hungaya (Hung)]

Câu a thì dễ rồi, vì nó thuộc 1 trong 2 trường hợp kinh điển của stars and bars problem. Mình giải câu b thôi.

Màu sơn lần lượt được kí hiệu là 1, 2,…, 12.
Trong số 15 hộp sơn được mua, gọi lần lượt x₁, x₂,…, x₁₂ là số hộp sơn có màu 1, 2,…, 12.
Như vậy:

x₁ + x₂ + … + x₁₂ = 15. (1)

Xét 1 trường hợp cụ thể: trong 15 hộp sơn có ít nhất 1 hộp có màu 1, 2, 3, 4, 5, 6, 7, 8 (8 hộp từ 1 tới 8); các hộp 9, 10, 11, 12 có số lượng bằng 0. Từ đó có điều kiện:

• x_i ≥ 1, i ∈ { 1, 2, 3, 4, 5, 6, 7, 8 }
• x_j = 0, j ∈ { 9, 10, 11, 12 }

Phương trình (1) tương đương:

x₁ + x₂ + … + x₈ = 15 (2)

Đặt y_i = x_i - 1 ≥ 0, phương trình (2) trở thành:

y₁ + y₂ + … + y₈ = 15 - 8 = 7 (3)

(3) là 1 trường hợp của stars and bars, gồm 7 bars (ngăn cách giữa y_i), 7 stars (tổng các y_i).
Số cách chọn là (7+7)C7 = 14C7 = 3432.

Tổng trường hợp thoả mãn điều kiện có đúng 8 màu khác nhau là số cách chọn 8 màu trong 12 màu, hay 12C8 = 495.

Áp dụng quy tắc nhân, 14C7 . 12C8 = 3432 . 495 = 1,698,840.

[tntxtnt]

câu b cũng tương tự câu a thôi có gì đâu :V câu a là 12 màu bỏ vào 3 vị trí (3C14), câu b là 8 màu bỏ vào 15 vị trí (15C22), rồi nhân với cách chọn 8 màu từ 12 màu (8C12) là xong :V

Combination | Number of combinations with repetition

n phần tử bỏ vào k vị trí có thể có nhiều phần tử lập lại (dịch ra tiếng Việt hơi lạ :V) được wiki nó ghi là ((n, k)) = (n + k - 1, k) là tổ hợp chập k của n+k-1

câu a là 12 màu bỏ vào 15 hộp, và có đủ 12 màu, vậy 12 hộp đầu ta bỏ 12 màu vào :V rồi còn 3 hộp thích bỏ màu gì trong 12 màu này cũng được, vậy bài toán trở thành bỏ 12 màu vào 3 hộp, có thể có hộp trùng màu, hay là ((12, 3)) = (12+3-1, 3) = (14, 3) hay 3C14

câu b thì gồm đúng 8 màu, thì đầu tiên chọn 8 màu từ 12 hộp: 8C12, rồi tương ứng mỗi 8 màu này bỏ vào 15 hộp, có thể có hộp trùng màu tức là ((8, 15)) = (8+15-1, 15) = (22, 15) hay 15C22, nhân vào ta có đáp án :V

[tntxtnt]

cách giải câu a theo phương pháp mò :V mà mò 1 hồi cũng quay về cái stars and bars kia thôi

1 cách chọn là 1 vector gồm 12 phần tử, tổng các phần tử là 15. ví dụ [5,1,1,1,1,1,1,1,1,1,1,0] (1 số 5, 10 số 1, 1 số 0)

cách chọn thỏa mãn yêu cầu câu a là các vector gồm 12 phần tử, tổng các phần tử là 15, và mỗi phần tử có giá trị > 0, ví dụ [4,1,1,1,1,1,1,1,1,1,1,1] (1 số 4, 11 số 1)

vì mỗi phần tử đều > 0, ta có thể - 1 cho mỗi phần tử trong vector, để được kiểu vector mới gồm 12 phần tử, tổng cách phần tử là 15 - 1*12 = 3, ví dụ [0,0,0,3,0,0,0,0,0,0,0,0] (1 số 3, 11 số 0). (bước này là để cho dễ nhìn :V)

tới đây các vector kiểu này chỉ có thể có 3 loại:
loại 1: 1 số 3, còn lại toàn số 0
loại 2: 1 số 2, 1 số 1, còn lại toàn số 0
loại 3: 3 số 1, còn lại toàn số 0

số cách chọn loại 1 đơn giản là 12 cách: chọn 1 vị trí trong 12 phần tử [0,0,0,x,0,0,0,0,0,0,0,0] = 1C12, rồi bỏ số 3 vào = 1 cách, vậy số cách là 1C12 * 1 = 12 cách

số cách chọn loại 2 cách tính tương tự: chọn 2 vị trí trong 12 phần tử [0,x,0,x,0,0,0,0,0,0,0,0] = 2C12, rồi bỏ số 1 và 2 vào 2 vị trí này, vì 1 và 2 khác nhau nên ta có tổng cộng 2 cách, ví dụ [0,1,0,2,0,0,0,0,0,0,0,0] và [0,2,0,1,0,0,0,0,0,0,0,0], vậy số cách là 2C12 * 2 = 132 cách

số cách chọn loại 3 cũng làm tương tự: chọn 3 vị trí trong 12 phần tử [0,x,x,x,0,0,0,0,0,0,0,0] = 3C12, rồi bỏ 3 số 1 vào 3 vị trí này, vì 3 số giống nhau nên ta chỉ có 1 cách :V vậy số cách là 3C12 * 1 = 220 cách

tổng cộng 3 cách = 12 + 132 + 220 = 364 cách, bằng đúng 3C14 :V

---

giải cho 12 màu vào 16 hộp với lập luận tương tự thì có 4 loại:
1111 --> 4C12 * 1 = 495
112 --> 3C12 * 3 (112, 121, 211) = 660
13, 22 --> 2C12 * 3 (13, 31, 22) = 198
4 --> 1C12 * 1 = 12
tổng là 495 + 660 + 198 + 12 = 1365 = 4C15 :V

cho 12 màu vào 17 hộp
5C12 * 1 + 4C12 * 4 + 3C12 * 6 + 2C12 * 4 + 1C12 * 1 = 4368 = 5C16 :V

1 2 1, 1 3 3 1, 1 4 6 4 1 quen quen :V

chứng minh pt này thế nào đây :V

[hungaya (Hung)]

Chứng minh bằng phương pháp tổ hợp, xét bài toán:

x_1 + x_2 + \ldots + x_n = k \: (x_i \ge 0, n \ge k \ge 1)

Cách 1:
Áp dụng công thức, được \binom{n+k-1}{k}.

Cách 2:
Trước tiên, có mệnh đề:
(chứng minh bằng cách sử dụng công thức stars and bars cho số hạng dương)

T(n,k): số cách phân chia có thứ tự n thành tổng gồm k số hạng nguyên dương là \binom{n-1}{k-1} \: (n \ge k \ge 1).

Vì n \ge k nên có ít nhất n-k số hạng x_i = 0, hay nhiều nhất k số hạng x_i > 0. Chia thành các trường hợp dựa theo số lượng x_i > 0.

Nếu số x_j > 0 là i: (1 ≤ i ≤ k)

• Vì tổng i số hạng nguyên dương là k (n-i số hạng còn lại bằng 0), nên số cách bằng số cách của T(k,i).
• Số cách chọn i vị trí trong n số hạng: \binom{n}{i}.

Vì i đi từ 1 tới k nên được tổng: \sum_{i=1}^k \binom{k-1}{i-1}\binom{n}{i}

Từ cách 1 và cách 2, có công thức:
\sum_{i=1}^k \binom{k-1}{i-1} \binom{n}{i} = \binom{n+k-1}{k}

---

Biến đổi đại số tí xíu, đặt j = k-i+1, hay i = k-j+1.
Lower bound và upper bound thay đổi như sau:

• i = 1: j = k - 1 + 1 = k
• i = k: j = k - k + 1 = 1

\begin{aligned} \sum_{i=1}^k \binom{k-1}{i-1} \binom{n}{i} &= \sum_{j=k}^1 \binom{k-1}{k-j} \binom{n}{k-j+1} = \sum_{i=1}^k \binom{n}{k-i+1} \binom{k-1}{k-i} \\ &= \sum_{i=1}^k \binom{n}{k-i+1} \binom{k-1}{(k-1) - (k-i)} = \sum_{i=1}^k \binom{n}{k-i+1} \binom{k-1}{i-1}. \end{aligned}

Kết luận:
\begin{aligned}\sum_{i=1}^k \binom{n}{k-i+1} \binom{k-1}{i-1} = \binom{n+k-1}{k}.\end{aligned}

---

Thanks @rogp10

[rogp10]

Phía trên tổng quát lên sẽ ra hằng đẳng thức Vandermonde.

( Sao ra công thức khác thế nhỉ? )

Bằng nhau đó Khi i chạy từ 1 đến k thì k-i+1 sẽ ntn?

Công thức:

1. Sigma(i=k'..k) f(i) = Sigma(i=k'+m..k+m) f(i-m) m là hằng số nguyên
2. Sigma(i=0..n) f(i) = Sigma(i=0..n) f(n-i)