Kombinatoryka - enumeratory

[Fluorek]

Cześć,
mam problem z zadaniem z matematyki dyskretnej.


Rzucamy 2022 uczciwymi czworościennymi kośćmi do gry (na każdej z kostek niezależnie może wypaść 1, 2, 3 albo 4 oczka z jednakowymi prawdopodobieństwami).
Przez \(\displaystyle{ p_n}\) oznaczmy prawdopodobieństwo, że wypadło w sumie n oczek. Wynika z tego, że:

a. \(\displaystyle{ p_{2n+2022} = \frac{1}{4^{2022}} \cdot \sum_{i=0}^{n} {2022 \choose 2i} {2022 \choose n-i} }\)

c. funkcja tworząca ciągu \(\displaystyle{ \left\langle p_n \right\rangle }\) jest pewnym wielomianem



Staram się znaleźć wzór ogólny dla tego problemu.
Próbowałem przy mniejszej ilości kostek, ale na nic nie wpadłem.

Czy może ma ktoś jakiś pomysł jak sobie z tym poradzić?

[Janusz Tracz]

Ja to widzę tak, że \(\displaystyle{ \Omega=\left\{ 1,2,3,4\right\}^{2022} }\), czyli przestrzenią są ciągi długości \(\displaystyle{ 2022}\) o wartościach \(\displaystyle{ 1,2,3,4}\). A zdarzenie które nas interesuje to takie, że wybrany ciąg sumuje się do \(\displaystyle{ n}\). Wystarczy więc zliczyć ile jest takich ciągów które spełniają układ warunków

\(\displaystyle{ x_1+\ldots+x_{2022}=n \quad \& \quad \bigwedge_{k=1}^{2022} x_k\in\left\{ 1,2,3,4\right\}. }\)

Liczba ta występuje przy \(\displaystyle{ x^n}\) w wielomianie \(\displaystyle{ \left( x+x^2+x^3+x^4\right)^{2022} }\). To oznacza się czasem

\(\displaystyle{ \mathcal{G}_n=[\mathrm{x}^n]\left( x+x^2+x^3+x^4\right)^{2022}}\)

przy czym milcząco zakładam, że \(\displaystyle{ 2022\le n \le 4 \cdot 2022}\) bo inaczej kładziemy \(\displaystyle{ \mathcal{G}_n}\). Ostatecznie

\(\displaystyle{ p_n= \frac{\mathcal{G}_n}{\left| \Omega\right| } = \frac{[\mathrm{x}^n]\left( x+x^2+x^3+x^4\right)^{2022} }{4^{2022}}. }\)

Jeśli o jawne obliczenie \(\displaystyle{ \mathcal{G}_n}\) to mam taki pomysł aby zauważyć, że

\(\displaystyle{ \left( x+x^2+x^3+x^4\right)^{2022}=x^{2022} \sum_{i=0}^{ \infty } {2022 \choose i}\chi_{\left\{ 0,1,\ldots,2022\right\} }(i)x^i \times \sum_{j=0}^{ \infty } {2022 \choose j}\chi_{\left\{ 0,1,\ldots,2022\right\} }(j)x^j }\)

A to z iloczynu Cauchy’ego można zapisać jako

\(\displaystyle{ \left( x+x^2+x^3+x^4\right)^{2022}=x^{2022} \sum_{\ell=0}^{ \infty } \sum_{k=0}^{\ell} {2022 \choose \ell-k} {2022 \choose k} \chi_{\left\{ 0,1,\ldots,2022\right\} }(\ell-k) \chi_{\left\{ 0,1,\ldots,2022\right\} }(k) x^{\ell}}\)

To przypomina Twój wzór. Dla \(\displaystyle{ \ell=n-2022}\) mamy

\(\displaystyle{ \mathcal{G}_n=\sum_{k=0}^{n-2022} {2022 \choose n-2022-k} {2022 \choose k} \chi_{\left\{ 0,1,\ldots,2022\right\} }(n-2022-k) \chi_{\left\{ 0,1,\ldots,2022\right\} }(k). }\)

EDIT: Niestety pojawiło się kilka literówek, które szczęśliwie Dasio11 wyłapał (za co dziękuję).

ERRATA

Jest

• kładziemy \(\displaystyle{ \mathcal{G}_n}\)

• \(\displaystyle{ \left( x+x^2+x^3+x^4\right)^{2022}=x^{2022} \sum_{i=0}^{ \infty } {2022 \choose i}\chi_{\left\{ 0,1,\ldots,2022\right\} }(i)x^i \times \sum_{j=0}^{ \infty } {2022 \choose j}\chi_{\left\{ 0,1,\ldots,2022\right\} }(j)x^j}\)

Powinno być

• kładziemy \(\displaystyle{ \mathcal{G}_n=0}\)

• \(\displaystyle{ \left( x+x^2+x^3+x^4\right)^{2022}=x^{2022} \sum_{i=0}^{ \infty } {2022 \choose i}\chi_{\left\{ 0,1,\ldots,2022\right\} }(i)x^i \times \sum_{j=0}^{ \infty } {2022 \choose j}\chi_{\left\{ 0,1,\ldots,2022\right\} }(j)x^{2j}}\)

O ile pierwszy błąd drukarski jest nie zmienia rozwiązania to drugi wymaga pewnego komentarza. Aby skorzystać z iloczynu Cauchy’ego trzeba wykonać jeszcze jeden krok pośredni mianowicie

\(\displaystyle{ \sum_{j=0}^{ \infty } {2022 \choose j}\chi_{\left\{ 0,1,\ldots,2022\right\} }(j)x^{2j} = \sum_{j=0}^{ \infty } {2022 \choose j/2}\chi_{\left\{ 0,2,4,\ldots,4044\right\} }(j)x^{j} }\)

przy czym napisy typu \(\displaystyle{ {2022 \choose 1/2},{2022 \choose 3/2} }\) umawiamy się interpretować jako \(\displaystyle{ 0}\). To niegroźna umowa którą możemy tu lokalnie zastosować w opozycji do innych strasznych rozwiązań typu

jak się zwykle uogólnia dwumian:    

\(\displaystyle{ {x \choose y}={\frac {\Gamma (x+1)}{\Gamma (y+1)\Gamma (x-y+1)}}={\frac {1}{(x+1)\mathrm {B} (x-y+1,y+1)}}}\)

Tak czy inaczej te dziwne napisy będą mnożone przez \(\displaystyle{ 0}\) więc nie ma to większego znaczenia. Ważne jest jednak to, że teraz można zastosować iloczyn Cauchy’ego z podobnym rezultatem co w pierwszym podejściu.