Ile jest zdominowanych \(\displaystyle{ (n, m)}\) ciągów ?
\(\displaystyle{ (n, m)}\) ciąg to ciąg binarny o \(\displaystyle{ n+m}\) wyrazach (w którym \(\displaystyle{ m}\) jest zer zaś \(\displaystyle{ n}\) jedynek).
Ciąg zdominowany to taki ciąg, w którym wśród początkowych \(\displaystyle{ j}\) wyrazów jest co najmniej tyle zer co jedynek dla \(\displaystyle{ j=1, … ,n+m}\) .
* Jak zmieni się odpowiedź przy modyfikacji tej definicji (zamiast „co najmniej” będzie „więcej”) ?
Ciągi zdominowane
- mol_ksiazkowy
- Użytkownik
- Posty: 11407
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
- 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
Re: Ciągi zdominowane
załóżmy dla ścisłości, że to jedynki dominują zera.
Pierwszy wzór jest prosty pani mnie tego w szkole uczyła, a mianowicie:
n- zera, m- jedynki
\(\displaystyle{ d(n,m)= \frac{m+1-n}{m+1} {n+m \choose m}}\)
\(\displaystyle{ d(n,n)}\)- to liczby Catalana
A teraz taki wzór aby zawsze jedynek było więcej w każdej serii od początku niż zer,
ja tu kombinowałem aby od początku odrzucać takie serie jak:
\(\displaystyle{ (1,0)(11,00)(111,000)}\), itd...
a pozostałe co zostanie dominować wzorem.
I tak np:
\(\displaystyle{ d(2,4)=9}\)
D - niech to będzie zdominowanie z punktu drugiego
czyli np:
\(\displaystyle{ D(2,4)=d(2,4)-d(1,3)-d(0,2)=9-3-1=5}\)
\(\displaystyle{ D(3,5)=d(3,5)-d(2,4)-d(1,3)-d(0,2)=28-9-3-1=15}\)
\(\displaystyle{ D(3,3)=0}\)
Wogóle:
\(\displaystyle{ D(n,n)=0}\)
Powinno być:
dla: \(\displaystyle{ n<m}\)
\(\displaystyle{ D(n,m)=d(n,m)-d(n-1,m-1)-d(n-2,m-2)-...-d(0,m-n)}\)
Udało mi się to skrócić i doprowadzić na lepszy poziom te moje dywagacje i wyszło mi:
Tzn kombinowałem to tak:
\(\displaystyle{ {m+n-1 \choose n}- {m+n-1 \choose m} = \frac{m-n}{m+n} {m+n \choose m}}\)
odrzucałem to co nie pasowało podobnie jak na początku tylko tam chyba z gorszym skutkiem,
i wyszło:
\(\displaystyle{ D(n,m)= \frac{m-n}{m+n} {m+n \choose m}}\)
te moje pierwsze próby zamieniłem w coś lepszego na zasadzie prób i błędów i ten wzór już sprawdzałem na wielu hula dobrze, i wynika z niego iż:
\(\displaystyle{ D(n,n)=0}\)
moje pokrętne ścieżki takiego rozumowania...
Pierwszy wzór jest prosty pani mnie tego w szkole uczyła, a mianowicie:
n- zera, m- jedynki
\(\displaystyle{ d(n,m)= \frac{m+1-n}{m+1} {n+m \choose m}}\)
\(\displaystyle{ d(n,n)}\)- to liczby Catalana
A teraz taki wzór aby zawsze jedynek było więcej w każdej serii od początku niż zer,
ja tu kombinowałem aby od początku odrzucać takie serie jak:
\(\displaystyle{ (1,0)(11,00)(111,000)}\), itd...
a pozostałe co zostanie dominować wzorem.
I tak np:
\(\displaystyle{ d(2,4)=9}\)
D - niech to będzie zdominowanie z punktu drugiego
czyli np:
\(\displaystyle{ D(2,4)=d(2,4)-d(1,3)-d(0,2)=9-3-1=5}\)
\(\displaystyle{ D(3,5)=d(3,5)-d(2,4)-d(1,3)-d(0,2)=28-9-3-1=15}\)
\(\displaystyle{ D(3,3)=0}\)
Wogóle:
\(\displaystyle{ D(n,n)=0}\)
Powinno być:
dla: \(\displaystyle{ n<m}\)
\(\displaystyle{ D(n,m)=d(n,m)-d(n-1,m-1)-d(n-2,m-2)-...-d(0,m-n)}\)
Udało mi się to skrócić i doprowadzić na lepszy poziom te moje dywagacje i wyszło mi:
Tzn kombinowałem to tak:
\(\displaystyle{ {m+n-1 \choose n}- {m+n-1 \choose m} = \frac{m-n}{m+n} {m+n \choose m}}\)
odrzucałem to co nie pasowało podobnie jak na początku tylko tam chyba z gorszym skutkiem,
i wyszło:
\(\displaystyle{ D(n,m)= \frac{m-n}{m+n} {m+n \choose m}}\)
te moje pierwsze próby zamieniłem w coś lepszego na zasadzie prób i błędów i ten wzór już sprawdzałem na wielu hula dobrze, i wynika z niego iż:
\(\displaystyle{ D(n,n)=0}\)
moje pokrętne ścieżki takiego rozumowania...