zastanawiam się jak zrobić to zadanie korzystając z funkcji tworzących:
Ile jest ciągów binarnych długości \(\displaystyle{ n}\) mających \(\displaystyle{ k}\) jedynek oraz żadne z jedynek nie stoją obok siebie ?
mógłby ktoś, proszę, pokazać mi jakoś przejrzyście jak się tego typu zadania robi?
ciągi binarne mające k jedynek
-
arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
ciągi binarne mające k jedynek
Powiem ci jak się zachowuje ciąg jeżeli weźmiemy pod uwagę wszystkie możliwe jedynki:
Zauważ, że gdy ciąg jest jednoelementowy to wtedy jedynek może być jedna lob zero razem dwie,
ciąg dwuelementowy to jedynek: 0, lub 1 i gdy jedynek jedna sztuka to ilość możliwości 2 czyli razem trzy,
dla ciągu 3 elementowego jedynek może być: 0 i tu 1 możliwość, 1 - 3 możliwości 2 - 1 możliwość,
dla 4 elementowego:
0 - 1 , 1 - 4 możliwości, 2- 3 możliwości, itd...
jak widać można porachować:
jeśli przez a en oznaczymy ciąg ilości jedynek to będzie spełniał rekurencję:
\(\displaystyle{ a_{n+2}=a_{n+1}+a_{n}}\) gdzie:
\(\displaystyle{ a_{0}=2, a_{1}=3}\)
Ciąg prawie jak Fibonacciego i w tym przypadku "prawie" robi małą różnicę.
Ciut gorzej z założeniem, że jest tylko k jedynek bo zauważ, że:
\(\displaystyle{ 0 \le k \le \frac{n}{2}}\) dla n parzystego,
i:
\(\displaystyle{ 0 \le k \le [\frac{n}{2}]+1}\) dla n nieparzystego,
potem jakoś coś trzeba kombinować w przypadku różnych k...
Zaobserwowałem jeszcze jedną rzecz, mianowicie, jeżeli ustalimy ilość jedynek w ciągu, niech ich będzie k, oczywiście k spełnia powyższe warunki, to ilość ciągów nas interesujących spełnia:
"ilość ciągów o ilości jedynek k w ciągu o długości n={ilość ciągów o ilości k-1 jedynek w ciągu o długości
n-2}+{ilość ciągów o ilości k jedynek w ciągu o długości n-1}"
Bardziej formalnie to będzie:
\(\displaystyle{ a_{n}[k]=a_{n-2}[k-1]+a_{n-1}[k], k \ge 1}\)
\(\displaystyle{ 0 \le k \le \frac{n}{2}}\) dla n parzystego,
i:
\(\displaystyle{ 0 \le k \le [\frac{n}{2}]+1}\) dla n nieparzystego,
gdzie:
\(\displaystyle{ a_{i}[j]}\) to ilość ciągów spełniających nasze zadanie - ciągu o długości i, w którym występuje j jedynek.
i tak np:
\(\displaystyle{ a_{2}[0]=1}\)
\(\displaystyle{ a_{3}[1]=3}\)
\(\displaystyle{ a_{4}[1]=4}\)
\(\displaystyle{ a_{5}[2]=6}\)
\(\displaystyle{ a_{6}[2]=10}\) ( w ciągu o długości 6, w którym występuje 2 jedynki tych możliwości
jest 10...itd...
\(\displaystyle{ a_{6}[2]=a_{4}[1]+a_{5}[2]}\)
bo: 10=4+6...
a funkcjami tworzącymi pobaw się podczas zamiany ciągu rekurencyjnego na postać jawną...
W sumie moje założenia o liczbie k jest niepotrzebne, bo dla k odpowiednio większych
\(\displaystyle{ a_{n}[k]}\) się zeruje
Zauważ, że gdy ciąg jest jednoelementowy to wtedy jedynek może być jedna lob zero razem dwie,
ciąg dwuelementowy to jedynek: 0, lub 1 i gdy jedynek jedna sztuka to ilość możliwości 2 czyli razem trzy,
dla ciągu 3 elementowego jedynek może być: 0 i tu 1 możliwość, 1 - 3 możliwości 2 - 1 możliwość,
dla 4 elementowego:
0 - 1 , 1 - 4 możliwości, 2- 3 możliwości, itd...
jak widać można porachować:
jeśli przez a en oznaczymy ciąg ilości jedynek to będzie spełniał rekurencję:
\(\displaystyle{ a_{n+2}=a_{n+1}+a_{n}}\) gdzie:
\(\displaystyle{ a_{0}=2, a_{1}=3}\)
Ciąg prawie jak Fibonacciego i w tym przypadku "prawie" robi małą różnicę.
Ciut gorzej z założeniem, że jest tylko k jedynek bo zauważ, że:
\(\displaystyle{ 0 \le k \le \frac{n}{2}}\) dla n parzystego,
i:
\(\displaystyle{ 0 \le k \le [\frac{n}{2}]+1}\) dla n nieparzystego,
potem jakoś coś trzeba kombinować w przypadku różnych k...
Zaobserwowałem jeszcze jedną rzecz, mianowicie, jeżeli ustalimy ilość jedynek w ciągu, niech ich będzie k, oczywiście k spełnia powyższe warunki, to ilość ciągów nas interesujących spełnia:
"ilość ciągów o ilości jedynek k w ciągu o długości n={ilość ciągów o ilości k-1 jedynek w ciągu o długości
n-2}+{ilość ciągów o ilości k jedynek w ciągu o długości n-1}"
Bardziej formalnie to będzie:
\(\displaystyle{ a_{n}[k]=a_{n-2}[k-1]+a_{n-1}[k], k \ge 1}\)
\(\displaystyle{ 0 \le k \le \frac{n}{2}}\) dla n parzystego,
i:
\(\displaystyle{ 0 \le k \le [\frac{n}{2}]+1}\) dla n nieparzystego,
gdzie:
\(\displaystyle{ a_{i}[j]}\) to ilość ciągów spełniających nasze zadanie - ciągu o długości i, w którym występuje j jedynek.
i tak np:
\(\displaystyle{ a_{2}[0]=1}\)
\(\displaystyle{ a_{3}[1]=3}\)
\(\displaystyle{ a_{4}[1]=4}\)
\(\displaystyle{ a_{5}[2]=6}\)
\(\displaystyle{ a_{6}[2]=10}\) ( w ciągu o długości 6, w którym występuje 2 jedynki tych możliwości
jest 10...itd...
\(\displaystyle{ a_{6}[2]=a_{4}[1]+a_{5}[2]}\)
bo: 10=4+6...
a funkcjami tworzącymi pobaw się podczas zamiany ciągu rekurencyjnego na postać jawną...
W sumie moje założenia o liczbie k jest niepotrzebne, bo dla k odpowiednio większych
\(\displaystyle{ a_{n}[k]}\) się zeruje