Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-mathematics]

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.

0
votes
0answers
12 views

Arrange the functions in a list so that each function is big-O of the next function.

If 2 functions each big $\mathcal O$ of each other, then place them on the same level. $x^2 + x^3, 3^x, x! x \log(x), x^2 + 2^x, 2^{x \log(x)}, \log(x^2), 6 \log(x), 2^x, x(1+2+\dots+x)$ My answer ...
0
votes
4answers
26 views

Why does x! grow faster than $(x/2)^{(x/2)}$ but slower than $x^x$?

I'm having trouble understanding this. I understand the reasoning about why x! grows slower than $x^x$. However, I'm not sure how to show that x! grows faster than $(x/2)^{(x/2)}$. I was thinking ...
-1
votes
1answer
27 views

Let $f(n) = 5n^4 + 3n^3 − 5$. Show that $f(n)$ is $Θ(n^4)$.

How should this be proved? I know that $f(n)$ is $Θ(n)$ if and only if $f(n)$ is $O(g(n))$ and $f(n)$ is $Ω(g(n))$ and that If $f(n)=\theta(g(n))$ then $\lim_{n \to \infty}\frac{f(n)}{g(n)}$ will be ...
0
votes
2answers
17 views

Roots of unity divisibility.

Suppose $r | n$. Then $R:= e^{2i \pi k/r}$ is an $n$-th root of unity. Thus, there exists a unique $l \in \{0, \dots, n-1\}$ such that $R = e^{2\pi i l/n}$. Does it hold that $l |n$? I tried to ...
0
votes
0answers
29 views

I did not know how to Express in terms of a and b

The vectors a and b are the two vectors drawn from a vertex of a square to the two adjacent vertices. Express in terms of a and b the vector of the diagonal drawn from the same vertex.
0
votes
2answers
40 views

Proving $1+\sqrt2+\sqrt3$ is irrational [duplicate]

How can I prove that $1+\sqrt2+\sqrt3$ is an irrational number, without proving first $\sqrt2$ and $\sqrt3$ are irrational numbers? Please give some hints or suggestion to proceed with this proof. ...
1
vote
3answers
38 views

A coin is flipped 14 times. How many different outcomes have at most 10 heads?

I followed the pattern here but it still resulted in my problem being incorrect. How many outcomes of a coin being flipped 12 times have exactly 4 heads? (1 pt) A coin is tossed 14 times. d) How ...
0
votes
2answers
40 views

How many times does the binary digit $1$ appear in numbers $0$ to $255$?

I am trying to find an easy way to calculate the number of times that the digit "$1$" appears in numbers $0-255$ (in the binary system). I consider the answer must be a power of $2$ since $256 = 2^8$ ...
0
votes
0answers
28 views

Rewrite a cubic summation [on hold]

how do you write $$\left(\sum_{i=1}^{k}{ i^3}\right) + (k+1)^3$$ as a single summation?
0
votes
1answer
48 views

Is $2(2^{p} − 1)$ a divisor of $n$? How about $2^2(2^p − 1)$? Finish the proof. [on hold]

A positive integer is called perfect if it equals the sum of its positive divisors. Example: $6$ is perfect because the divisors of $6$ are $1,2$ and $3$ and $6=1+2+3$. Show that $28$ is perfect. ...
-2
votes
1answer
23 views

How do you find a defined relation?

So this may be a really simple obvious question, but this is something that kind of trips me up. I'm a beginner at this type of stuff, and still learning. In my past experience if I see the relation ...
0
votes
1answer
14 views

