Kaç tane farklı $iyi$ dizi vardır?

1 beğenilme 0 beğenilmeme
40 kez görüntülendi
Pozitif tam sayılardan oluşan   $a_{1} ,.....,a_{2014}$   dizisi

  • $a_{i}\leq2014$
  • $\forall$ $i\neq j$ için $a_{i}\neq a_{j}$
  • $\forall$ $i<j$ için $a_{i}+i\leq a_{j}+j$
  • koşullarını sağlıyorsa bu diziye $iyi$ dizi diyelim.Kaç tane farklı  $iyi$  dizi vardır?
31, Ocak, 31 Orta Öğretim Matematik kategorisinde ysf.knt (193 puan) tarafından  soruldu
31, Ocak, 31 alpercay tarafından düzenlendi

1 cevap

1 beğenilme 0 beğenilmeme

$\forall$   $1\leq i <j\leq n$ için $a_{i}+i \leq a_{j}+j$   $n$ elemandan oluşan $iyi$ dizilerin sayısı $f(n)$ olsun. O zaman $f(1)=1$.

Bir iyi dizide $a_{1}=n$ olursa $a_{2}=n-1$ , $a_{3}=n-2$,....$a_{n}=1$ olmak zorundadır.Bir iyi dizide $1\leq k\leq {n-1}$ olmak üzere bir $k$ için $a_{k+1}=n$ olursa $n-a_{k+2}\leq 1$ ve buradan $a_{k+2}=n-1$.Benzer şekilde tüm $3\leq j \leq n-k$ değerleri için $a_{k+j}=n+1-j$ olmak zorundadır.O zaman dizinin ilk $k$ elemanından oluşan kısmı $a_{1},a_{2},...,a_{k}$ da iyi dizi olma zorundadır ve $a_{1},a_{2},....,a_{k}$ ve $a_{k+1},....,a_{n}$ dizilerinin bileşimi açık şekilde iyi dizi olacaktır.

Sonuç olarak $f(n)_1+ f(1)+f(2)+...+f(n-1)$ ve buradan $f(n)=2f(n-1)$ elde ediyoruz : $f(n)=2^{n-1}.$

Cevap: $2^{2013}$ tür.

31, Ocak, 31 ysf.knt (193 puan) tarafından  cevaplandı
...