zliczanie liczby ciagów

[matinf]

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 ?

[MatXXX]

Skoro ciąg \(\displaystyle{ n+m}\)-elementowy zachowuje kolejność elementów z ciągów \(\displaystyle{ n}\)-elementowego oraz \(\displaystyle{ m}\)-elementowego, to wystarczy, że wybierzemy pozycje, na które wstawione zostaną elementy krótszego ciągu (z zachowaniem kolejności, jednoznacznie wyznaczy to również miejsca na drugi ciąg). Wtedy mając \(\displaystyle{ m+n}\) miejsc, z czego \(\displaystyle{ m}\) wyróżnionych, na miejsca niewyróżnione przepiszemy ciąg dłuższy, a na wyróżnione krótszy. Czyli z \(\displaystyle{ m+n}\) miejsc w wyjściowym ciągu wybieramy \(\displaystyle{ m}\) na elementy krótszego ciągu. Robimy to na \(\displaystyle{ {n+m \choose m}}\) sposobów.

--EDIT--
Co do twojej sumy: Kiedy \(\displaystyle{ i=1}\), to dzielisz \(\displaystyle{ m}\)-elementowy ciąg na jeden blok i robisz to na \(\displaystyle{ m}\) sposobów. Coś za dużo

Takiego podziału powinieneś dokonać tak, jak dzieliłbyś liczbę \(\displaystyle{ m}\) na \(\displaystyle{ i}\) dodatnich składników ze znaczącą kolejnością składników. Czyli pomiędzy \(\displaystyle{ m}\) nierozróżnialnych elementów wstawić bez powtórzeń \(\displaystyle{ i-1}\) rozdzielaczy. Czyli pierwszy czynnik w sumie powinien wyglądać \(\displaystyle{ {m-1 \choose i-1}}\).

[matinf]

Ja się zgadzam co do Twojego wyniku, on jest prawidłowy

Nie mnie jednak moja suma była prawie dobra
Dzięki za jej poprawienie.
\(\displaystyle{ \sum_{i=1}^{m}{m-1\choose i-1}{n+1\choose i} = {n+m\choose m}}\)