Ciągi zdominowane

[mol_ksiazkowy]

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”) ?

[arek1357]

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...