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

3
votes
1answer
57 views

Does $\theta(n)$ = $1/x$ make any sense?

So, I asked this question on a discrete structures exam today, which I apparently didn't give enough thought to: $f(x) = (5x^2 + 6x + 2)/(x^3 + 4x^2 +x)$ Find the correct theta notation for the ...
0
votes
1answer
47 views

Basic Set Theory regarding the set $\{0\}$

For each nonnegative integer $n$, let $U_n = \left \{n,−n\right \}$. Find $U_1,\:U_2,\:\text{and}\:U_0$. $U_1 = \left \{1,−1\right \}, U_2=\left \{2,−2\right \}, U_0 = \left \{0,−0\right \} = \left ...
0
votes
0answers
6 views

Submodularity in Max-k-Coverage

Why the coverage function $f(S)$ for the Maximum-k-coverage is submodular? The function is defined here (see Coverage Functions) ...
0
votes
2answers
26 views

Big $O$ estimate of $(n\log n+1)^2+ (\log n +1)(n^2+1)$

Give the Big $O$ estimate of $(n \log n +1)^2 + (\log n +1)(n^2+1)$ Taking big $O$ of the first function (ignoring constant and exponent), ($n\log n + 1)^2$ we get $O (n \log n)$ Taking big $O$ of ...
4
votes
2answers
179 views

Determining the truth value of certain quantifiers based on this proposition being false.

Can you help me verify if I answered this question correctly? Consider $[(\forall x)(P(x)) \land (\exists x)(\lnot Q(x))] \implies \{(\forall x)(P(x)) \iff [\lnot(\forall x)(R(x)) \lor ...
2
votes
4answers
51 views

Help with proposition whether it's true or false [on hold]

Is this proposition true or false? $$\exists y \in \mathbb R \;\forall x \in \mathbb R\,(xy\neq x \rightarrow x=0) $$ And why?
-7
votes
0answers
28 views
2
votes
1answer
49 views

Fourier transform of $f[n]$ and $f[-n]$

Hi I am just wondering, If I have a signal $f[n]\in \mathbb{C}^L$, i.e. $f$ is $L$-periodic, i can also define $h[n]=f[-n]$. Is it true that the Fourier transform of $f$, say $\hat{F}$, and the ...
114
votes
17answers
9k views

Zero to the zero power - Is $0^0=1$?

Could someone provide me with good explanation of why $0^0 = 1$? My train of thought: $x > 0$ $0^x = 0^{x-0} = 0^x/0^0$, so $0^0 = 0^x/0^x = ?$ Possible answers: $0^0 * 0^x = 1 * 0^x$, so ...
0
votes
1answer
59 views

Check if Sequence is Graphic: 8, 8, 7, 7, 6, 6, 4, 3, 2, 1, 1, 1 [duplicate]

This is part of my Discrete Math homework and I have no idea how to solve this. I am given this sequence: $8, 8, 7, 7, 6, 6, 4, 3, 2, 1, 1, 1 $ I have to check whether it is graphic or not. How do ...
0
votes
0answers
16 views

Closed $SL_2(\mathbb{Z})$ conjugacy class [on hold]

For what matrices $A \in SL_2(\mathbb{R})$ is the conjugacy class by $SL_2(\mathbb{Z})$ closed ?
2
votes
2answers
31 views

Determine whether each of the functions $2^{n+1}$ and $2^{2n}$ is $O(2^n)$.

Determine whether each of the functions $2^{n+1}$ and $2^{2n}$ is $O(2^n)$. Since $2^n$ < $2^{n+1}$, you can say $2^{n+1}$ is not $O(2^{n})$ Since $2^n$ is < $2^{2n}$, you can say $2^{2n}$ ...
2
votes
3answers
100 views

How does $\log(x^2 + 1)$ become $\log(2x^2)$?

My textbook attempts to take the big O of $\log(x^2 +1)$. It proceeds by saying $x^2 + 1 \le 2x^2$ when $x \ge 1$. But I don't know how it came up with this idea. Question: Why set $x^2+1$ to a ...
2
votes
4answers
261 views

Proving there exist an infinite number of real numbers satisfying an equality

Prove there exist infinitely many real numbers $x$ such that $2x-x^2 \gt \frac{999999}{1000000}$. I'm not really sure of the thought process behind this, I know that $(0,1)$ is uncountable but I ...
0
votes
1answer
23 views

Verify answers to these big o notation questions

May someone look over if I did these big o notation problems correctly? Some of them were tricky. 1) $f(x) = 10 = O(10)$ 2) $f(x) = 3x + 7 = O(x) $ 3) $f(x) = x^2 + x + 1 = O(x^2) $ 4) ...
3
votes
2answers
59 views

