Tablica Wythoffa

Czyli macierz powstała z ciągu Fibonacciego, która ma wiele ciekawych właściwości.

Wygląda ona tak:

Konstruowana jest w następujący sposób:
1. Pierwsza kolumna to kolejne nieujemne liczby całkowite: 0, 1, 2, 3...

2. Druga kolumna to dolna sekwencja Wythoffa (http://www.research.att.com/~njas/sequences/A000201), której n-ty element jest równy części całkowitej z (n+1)*φ
gdzie φ to złoty podział (1,61803399...), który jak wiadomo pojawia się też w ciągu Fibonacciego ;)

3. Mając pierwsze dwie kolumny wiersze konstruujemy podobnie do ciągu Fibonacciego - każda kolejna kolumna to suma dwóch poprzednich.

OK, to jakie są ciekawe właściwości tablicy Wythoffa?

Formalnie rzecz biorąc tablicą Wythoffa nazywamy tylko to, co na obrazku powyżej znajduje się po prawej stronie kreski (czyli bez pierwszych dwóch kolumn). Poniższe własności odnoszą się do tej części macierzy:

1. Pierwszy wiersz to fragment ciągu Fibonacciego (OK, to było całkiem oczywiste).
2. Pierwszy element każdego wiersza to najmniejsza liczba, której nie ma w wierszach które są powyżej danego wiersza.
3. Każda liczba naturalna pojawia się w macierzy dokładnie raz.
4. Każda kolumna i każdy wiersz zawiera ciąg rosnący.

Tablica Wythoffa ma też własności fraktalo-podobne. Z jej użyciem można zdefiniować ciąg para-Fibonacciego (http://www.research.att.com/~njas/sequences/A019586):

0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, 3, 2, 6, 1, 7, 4, 0, 8, 5, ...

n-ty wyraz tego ciągu jest równy numerowi wiersza tablicy Wythoffa (numerowanym po ludzku, od 0), gdzie znajduje się liczba n. I tak 1, 2 i 3 znajdziemy w pierwszym wierszu (o indeksie 0), a np. dwunastkę dopiero w piątym wierszu (indeks równy 4). Ciekawą własnością tego ciągu jest to, iż jest podobny do fraktala. Np. usuńmy pierwsze wystąpienie każdej liczby z tego ciągu (pogrubione cyfry):

0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, 3, 2, 6, 1, 7, 4, 0, 8, 5, ...

Usuwając pogrubione cyfry otrzymujemy:

0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, ...

Tak, to nadal jest ciąg para-Fibonacciego. Usuwamy z niego elementy, a on nadal jest taki sam ;)

Więcej:
http://mathworld.wolfram.com/WythoffArray.html