-
Notifications
You must be signed in to change notification settings - Fork 2
/
kombinatorik.txt
110 lines (63 loc) · 3.28 KB
/
kombinatorik.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
=== Interpretation von alternierenden Summen
https://www.math.hmc.edu/~benjamin/papers/DIE.pdf
=== Schur-Funktoren und Young-Diagramme
http://golem.ph.utexas.edu/category/2007/12/this_weeks_finds_in_mathematic_19.html#c013821
Tensorprodukt von Schur-Funktoren:
http://www.combinatorics.org/ojs/index.php/eljc/article/download/v9i1n5/pdf
Stembridge, A Concise Proof of the Littlewood-Richardson Rule.
=== Ungeordnete Tupel
* Anzahl der ungeordneten 2-Tupel (a,b) aus einer Menge mit n Elementen,
wobei a != b sein muss:
binom{n}{2} = n * (n-1) / 2
* Anzahl der ungeordneten 2-Tupel (a,b) aus einer Menge X mit n Elementen,
wobei a = b sein darf:
binom{n+1}{2} = n * (n+1) / 2
Das kann man schnell einsehen, wenn man die Menge X mit {1,...,n}
identifiziert und die Gaußsche Summenformel verwendet. Es gibt aber auch
einen kombinatorischen Beweis:
Ein Tupel (a,b) mit a = b erlaubt und a, b aus X entspricht einem Tupel (x,y)
mit x != y und x, y aus X amalg {*}.
Ein Tupel (x,y) mit x != y und a, b aus X amalg {*} entspricht einem Tupel
(a,b) mit a = b erlaubt und a, b aus X.
=== Wege zählen ("die Transfermatrixmethode")
Sei ein Graph durch eine Adjazenzmatrix A gegeben.
* Die Anzahl der Wege von i nach j der Länge k ist dann der (i,j)-Eintrag von A^k,
oder witziger ausgedrückt: der (i,j)-Eintrag des Koeffizienten von t^k in der
Potenzreihe (I - tA)^(-1).
* Die Anzahl der geschlossenen Wege der Länge k ist der Koeffizient von t^k
in der Potenzreihe tr((I - tA)^(-1)).
* Damit kann man zum Beispiel zählen, wie viele Wörter einer gewissen Länge
zu der Sprache eines deterministischen endlichen Automaten gehören.
http://www.uwyo.edu/moorhouse/slides/transfer.pdf
=== Sperners Lemma
* Ein toller grafischer Beweis:
https://people.math.osu.edu/fowler.291/teaching/talks/cutting.pdf
Anzahl AB-Kanten = Anzahl ABC-Dreiecke (modulo 2).
* http://en.wikipedia.org/wiki/Simmons%E2%80%93Su_protocols
Sperner für Kuchenzuteilung (fair division)
* https://www.union.ic.ac.uk/rcsu/mathsoc/ugc.html
Es gibt wohl (ko-)homologische Beweise von Sperners Lemma!
Das sollte interessant sein.
=== Auswertung von Determinanten
Evaluating determinants may not be difficult.
Christian Krattenthaler
Advanced Determinant Calculus
http://arxiv.org/abs/math/9902004
=== Teilbarkeitseigenschaft von Binomialkoeffizienten
* Dass \binom{p}{k} ein Vielfaches von p ist, kann man so einsehen: Wir haben
p! = \binom{p}{k} k! (p-k)!.
Links kommt der Primfaktor p vor. Also auch rechts. Aber für 1 <= k <= p-1
kommt er nicht in k! und nicht in (p-k)! vor.
* Das Produkt von n aufeinanderfolgenden Zahlen ist stets durch n! teilbar.
Denn (a+1) ... (a+n) / n! = \binom{a+n}{n}.
=== Spezies
* https://byorgey.wordpress.com/2016/06/20/any-clues-about-this-newton-iteration-formula-with-jacobian-matrix/
* https://arxiv.org/abs/1109.2688 (Newton-Verfahren!)
=== Bijektive Beweise
* /Bijective matrix algebra/ von Loehr und Mendes:
https://www.sciencedirect.com/science/article/pii/S0024379506000218
Sehr geil. Via
https://mathoverflow.net/questions/302516/constructively-is-the-unit-of-the-free-abelian-group-monad-on-sets-injective.
=== Ramsey-Theorem
* Verlockender Beweis mit Ultrafiltern:
https://publications.mfo.de/bitstream/handle/mfo/3870/snapshot-2021-006.pdf