maths.free › Combinatorics & Graph Theory › An Introduction to Combinatorics › Combinatorics and Number Theory
Combinatorics and Number Theory
Broadly, number theory concerns itself with the properties of the positive integers.
Combinatorics and Number Theory
Broadly, number theory concerns itself with the properties of the positive integers. G.H.Hardy was a brilliant British mathematician who lived through both World Wars and conducted a large deal of number-theoretic research. He was also a pacifist who was happy that, from his perspective, his research was not useful. He wrote in his 1940 essay A Mathematician's Apology [n]o one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems very unlikely that anyone will do so for many years.G.H.Hardy, A Mathematician's Apology, Cambridge University Press, p. 140. (1993 printing) Little did he know, the purest mathematical ideas of number theory would soon become indispensable for the cryptographic techniques that kept communications secure. Our subject here is not number theory, but we will see a few times where combinatorial techniques are of use in number theory.
Example
Form a sequence of positive integers using the following rules. Start with a positive integer \(n>1\). If \(n\) is odd, then the next number is \(3n+1\). If \(n\) is even, then the next number is \(n/2\). Halt if you ever reach\(1\). For example, if we start with \(28\), the sequence is \[\begin{aligned}\end{aligned}\]
Now suppose you start with \(19\). Then the first few terms are \[\begin{aligned}\end{aligned}\] But now we note that the integer \(22\) appears in the first sequence, so the two sequences will agree from this point on. Sequences formed by this rule are called Collatz sequences.
Pick a number somewhere between \(100\) and \(200\) and write down the sequence you get. Regardless of your choice, you will eventually halt with a\(1\). However, is there some positive integer \(n\) (possibly quite large) so that if you start from \(n\), you will never reach\(1\)?
Questions arising in number theory can also have an enumerative flair, as the following example shows.
Example
In , we show the integer partitions of\(8\).
There are\(22\) partitions altogether, and as noted, exactly\(6\) of them are partitions of\(8\) into odd parts. Also, exactly\(6\) of them are partitions of\(8\) into distinct parts.
What would be your reaction if we asked you to find the number of integer partitions of \(25892\)? Do you think that the number of partitions of \(25892\) into odd parts equals the number of partitions of \(25892\) into distinct parts? Is there a way to answer this question without actually calculating the number of partitions of each type?
Condensed: the full section is in Keller & Trotter, Applied Combinatorics.
Nu är det din tur. Ingen miniräknare bestämmer detta, men bitarna i det är beräkningsbara. Prova en nedan, eller skriv din egen.
Ett gratis konto lägger till anteckningar om varje lektion, en förteckning över vad du har avslutat, dina lösta problem på ett ställe, och en handledare du kan fråga om denna sida. Matematiken i sig är öppen för alla, inloggad eller inte.
Registrera dig InloggningSymboler som används här
Knacka på alla symboler för den fullständiga definitionen, en bild, och vad varje bokstav i den betyder.
Frågor folk frågar
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
Delar av denna sida är anpassade från Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Kondenserad och återförklarad här; felen är våra.
Mer information Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs