szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 16 maja 2019, o 18:27 
Użytkownik

Posty: 31
Lokalizacja: Polska
Dla n \ge 1 dane są dwa różnowartościowe ciągi liczb: \left( a_{1}, \ldots, a_{n} \right) i \left( b_{1}, \ldots, b_{n} \right) takie, że dla dowolnych 1 \le i,j  \le n zachodzi a_{i} \neq b_{j} (czyli wszystkie liczby a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n} są różne). Na ile sposobów można te 2 ciągi scalić w ciąg \left( c_{1}, \ldots, c_{2n} \right) spełniający następujące warunki:

- każda z liczb a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n} występuje w wynikowym ciągu dokładnie 1 raz
- względna kolejność wyrazów każdego z 2 oryginalnych ciągów zostaje zachowana, tzn. dla dowolnych i, j, k, l \in \left\{ 1, \ldots, n \right\} jeśli c_{i}=a_{k} i c_{j}=a_{l} i i<j, to k<l oraz dla dowolnych i, j, k, l \in \left\{ 1, \ldots n \right\} jeśli c_{i}=b_{k} i c_{j}=b_{l} i i<j, to k<l. Krótko mówiąc: szukamy liczby takich permutacji elementów zbioru \left\{a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n} \right\}, że dowolne 2 wyrazy a_{i} ,a_{j} pierwszego ciągu i dowolne 2 wyrazy b_{i},b_{j} drugiego ciągu pojawiają się w nowym ciągu w takiej kolejności względem siebie, jak w oryginalnych ciągach (usunięcie z wynikowego ciągu wszystkich wyrazów pierwszego ciągu daje w wyniku drugi ciąg i vice versa).
Bardziej obrazowo: mamy 2n różnych książek, przy czym są one ułożone na 2 stosach po n książek każdy. W każdym kroku wybieramy jeden ze stosów, zdejmujemy książkę z jego szczytu i umieszczamy ją na kolejnej pozycji od lewej strony na półce (początkowo pustej). Czynność powtarzamy tak długo, aż wszystkie książki trafią na półkę. Ile jest różnych sposobów ułożenia książek według powyższej reguły? Dwa sposoby uważamy za różne jeśli odpowiadająca im kolejność książek na półce jest różna.

Przykład:
- dla n=1 mamy 2 takie ciągi: \left(a_{1}, b_{1} \right),\left(b_{1}, a_{1} \right)
- dla n=2 mamy 6 ciągów: \left(a_{1}, a_{2}, b_{1}, b_{2} \right), \left(a_{1}, b_{1}, a_{2}, b_{2} \right), \left(a_{1}, b_{1}, b_{2}, a_{2} \right), \left(b_{1}, b_{2}, a_{1}, a_{2} \right),\left(b_{1}, a_{1}, b_{2}, a_{2} \right),\left(b_{1}, a_{1}, a_{2}, b_{2} \right).
Udało mi się wyznaczyć (w dość pokrętny sposób) liczbę takich ciągów, mianowicie dla dowolnego n \ge 1 jest ona równa \sum_{i=0}^{n-1} {n-1 \choose i}  {n+1 \choose i+1}, ale interesuje mnie zwarta postać tej sumy (o ile istnieje), ewentualnie jakiś prosty sposób wyznaczenia liczby takich ciągów, prowadzący bezpośrednio do zwartego wzoru. Niestety kombinatoryka nigdy nie była moją mocną stroną.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2019, o 19:24 
Użytkownik

Posty: 662
Wolfram Alpha umie policzyć postać zwartą tej sumy:
\sum_{i=0}^{n-1} {n-1 \choose i} {n+1 \choose i+1}= \frac{4 ^{n}(n- \frac{1}{2})! }{ n!\sqrt{ \pi } }
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2019, o 20:26 
Użytkownik

Posty: 31
Lokalizacja: Polska
kmarciniak1 napisał(a):
Wolphram umie policzy postać zwartą tej sumy:
\sum_{i=0}^{n-1} {n-1 \choose i} {n+1 \choose i+1}= \frac{4 ^{n}(n- \frac{1}{2})! }{ n!\sqrt{ \pi } }


Jak rozumieć ułamkową silnię? Jako funkcję gamma Eulera? Ile ma wynosić \left( n- \frac{1}{2}\right)! ? Swoją drogą, jestem zaskoczony, że liczba opisanych przeze mnie ciągów nie da się wyrazić w prosty sposób bez użycia funkcji nieeelementarnych - strzelając "w ciemno" obstawiałbym coś bardzo prostego.
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2019, o 20:50 
Użytkownik

