Let n ≥ 8. Give a big-Θ estimate for the number of circuits of length 8 in Kn. Θ(n) Θ(n8) Θ(8) Θ(8n) Θ(8n)

Abstract algebra
asked 2021-06-23
Let \(\displaystyle{n}≥{8}\). Give a \(\displaystyle{b}{i}{g}-Θ\) estimate for the number of circuits of length 8 in Kn. \(\displaystyleΘ{\left({n}\right)}Θ{\left({n}{8}\right)}Θ{\left({8}\right)}Θ{\left({8}{n}\right)}Θ{\left({8}{n}\right)}\)

Answers (1)


A complete graph \(\displaystyle{K}{n}{\left({n}\Rightarrow{1}\right)}\) is a simple graph with n vertices and an edge between every pair of vertices.
Definition permutation (order is important): \(\displaystyle{n}{P}{r}={n}\frac{!}{{{n}-{r}}}!\)
Definition combination (order is not important)| \(\displaystyle{n}{C}{r}={\left({n}{r}\right)}={n}\frac{!}{{{r}!{\left({n}-{r}\right)}!}}\) with \(\displaystyle{n}\ne{n}\cdot{\left({n}-{1}\right)}\cdot\ldots\cdot{2}\cdot{1}\)
Solution Let n be the number of vertices in Kn
When \(n<8\), the graph contains less than 8 vertices and thus the graph can then not contain a circuit of length 8. 0 circuits of length 8 when \(n<8\)
When \(\displaystyle{n}\Rightarrow{8}\), any circuit of length 8 is a sequence of 8 vertices (as the last vertex in the sequence will be the first circuit again). The order of the vertices matters (as a different order will lead to the same sequence), thus we use the definition of a permutation. \(\displaystyle{n}{P}{s}={n}\frac{!}{{{n}-{8}}}\ne{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}\ldots{\left({n}-{7}\right)}\)
Every circuit will be counted twice in the \(n(n-1)(n-2)\cdots(n-7)\) sequences, as the opposite order of the sequence of vertices will lead to the same vertex, thus there are \(\displaystyle{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}\ldots\frac{{{n}-{7}}}{{2}}\) circuits of length 8.
Since \(n(n-1)(n-2)\cdots(n-7)\) is a polynominal function of degree 8, \(\displaystyle{n}{\left({n}-{1}\right)}{\left({n}-{2}\right)}\ldots{\left({n}-{7}\right)}{i}{s}Θ{\left({n}^{{8}}\right)}\)

Best answer

expert advice

Have a similar question?
We can deal with it in 3 hours

Relevant Questions

asked 2021-08-15
Let \(\displaystyle{n}≥{8}\). Give a \(\displaystyle{b}{i}{g}-Θ\) estimate for the number of circuits of length 8 in Kn. \(\displaystyleΘ{\left({n}\right)}Θ{\left({n}{8}\right)}Θ{\left({8}\right)}Θ{\left({8}{n}\right)}Θ{\left({8}{n}\right)}\)
asked 2020-12-09
Let X be a set with n elements, n > 3. Determine the size of the following set in terms of n, and give a big-Θ estimate for the answer. the set of all one-to-one correspondences \(\displaystyle{X}→{X}Θ{\left({2}{n}\right)}Θ{\left({\log{{2}}}{n}\right)}Θ{\left({n}{3}\right)}Θ{\left({n}{2}\right)}Θ{\left({n}!\right)}\)
asked 2021-08-02

Which expression has both 8 and n as factors?




asked 2021-03-24
A 2.4-kg object is attached to a horizontal spring of forceconstant k=4.5 kN/m. The spring is stretched 10 cm fromequilibrium and released. Find (a) the frequency of themotion, (b) the period, (c) the amplitude, (d) the maximum speed,and (e) the maximum acceleration. (f) When does the objectfirst reach its equilibrium position? What is itsacceleration at this time?
Two identical blocks placed one on top of the other rest on africtionless horizontal air track. The lower block isattached to a spring of spring constant k= 600 N/m. Whendisplaced slightly from its equilibrium position, the systemoscillates with a frequency of 1.8 Hz. When the amplitude ofoscillation exceeds 5 cm, the upper block starts to slide relativeto the lower one. (a) What are the masses of the twoblocks? (b) What is the coefficient of static frictionbetween the two blocks?