Čebiševljevi polinomi važan su i moćan alat koji se primjenjuju u različitim područjima znanosti i tehnike.
Ovdje opisujemo njihove kombinatorne modele, konkretno modele popločavanja, kojima možemo jednostavno pokazati neka svojstva ovih zanimljivih polinoma.
Uvod
Čebiševljeve polinome uveo je ruski matematičar Pafnuti Čebišev krajem 19. stoljeća. Pojavljuju se u različitim područjima matematike — algebri, teoriji brojeva no ponajviše u numeričkoj matematici. Njihova primjena veže se ponajviše za aproksimaciju funkcija, interpolaciju polinoma i numeričko rješavanje jednadžbi (posebice diferencijalnih jednadžbi). Posjeduju mnogo zanimljivih svojstava. Na primjer, međusobno su ortogonalni, zadovoljavaju rekurziju (drugog reda) pa se lako računaju, minimiziraju “maksimalnu pogrešku”, smanjuju vjerojatnost pojave tzv. Rungeova fenomena itd. Svima koji više žele doznati o primjeni Čebiševljevih polinoma u numeričkoj matematici preporučamo skriptu Numerička analiza [1] kolegija Numerička analiza (s Matematičkog odsjeka PMF-a u Zagrebu). Kad govorimo o ovom području, nemoguće je ne prisjetiti se troje prerano preminulih profesora: Mladena Rogine te supružnika Sanje i Saše Singer od kojih je i starija koautorica puno naučila.
Definicije i osnovna svojstva
Postoje četiri vrste Čebiševljevih polinoma. Nas zanimaju Čebiševljevi polinomi prve vrste i Čebiševljevi polinomi druge vrste koji se standarno označavaju s $T_n$ i $U_n$. Mogu se definirati primjenom trigonometrijskih funkcija.
Definicija 1. Neka je $n$ nenegativan cijeli broj. Čebiševljev polinom prve vrste stupnja $n$ definira se kao
\begin{equation} \tag{1}
T_n(x)=\cos (n\cdot\arccos x),
\end{equation}
za $x\in [-1,1]$. Čebiševljev polinom druge vrste stupnja $n$ definira se kao
\begin{equation} \tag{2} U_n(x)=\frac{\sin{((n+1)\cdot\arccos{x})}}{\sin(\arccos{x})},
\end{equation}
za $x\in \langle -1,1\rangle$.
Za početak trebamo utvrditi da su tako definirane funkcije $U_n$ i $T_n$ uistinu polinomi stupnja $n$. Za $n=0,1$ lako je vidjeti kako je
\begin{equation} \tag{3} T_0(x)=1,\ T_1(x)=x \end{equation}
te
\begin{equation} \tag{4} U_0(x)=1,\ U_1(x)=2x. \end{equation}
Sada pokažimo da nizovi polinoma $(T_n)$ i $(U_n)$ zadovoljavaju rekurzivne relacije. U tu svrhu primjenjujemo adicijske formule za kosinus
$$ \cos(\alpha \pm \beta )=\cos \alpha \cos \beta \mp \sin \alpha \sin \beta. $$
Njihovim zbrajanjem dobivamo
$$ \cos(\alpha + \beta )+ \cos(\alpha – \beta )=2\cos \alpha \cos \beta.$$
Za $\alpha=\theta$ i $\beta=(n-1)\theta$ dobivamo
$$\underbrace{ \cos{(n\theta)}}_{T_n(x)}+\underbrace{ \cos{((n-2)\theta)}}_ {T_{n-2}(x)}= 2\underbrace{ \cos{\theta}}_{x}\underbrace{ \cos{((n-1)\theta})}_{T_{n-1}(x)},$$
gdje smo označili $x=\cos\theta$, odnosno $\theta= \arccos x$. Slično, primjenom adicijskih formula za sinus
$$\sin{(\alpha \pm \beta)}=\sin{\alpha}\cos{\beta} \pm \sin{\beta}\cos{\alpha}, $$
dobivamo
$$ \underbrace{\frac{\sin{(n+1)\theta}}{\sin{\theta}}}_{U_n(x)} + \underbrace{\frac{\sin{(n-1)\theta}}{\sin{\theta}}}_{U_{n-2}(x)} = 2 \underbrace{\cos{\theta}}_{x}\underbrace{\frac{\sin{n\theta}}{\sin{\theta}}}_{U_{n-1}(x)}. $$
Stoga Čebiševljevi polinomi $(T_n)$ i $(U_n)$ zadovoljavaju (iste) rekurzije drugog reda
\begin{equation} \tag{5} T_n(x)=2xT_{n-1}(x)-T_{n-2}(x),\ \ n\ge2, \end{equation}
\begin{equation} \tag{6} U_n(x)=2xU_{n-1}(x)-U_{n-2}(x),\ \ n\ge2, \end{equation}
uz početne uvjete [3], odnosno [4]. Često se navedene rekurzivne relacije, iz kojih je sada jasno kako se radi o polinomima, primjenjuju za definiciju polinoma $T_n$ i $U_n$.
| $n$ | $T_n(x)$ | $U_n(x)$ |
| $0$ | $1$ | $1$ |
| $1$ | $x$ | $2x$ |
| $2$ | $2x^2-1$ | $4x^2-1$ |
| $3$ | $4x^3-3x$ | $8x^3-4x$ |
| $4$ | $8x^4-8x^2+1$ | $16x^4-12x^2+1$ |
| $5$ | $16x^5-20x^3+5x$ | $32x^5-32x^3+6x$ |
Na slikama 1a i 1b prikazano je po prvih pet Čebiševljevih polinoma.
Ideja popločavanja
Zamislimo da želimo popločati ploču veličine $1 \times n$ (ili kraće duljine $n$) s pomoću:
- kvadratnih pločica dimenzije $1\times 1$
- pravokutnih ili domino pločica dimenzije $1\times 2$.
Naše pitanje glasi: na koliko načina možemo to učiniti? Odgovor na ovo pitanje u vezi je s jednim od najpoznatijih rekurzivnih nizova — Fibonaccijevim nizom koji je određen rekurzijom
$ F_{n}=F_{n-1}+F_{n-2}, \ n > 1,$
uz početne uvjete $F_0=0$, $F_1=1$. Svaki Fibonaccijev broj može se interpretirati kao broj načina na koji ga možemo prikazati kao zbroj čiji su pribrojnici 1 ili 2 (vidi tablicu 2).
| $n$ | sume | broj načina |
| $1$ | $1$ | $1=F_2$ |
| $2$ | $1+1$, $2$ | $2=F_3$ |
| $3$ | $1+1+1$, $1+2$, $2+1$ | $3=F_4$ |
| $4$ | $1+1+1+1$, $1+1+2$, $1+2+1$, $1+1+2$, $2+2$ | $5=F5$ |
Zamislimo sada da svaku jedinicu u sumama iz tablice zamijenimo kvadratnom pločicom dimenzije $1\times 1$, a svaku dvojku domino pločicom dimenzije $1\times 2$. Uz tu “zamjenu” svaka suma $n$ postaje jedno popločavanje ploče duljine $n$, a ukupan broj svih mogućih popločavanja ploče duljine $n$ iznosi $F_{n+1}$.
Općenito, kod modela popločavanja potrebno je uvesti pojmove kao što su težina pločice, težina ploče (odnosno pojedinačnog popločavanja) i ukupna težina svih popločavanja. Težina pločica obično je jednaka koeficijentima iz rekurzije. U modelu popločavanja za Fibonaccijeve brojeve uzimamo da je težina obiju pločica (kvadratne i domino) jednaka 1. Težina svakog popločavanja, to jest težina ploče definira se kao umnožak težina svih pločica koje sudjeluju u tom popločavanju. Konačno, ukupna težina popločavanja ploče $1\times n$ jednaka je zbroju težina svih ploča $1\times n$. Budući da je u modelu popločavanja za Fibonaccijeve brojeve težina svake ploče jednaka 1, ukupna težina popločavanja jednaka je broju načina na koji ju možemo popločati (vidi sliku 2).
Četiri kombinatorna problema za Čebiševljeve polinome
U ovom odjeljku predstavljamo po dva kombinatorna modela za Čebiševljeve polinome prve, odnosno druge vrste. Najprije opisujemo modele za Čebiševljeve polinome druge vrste jer su nešto jednostavniji.
Model I za $U_n$: Popločavanje jednom bojom.
Ploču dimenzije $1\times n$ popločavamo kvadratnom $\boxed{{\color{white}a}}$ i domino pločicom $\boxed{{\color{white}aaa}}$ (u istoj boji). S obzirom na to da polinomi $U_n$ zadovoljavaju rekurzivnu relaciju (6), stavljamo da je težina kvadratne pločice $2x$, a pravokutne (domino) $-1$. Obično se težina označava s $\omega$, pa je
$$ \omega\left(\boxed{{\color{white}a}}\right)=2x,\ \ \omega\left(\boxed{{\color{white}aaa}}\right)=-1.$$
U prethodnom smo odjeljku težinu ploče definirali kao umnožak težina pločica od kojih je sastavljena. Tako je, na primjer
$$\omega\left(\boxed{{\color{white}a}}\boxed{{\color{white}aaa}}\boxed{{\color{white}a}}\boxed{{\color{white}a}}\right)= (2x)(-1)(2x)(2x)=-8x^3.$$
Težina “praznog popločavanja” (koje odgovara $n=0$) je po definiciji 1 (u ovom i sljedećim modelima).
Teorem 1. Ukupna težina svih popločavanja ploče dimenzije $1\times n$ prema modelu I jednaka je $U_n(x)$, za sve $n\ge0$.
Dokaz: Primjenjujemo načelo matematičke indukcije po $n\ge 0$.
Baza: Za $n=0, 1$ tvrdnja očito vrijedi (vidi sliku 3).
Pretpostavka indukcije: Pretpostavimo da tvrdnja vrijedi za popločavanje ploče duljine $n-1$ i $n-2$, $n\ge 2$.
Korak indukcije: Popločavanje ploče duljine $n$, $n\ge2$, može završiti kvadratnom ili domino pločicom. Dakle, svako popločavanje je oblika
\begin{equation}\label{e10}
\boxed{\text{popločavanje duljine } n-1}\ \boxed{{\color{white}j} 2x}\end{equation}
ili
\begin{equation}\label{e11}
\boxed{\text{popločavanje duljine } n-2}\ \boxed{{\color{white}p} -1 \ }\,.\end{equation}
Prema pretpostavci indukcije težina svih popločavanja tipa (7) je $2xU_{n-1}(x)$, a tipa (8) je $(-1)U_{n-2}(x)$. Stoga je težina svih popločavanja ploče duljine $n$ jednaka
$$2xU_{n-1}(x)-U_{n-2}(x)$$
što je upravo $U_n(x)$ prema rekurziji (6).
□
Model II za $U_n$: Popločavanje dvjema bojama.
Za popločavanje ploče duljine $n$ upotrebljavamo dvije vrste kvadratnih pločica — bijelu i sivu te (bijelu) domino pločicu. Težine pločica zadane su s:
Teorem 2. Ukupna težina svih popločavanja ploče dimenzije $1\times n$ prema modelu II jednaka je $U_n(x)$, za sve $n\ge0$.
Dokaz: Sve je analogno teoremu 1, samo što u “koraku” imamo tri mogućnosti za popločavanje ploče duljine $n$, $n\ge 2$. Popločavanje može završiti dominom, bijelim kvadratićem ili sivim kvadratićem:
Uz primjenu pretpostavke indukcije i relacije (6) imamo $$-U_{n-2}(x)+xU_{n-1}(x)+xU_{n-1}(x)=U_n(x).$$
□
Model III za $T_n$: Popločavanje jednom bojom.
Popločavamo kvadratnim i domino pločicama težina $2x$ i $-1$ kao u modelu I, osim u slučaju kada popločavanje započinje kvadratnom pločicom. Tada je njegova težina jednaka $x$. Dakle,
$$ \omega\left(\boxed{{\color{white}a}}\right)=\begin{cases}
x, \text{ ako je } \boxed{{\color{white}a}}\text{ početna pločica }\\
2x,\text{ inače }
\end{cases},\ \ \omega\left(\boxed{{\color{white}aaa}}\right)=-1.$$
Teorem 3. Ukupna težina svih popločavanja ploče dimenzije $1\times n$ prema Modelu III jednaka je $T_n(x)$, za sve $n\ge0$.
Dokaz: Analogno dokazu teorema 1. □
Model IV za $T_n$: Popločavanje dvjema bojama.
Ovaj je model analogan modelu II uz uvjet da popločavanje ne može započeti sivom kvadratnom pločicom. Dakle,
Teorem 4. Ukupna težina svih popločavanja ploče dimenzije $1\times n$ prema Modelu IV jednaka je $T_n(x)$, za sve $n\ge0$.
Dokaz: Analogno dokazu teorema 2. □
Identiteti
Čebiševljevi polinomi zadovoljavaju različite identitete. U ovom odjeljku iskazujemo one koje možemo pokazati primjenom opisanih kombinatornih modela i osnovnih načela prebrojavanja.
Teorem 5. $xU_{n-1}(x)+T_n(x)=U_n(x),\ n\geq 1.$
Dokaz: Primjenjujemo model II za $U_n$. Razlikujemo dva slučaja u ovisnosti o tome počinje li popločavanje “iz $U_n(x)$” sivom pločicom ili ne. Ako popločavanje započinje sivom pločicom, takvih je $xU_{n-1}(x)$ (prema modelu II), odnosno imamo:
Ako popločavanje ne započinje sivom pločicom, onda započinje bijelom kvadratnom ili domino pločicom, a takvih je $T_n(x)$ prema modelu IV, tj. imamo
Zbroj težina svih popločavanja iz ovih dvaju slučaja je
$$xU_{n-1}(x)+T_n(x),$$
što je jednako $U_n(x)$. □
Teorem 6. $ U_n – 2T_n = U_{n-2},\ n\ge2.$
Dokaz: $T_n(x)$ je, prema modelu IV, zbroj težina svih popločavanja ploče duljine $n$ koja ne počinju sivom pločicom. Stoga $2T_n(x)$ možemo prikazati kao
Budući da bijela i siva pločica imaju istu težinu, prethodna popločavanja možemo prikazati i na sljedeći način:
pri čemu smo težine svih popločavanja odredili prema kombinatornom modelu II.
Stoga je $2T_n=U_n-U_{n-2}$. □
Teorem 7. $T_{m+n} = T_mU_n – T_{m-1}U_{n-1},\ m,n\ge1.$
Dokaz: Prema modelu III $T_{m+n}(x)$ zbroj je težina svih popločavanja ploče duljine $m+n$, pri čemu je težina kvadratne pločice na početku jednaka $x$, a na ostalim pozicijama $2x$. Svako popločavanje može biti jednog od ovih oblika:
\begin{equation}\tag{9}
\boxed{\text{popločavanje duljine } m\hspace{1.5cm} }\ \boxed{\text{popločavanje duljine }n \hspace{1.8cm}}
\end{equation}
ili
\begin{equation}\tag{10} \boxed{\text{popločavanje duljine } m-1\ \ \ \ }\ \boxed{{\color{white}p} -1 \ }\ \boxed{\text{popločavanje duljine } n-1\ \ \ \ }
\end{equation}
Uočimo da prvi dio ploče (duljine $m$) iz (9) predstavlja neko popločavanje za $T_m(x)$ prema modelu III. Drugi dio ploče (duljine $n$) je neko popločavanje za $U_n(x)$ prema modelu I (jer nemamo uvjet da je početna kvadratna pločica težine $x$). Stoga je, prema osnovnim načelima prebrojavanja, zbroj težina svih popločavanja oblika (9) jednak $T_m(x)U_n(x)$.
Analogno zaključujemo da je zbroj težina svih popločavanja oblika (10) jednak $T_{m-1}(x)(-1)U_{n-1}(x)=-T_{m-1}(x)U_{n-1}(x).$ □
Identiteti iz teorema 5, 6 i 7 mogu se standardno pokazati s pomoću načela matematičke indukcije i rekurzivnih relacija (5), (6) ili primjenom odgovarajućih trigonometrijskih identiteta i definicije 1 (vidi [6]).
Formule za polinome $T_n$ i $U_n$ u terminima potencija od $x$ su posebno korisne. Može ih se dobiti primjenom de Moivreove formule
$$e^{in\theta}= (\cos \theta+i\sin \theta)^{n}=\cos n\theta+i\sin n\theta, $$
pri čemu je $i$ imaginarna jedinica (tj. $i^2=-1$). Otuda je
$$
\cos(n\theta)=\frac{e^{in\theta}+e^{-in\theta}}{2}
=\frac{(\cos \theta+i\sin \theta)^n+(\cos \theta-i\sin \theta)^n}{2}
$$
te
$$ \sin(n\theta) =\frac{e^{in\theta}-e^{-in\theta}}{2i}=\frac{(\cos \theta+i\sin \theta)^n-(\cos \theta-i\sin \theta)^n}{2i},$$
pa uz nešto raspisivanja gornji izrazi za $\cos(n\theta)$ i $\sin(n\theta)/\sin \theta $ mogu se prikazati sume potencija od $\cos \theta=x$ (vidi 6). U onome što slijedi pokazujemo kako dolazimo do formula za $T_n(x)$ i $U_n(x)$ s pomoću njihovih kombinatornih modela.
Teorem 8. $$U_n(x)=\sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k {n-k \choose k} (2x)^{n-2k}, \ n \geq 0$$
Dokaz: Neka je $U_n(x)$ dan modelom I. Pretpostavimo da u nekom popločavanju $P$ imamo točno $k$ ($\le \lfloor n/2 \rfloor$) domino pločica. To znači da u njemu mora biti točno $n-2k$ kvadratnih pločica, tj.
$ P\ : \ \ \boxed{{\color{white}aaa}} \ \ldots\ k,\ \ \boxed{{\color{white}a}}\ \ldots \ n-2k.$
Ukupan broj pločica u popločavanju $P$ je $k+n-2k=n-k$. Domino pločice na toj ploči možemo rasporediti na
$$ {n-k \choose k} $$
načina. Dakle, ukupna težina svih popločavanja ploče duljine $n$ koja sadržavaju točno $k$ domino pločica iznosi:
$$ {n-k \choose k} (-1)^k (2x)^{n-2k}.$$
Stoga je ukupna težina svih popločavanja ploče duljine $n$ jednaka
$$\sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k {n-k \choose k} (2x)^{n-2k}.$$ □
Primjer 1. (Kombinatorna interpretacija formule za $U_6(x)$)
Prema teoremu 8 je $$U_6(x)=\sum_{k=0}^{3} (-1)^k \binom{6-k}{k} (2x)^{6-2k} =(-1)^0 (2x)^6 + 5(-1)^1(2x)^4 + 6(-1)^2(2x)^2+(-1)^3(2x)^0$$
Prethodni izraz možemo “pročitati” na način da se popločavanje ploče duljine $6$ po modelu I sastoji od:
- jednog popločavanja bez domino pločica
- pet popločavanja s jednom domino pločicom
- šest popločavanja s dvjema domino pločicama
- jednog popločavanja s trima domino pločicama.
Teorem 9. $$2T_n(x)=\sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \frac{n}{n-k} {n-k \choose k} (2x)^{n-2k}, \ n \geq 1.$$
Dokaz: Neka je $P$ neko popločavanje polinoma $T_n$, $n\ge2$, prema modelu III u kojemu imamo $k\ge1$ domino pločica. Popločavanje $P$ može započeti kvadratnom pločicom težine $x$ ili domino pločicom, odnosno vrijedi jedna od sljedeći shema
\begin{equation}\tag{11}
\boxed{{\color{white}j} x} \ \boxed{\ \ \ \text{popločavanje duljine } n-1\ \ \ }\,,
\end{equation}
\begin{equation}\tag{12}
\boxed{{\color{white}p} -1 \, }\ \boxed{\text{popločavanje duljine } n-2}\, .
\end{equation}
U slučaju (11) $k$ domino pločica možemo rasporediti na “ostatku” popločavanja duljine $n-1$ na
$${n-k-1 \choose k}$$
načina. Naime, u popločavanju duljine $n-1$ nalazi se $k$ domino pločica i $n-1-2k$ kvadratnih pločica, odnosno ukupno $n-k-1$ pločica.
U slučaju (12) na “ostatku” popločavanja duljine $n-2$ imamo $k-1$ domino pločica i $n-2-2(k-1)=n-2k$ kvadratnih pločica, tj. ukupno $n-k-1$ pločica. Stoga je broj takvih popločavanja jednak
$${n-k-1 \choose k-1}. $$
Težina svih popločavanja duljine $n\ge2$ koje zadrže točno $k\ge1$ domino pločica je
\begin{align} & x\cdot {n-k-1 \choose k}(-1)^k(2x)^{n-2k-1}+ (-1)\cdot {n-k-1 \choose k-1}(-1)^{k-1}(2x)^{n-2k}\\ =&\frac12 \left( {n-k-1 \choose k}+2{n-k-1 \choose k-1}\right)(-1)^k(2x)^{n-2k}\\ =& \frac12 \left( {n-k \choose k}+{n-k-1 \choose k-1}\right)(-1)^k(2x)^{n-2k}\\ =& \frac12\cdot \frac{n}{n-k} {n-k \choose k}(-1)^k(2x)^{n-2k}. \end{align}
Težina popločavanja duljine $n$ koje ne sadrži domino pločicu je
$$ x\cdot(2x)^{n-1}=\frac12\cdot(2x)^{n}.$$
Konačno, ukupna težina svih popločavanja duljine $n\ge 2$ je
$$\frac12\cdot(2x)^{n} + \sum_{k= 1}^{\lfloor n/2 \rfloor} \frac12 \cdot \frac{n}{n-k} {n-k \choose k}(-1)^k(2x)^{n-2k}=\frac12 \sum_{k= 0}^{\lfloor n/2 \rfloor} \frac{n}{n-k} {n-k \choose k}(-1)^k(2x)^{n-2k} .$$
Za $n=1$ formula se direkno lako provjeri. □
Zahvale: Autorica Z. F. zahvaljuje Hrvatskoj zakladi za znanost na financijskoj potpori projekta IP-2022-10-5008.
Literatura
- Z. Drmač, V. Hari, M. Marušić, M. Rogina, Sanja Singer, Saša Singer, Numerička analiza, Sveucilište u Zagrebu, PMF — Matematički odsjek, 2007.
- J. C. Mason, D. C. Handscomb, Chebyshev Polynomials, Chapman and Hall/CRC, 2002.
- T. J. Rivlin, Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory: Second Edition, John Wiley $\&$ Sons, Inc., New York, 1990.
- D. Walton, A Tiling Approach to Chebyshev Polynomials, Harvey Mudd College, Department of Mathematics, 2007.
- J. Zubak, Kombinatorni modeli Čebiševljevih polinoma, diplomski rad, PMF-Matematički odsjek, Sveučilište u Zagrebu, 2024.