Posty: 662
Peter_85 napisał(a):
Jak rozumieć ułamkową silnię? Jako funkcję gamma Eulera? Ile ma wynosić \left( n- \frac{1}{2}\right)! ? Swoją drogą, jestem zaskoczony, że liczba opisanych przeze mnie ciągów nie da się wyrazić w prosty sposób bez użycia funkcji nieeelementarnych - strzelając "w ciemno" obstawiałbym coś bardzo prostego.

Tak, trzeba to traktować jako funkcję gamma.Myślałem, że może chcesz jakieś konkretne wartości .Pierwsze pięć to odpowiednio 2,6,20,70,252
A jeśli po prostu chciałeś dojść do zwartej postaci wyrażonej bardziej elementarnie to wychodzi na to, że się nie da :wink:
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2019, o 21:32 
Użytkownik
Avatar użytkownika

Posty: 2058
Lokalizacja: hrubielowo
Cytuj:
kmarciniak1 napisał(a):
Wolphram umie policzy postać zwartą tej sumy:
\sum_{i=0}^{n-1} {n-1 \choose i} {n+1 \choose i+1}= \frac{4 ^{n}(n- \frac{1}{2})! }{ n!\sqrt{ \pi } }


Można to uprościć jeszcze posługując się własnościami gamma lub kombinować coś w stronę Wzór Vandermondsa. Dobrze było poszukać też interpretacji kombinatorycznej, albo dowód indukcyjny tez powinien przejść. Postuluję tezę (której nie mam czasu teraz dokładnie udowadniać):

\sum_{i=0}^{n-1} {n-1 \choose i} {n+1 \choose i+1}= {2n \choose n}
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2019, o 22:11 
Użytkownik
Avatar użytkownika

Posty: 13706
Lokalizacja: Wrocław
Istotnie. Mamy
{n+1\choose i+1}={n \choose i}+{n \choose i+1}={n-1\choose i-1}+2{n-1\choose i}+{n-1\choose i+1}
dla i\ge 1, toteż
\sum_{i=0}^{n-1} {n-1 \choose i} {n+1 \choose i+1}=\\=n+1+\sum_{i=1}^{n-1} {n-1 \choose i} {n-1 \choose i-1}+2\sum_{i=1}^{n-1} {n-1 \choose i}^2+\sum_{i=1}^{n-1} {n-1 \choose i} {n-1 \choose i+1}=\\=2\sum_{i=0}^{n-2} {n-1 \choose i+1} {n-1 \choose n-1-i}+2\sum_{i=0}^{n-1} {n-1 \choose i}{n-1\choose n-1-i}=\\=2{2n-2\choose n}+2{2n-2\choose n-1}=2{2n-1\choose n}={2n \choose n}
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2019, o 22:18 
Użytkownik
Avatar użytkownika

Posty: 2058
Lokalizacja: hrubielowo
Chociaż... może i mam pomysł na interpretację kombinatoryczną. Załóżmy, że mamy dwie osoby posiadające kolekcję elementów czyli jedna ma zbiór \left( a_{1}, \ldots, a_{n} \right) oraz druga też ma zbiór \left( b_{1}, \ldots, b_{n} \right). Pytanie na ile sposobów mogą się mogą się powymieniać elementami (reguła wymiany to jeden za jeden oraz dopuszczam wymianę pustą czyli brak wymiany). Można to policzyć na przykład zakładając, że jedna i druga osoba wsypie do jednego wora to co ma czyli \left( a_{1}, \ldots, a_{n} \right) i \left( b_{1}, \ldots, b_{n} \right) a potem jedna z nich wybierze losowa n elementów co może uczynić na {2n \choose n} sposobów (druga osoba zabiera resztę n elementów). Po takiej wymianie ich zbiory po "sklejeniu" są jednym z możliwych zbiorów \left( c_{1}, \ldots, c_{2n} \right) zatem jest ich {2n \choose n}.
Góra
Mężczyzna Offline
PostNapisane: 16 maja 2019, o 22:37 
Użytkownik

Posty: 31
Lokalizacja: Polska
Dziękuję za wszystkie odpowiedzi. Czułem, że wynik da się opisać zgrabniej niż ja to zrobiłem. Tak, jak wcześniej wspomniałem, swój rezultat uzyskałem okrężną drogą, stąd jego mniej przystępna postać. Mam jeszcze takie pytania:

1) a propos podanej tu postaci wyniku z użyciem silni/funkcji gamma: ile to jest konkretnie \left( n- \frac{1}{2} \right)! po "przetłumaczeniu" na funkcję gamma? Chyba nie jest to po prostu \Gamma\left( n- \frac{1}{2} \right) ? Gdyby tak było, to już dla n=1 mielibyśmy niezgodność: \Gamma\left( n- \frac{1}{2} \right) = \Gamma\left( 1- \frac{1}{2} \right) = \Gamma\left( \frac{1}{2} \right) = \sqrt{ \pi } i wartość całej sumy wynosiłaby 4, podczas gdy naprawdę wynosi 2.

2) czy to, co zdefiniowałem, to jakiś powszechnie znany i opisywany w literaturze matematycznej ciąg? Mam nieodparte wrażenie, że to jakiś bardzo klasyczny problem.
Góra
Mężczyzna Offline
PostNapisane: 17 maja 2019, o 07:09 
Użytkownik
Avatar użytkownika

Posty: 2058
Lokalizacja: hrubielowo
Cytuj:
a propos podanej tu postaci wyniku z użyciem silni/funkcji gamma: ile to jest konkretnie \left( n- \frac{1}{2} \right)!po "przetłumaczeniu" na funkcję gamma? Chyba nie jest to po prostu \Gamma\left( n- \frac{1}{2} \right) ?
Nie. Gamma i silnia są ze sobą związane ale przesunięte o jeden zobacz własności Gammy. Zachodzi

\left( n- \frac{1}{2} \right)!
=\Gamma\left( n+ \frac{1}{2} \right)

Zatem dla n=1 masz \Gamma\left(1+ \frac{1}{2} \right)= \frac{ \sqrt{ \pi } }{2} co już będzie dawać spodziewany wynik.
Cytuj:
czy to, co zdefiniowałem, to jakiś powszechnie znany i opisywany w literaturze matematycznej ciąg? Mam nieodparte wrażenie, że to jakiś bardzo klasyczny problem.
Nie wiem.
Góra
Mężczyzna Offline
PostNapisane: 19 maja 2019, o 10:30 
Użytkownik
Avatar użytkownika

Posty: 3681
Lokalizacja: blisko
Może się niepotrzebnie wtrącam ale jak widzę wzór gdzie lewa strona jest całkowita a prawa niewymierna, z uzasadnieniem, że wyliczył tak wolfram to dostaję torsji, podobnie jak wczoraj na marszu równości w Krakowie...
Góra
Mężczyzna Offline
PostNapisane: 19 maja 2019, o 11:00 
Użytkownik

Posty: 16533
Lokalizacja: Bydgoszcz
arek1357 napisał(a):
Może się niepotrzebnie wtrącam ale jak widzę wzór gdzie lewa strona jest całkowita a prawa niewymierna, z uzasadnieniem, że wyliczył tak wolfram to dostaję torsji, podobnie jak wczoraj na marszu równości w Krakowie...


Jeżeli dowodem na niewymierność liczby jest obecność we wzorze liczby \pi, to niestety czeka cię mnóstwo nieprzyjemnych chwil w toalecie. Może lepiej, żebyć tam siedział zamiast chodzić ma takie marsze :P

1=\frac{\pi}{\pi} - tak mi Wolfram wyliczył https://www.wolframalpha.com/input/?i=pi%2Fpi
Góra
Mężczyzna Offline
PostNapisane: 19 maja 2019, o 13:04 
Użytkownik
Avatar użytkownika

Posty: 3681
Lokalizacja: blisko
Niestety w tym wzorze do którego się odniosłem niewymierność wynikająca z liczby pi jest tak samo prawdziwa jak prawda najprawdziwsza, natomiast niewymierność w Twoim wzorze wynikająca z obecności liczby pi jest tak samo prawdziwa jak Twoja dzisiaj na mszy w kościele...
A co do marszu to niestety przypadkowo się tam znalazłem...
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile różnych dzielników ma liczba  Anonymous  8
 Ilu jest uczniów w klasie jesli wiadomo że liczba utworzo  Acura_100  5
 wykazać że istnieje liczba całkowita podzielna przez 17..  noob  2
 liczba znajomych  noob  1
 liczba 4 cyfrowa  wojteka  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl