Sloane's On-Line Encyclopedia of Integer Sequences
Von: matroid
Datum: Mo. 10. Juni 2002 00:03:18
Thema: Tools



Meine heutige Empfehlung gilt einer Datenbank für Folgen. Darin kann man nach einem bekannten Teilstück einer Zahlenfolge suchen und erhält als Antwort alle gespeicherten Folgen, die diese Sequenz enthalten.


Meiner Erfahrung nach, findet man so gut wie alles, was eine mathematisch begründbare Herleitung hat. Die Suchergebnisse enthalten den Namen der Folge, ein Bildungsgesetz oder eine Rekursion - soweit bekannt - und durchweg Literaturhinweise oder manchmal auch Verweise auf Webseiten. Die Datenbank wächst mit der Hilfe Vieler, die weitere Folgen eintragen.


Hier geht es zu Sloane's On-Line Encyclopedia of Integer Sequences.


Wie kann man diese Datenbank nutzen?

  1. Ist die Aufgabe als Rätsel gemeint, dann ist Sloane's einen Versuch wert, allerdings gibt es viele Rätsel ohne mathematischen Hintergrund. Manchmal findet man etwas, aber nicht immer.

    Beispiel: Setze die Folge 4,1,5,9,2,6 mit 5 weiteren Zahlen fort!

    Lösung: 5,3,5,8,9, denn die gegebenen Zahlen sind die 3. bis 8. Zahl aus der Dezimaldarstellung von p.

  2. Meine häufigste Anwendung: Es ist eine kombinatorische Aufgabe gestellt, in der etwas gezählt werden muß. Findet ich keinen Ansatz für eine allgemeine Formel oder Rekursion, dann bestimme ich für kleine n einige Folgenglieder. Mit dem Anfangsstück der Folge suche ich bei Sloane's. Aus der Beschreibung und den gegebenen Formeln der gefundenen Formeln erhalte ich nützliche Hinweise zur Behandlung der Aufgabenstellung oder einfach die Bestätigung, daß meine eigene Überlegung richtig war.


Beispielsweise folgende Aufgabe:

Wie viele unterscheidbare ringförmige Sitzordnungen von n Personen
gibt es, bei denen - relativ zu einer vorgegebenen Anfangssitzordnung
(1-2-3....-n) - jeder 2 neue Nachbarn hat?

Einige Werte der gesuchte Anzahl kann man relativ einfach durch Abzählen bekommen - unter Einsatz eines Computers -, aber irgendwann werden die
Werte natürlich astronomisch.

Plätze     Sitzordnungen

------------------------

5 2

6 6

7 46

8 354

9 3106

10 29926

11 315862

12 3628906



Zum Programm, mit dem ich gezählt habe.


Mit den Zahlen 2,6,46,354,3106,29926 stieg ich in die Suche bei Sloane's ein. Und ...

... kein Treffer. Hatte ich eine unbekannte Folge entdeckt? Würde ich unsterblich werden?

Zu früh gefreut! Die Folge zur Lösung der Aufgabe ist bei Sloane's zu finden. Ich hatte zu viele Möglichkeiten mitgezählt, auch die, die durch Spiegelung auseinander hervorgehen.
Ohne gespiegelte Lösungen lautet der Anfang der Folge: 1,3,23,177,1553.

Bingo! Suche danach ist ein Treffer. Unter der A-Nummer A002816 stehen die Zahlen 0, 0, 1, 3, 23, 177, 1553, 14963, 157931, 1814453, 22566237, 302267423, ... und die Beschreibung lautet:

Polygons formed from n points on circle, no 2 adjacent.

Also number of ways of seating n people around a circular table so that no
one sits next to any of his neighbors in a previous seating order.

Eine Formel ist angegeben
(n^2 - 7n + 9)a(n) =   (n^3 - 8n^2 + 18n - 21)a(n - 1)

+ 4n(n - 5)a(n - 2)

- 2(n - 6)(n^2 - 5n + 3)a(n - 3)

+ (n^2 - 7n + 9)a(n - 4)

+ (n - 5)(n^2 - 5n + 3)a(n - 5)


und auch noch ein Link.


Ich habe keine Ahnung, wie man diese Rekursionsformel herleitet und muß
nun gestehen, daß es sich nicht um eine Übungsaufgabe handelt, sondern um ein echtes Problem, das in der Newsgroup de.sci.mathematik vor einiger Zeit aufgetaucht war.


Der Eintrag bei Sloane's ist auch erst während dieser Diskussion entstanden. Offensichtlich hat der Fragende aus d.s.m. eine neue Folge gefunden - und eingetragen.



Trennlinie
Zum Abschluß gebe ich noch eine Erläuterung zur zweiten Bedeutung der Folge.
Betrachte den vollständigen Graphen Kn.
Kn hat n Ecken, die paarweise durch Kanten verbunden sind.

Die Namen der Ecken seien 1,2,3,...,N


Aus Kn entferne ich die Kanten
des Kreises C := 1-2-3-....-N-.

Den so verkleinerten Graphen nennen ich KnC



Nun ist die gestellte Aufgabe gleichwertig zum Problem in KnC die Anzahl der verschiedenen Kreise der Länge n zu zählen [das ist die Anzahl der Hamilton-Kreise in KnC].


Beispiel:

In K5C existiert genau ein Kreis, nämlich 13524.
K<sub>n</sub>C


In K6C kann man 3 Kreise finden: 135264, 136425, 142635.

Das ist das Gute an Sloane's, man findet auch interessante Querbezüge.

Meine ausdrückliche Empfehlung für Sloane's On-Line Encyclopedia of Integer Sequences


Dieser Artikel kommt von Matroids Matheplanet
http://matheplanet.com

Die Url für diesen Artikel ist:
http://matheplanet.com/default3.html?article=152