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.
现在轮到你 没有计算器能解决这一个问题, 但其中的碎片是可以计算的。 请在下面尝试一个, 或者输入您自己的 。
此处所用符号
输入完整定义、图片和其中每个字母的含义的符号。
人们对人们提出的问题
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.
本页部分内容从 Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). 在这里进行浓缩和重新解释;错误属于我们。
更多 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