Math 2.0

Learn Year 1

Discrete mathematics

188 ideas in teaching order. Each idea comes after the ideas that it builds on. 186 of them have a page so far; the others are on the list in grey.

Start with Combinatorics →

  1. Combinatorics concept
  2. Cardinality of a finite set definition
  3. Rule of sum statement
  4. Rule of product statement
  5. Bijection principle statement
  6. Double counting concept
  7. Complement principle statement
  8. Number of functions between finite sets statement
  9. Number of subsets of a finite set statement
  10. Factorial definition
  11. Permutation definition
  12. Number of permutations statement
  13. Falling factorial definition
  14. Number of injections statement
  15. Combination definition
  16. Binomial coefficient definition
  17. Number of k-element subsets statement
  18. Factorial formula for binomial coefficients statement
  19. Symmetry of binomial coefficients statement
  20. Pascal's rule statement
  21. Pascal's triangle object
  22. Binomial theorem statement
  23. Sum of binomial coefficients statement
  24. Alternating sum of binomial coefficients statement
  25. Vandermonde's identity statement
  26. Hockey-stick identity statement
  27. Central binomial coefficient definition
  28. Multinomial coefficient definition
  29. Multinomial theorem statement
  30. Combinations with repetition definition
  31. Stars and bars statement
  32. Lattice path concept
  33. Pigeonhole principle statement
  34. Generalized pigeonhole principle statement
  35. Infinite pigeonhole principle statement
  36. Erdős–Szekeres theorem statement
  37. inclusion-exclusion for two sets statement
  38. Inclusion–exclusion principle statement
  39. Derangement definition
  40. Number of derangements definition
  41. numDerangements counts derangements statement
  42. Formula for the number of derangements statement
  43. Recurrence for derangements statement
  44. Stirling numbers of the second kind definition
  45. Recurrence for Stirling numbers of the second kind statement
  46. Stirling numbers of the first kind definition
  47. Recurrence for Stirling numbers of the first kind statement
  48. Bell numbers definition
  49. Recurrence for Bell numbers statement
  50. Catalan numbers definition
  51. Catalan recurrence statement
  52. Closed formula for Catalan numbers statement
  53. Dyck word definition
  54. Dyck words are counted by Catalan numbers statement
  55. Binary trees are counted by Catalan numbers statement
  56. Bertrand's ballot theorem statement
  57. Fibonacci sequence example
  58. Fibonacci recurrence statement
  59. Golden ratio object
  60. Binet's formula statement
  61. Cassini's identity statement
  62. Addition formula for Fibonacci numbers statement
  63. Fibonacci numbers as sums of binomial coefficients statement
  64. Gcd of Fibonacci numbers statement
  65. Zeckendorf's theorem statement
  66. Integer partition definition
  67. Partition function definition
  68. Young diagram definition
  69. Euler's partition theorem statement
  70. Composition of an integer definition
  71. Number of compositions statement
  72. Recurrence relation definition
  73. Tower of Hanoi example
  74. Linear recurrence with constant coefficients definition
  75. Solution of a linear recurrence definition
  76. Characteristic polynomial of a linear recurrence definition
  77. Geometric solutions come from roots of the characteristic polynomial statement
  78. Space of solutions of a linear recurrence definition
  79. Generating function definition
  80. Formal power series definition
  81. Coefficient of a power series definition
  82. Product of power series statement
  83. Geometric series as a power series example
  84. Exponential generating function definition
  85. Partial fraction decomposition concept
  86. Generating function for partitions statement
  87. Graph definition
  88. Edge set definition
  89. Multigraph definition
  90. Directed graph definition
  91. Neighbourhood definition
  92. Degree of a vertex definition
  93. Minimum degree definition
  94. Maximum degree definition
  95. Handshaking lemma statement
  96. Number of odd-degree vertices is even statement
  97. Regular graph definition
  98. Complete graph example
  99. Number of edges of a complete graph statement
  100. Cycle graph example
  101. Path graph example
  102. Complete bipartite graph example
  103. Petersen graph example
  104. Subgraph definition
  105. Induced subgraph definition
  106. Complement graph definition
  107. Graph homomorphism definition
  108. Graph isomorphism definition
  109. Adjacency matrix definition
  110. Walk definition
  111. Trail definition
  112. Path definition
  113. Every walk contains a path statement
  114. Circuit definition
  115. Cycle definition
  116. Reachability definition
  117. Connected graph definition
  118. Connected component definition
  119. Distance in a graph definition
  120. Bridge definition
  121. Characterization of bridges statement
  122. Acyclic graph definition
  123. Tree definition
  124. Forest definition
  125. Every finite tree with at least two vertices has a leaf statement
  126. A tree on n vertices has n − 1 edges statement
  127. Unique paths in trees statement
  128. Rooted tree definition
  129. Binary tree definition
  130. Spanning tree definition
  131. Every connected graph has a spanning tree statement
  132. Cayley's formula statement
  133. Prüfer sequence definition
  134. Minimum spanning tree definition
  135. Bipartite graph definition
  136. Trees are bipartite statement
  137. A graph is bipartite iff it has no odd cycle statement
  138. Eulerian trail definition
  139. Seven Bridges of Königsberg example
  140. Degrees along an Eulerian trail statement
  141. Euler's theorem on Eulerian circuits statement
  142. Hamiltonian cycle definition
  143. Hamiltonian graph definition
  144. Dirac's theorem on Hamiltonian cycles statement
  145. Ore's theorem statement
  146. Planar graph definition
  147. Euler's formula for planar graphs statement
  148. Edge bound for planar graphs statement
  149. K5 and K3,3 are not planar statement
  150. Kuratowski's theorem statement
  151. Graph colouring definition
  152. K-colourable graph definition
  153. Chromatic number definition
  154. Chromatic number of a complete bipartite graph statement
  155. Greedy colouring concept
  156. Brooks' theorem statement
  157. Chromatic polynomial definition
  158. Five colour theorem statement
  159. Four colour theorem statement
  160. Edge colouring definition
  161. Clique definition
  162. Clique number definition
  163. Independent set definition
  164. Matching definition
  165. Perfect matching definition
  166. Hall's marriage theorem statement
  167. Hall's theorem for bipartite graphs statement
  168. Vertex cover definition
  169. Kőnig's theorem statement
  170. Tutte's theorem statement
  171. Ramsey number definition
  172. Theorem on friends and strangers statement
  173. Ramsey's theorem statement
  174. Mantel's theorem statement
  175. Turán graph example
  176. Turán's theorem statement
  177. Sperner's theorem statement
  178. Boolean algebra definition
  179. Two-element Boolean algebra example
  180. Power set Boolean algebra example
  181. Distributive lattice definition
  182. Absorption law statement
  183. De Morgan's laws in a Boolean algebra statement
  184. Boolean ring definition
  185. Boolean function definition
  186. Disjunctive normal form definition
  187. Conjunctive normal form definition
  188. Stone's representation theorem for finite Boolean algebras statement