Kolejka do kina z pustą kasą

[bartm]

W kolejce do kina stoi 2n osób. Bilet kosztuje 1 dukata. Każda osoba ma jedną monetę: n osób ma 1-dukatową, n osób ma 2-dukatową. W kasie nie ma pieniędzy. Ile jest sposobów ustawienia w tej kolejce osób tak, aby każda kupiła bilet?

Głowię się nad tym zadaniem i nic mądrego nie wymyśliłem. Widzę tylko tyle, że pierwszą osobą musi być ta, która ma 1 dukata. I ogólnie w każdym momencie, gdy kolejna osoba podchodzi do kasy, musi być więcej klientów "1-dukatowych" od "2-dukatowych". Ale jak to wszystko zapisać i policzyć - nie mam pojęcia.

Będę wdzięczny za podpowiedź.

[klaustrofob]

jak zauważyłeś, każde rozstawienie wyznacza pewien ciąg złożony z jedynek i minus jedynek, gdzie jedynka na k-tym miejscu oznacza wpływ dukata do kasy, a minus jedynka wypływ. oczywiście, nie każdy ciąg jedynek i minus jedynek jest dozwolony, np. taki (1,-1,1,-1,..., 1,-1) jest ok, ale taki (1,-1,-1,1,1,1,-1,-1...) nie (co zauważyłeś). zauważmy jednak, że "dobre" ciągi są we wzajemnie jednoznacznej odpowiedniości z ciągami niemalejącymi o wyrazach ze zbioru {1,...,n}. odpowiedniość tę zadaje przyporządkowanie \(\displaystyle{ a_i\mapsto a_i+i-1}\), gdzie \(\displaystyle{ a_i}\) to i-ty wyraz "dobrego" ciągu, a \(\displaystyle{ i}\) to jego numer. wystarczy zatem obliczyć ile jest takich ciągów.

korekta - to nie jest rozwiązanie - ta bijekcja nie prowadzi do zbioru wszystkich niemalejących, a słabo rosnących i też nie wszystkich...

w ogólności problem jest rozwiązany np. w książce: Palka, Ruciński, "Wykłady z kobinatoryki". jest to problem ciągów zdominowanych, odpowiedź to: \(\displaystyle{ \frac{1}{n+1}{2n \choose n}}\). można przerobić tam zamieszczone rozwiązanie, ale chętnie zobaczyłbym rozumowanie specyficzne dla tego przykładu.