The study of discrete mathematical structures. Consider using a more specific tag instead, such as: (combinatorics), (graph-theory), (computer-science), (probability), (elementary-set-theory), (induction), (recurrence-relations), etc.

learn more… | top users | synonyms

2
votes
1answer
70 views

Help Needed Showing that $\chi(\overline{G \times H}) \leq \chi(\overline{G}) \times \chi(\overline{H})$

Where $\chi(G)$ denotes the chromatic number, $\overline{G}$ the graph complement, and $\times$ the Cartesian Graph Product: I need to show that $(\forall G,H)( \chi(\overline{G \times H}) \leq ...
1
vote
2answers
384 views

how to calculate vehicle speed using mathematics and Image processing?

i am doing my project in image processing.using segmentation i have detected the moving part(i.e the car) in the video successfully. But now i want to calculate speed of vehicle. in the above ...
1
vote
1answer
77 views

How do we determine the duration of a fundamental frequency using the DFT (or FFT)?

I'm still in the process of learning the details of the DFT (and FFT) and I've just made a test .wav file in Audacity by joining 3 one-second sine waves together. .wav file 1 = 440 Hz, sample rate ...
2
votes
2answers
75 views

Constructing a function similar to x^3 between [0,1]

I'm trying to construct a function $f$, in order to normalize a dataset(obviously where all the element come from $[0,1] \in \mathbb{R}$. The big picture is that the envisioned $f: [0,1] \rightarrow ...
0
votes
1answer
81 views

Find the largest integer $n$ such that $10^n$ divides $10^6!$

Let $N=10^6!$ Find the largest integer $n$ such that $10^n$ divides $N$. Furthermore, compute the first digit and the last non-zero digit of $N$. I have some ideas that you should be able to use ...
2
votes
1answer
74 views

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers. I have tried using the fact that $F_{n^k} \bmod F_n = 0, k=1,2,3,...$ but that doesn't get me anywhere. Thanks!
1
vote
3answers
40 views

Question regarding Strong Principle of Induction

I'm currently studying Discrete mathematics from a book by Normal L. Biggs and i don't understand the thinking about an example on Strong Principle of Induction, The example i need help ...
1
vote
4answers
58 views

Help with groups

let $G$ be a finite group with $e$ Identity element and let $a$ and $b$ belong to $g$ prove that if: $\gcd(o(a),o(b)) =1$ then $\langle a \rangle \cap \langle b \rangle = \{ e \}$. if someone can ...
2
votes
1answer
81 views

Prove $\gcd(k, l) = d \Rightarrow \gcd(2^k - 1, 2^l - 1) = 2^d - 1$ [duplicate]

This is a problem for a graduate level discrete math class that I'm hoping to take next year (as a senior undergrad). The problem is as stated in the title: Given that $\gcd(k, l) = d$, prove that ...
1
vote
2answers
74 views

Solving $x^2 + 96=0$ in $\mathbb{Z}_{100}$

I'm trying to find all solutions to $x^2 + 96=0$ in $\mathbb{Z}_{100}$. $x^2 + 96 \equiv 0 \bmod 100$ implies that $x^2 + 96 \equiv 0 \bmod 2$ and $x^2 + 96 \equiv 0 \bmod 5$. $$x^2 + 96 \equiv 0 ...
3
votes
4answers
350 views

GCD proof - by contradiction?

$a, b$ are relatively prime and $a > b$. Prove that $\text{gcd}(a-b,a+b) = 1 \,\,\text{or}\,\, 2$. Attempt: Since $a, b$ are relatively prime, I know that $\text{gcd}(a,b) = 1$. Also, know that ...
1
vote
1answer
52 views

Designing a context free grammar

I have to design a grammar over the alphabet $\sum=(a,b)$, so that $c^a(\alpha)=c^b(\alpha)$ and the second part $c^a(\alpha)\leq c^b(\alpha)$ , where $\alpha$ is a word and $c^a$ and $c^b $ are ...
0
votes
2answers
79 views

Is $x^2+25x+4 \in \mathcal{O}(x^2)$? If yes how? If no why not?

Is $x^2+25x+4 \in \mathcal{O}(x^2)$ ? if yes how ?, if no why? I know $x^2+25x+4\leq 25x^2+25x+25\leq 25x^2+25x^2+25x^2=75x^2$ for some $x$. What confuses me is $x^2+25x+4\leq 25x^3+25x+25\leq ...
0
votes
1answer
50 views

Help on understanding how to express sets and their relations graphically

Let $A=\{0,1\}, B=\{a,b,c\}, R=id_A, S=\{(a,b),(a,c) \}\cup id_B$ Express graphically the following: $(A,R)+(B,S)\\ (B,S)+(A,R)\\ (A,R)\times(B,S)\\ (B,S)\times(A,R)$ I'm not sure how ...
1
vote
2answers
61 views

problem with GCD/Euclidean algorithm

This problem is in a chapter on the Greatest Common Divisor: The Euclidean Algorithm. Apparently I managed to arrive at one of the 3 possible solutions. Problem goes 'man at a casino wins \$1020 in ...
1
vote
2answers
271 views

Hamilton Paths in n-Wheel Graph

According to wolfram, $n$-wheel graphs have $4(n-1)(n-2)$ Hamilton paths in them. $n$-wheel graph = http://mathworld.wolfram.com/WheelGraph.html http://mathworld.wolfram.com/HamiltonianPath.html ...
1
vote
1answer
26 views

arrangement of numbers so that a condition is satisfied…

In how many ways can we arrange the numbers $1,2, \dots, 3n (n \geq 1)$, so that, at the positions that are multiple of $3$, there are only numbers that are multiple of $3$? I thought that the answer ...
-1
votes
2answers
193 views

Recurrence Relation Solving Problem

Can anyone help me in solving this complex recurrence in detail? $T(n)=n + \sum\limits_{k-1}^n [T(n-k)+T(k)] $ $T(1) = 1$. We want to calculate order of T. I'm confused by using recursion tree ...
1
vote
1answer
216 views

Using arithmetic progression sum to show an algorithm is both $\Theta(n^2)$ and $O(n^2)$

Exercise 4 in http://discrete.gr/complexity/ askes to give an arithmetic progression sum to show that the following algorithm is both $O(n^2)$ and $\Theta(n^2)$. ...
0
votes
0answers
34 views

Discrete Laplace operator (on graphs) - why are its units not the same as the continuous version of the Laplace operator?

From Wikipedia: Let $G = (V,E)$ be a graph with vertices $\scriptstyle V$ and edges $\scriptstyle E$. Let $\phi\colon V\to R$ be a function of the vertices taking values in a ring. Then, the discrete ...
0
votes
2answers
60 views

Divide and Conquer Recurrence Relation help?

So the divide and concur recurrence has to be of the form H($n$) = $a$H($n$/$b$) + $cn^d$. I already figured out that $a$ = 4 and $b$ = 2. I am really stuck on how to find $cn^d$ however. I ...
1
vote
0answers
123 views

How to find the lengths of the shortest paths in a directed graph in $O(m)$ steps?

Let $G = (V,A)$ be a directed graph for which it is true that if $(v_i , v_j) \in A$, it is implied that $i < j$. Question: How does one construct an $\mathcal{O}(m)$ algorithm to find the ...
0
votes
2answers
119 views

Burnside's lemma - show that there are just five necklaces

Show that there are just five different necklaces which can be constructed from five white beads and three black beads. Sketch them. The lemma tells us that The number of orbits of G on X ...
10
votes
3answers
397 views

Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
1
vote
0answers
15 views

Efficient way needed

Given N, M find the : GCD(1, 1) * GCD(1, 2) * … * GCD(1, M) * GCD(2, 1) * GCD(2, 2) * … * GCD(2, M) * … * GCD(N, 1) * GCD(N, 2) * … * GCD(N, M) modulo 10^9+7 Constraints: 1 <= N, M <= 2 * ...
2
votes
2answers
56 views

feedback on my solution regarding eqivalence relations. [duplicate]

For all $x, y \in \mathbb{R}$ define that $x \equiv y$ if $x^2 = y^2$. Then $\equiv$ is an equivalence relation on $\mathbb{R}$, there are infinitely many equivalence classes, one of them consists of ...
0
votes
1answer
97 views

Feedback on my answer for $X^n + Y^n = Z^n $ [duplicate]

The equation $X^n + Y^n = Z^n $ , where $n \ge 3$ is a natural number, has no solutions at all where X; Y;Z are integers. solution: the above is a false statement counter example: let: n=3 ,x=0 y=0 ...
0
votes
1answer
44 views

Particular solution of recurrence relation

I've got this recurrence relation: $$M_n = M_{n-1} + n(2n-1)|M_0 = 0$$ and can't think of any form of particular solution to get a solvable constant. With $M_n^H = K$being the homogeneous part of ...
3
votes
1answer
125 views

Show: group $G$ has one orbit on $ X$, stabilizer of $z$ is $3$…

If $X$ denotes the set of corners of a cube and let $G$ denote the group of permutations of $X$ which correspond to rotations of the cube. (i) $G$ has just one orbit (ii) if ...
2
votes
1answer
39 views

Find the permutation

This is part of an exercise I did on an assignment but I am having trouble remembering how to complete the exercise (even though I got full marks on my assignment). Let $P_1=(3\,4\,1\,2\,5), ...
0
votes
3answers
56 views

Need help explaining this combinations answer from another post

I was looking around questions and I found one that intrigued me, and I need help explaining it. Here is the question with the answers, Discrete math and integer solutions problem Can someone ...
1
vote
4answers
135 views

Discrete math and integer solutions problem

How do we find the number of nonnegative integer solutions of the inequality: $$x_1 + x_2 + \cdots + x_6 < 10\text{ ?}$$ Answer is $5005$, can someone elaborate and show me the steps required to ...
1
vote
1answer
34 views

Expressing the generating function defined by $b_n = \sum_{k=0}^{n} 3^k\cdot a_k$

The title is probably somewhat unclear, sorry if it is.. Let $F$ be the generating function of the sequence $(a_n)_{n=0}^{\infty}$ Use $F$ to express the generating function for ...
1
vote
1answer
54 views

Discrete Mathematics problem

Consider this equation: $x_1 + x_2 + \cdots + x_k = n$ with these following constraints: $x_i ≥ 0;\; i = 1,2,\ldots, k$ How would I go about formulating each of the following problems as a ...
0
votes
2answers
76 views

How many coefficients are in the expansion $(x + y + z)^{10}$

I need to find the number of coefficients in the expansion $(x + y + z)^{10}$. I had this exercise on a recent assignment. The answer I gave is: $3^{10} = \binom {3 + 10 - 1}{10} = \binom{12}{10} = ...
3
votes
3answers
86 views

Induction: Prove that it is possible to seat people in a circle so that everyone sits beside a friend

Use induction to prove the following: If each person in a group of $n$ people is a friend of at least half the people in the group, then prove that it is possible to seat them in a circle so that ...
2
votes
3answers
67 views

Why in formulas a return value of a function sometimes shown as an argument?

Sorry for a perhaps newbie question, I had a hard time in the school. Well, the title says the problem, let's look at example, which I stole from the coursera video-lectures about an algorithms: ...
0
votes
2answers
22 views

Discrete Math Probability

Suppose we toss a fair coin four ($4$) times. The outcome of the $1$st three tosses is {HHH}. What is the probability of the next toss being heads $P(head)$? $P(Head)=$ possible outcome/total ...
0
votes
1answer
240 views

What is a strictly increasing sequence in discrete math?

Consider selecting $3$ objects from the set $A = \{ 1,2,3,4,5,6\}$, how many strictly increasing sequences can be chosen from $A$? Answer is $C_3^6$, but my problem is that I don't know what it means ...
1
vote
1answer
27 views

Number of nonzero intersections with translated sets

Suppose we have two finite sets $A,B\subset\mathbb Z$. I am interested in an upper bound on the number of translations of $B$ by integers that have nonzero intersections with $A$ i.e. ...
4
votes
1answer
222 views

subgroups of the group of pentagon symmetries

The pentagon has 5 line symmetries and therefore we will have 10 symmetries. So, we let the group G with order 10 denote the symmetry group of a pentagon. A subset $H$ of $G$ is a subgroup $(H, *)$ ...
2
votes
0answers
57 views

Prove the following : [duplicate]

Prove the following : $$ {{n}\choose{7}}-\left \lfloor{\frac{n}{7}}\right \rfloor $$ is divisible by 7.
0
votes
1answer
45 views

a discrete mathematics problem

Let A(n) be a sentence with one variable defined in the set of all natural numbers N then which of the following is true ? a.-A(0) is valid and if for all n, A(n) is valid then for all n, A(n+1) is ...
10
votes
3answers
189 views

Show that $2^n(\cos^n(\frac{2\pi}{9})+\cos^n(\frac{4\pi}{9})+\cos^n(\frac{8\pi}{9}))\in\mathbb{Z}$

$a_n=2^n\left[\cos^n\left(\dfrac{2\pi}{9}\right)+\cos^n\left(\dfrac{4\pi}{9}\right)+\cos^n\left(\dfrac{8\pi}{9}\right)\right]$. Show that $a_n\in\mathbb{Z}$ for all $n\in\mathbb{Z}$. Find the last ...
3
votes
2answers
121 views

equivalence classes of ∼ are left cosets of H in G - my attempt

Let $H$ be a subgroup of G, and define a relation $∼$ on G by the rules that $x∼y$ mean $x^{-1}y\in H $. Show that $∼$ is an equivalence relation and its equivalence classes are the left cosets ...
1
vote
2answers
100 views

Chromatic recurrence

1) How do you prove the Chromatic recurrence theorem: $$χ(G;k)=χ(G−e;k)−χ(G·e;k)$$ I'm thinking by induction, but then you would have to assume something about the type of graph G...surely it can't ...
1
vote
1answer
30 views

Generating functions for $n*2^n$ & the seq a0+a1+a2+…

1) What is the generating function of $a_n = n2^n, n\geq0$? My answer: $f(x) = \sum a_nx^n = \sum n2^nx^n = \sum n(2x)^n$, but I have no idea where to go from here. 2) Let the sequence $s_n = a_0 + ...
0
votes
3answers
36 views

find a base to U Linear Algebra

dear users please help me... im answering a long question now ive been guided to find a base to U at the end of the process i got this $u= Sp\{x^4-3x^3+2x^2, 3x^4-7x^3+4x ,1\}$ and ive been guided to ...
2
votes
3answers
122 views

Summation with Ceilinged Logarithmic Function

According to Johann Blieberger's paper - "Discrete Loops and Worst Case Performance" (1994): $$ \sum_{i = 1}^{n}\left \lceil \log_2{(i)} \right \rceil = n\left \lceil \log_2{(n)} \right \rceil - ...
1
vote
1answer
29 views

A general answer to the number of solutions to an inequality

Given the following inequality: $x_1 + x_2 + x_3 + .... + x_N < r$ we are asked to solve the number of non-negative integer solutions could the solution be described as: $\displaystyle ...