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