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
2answers
52 views

Calculating interaction beween 100 objects with each other.

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result ...
5
votes
4answers
317 views

For every positive integer $n, n^2 + 4n + 3$ is not a prime

Prove: For every positive integer $n, n^2 + 4n + 3$ is not a prime. I tried to disprove the statement, which I could not using several number examples with constructive proof. However I am not sure ...
1
vote
2answers
70 views

methods of proof, discrete mathematics

"Disprove: For all integers $r, m,$ and $n$, if $r$ divides $mn$ then either $r$ divides $m$ or $r$ divides $n$." I am not sure if I am on the right track To disprove I try the negation of a ...
0
votes
0answers
39 views

Evaluate the sum $n$ of geometric random variables

Let $X_i\sim G\left (1-\frac{1-i}{n}\right)$. Evaluate $ \sum_{n=1}^n X_i$ My Try: $$ \sum_{i=1}^n X_i = \sum_{i=1}^n \sum_{k=1}^\infty \left(\frac {i-1}{n}\right)^{k-1}\left( 1 - ...
0
votes
0answers
61 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
1answer
76 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
107 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
51 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
91 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
59 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
45 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 ...
0
votes
1answer
114 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
101 views

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

Is this proposition true or false? $$\exists y \in \mathbb R \;\forall x \in \mathbb R\,(xy\neq x \rightarrow x=0) $$ And why? I'm confused as to what exactly is being claimed.
2
votes
2answers
49 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
91 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
89 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
110 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 ...
16
votes
1answer
86 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 ...
2
votes
0answers
22 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
39 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
21 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 ...
3
votes
1answer
45 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
34 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
48 views

Reachability relation set

How can i define reachable relation set of R for a given di-graph below?
1
vote
1answer
36 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
64 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
59 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
109 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
110 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 ...
0
votes
1answer
96 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
57 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
77 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
59 views

How does the function work? [closed]

Could you explain me the function of the following two algorithms? ...
0
votes
1answer
27 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
123 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
39 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
2answers
79 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 ...
3
votes
1answer
64 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
24 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?
6
votes
0answers
58 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 ...
12
votes
4answers
1k 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
196 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 ...
0
votes
2answers
60 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
69 views

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

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

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

So I have this question ...
0
votes
2answers
32 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
71 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
52 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
16 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 ...