zliczanie liczby ciagów
: 23 lip 2015, o 21:54
Mamy dwa ciągi liczb:
pierwszy \(\displaystyle{ n}\) liczb, drugi \(\displaystyle{ m}\) liczb. \(\displaystyle{ n\ge m}\)
Ile jest ciągów długości \(\displaystyle{ m+n}\), takich że otrzymujemy je przez splot dwóch innych w taki sposób, że:
dla każdego elementu z krótszego ciągu losujemy pozycję w ciągu \(\displaystyle{ n}\) liczb. Wstawiamy go. Potem losujemy dla kolejnego, ale już tylko spośród pozycji późniejszych, np:
3 9 8 2 1 4 5
4 7 8
Losuję dla czwórki, powiedzmy:
3 9 4 8 2 1 4 5
Teraz losuję dla siódemki, np:
3 9 4 7 8 2 1 4 5
Teraz dla ósemki:
3 9 4 7 8 2 1 4 5 8
I teraz ja bym podszedł do tego tak:
\(\displaystyle{ \sum_{i=1}^{m}{m\choose i}{n+1\choose i}}\)
Dzielę krótszy ciąg na \(\displaystyle{ i}\) bloków, a następnie dla tych bloków wybieram pozycje w ciągu \(\displaystyle{ n}\) liczb.
Raz, że nie wiem czy to dobrze, a dwa że nie wiem jak tą sumę uprościć.
Co Wy na to ?
pierwszy \(\displaystyle{ n}\) liczb, drugi \(\displaystyle{ m}\) liczb. \(\displaystyle{ n\ge m}\)
Ile jest ciągów długości \(\displaystyle{ m+n}\), takich że otrzymujemy je przez splot dwóch innych w taki sposób, że:
dla każdego elementu z krótszego ciągu losujemy pozycję w ciągu \(\displaystyle{ n}\) liczb. Wstawiamy go. Potem losujemy dla kolejnego, ale już tylko spośród pozycji późniejszych, np:
3 9 8 2 1 4 5
4 7 8
Losuję dla czwórki, powiedzmy:
3 9 4 8 2 1 4 5
Teraz losuję dla siódemki, np:
3 9 4 7 8 2 1 4 5
Teraz dla ósemki:
3 9 4 7 8 2 1 4 5 8
I teraz ja bym podszedł do tego tak:
\(\displaystyle{ \sum_{i=1}^{m}{m\choose i}{n+1\choose i}}\)
Dzielę krótszy ciąg na \(\displaystyle{ i}\) bloków, a następnie dla tych bloków wybieram pozycje w ciągu \(\displaystyle{ n}\) liczb.
Raz, że nie wiem czy to dobrze, a dwa że nie wiem jak tą sumę uprościć.
Co Wy na to ?