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
32 views

Find the finite sequence that minimizes the value of $T_5(P)$

Given a finite sequence $P(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$, define $T_1(P):=a_1+b_1$, $\forall 2\leq k\leq n$, $T_k(P)=b_k+\max\{T_{k-1}(P),a_1+a_2+...+a_k\}$. Let $m=\min\{a,b,c,d\}$. ...
2
votes
0answers
26 views

Maximization problem related to set of common representatives

We are given set $\{1, \dots n\}$ and requested to construct $A = \{A_1 \dots A_s\}$, where $|A_i|=k$, $|A| = s$, $A_i \subset \{1, \dots n\}$. We say that $S$ is a minimal set of common ...
2
votes
2answers
54 views

Set theory intersections and unions

I'm in an intro to discrete mathematics course, and this is a question on my first homework. I showed what I have so far, I think the answer to the first part of the question may be right, but I'm ...
2
votes
1answer
28 views

Set of common representatives and pigeonhole principle in one problem

We are given set $\{1, \dots n\}$ and $A = \{A_1 \dots A_s\}$ such as $|A_i|=k$, $|A| = s = \binom n k$, namely $A$ contists of all possible subsets of size $k$. We say that $S$ is a set of common ...
0
votes
2answers
46 views

Exclusion-Inclusion principle.

I have this problem in discrete maths (combinatorics) which nags me. We have a computer system, where a password is of length of at least 3 signs and at most 100 signs. The premitted signs to use ...
1
vote
1answer
53 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
2answers
30 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 ...
-9
votes
0answers
37 views
-6
votes
0answers
34 views

Stochastic Process random process [on hold]

Full Details please about the stochastic process ( random process)
0
votes
1answer
64 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 ...
1
vote
4answers
67 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?
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
34 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
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
60 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
103 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
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 ...
-2
votes
1answer
31 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
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 ...
-3
votes
1answer
30 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
25 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 ...
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
67 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
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 ...
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
54 views

How does the function work? [on hold]

Could you explain me the function of the following two algorithms? ...
0
votes
1answer
10 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
101 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
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 ...
3
votes
1answer
43 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
21 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
20 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
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 ...
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? [closed]

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
59 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? [closed]

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 + ...