Liczba ciągów - postać zwarta

[Peter_85]

Dla \(\displaystyle{ n \ge 1}\) dane są dwa różnowartościowe ciągi liczb: \(\displaystyle{ \left( a_{1}, \ldots, a_{n} \right)}\) i \(\displaystyle{ \left( b_{1}, \ldots, b_{n} \right)}\) takie, że dla dowolnych \(\displaystyle{ 1 \le i,j \le n}\) zachodzi \(\displaystyle{ a_{i} \neq b_{j}}\) (czyli wszystkie liczby \(\displaystyle{ 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 \(\displaystyle{ \left( c_{1}, \ldots, c_{2n} \right)}\) spełniający następujące warunki:

- każda z liczb \(\displaystyle{ 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 \(\displaystyle{ i, j, k, l \in \left\{ 1, \ldots, n \right\}}\) jeśli \(\displaystyle{ c_{i}=a_{k}}\) i \(\displaystyle{ c_{j}=a_{l}}\) i \(\displaystyle{ i<j}\), to \(\displaystyle{ k<l}\) oraz dla dowolnych \(\displaystyle{ i, j, k, l \in \left\{ 1, \ldots n \right\}}\) jeśli \(\displaystyle{ c_{i}=b_{k}}\) i \(\displaystyle{ c_{j}=b_{l}}\) i \(\displaystyle{ i<j}\), to \(\displaystyle{ k<l}\). Krótko mówiąc: szukamy liczby takich permutacji elementów zbioru \(\displaystyle{ \left\{a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n} \right\}}\), że dowolne 2 wyrazy \(\displaystyle{ a_{i} ,a_{j}}\) pierwszego ciągu i dowolne 2 wyrazy \(\displaystyle{ 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 \(\displaystyle{ 2n}\) różnych książek, przy czym są one ułożone na 2 stosach po \(\displaystyle{ 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 \(\displaystyle{ n=1}\) mamy 2 takie ciągi: \(\displaystyle{ \left(a_{1}, b_{1} \right),\left(b_{1}, a_{1} \right)}\)
- dla \(\displaystyle{ n=2}\) mamy 6 ciągów: \(\displaystyle{ \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 \(\displaystyle{ n \ge 1}\) jest ona równa \(\displaystyle{ \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ą.

[kmarciniak1]

Wolfram Alpha umie policzyć postać zwartą tej sumy:
\(\displaystyle{ \sum_{i=0}^{n-1} {n-1 \choose i} {n+1 \choose i+1}= \frac{4 ^{n}(n- \frac{1}{2})! }{ n!\sqrt{ \pi } }}\)

[Peter_85]

Wolphram umie policzy postać zwartą tej sumy:
\(\displaystyle{ \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ć \(\displaystyle{ \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.

[kmarciniak1]

Jak rozumieć ułamkową silnię? Jako funkcję gamma Eulera? Ile ma wynosić \(\displaystyle{ \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 \(\displaystyle{ 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

[Janusz Tracz]

kmarciniak1 napisał(a):
Wolphram umie policzy postać zwartą tej sumy:
\(\displaystyle{ \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ę

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Vandermonde%27s_identity

. 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ć):

\(\displaystyle{ \sum_{i=0}^{n-1} {n-1 \choose i} {n+1 \choose i+1}= {2n \choose n}}\)

[Premislav]

Istotnie. Mamy
\(\displaystyle{ {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 \(\displaystyle{ i\ge 1}\), toteż
\(\displaystyle{ \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}}\)

[Janusz Tracz]

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 \(\displaystyle{ \left( a_{1}, \ldots, a_{n} \right)}\) oraz druga też ma zbiór \(\displaystyle{ \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 \(\displaystyle{ \left( a_{1}, \ldots, a_{n} \right)}\) i \(\displaystyle{ \left( b_{1}, \ldots, b_{n} \right)}\) a potem jedna z nich wybierze losowa \(\displaystyle{ n}\) elementów co może uczynić na \(\displaystyle{ {2n \choose n}}\) sposobów (druga osoba zabiera resztę \(\displaystyle{ n}\) elementów). Po takiej wymianie ich zbiory po "sklejeniu" są jednym z możliwych zbiorów \(\displaystyle{ \left( c_{1}, \ldots, c_{2n} \right)}\) zatem jest ich \(\displaystyle{ {2n \choose n}}\).

[Peter_85]

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 \(\displaystyle{ \left( n- \frac{1}{2} \right)!}\) po "przetłumaczeniu" na funkcję gamma? Chyba nie jest to po prostu \(\displaystyle{ \Gamma\left( n- \frac{1}{2} \right)}\) ? Gdyby tak było, to już dla \(\displaystyle{ n=1}\) mielibyśmy niezgodność: \(\displaystyle{ \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 \(\displaystyle{ 4}\), podczas gdy naprawdę wynosi \(\displaystyle{ 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.

[Janusz Tracz]

a propos podanej tu postaci wyniku z użyciem silni/funkcji gamma: ile to jest konkretnie \(\displaystyle{ \left( n- \frac{1}{2} \right)!}\)po "przetłumaczeniu" na funkcję gamma? Chyba nie jest to po prostu \(\displaystyle{ \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

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

Zatem dla \(\displaystyle{ n=1}\) masz \(\displaystyle{ \Gamma\left(1+ \frac{1}{2} \right)= \frac{ \sqrt{ \pi } }{2}}\) co już będzie dawać spodziewany wynik.

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.

[arek1357]

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

[a4karo]

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 \(\displaystyle{ \pi}\), to niestety czeka cię mnóstwo nieprzyjemnych chwil w toalecie. Może lepiej, żebyć tam siedział zamiast chodzić ma takie marsze

\(\displaystyle{ 1=\frac{\pi}{\pi}}\) - tak mi Wolfram wyliczył

Kod: Zaznacz cały

https://www.wolframalpha.com/input/?i=pi%2Fpi

[arek1357]

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