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

0
votes
0answers
12 views

Closed $SL_2(\mathbb{Z})$ conjugacy class

For what matrices $A \in SL_2(\mathbb{R})$ is the conjugacy class by $SL_2(\mathbb{Z})$ closed ?
2
votes
2answers
27 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}$ ...
0
votes
1answer
22 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
56 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
3answers
99 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 ...
15
votes
1answer
52 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
12 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
35 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
17 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 ...
-2
votes
1answer
26 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
3
votes
1answer
36 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 ...
-3
votes
1answer
27 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
14 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 ...
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 ...
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
56 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 ...
-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 ...
2
votes
1answer
32 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 ...
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
1answer
52 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
1
vote
2answers
91 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
26 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 ...
3
votes
1answer
39 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 ...
1
vote
0answers
20 views

Calculate year for a provided yield

\$146.25 will yeild \$46.25 at 7.5% per annum. How to get the number of years? Answer is 6 but how do you get it? What is the formula?
5
votes
0answers
19 views

Discrete analogue of Green's theorem

Following formula concerning finite differences is in a way a discrete analogue of the fundamental theorem of calculus: $$\sum_{n=a}^b \Delta f(n) = f(b+1) - f(a) $$ We can think about the Green's ...
11
votes
4answers
926 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 ...
1
vote
1answer
20 views

Directed Multigraph or Directed Simple Graph?

I have the following two questions in my book: Question # 1 Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more ...
-3
votes
2answers
71 views

How many integers from 1 to 100,000 contain the digit 6 at least once? [on hold]

How many integers from 1 to 100,000 contain the digit 6 at least once? I have no idea how to solve this, can somebody help me out?
0
votes
2answers
30 views

Repeated squaring method

How do I use the repeated squaring method to calcualte 2^176 (mod 177)? I'm not sure, but is there something about the fact that 177 is 1 greater than 176 that makes this a problem?
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
0answers
29 views

how to show a function is non-conservative? [on hold]

So I have this question ...
0
votes
2answers
11 views

Expressing n mod m in terms of floor values?

I'm trying to prove the expression: $$\left\lceil\frac{n}m\right\rceil = \left\lfloor n+m-\frac1m\right\rfloor\;,$$ where $n,m$ are integers` So I've come across this article (PDF) which gives a ...
1
vote
3answers
60 views

Why is this combinatoric solution not correct?

I'm trying to solve the following problem: Balls of the colors red, orange, yellow, green, blue, indigo, violet (7 colors, 1 ball per color) are placed into 4 different boxes A,B,C,D so that no box ...
0
votes
2answers
35 views

Solve the recurrence relation (using iteration?)

$a_n = a_{n-1} + 1 + 2^{n-1}\\ a_0 = 0$ Not sure how to iterate with the exponent term. Here's what I got: $= (a_{n-2} + 1 + 2^{n-1}) + 1 + 2^{n-1} = a_{n-2} + 2 + 2(2^{n-1})\\ = (a_{n-3} + 1 + ...
0
votes
0answers
33 views

Boolean algebra and boolean subalgebra

I have to prove that set of all dividers of number 210 with appropriate operations forms a Boolean algebra. And describe these operations and create a Hasse diagram. In the secondd part I have to ...
0
votes
0answers
12 views

Inverse of a discrete trasformation

I have defined the discrete transformation-like relationship: $$ Y(k)=\sum_{n=0}^{N-1} \frac{A(n)}{1+j \frac{w(k)}{p(n)}} $$ with $w(k)$ the k-th element of the vector $w$, $p(n)$ the n-th element ...
0
votes
1answer
24 views

Recurrence relation advice

$t_n=5t_{n-1}+6t_{n-2}$ Is the characteristic equation of this correct? This is what I have: $x$- 5$x$ -6=0 Is this correct?
1
vote
2answers
35 views

tips and tricks for understanding induction proofs in discrete structures.

I have my discrete structures exam tomorrow, and right now i am practicing mathematical induction, specially proofs. while proving, i just get confused because i don't understand what should i add or ...
-1
votes
0answers
33 views

Difference between two expressions for combinations with repetition.

While attempting to solve problems that compute the number of combinations with repetition (ie, a store has 4 flavors of ice cream and you are picking 3 with repetitions allowed, how many ways can you ...
0
votes
3answers
52 views

How to find upper and lower bound without using formula?

I am studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything usefull. Prove the following sum is theta(n^2) (we have to find ...
0
votes
1answer
37 views

S is a finite set show that $|P(S)|$ is $2^{|S|}$. [duplicate]

If $S$ is a finite set, show that $|P(S)| = 2^{|S|}$. So I know that $|P(S)|$ means the number of elements in the power set of $S$, but I don't understand the relation between the power set and ...
1
vote
2answers
36 views

Order of $f(n) = 4n + 6n^3 - 8n^5$

If a function $$f(n) = 4n + 6n^3 - 8n^5$$ then the order of $f$ is: The answer I have is $\log(n)$, but I'm not sure if it's right.
1
vote
1answer
36 views

Proving the upper bound of edges in a convex polyhedron

The question is the following: Suppose Every face of a convex polyhedron has at least $5$ vertices and every vertex has degree $3$. Prove that if the number of vertices is $n$, then the number of ...
2
votes
1answer
45 views

Hierarchy of Mathematics Breakdown

Can you provide me with a hierarchical breakdown on Discrete Math as it applies to computer science? By this I mean a breakdown on topics that fall under the study of discrete numbers, specifically ...
1
vote
3answers
33 views

Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$ a) Find $a_2,a_3,a_4,a_5$ b) Find a closed form-formula for $a_n$ I found the value to be ...