Show that $\mathbb{Q}\times \mathbb{Q}$ is denumerable [duplicate]

I am new to functions and relations, and with some concepts I am not so familiar. I have a question in an homework: Show that $\mathbb{Q} \times\mathbb{Q}$ is denumerable. From what I ...
2
votes
2answers
59 views

Probability for having consecutive success in an experiment

A friend asked me the following question: "In an experiment, we are tossing a fair coin 200 times. We say that a coin flip was a success if it's heads. What is the chance for having at least 6 ...
15
votes
1answer
54 views

Find all $A\subseteq\mathbb{N}$ such that $A=\{|a-b|:a,b\in A\}$.

For a set $A$ of real numbers, denote $$A^\ast:=\{|a-b|:a,b\in A\}.$$ Question: Find all finite subsets $A\subseteq\mathbb{N}$ of the natural numbers such that $$A^*=A.$$ Attempt: The empty ...
1
vote
0answers
13 views

Estimating the discrete laplacian to prove recurrence of simple random walk for d=2

Given a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}$ we define the discrete laplacian of $f$, $\triangle_df$, by the following rule $\triangle_df(x,y)= \dfrac{f(x + 1, y)+f(x, y + ...
0
votes
0answers
36 views

Finding $2^{2^n}$ mod $m$

Is there any special technique for finding $2^{2^n} \pmod m$? Taking $n$ and $m$ to be very high. Approx till $10^4$
-1
votes
1answer
18 views

Relation Proofs on finite set [duplicate]

I have this problem I can't figure out how to do it Suppose A and B are finite sets and $f : A → B$ is surjective. Is it true that the relation $“|A| < |B|”$ is a sufficient condition for claming ...
1
vote
3answers
325 views

Show that in a group of 10 people (where any 2 are either friends or enemies), there are either 3 mutual friends or 4 mutual enemies$\dots$

Question:Show that in a group of 10 people (where any 2 are either friends or enemies), there are either 3 mutual friends or 4 mutual enemies, and there are either 3 mutual enemies or 4 mutual ...
-2
votes
1answer
29 views

Infinite Set Proof (Countable and Uncountable ) [on hold]

I can't figure out this problem, I have to prove that $\mathbb Q \times \mathbb Q$ is enumerable, but I have no idea how to do it. Thanks
1
vote
0answers
54 views

Need help to prove this by using natural deduction.

i m concerned to prove these by using Natural Deduction. And i am also concerned to prove it for both sides. $$\exists x(P (x) \implies A) \equiv \forall xP (x) \implies A$$ I have some difficulties ...
2
votes
1answer
53 views

Composite function intersection

I m stacked in one prove which dealt with sets and functions. I m concerned to prove that: $$f \circ g ( X \cap Y) \subseteq (f \circ g)( X) \cap (f \circ g) (Y)$$ Assume that $g$ is function from $A$ ...
2
votes
1answer
30 views

Invalid operator in sequences

$V_n = n! + 2$ $n \ge 1$ Find $V_3$. I am just wondering what does the "!" operator after "$n$" mean?
3
votes
1answer
42 views

What is the discrete log used for?

Perusing Wikipedia, I stumbled on the discrete logarithm. I looks interesting that we'd be able have a function that could solve $b^k=g$ for integers $b,k,$ and $g$. However, Wikipedia says "No ...
1
vote
1answer
27 views

Combining Two Gaussian Filters

I am taking a class related to image processing and we were taught about Gaussian Filters that are related to the following Gaussian Function: $$G(u,v) = \frac{1}{2\pi\sigma^2}e^{-\frac{u^2 + ...
-3
votes
1answer
29 views

Show that $a$ is minimum [duplicate]

If $(A,<)$ totally ordered, show that if $a$ is a minimal element of $A$ then $a$ is minimum. Could you give me a hint how we could do this? Definitions: Let $(A, \leq)$ be an ordered set. We say ...
0
votes
1answer
24 views

Reachability relation set

How can i define reachable relation set of R for a given di-graph below?
1
vote
1answer
27 views

Combinations - no repetition for mirrors?

My question is, if there is a simple explanation as to why mirrors aren't counted twice with binomials such as it is in the case it's not a mirror? Here is an example: Consider the elements {1, 4}. ...
1
vote
1answer
15 views

Find #committee of 8 from 3 freshmen, 4 sophomores, 4 juniors, and 5 seniors contain at least one of each class

The question: A student council consists of three freshmen, four sophomores, four juniors, and five seniors. How many committees of eight members of the council contain at least one member from ...
11
votes
8answers
2k views

Proof that the sum of the cubes of any three consecutive positive integers is divisible by three.

So this question has less to do about the proof itself and more to do about whether my chosen method of proof is evidence enough. It can actually be shown by the Principle of Mathematical Induction ...
2
votes
1answer
33 views

Derivatives defined on a discrete state space

Ive been looking at certain economic papers, and optimal control papers. They define a state variable, $\omega$, which follows a discrete time Markov Chain. Then they define a utility function ...
3
votes
0answers
39 views

Number of functions from domain to codomain

Let A and B be finite sets. Let a be the size of A. Let b be the size of B. Assume 0 < a < b. (a) How many functions are there with domain A and co-domain B? (b) How many one-to-one functions ...
2
votes
2answers
39 views

Maximum number of relations?

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B. Now I know that a relation $R$ from $A$ to $B$ is ...
-1
votes
1answer
52 views

Hasse diagram question about relations

I have the following Hasse diagram below, the question is given specific generalised quantifiers I have to list the subsets of {a,b,c,d} which the quantifier corresponds to. I have completed the ...
0
votes
2answers
58 views

Show that a function from a set is non-conservative [on hold]

So I have this question There exists some set A = (a,b,c,d), we have a function H from Powerset(A) into Powerset(A) -> {T,F} given by H(X)(Y) = True iff |X|<|Y| I need to show some ...
0
votes
2answers
60 views

Probability that n people collectively occupy all 365 birthdays

The problem is quite simple to formulate. If you have a large group of people (n > 365), and their birthdays are uniformly distributed over the year (365 days), what's the probability that every day ...
1
vote
2answers
99 views

An exercise from Knuth's book - Proving a formula by induction

I would like to find a formula for this sum: $$ \frac{1^3}{1^4+4} - \frac{3^3}{3^4+4} + \frac{5^3}{5^4+4} - ... + \frac{(-1)^n(2n+1)^3}{(2n+1)^4+4} $$ The answer given (Knuth's book, The Art of ...
0
votes
1answer
34 views

Multinomial theorem: find the coefficient of $x^3 y^4$ in $(x+2y+3)^{10}$

I have trouble solving this problem: Find the coefficient of $x^3y^4$ in $(x+2y+3)^{10}$ The reason for that I struggle with this problem, is because it has an higher order (10) the $x^3y^4$. ...
1
vote
1answer
53 views

How does the function work? [on hold]

Could you explain me the function of the following two algorithms? ...
0
votes
1answer
9 views

Is there a closed form expression for the Taylor series of (1- a X - b Y - c XY )^ (-1)?

Is there a closed form expression for the Taylor series of f(X , Y ) = (1- a X - b Y - c XY )^ (-1) ? a, b and c are constants X and Y are thank you
11
votes
4answers
929 views

Is Cantor's diagonal argument dependent on the base used?

Applying Cantor's diagonal argument to irrational numbers represented in binary, one and only one irrational number can be generated that is not on the list. Wikipedia image: But if you change ...
0
votes
1answer
27 views

Creating equation for a given recurrence relation

I'm studying discrete math in the university, and we are given questions and answers for some problems, and I dont understand most of them. So I need help understanding one of them... Appreciate the ...
0
votes
1answer
266 views

How many outcomes of a coin being flipped 12 times have exactly 4 heads?

I know that there are a total of 4096 possible outcomes of tossing a coin twelve times, but I do not know how to calculate the number of possible outcomes with exactly 4 heads, with at least 2 heads, ...
3
votes
1answer
41 views

Triangulation of hypercubes into simplices

A square can be divided into two triangles. A 3-dimensional cube can be divided into 6 tetrahedrons. Into what number of simplices an n-dimensional hypercube can be divided? (For example, a ...
2
votes
0answers
33 views

Sizes of Hamming balls on the discrete torus

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in ...