[Kombinatoryka] szachownica, wieża i fajny podzbiór

[porfirion]

Czy zna ktoś z Was rozwiązanie takiego problemu:
Dana jest szachownica \(\displaystyle{ m \times n}\). Podzbiór pól tej szachownicy nazwiemy fajnym, jeśli z każdego pola podzbioru można wieżą przejść na dowolne inne pole podzbioru, przy czym podczas ruchów wieża nie może poruszać się po polach nie należących do podzbioru. Ile jest fajnych podzbiorów?
// (Inaczej mówiąc nasza wieża to taki król nie chodzący po skosie...)
?

[kerajs]

Jeśli dobrze rozumiem , a wcale nie jestem tego pewien, to opis fajnego podzbioru dla króla niechodzącego po skosie spełnia jedynie prostokąt 2X1 pól.
Wtedy szukana ilość to \(\displaystyle{ \frac{nm-1}{2}}\) dla szachownicy o nieparzystej liczbie pól i \(\displaystyle{ \frac{nm}{2}}\) dla szachownicy o parzystej liczbie pól .

[a4karo]

Chyba źle rozumiesz. Fajny jest na przykład kwadrat 3x3 z wyciętym środkiem.

Generalnie, niefajne są zbiory niespójne i takie, które mają "coś po skosie" (choć też nie do końca: jak z kwadratu 3x3 wytniesz środek i jeden wierzchołek, to on nadal będzie fajny)

Fajne na pewno są węże zakręcające pod kątem prostym (w szczególności takimi są prostokąty i przykłądy powżej.

[kerajs]

Twój przykład nie spełnia:

jeśli z każdego pola podzbioru można wieżą przejść na dowolne inne pole podzbioru

Przejście miedzy wierzchołkami odbyłoby się po skosie.

Ponadto, co z ruchem króla tylko o jedno pole.

[a4karo]

A1-A2-A3-B3-C3-C2-C1-B1-A1. W ten sposob obejdę cały zbiór, wiec dostane sie z każdego pola na każde inne.

[porfirion]

a4karo, oczywiście dobrze mnie zrozumiałeś.

[Swistak]

Jak na mój gust, to szczerze mówiąc, nie wydaje mi się, aby to się jakkolwiek dało policzyć. Skądś wziąłeś ten problem, czy samemu taki wytrzasnąłeś?

[porfirion]

Autorski problem (niestety).
Oczywiście nie mam pojęcia jak go rozwiązać i to boli.

[kaszubki]

Niech ta liczba to będzie \(\displaystyle{ f(n, m)}\).
\(\displaystyle{ f(1, m)}\) to liczba wszystkich podpasków paska \(\displaystyle{ 1 \times m}\), czyli \(\displaystyle{ 1 + m + \binom{m}{2} = \frac{m^2 + m + 2}{2}}\).

Ok, teraz załóżmy, że jest jakiś ładny wzór na \(\displaystyle{ f(n,m)}\). Jeśli jest, to jest też na \(\displaystyle{ f(2, m)}\).
Aby znaleźć \(\displaystyle{ f(2, m)}\) zapuściłem backtracka, dzięki któremu znalazłem początkowe wartości: {{0,1}, {1,4}, {2,14}, {3,41}, {4,109}, {5,276}, {6,682}, {7,1665}, {8,4041}, {9,9780}, {10,23638}, {11,57097}, {12,137877}, {13,332900}, {14,803730}, {15,1940417}, {16,4684625}} gdzie {a,b} oznacza, że \(\displaystyle{ f(2, a) = b}\).
Wartości te rosną jakoś wykładniczo, ale nie widzę jak. OEIS nie podaje żadnego ciągu.
Więc raczej nie istnieje żaden sensowny wzór.

A, jest szansa że nie umiem klepać. Jakby komuś wyszły inne wartości, to niech napisze.

[micha73]

Po prostu wliczałeś też zbiór pusty, a na OEIS jest bez niego.

Kod: Zaznacz cały

https://oeis.org/A059020

- \(\displaystyle{ 2 \times n}\),

Kod: Zaznacz cały

https://oeis.org/A059021

- \(\displaystyle{ 3 \times n}\), https://oeis.org/A059524 - \(\displaystyle{ 4 \times n}\), https://oeis.org/A059525 - \(\displaystyle{ n \times n}\). Więcej nie znalazłem.

[Msciwoj]

Uwzględniłeś zbiór pusty. Jeżeli go nie uwzględnisz i odejmiesz od wszystkich wartości 1, to OEIS już coś tam podaje:

Kod: Zaznacz cały

https://oeis.org/A059020

Podaje nawet wzór jawny: \(\displaystyle{ a(n)= -\frac{7}{2}+\frac{7}{4} \cdot (1+ \sqrt{2})^n-2n-\frac{5}{4}\cdot \sqrt{2} \cdot (1-\sqrt{2})^n+\frac{7}{4} \cdot (1- \sqrt{2})^n+\frac{5}{4} \cdot [1 + \sqrt{2}]^n \cdot \sqrt{2}}\)

EDIT: Ubiegłeś mnie...

[kaszubki]

OK, to w takim razie nie spodziewałem się tego, że jakiś śmieszek wrzuci ciąg zmniejszony o 1. I jeszcze niepoprawnie go nazwie.
Precz z dyskryminacją zbiorów pustych!