Is this the correct relation for a finite set?

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Show whether or not R is reflexive, symmetric, antisymmetric or transitive. So if S = {1,2} $R = \{(\emptyset,\...
2
votes
1answer
31 views

Is this the correct solution to find a number of one-to-one functions?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x? If we take $A_{i}$ to be a set of one-to one ...
0
votes
1answer
43 views

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x?

What is the number of one-to-one functions f from the set {1, 2, . . . , n} to the set {1, 2, . . . , 2n − 1} so that f(x) $\neq$ 2x − 1 for all x? Alright so I did see this question, but it really ...
0
votes
3answers
19 views

How do I prove growth of functions with exponents?

Prove that $16 + 3^n=O(4^{n})$. I have tried to do this problem but cannot find a constant $c$ that I am supposed to find.
0
votes
2answers
43 views

How to prove there are unreachable states in this bit flipping algorithm only for lengths $n=3k+2$?

This is similar to Bit flipping algorithm, but the algorithm is a little different. Specifically, we have bit string of length $n$, and we can choose any bit to flip and then we flip also the two ...
0
votes
0answers
9 views

Given L, s and d, which are positive real number, what is the probability that there exist integer k and k', such that $kd\in [k'(L+s)-s, k'(L+s)]$

Given $L$, $s$ and $d$, which are positive real numbers, is there always a pair of integers k and k', such that $kd\in [k'(L+s)-s, k'(L+s)]$. It is like there is a line which is painted red of length $...
2
votes
1answer
34 views

fibonacci and lucas numbers induction

I'm having trouble proving by induction that this following Fibonacci-Lucas equation $$F_{2n+k} = F_n L_{n+k} + (-1)^n F_k \tag{*}$$ is true, given that $$F_{2n} = F_nL_n$$ and $$F_{2n+1} = ...
-1
votes
1answer
34 views

I need help with induction proof [on hold]

Prove by induction if Chicken McNuggets are sold in quantities of 6, 9, and 20, then the largest amount that cannot be purchased is 43.
0
votes
0answers
10 views

What is the cardinality of |S x I| for an elevator FSM that serves n floors? [on hold]

S = Set of states and I = Set of inputs. S = {Ground, first, second, n} I = {G, 1, 2, n}
0
votes
0answers
28 views

If more than half of the integers from $\{1, 2, \ldots, 2n\}$ are selected, then they must include two integers such that one divides the other [duplicate]

Pigeonhole Principle problem: If more than half of the integers from $\{1, 2, \ldots, 2n\}$ are selected, then there must exist two integers among the selected integers that have the property that ...
2
votes
0answers
38 views

Assigning people to jobs

We have $n$ people and $n$ jobs. Assume that each person is able to do $k$ jobs $0<k<n$ and each job can be done by $k$ people. Proof that each job can be done at the same time My try Ok, I ...
-1
votes
1answer
32 views

How to discretize and normalize an $n*n$ Gaussian kernel?

A 3x3 Gaussian kernel is usually shown as $$\frac{1}{16} \begin{bmatrix}1 & 2 & 1\\ 2 & 4 & 2\\ 1 & 2 & 1\end{bmatrix}$$ But where does that actually come from?
0
votes
1answer
23 views

How would you notate that something is not in the domain of discourse?

For example, saying that something is specifically not in the domain of integers (not sure how to write the 'N' symbol).
-1
votes
2answers
45 views

How do I prove this by induction? With the induction on n [on hold]

How do I prove this with mathematical induction, the entire problem is like a Putnam/coffin problem, where the solution is almost impossible.I proved the basis case with a_0. But after that, when I ...
0
votes
1answer
26 views

How to prove this fact about the discrete closure? [on hold]

The content is given two relationships: R₁ and R₂ prove that s(R₁ ∩ R₂)=s(R₁) ∩ s(R₂) My teacher has taught us the UNION versions in class, and I figure it's easy. Also I have already finished the ...
1
vote
2answers
54 views

Is there a way to classify all power-invariant graphs?

Suppose $G = (V, E)$ is a finite undirected simple graph. Let’s, define the $n$-th power of a graph (where $n \in \mathbb{N}$) as graph $G^n = (V, E_n)$, where $$E_n = \begin{cases} E & \quad n = ...
1
vote
0answers
25 views

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Is R reflexive, symmetric, antisymmetric or transitive.

Given a finite set S, let the relation R = {(S1, S2) | |S1| < |S2|, S1, S2 ⊆ S}. Show whether or not R is reflexive, symmetric, antisymmetric or transitive. I'm shaky on how to approach this ...
-1
votes
3answers
27 views

Explicit form of $ b_1= 2, b_k = b_{k-1} + 2\cdot 3^k$ for all integers $ k\ge 2 $ [on hold]

As the title says, I need to find the explicit form of the recursive sequence defined above, and I am very stuck on this.
0
votes
0answers
51 views

Check my math - Number of one-to-one functions $f$ from $\{1, \ldots, n\}$ to $\{1, \ldots, 2n-1\}$ such that $f(x) \neq 2x - 1$ for all $x$

What is the number of one-to-one functions $f$ from the set $\{1, 2, \ldots, n\}$ to the set $\{1, 2, \ldots, 2n − 1\}$ so that $f(x) \neq 2x − 1$ for all $x$? I'm not sure if I did the question ...
0
votes
1answer
15 views

Recurrence relation general solution

I am sorry I'm posting this on phone, I have the recurrence an = 5an−1 − 6an−2 + 7^n When solved with the method of particular solution coefficient of 7^...
1
vote
1answer
41 views

Is my proof of $\binom{m+n}{r}=\binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r-1} + … + \binom{m}{r}\binom{n}{0}$ right?

As the title says, I was requested to prove $\binom{m+n}{r}=\binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r-1} + ... +\binom{m}{r}\binom{n}{0}$ I was requested to do this using the following ...
0
votes
1answer
44 views

What is the probability that the monkey will type the phrase “Call me Ishmael”?

Random events are independent events. Consider a typical computer keyboard with 82 keys. And a monkey typing on this keyboard, at random. The output of the typing would look like: jw9:.2wb0288q 1nej@...
1
vote
1answer
32 views

Conservative obfuscations

I am reading this paper. Could someone please explain, at a high level, what 4.2.1 Conservative Obfuscations does? How is it different to non-conservative obfuscation? Just a basic explanation is ...
0
votes
1answer
14 views

How do I use induction to prove a claim of a recursive set definition?

The set X is defined as 12 ∈ X 15 ∈ X if x, y ∈ X, then x + y ∈ X if x, y ∈ X, then x − y ∈ X Claim: for every natural number n, 3n ∈ X I know I should induct on natural numbers that means my base ...
0
votes
0answers
36 views

Propositional Logic: $Τ\vDash\varphi\implies\existsΤ_0\subseteq T$ such that $Τ_0\vDash\varphi$

Suppose $Τ$ is an infinite set of propositional types and $\varphi$ a propositional type. Prove that if $Τ\vDash\varphi$, then a finite set $Τ_0\subseteq T$ exists, such that $Τ_0\vDash\varphi$. I ...
0
votes
1answer
22 views

How to find the prime factors when knowing some congruence?

In order to factorize the integer $N = 67591$, choose a factor base $\{2,3,5\}$ and four congruences: $24256^2 \equiv 2^9 \cdot 3^4(mod\ N)$; $59791^2 \equiv 2^2 \cdot 3^4\cdot 5^2(mod\ N)$; $23541^2 \...
0
votes
0answers
14 views

Checking of Delaunay trianhulation in 3D

One of the easy ways of checking Delaunay triangulation in 2D is to see if all the angles are acute or right angles. Do we have some kind of easy checking in 3D as well?
-1
votes
0answers
11 views

security knapsack problem [on hold]

hi I can encrypt knapsack without problem but I have problem with decryption please can you help me thanks for help?
0
votes
0answers
24 views

Most General unifier in logic

i have a question about most general unifier in logic. i'll begin by saying that in the class we were only given a summary in a few words, without any example, and they just moved on to the next topic ...
2
votes
1answer
39 views

Prove that if two graphs, $G$ and $\overline{G}$, are isomorphic, the number of nodes cannot be twice an odd number.

Having a really hard time going about proving this. First, Graph $G$ is constructed by having $n$ nodes and joining some pairs of distinct nodes with at most one line. Second, Graph $\overline{G}$ ...
0
votes
0answers
42 views

Discrete derivative of array

In relation to computational photography, let's say we have a 1 dimensional mean filter defined as $h =\begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{bmatrix}$ Where $u$ is ...
4
votes
3answers
94 views

Help on proof of $\binom{n}{0}^2 + \binom{n}{1}^2 + … + \binom{n}{n}^2 = \binom{2n}{n}$

The proof is required to be made through the binomial theorem. I will expose the demonstration I was tought, and forward my questions after exposing it. You'll see question marks like this one (?-n) ...
0
votes
1answer
23 views

How to solve a recurrence relation for a bit string of length n that starts with 1?

I am doing a homework assignment and am stuck on the following problem: Find a recurrence relation and give initial conditions for the number of bit strings of length n begin with 1. I'm not sure how ...
-1
votes
0answers
20 views

Prove by induction that k divides n(n+1)(n+2)…(n+k-1) for k and n >= 2. [duplicate]

Heading Prove by induction on n that k divides n(n+1)(n+2)...(n+k-1) for integers k >=2 and n >= 2. Basis: (for n >= 2 and k >= 2) 2 divides 2(2+1) is true since 2 divides 6. Hypothesis: Let's ...
0
votes
3answers
31 views

In how many ways we can split set$ \{a_{1},..,a_{9}, b_{1},.., b_{9}, c_{1} ,.., c_{9}\}$ into 9 set of shape $\{ a_{i}, b_{j}, c_{k} \} $

In how many ways we can split set$ \{a_{1},..,a_{9}, b_{1},.., b_{9}, c_{1} ,.., c_{9}\}$ into 9 set of shape $\{ a_{i}, b_{j}, c_{k} \}$?
0
votes
1answer
24 views

Roll n 3-sided dice (ABC). What's the probability of at least one A and two Bs?

Suppose you have n three-sided dice, with sides labelled A, B, C. What is the probability of getting ABB among your dice (i.e. at least one A, at least two Bs)? Order is not important. (By ...
0
votes
1answer
18 views

Create subsets of $[0, 1]$

I would like to create a sequence of subsets $(D_{k})_{k \in \mathbb{N}^{\ast}}$ of $[0 ,1]$ in the following way: $D_{1} = \{0, 1\}$, $D_{2} = \{0, \frac{1}{2}, 1\}$, $D_{3} = \{0, \frac{1}{4}, \...
0
votes
1answer
17 views

What does it mean to calculate a relation's quotient set (the set of all of equivalence classes)?

The set in question: T = {(a,a),(b,b),(c,c)}. I am confused what it means by this, and I haven't found any resources online that helps explain this to me well enough. Any help is much appreciated.