anh nào ơi, giúp em với

[skater]

em có một bài tổ hợp bằng tiếng anh, dịch đi dịch lại vẫn ko hiểu đề, đại ca nào giúp đc ko???
A sequence of n positive integers is full if for eack $k > 1 $, $k $ only occurs if $k-1 $ occurs before the last occurrence of $k $. How many full sequences are there for each $n $?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[n.t.tuan]

Một dãy gồm n số nguyên dương được gọi là đủ nếu với mỗi k>1, k chỉ xuất hiện nếu k-1 xuất hiện trước lần xuất hiện cuối cùng của k. Có bao nhiêu dãy đủ.

CHẮC THẾ!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[skater]

em cũng dịch ra như vậy nhưng có chỗ này ko hiểu:
k chỉ xuất hiện nếu k-1 xuất hiện trước lần xuất hiện cuối cùng của k. thì với mỗi $2 <= k <= n $ thì luôn tồn tại dãy đủ là $1,2,...,k $. Như thế là có $n-1 $ dãy đủ nhưng mà đáp số là $n! $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[psquang_pbc]

Đáp số bài này là n!, mình có đọc qua bài giải rồi, reply cho Lộc nhé

Ta xây dựng song ánh từ tập $A\longrightarrow B $

trong đó

$A $ là tập tất cả các bộ đầy đủ

$B $ là hoán vị của bộ $\{1,2,..,n\} $

Thật vậy, mỗi bộ $(b_1,b_2,..,b_n)\in B $, ta xây dựng 1 dãy đầy đủ như sau

Gọi $S_1=\{b_1,..,b_{k_1}\} $ trong đó $b_1>..b_{k_1-1} < b_{k_1} $

$S_2=\{b_{k_1},...,b_{k_2}\} $ trong đó $b_{k_1}>...>b_{k_2-1}<b_{k_2} $

Định nghĩa tương tự cho $S_i $

Chọn ngay $a_1=1 $, giả sử $2\in S_j $, từ đó $a_2=...=a_j=2 $, Nếu $3\in S_t, t\le j $ thì chọn $a_m=2 $ với $m\ge j $

Nếu $3\in S_t,t>j $ thì chọn $a_{j+1}=...=a_t=3 $, quá trình tiếp tục như trên, và hiển nhiên rằng dãy $(a_1,a_2,..,a_n) $ là 1 dãy đầy đủ

Mỗi dãy đầu đủ $(a_1,a_2,..,a_n) $ ta đặt $k=a_t=max (a_1,a_2,..,a_n) $

Khi đó $(a_1,...,a_n)=(1,2,...,k) $ Đặt $S_i=\{k:a_k=i\}\;,\;|S_i|\not=0,\forall i $

Do bộ trên là đầy đủ nên $min S_{i-1}<max S_{i} $

Xếp các phần tử của $S_i $theo chiều giảm ta được 1 bộ hoán vị của $(1,2,...,n) $

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]