szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 23 lip 2015, o 20:54 
Użytkownik

Posty: 1936
Lokalizacja: Warszawa
Mamy dwa ciągi liczb:
pierwszy n liczb, drugi m liczb. n\ge m

Ile jest ciągów długości 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 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:

\sum_{i=1}^{m}{m\choose i}{n+1\choose i}
Dzielę krótszy ciąg na i bloków, a następnie dla tych bloków wybieram pozycje w ciągu n liczb.
Raz, że nie wiem czy to dobrze, a dwa że nie wiem jak tą sumę uprościć.
Co Wy na to ?
Góra
Mężczyzna Offline
PostNapisane: 24 lip 2015, o 14:53 
Użytkownik

Posty: 59
Lokalizacja: Polska
Skoro ciąg n+m-elementowy zachowuje kolejność elementów z ciągów n-elementowego oraz 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 m+n miejsc, z czego m wyróżnionych, na miejsca niewyróżnione przepiszemy ciąg dłuższy, a na wyróżnione krótszy. Czyli z m+n miejsc w wyjściowym ciągu wybieramy m na elementy krótszego ciągu. Robimy to na {n+m \choose m} sposobów.

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

Takiego podziału powinieneś dokonać tak, jak dzieliłbyś liczbę m na i dodatnich składników ze znaczącą kolejnością składników. Czyli pomiędzy m nierozróżnialnych elementów wstawić bez powtórzeń i-1 rozdzielaczy. Czyli pierwszy czynnik w sumie powinien wyglądać {m-1 \choose i-1}.
Góra
Mężczyzna Offline
PostNapisane: 24 lip 2015, o 16:46 
Użytkownik

Posty: 1936
Lokalizacja: Warszawa
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.
\sum_{i=1}^{m}{m-1\choose i-1}{n+1\choose i} = {n+m\choose m}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest dzielnikow liczby  Anonymous  6
 ustawianie osob w rzedzie, liczby n-cyfrowe itp  Anonymous  16
 liczby podzielne  BSD  9
 liczby podzielne - zasada wlaczania i wylaczania  BSD  3
 Liczby Bella - pytanie[nowe]  author  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl