Rozstania są ciężkie. Czasem trzeba podzielić się wspólnymi książkami, czasem wspólnym psem. Najgorzej jest jednak, gdy mamy wspólną szachownicę. Jeżeli nie dojdziemy do porozumienia, to możemy skończyć z połową szachownicy. A jak negocjacje pójdą bardzo źle, to z połową trójkątną, na której nie możemy nawet poćwiczyć debiutów.
Dla takiej dziwnej półszachownicy zastanowimy się nad klasycznym problemem: na ile sposobów możemy rozstawić kilka, powiedzmy 4, nieatakujące się wieże?
Wieże atakują się, kiedy są w tym samym wierszu lub w tej samej kolumnie.
Jeżeli uczyliśmy się kiedyś programować, to aby odpowiedzieć na to pytanie, możemy napisać prosty program, który rozważy wszystkie możliwe rozstawienia wież i dla każdego sprawdzi, czy jest poprawne.
Jeśli jest – dodajemy do naszego licznika jeden.
Poniżej znajduje się pseudokod takiego programu (w którym, o dziwo, wcięcia tworzą półszachownicę).
Ten algorytm działa i wyznaczył liczbę 1701. Czuję jednak, że Bardziej Doświadczeni Czytelnicy, widząc go, mogli złapać się za głowę.
Nasze rozwiązanie nie jest bowiem idealne (łagodnie mówiąc). Widzimy na przykład, że gdybyśmy mieli planszę o 20 wierszach, musielibyśmy napisać nowy program, który miałby 20 pętli. Czy da się tego uniknąć? Oczywiście, że tak – wystarczy użyć rekurencji.
Napiszmy funkcję, która – wiedząc, ile wierszy () i wież () zostało jeszcze do rozpatrzenia oraz które kolumny są już zajęte ( to liczba wież w -tej kolumnie) – policzy, ile jest rozmieszczeń wież.
Funkcja ta będzie wywoływała siebie samą dla mniejszej liczby wierszy. Nie jest to problemem, musimy tylko zadbać o warunki brzegowe, aby obliczenie się zakończyło.
Ten algorytm też działa i też wyszło mu 1701. Zaczynamy podejrzewać, że jest to zatem dobry wynik.
A jak szybkie są nasze algorytmy, czyli jaka jest ich złożoność? Koszmarna! !
Zamiast programować, musimy chyba jednak pomyśleć.
Oba powyższe algorytmy w trakcie działania przeglądają wszystkie możliwe rozstawienia wież. Nie musimy jednak tego robić – zależy nam przecież tylko na ich liczbie.
Niech będzie szukaną liczbą rozstawień wież na półszachownicy o wierszach.
Zastanówmy się, jak, znając liczbę rozstawień dowolnej liczby wież dla mniejszej półszachownicy, wyznaczyć
W rozstawieniach tych albo w ostatnim wierszu jest wieża, albo nie.
Rozstawień bez wieży jest dokładnie tyle samo co rozstawień wież na planszy bez ostatniego wiersza, czyli
Rozstawienia z wieżą w ostatnim wierszu to po prostu rozstawienia wież na planszy bez ostatniego wiersza rozszerzone o dostawienie wieży w ostatnim wierszu.
Tę wieżę zawsze możemy dostawić na sposobów, bo kolumn jest już zajętych. Dostajemy więc następujące równanie rekurencyjne:
Dodatkowo musimy przyjąć oraz dla
Możemy teraz sformułować algorytm dynamiczny oparty na powyższym równaniu rekurencyjnym, który po prostu wypełnia tabelkę znajdującą się na marginesie.

Ten algorytm działa w czasie No i znowu znaleźliśmy liczbę 1701!
Jeżeli zależało nam tylko na efektywnej metodzie znalezienia wyniku, to może nam to wystarczyć, jednak z naukowej ciekawości fajnie byłoby trochę lepiej zrozumieć, czym są liczby w tej tabelce. Na pierwszy rzut oka nie przypominają niczego szczególnego. Spróbujmy jednak jakoś je wytropić.
W tym celu wpiszmy ciąg złożony z kolejnych wierszy w internetową encyklopedię ciągów: oeis.org. Okazuje się, że jest to ,,odbity trójkąt liczb Stirlinga drugiego rodzaju”. Co to znaczy? Liczby Stirlinga drugiego rodzaju opisują liczbę różnych podziałów zbioru na podzbiory. Konkretniej, dla liczb naturalnych to liczba możliwych podziałów zbioru złożonego z rozróżnialnych elementów na podzbiorów.
Rzeczywiście, patrząc na trójkąt liczb Stirlinga, widzimy, że wygląda prawie identycznie jak nasz – jest tylko trochę przesunięty (o jeden wiersz i kolumnę w dół) i każdy jego wiersz ma odwróconą kolejność.
Dokładniej:
Chwila, chwila, zliczaliśmy rozstawienia wież i wyszły nam podziały zbioru? Jakiemu podziałowi ma niby odpowiadać rozstawienie wież z początku artykułu? Jest to co najmniej dziwne. Okazuje się jednak, że istnienie tej odpowiedniości to prawda! I to nie byle jaka, bo to taka prawda, którą można ładnie udowodnić.
A takie prawdy to jest to, co w Delcie lubimy najbardziej.
Dodajmy sztuczny -szy wiersz i ponumerujmy kolumny półszachownicy od prawej do lewej,
zaczynając od Teraz półszachownica składa się z wszystkich pól o współrzędnych gdzie (pierwsza współrzędna odpowiada wierszowi, a druga kolumnie). Postawienie wieży w -tym wierszu będziemy teraz odczytywać jako informację, która liczba jest po w jej podzbiorze. Jeżeli wieża stoi na polu to po jest (np. wieża na polu oznacza, że po jest ).
Z kolei jeżeli -ty wiersz jest pusty, to jest ostatnią liczbą w swoim podzbiorze.
Z faktu, że wieże się nie atakują, wiemy, że te informacje są niesprzeczne – nie więcej niż raz wskażemy poprzednika i następnika każdej liczby.
Łącząc te fakty, dostajemy pewien podział zbioru
Na ile części?
Tyle, ile wierszy jest bez wież, czyli dokładnie
Dokładnie tak, jak miało wyjść!
Z różnych rozstawień wież oczywiście wyjdą różne podziały. Ale czy dostaniemy je wszystkie? No tak, bo łatwo wskazać konstrukcję działającą w drugą stronę: z podziału możemy dostać rozstawienie nieatakujących się wież, po prostu wypisując pary elementów sąsiadujących w jego zbiorach, np. da nam wieże I to kończy nasz piękny dowód.