Trdnjavski polinomi

Definicija: je šahovska deska velikosti , na kateri so določena polja označena kot prepovedana.

t_i(D) - število razporeditev i trdnjav na desko D tako, da v nobeni vrstici in stolpcu ni več kot ena trdnjava.

Definicija: je trdnjavski polinom deske D.

Vemo da velja:

Iz trdnjavskega polinoma deske D lahko izvemo koliko je možnih postavitev k trdnjav na to desko. Število dobimo tako da odčitamo koeficient pred x^k.

Za desko D brez prepovedanih polj velja:

Lastnosti:

1. Število t_i(D) se ne spremeni, če šahovnico transponiramo, zavrtimo ali med seboj zamenjamo vrstice ali stolpce.
2. Osnovna rekurzivna zveza:

   naj bo , ki ni prepovedano.

   D - e: deska, ki jo dobimo, če na D prepovemo polje e

   D / e: deska, ki jo dobimo iz deske D, če iz nje odstranimo celotno vrstico a in celoten stolpec b.

   Za desko D in velja T(D;x) = T(D − e;x) + xT(D / e;x)

3. Naj bo I nabor nekaj vrstic in J nabor nekaj stolpcev. Denimo, da so prepovedana vsa polja deske D, ki bodisi ležijo v vrstici iz I in zunaj stolpcev iz J, bodisi zunaj vrstic iz I in v stolpcu iz J.

   Naj bo: in ali drugače (direktna vsota šahovnic)

   Potem velja: T(D;x) = T(D₁;x)T(D₂;x)

4. Naj bo D deska velikosti m x n. Potem je:

   

   komplementarna deska (zamenjane vloge prepovedanih in dovoljenih polj)

   In za koeficiente velja, da jih dobimo iz koeficientov originalne deske s pomočjo formule: