MB Matheblog # 49voriger Eintrag
Index der gesamten Website
| MB Matheblog # 49 |
Inhalt Blog voriger Eintrag |
zur Leitseite Index der gesamten Website |
Endliche Surjektionen mit eindeutigem letzten Element Kommentare sind willkommen.
Hier geht es um surjektive Abbildungen zwischen endlichen Mengen – mit einer Zusatzbedingung:
\(f:~[_~n_~]~\rightarrow~[_~m_~]~~\) surjektiv mit \(~~f(n)\neq f(j)~~\) für \(~~j\lt n\)
\([_~i_~]_~\) ist die Menge der ersten \(~i~\) positiven natürlichen Zahlen. – Wir betrachten also nicht alle Surjektionen, sondern nur diejenigen, bei denen die letzte Zahl \(~f(n)_~\) sonst in der Wertemenge nicht vorkommt.
Gesucht ist die Anzahl dieser Surjektionen.
Die Zahlenfolge OEIS A380977 wurde am 21.2.2025 in OEIS eingefügt. Sie gibt diese gesuchte Anzahl sowie die äquivalente Definition:
"Anzahl \(_~n-\)Tupel, die alle Elemente in \(_~[m]_~\) enthalten, mit einem eindeutigen letzten Element"
Wegen \(~m\le n~\) lassen sich diese Anzahlen \(~a(n,m)_~\) in einer dreieckigen Tabelle angeben:
m
1 2 3 4 5 6
n 1 1
2 0 2
3 0 2 6
4 0 2 18 24
5 0 2 42 144 120
6 0 2 90 600 1200 720
...
Der Beweis für die Zahlen in der Tabelle wurde in der Lösung zu Problem # 137 geführt. Es gilt:
\(a(n,m) = m_~!\cdot S_{_~2_~}(n-1,~m-1)\)
mit \(~S_{_~2_~}(..,~..)_~\) Stirling-Zahlen 2. Art .
Die beiden ersten Spalten der Tabelle und deren Diagonale \(~a(n,n)=n_~!_~\) erklären sich von selbst.
\(m=3:~~~a(n,_~3)~=~6\cdot (2^{_~n-2}-1)~\) mit \(~n\ge 3~~~~~~→~~\)OEIS A068293(n-1)
Beweis:
Für die letzte Stelle im \(~n-\)Tupel gibt es \(~3~\) Möglichkeiten.
Es verbleiben \(~2~\) Zahlen, die auf \(~2^{_~n-1}_~\) Weisen auf die ersten \(~n-1~\) Stellen gesetzt werden können; es entfallen aber die beiden Fälle, in denen alle \(~n-1~\) Stellen durch die gleiche Zahl besetzt sind.
So erhalten wir \(~3\cdot (2^{_~n-1}-2) = 6\cdot (2^{_~n-2}-1)_~\) Tupel.
\(m=4:~~~a(n,_~4)~=~12\cdot (3^{_~n-2}-2^{_~n-1}+1)~\) mit \(~n\ge 4~~~~~~→~~12_~\times_~\)OEIS A028243(n-1)
Beweis:
Für die letzte Stelle im \(~n-\)Tupel gibt es \(~4~\) Möglichkeiten.
Es verbleiben \(~3~\) Zahlen, die auf \(~3^{n-1}_~\) Weisen auf die ersten \(~n-1~\) Stellen gesetzt werden können; es entfallen aber folgende Fälle:
– Die \(~n-1~\) Stellen sind durch die gleiche Zahl besetzt; dafür gibt es \(~3~\) Möglichkeiten.
– Die \(~n-1~\) Stellen sind durch genau \(~2~\) Zahlen besetzt; dafür gibt es \(~2^{n-1}-2~\) Möglichkeiten; für die Auswahl dieser zwei Zahlen gibt es \(~3~\) Möglichkeiten.
So erhalten wir \(~4\cdot (3^{_~n-1}-3-3\cdot (2^{_~n-1}-2)) = 12\cdot (3^{_~n-2} - 2^{_~n-1}+1)_~\) Tupel.
Beispiel:
\(a(5,~3)=42~\) ist die Anzahl der Quintupel, jedes gebildet aus allen Zahlen \(~1,~2,~3~\), mit eindeutigem letzten Element:
11123 11213 11223 12113 12123 12213 12223 21113 21123 21213 21223 22113 22123 22213
11132 11312 11332 13112 13132 13312 13332 31112 31132 31312 31332 33112 33132 33312
22231 22321 22331 23221 23231 23321 23331 32221 32231 32321 32331 33221 33231 33321
Die Zeilensummen \(~s(n)_~\) der Tabelle findet man in OEIS unter A005649(n-1). Sie geben die Anzahl aller Surjektionen mit Definitionsbereich \(_~[n]_~\) und eindeutigem \(~f(n)_~\) an:
1, 2, 8, 44, 308, 2612, 25988, 296564, 3816548, 54667412, 862440068, 14857100084, 277474957988, 5584100659412, 120462266974148, ...
Beispiel: \(_~s(3)=8~\) – Begründung:
Es gibt keine Surjektion \(_~f_~\) von \(_~[3]_~\) in eine einelementige Menge mit eindeutigem \(_~f(3)_~\), da \(_~f(1)=f(2)=f(3)\).
Es gibt zwei Surjektionen \(_~f_~:~[3]~\rightarrow~[2]_~\) mit eindeutigem \(_~f(3)_~\):
\(f(1)=f(2)=1,~~f(3)=2\)
\(f(1)=f(2)=2,~~f(3)=1\)
Es gibt sechs Surjektionen \(_~f_~:~[3]~\rightarrow~[3]_~\) mit eindeutigem \(_~f(3)_~\):
\(f(1)=1,~~f(2)=2,~~f(3)=3\)
\(f(1)=2,~~f(2)=1,~~f(3)=3\)
\(f(1)=1,~~f(2)=3,~~f(3)=2\)
\(f(1)=3,~~f(2)=1,~~f(3)=2\)
\(f(1)=2,~~f(2)=3,~~f(3)=1\)
\(f(1)=3,~~f(2)=2,~~f(3)=1\)
Motivation
Warum beschäftigt man sich mit diesen speziellen Surjektionen? Es gibt eine Reihe von naheliegenden Anwendungen, die alle mit Wartezeiten zu tun haben:
Stand 2025-03-23