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
3answers
39 views

Prove that it is impossible to find integers $x, y$ with $2^x + 6 = 8y + 5$ [on hold]

Prove that it is impossible to find integers $x, y$ such that $2^x + 6 = 8y + 5$.
0
votes
0answers
9 views

Determining intersection number of $C_n+C_n$ and $\overline{C_n}$.

Is there a method to compute intersection numbers of graphs? For example, I would like to compute the intersection number of $C_n+C_n$ and $\overline{C_n}$, where $C_n$ is the $n-$cycle. I was trying ...
-2
votes
3answers
35 views

Proving that $6|n(n + 1)(n + 2)$ for any integer $n \geq 1$

I am having difficulty proving that $6|n(n + 1)(n + 2)$ for any integer $n \geq 1$. How can I go about this?
0
votes
1answer
19 views

Inference Rules, Not(P) Implies Not(Q) / Q Implies P

I do not understand Implication and Inference, I am going over the MIT Computer Science course and they have this part in their lecture notes, why is the second rule not a logical deduction? Can ...
1
vote
0answers
37 views

Proof: For every positive integer $n$, there is a sequence of $n$ consecutive positive integers containing no primes.

Let $x=(n+1)!+2$. I get how to prove that $x$ or $x+1$ is prime, but there is a step in my book that proves that $x+i$ is prime like this: $x+i=(1)(2)(3)(4)....(n+1)+(i+2)$. But then it factors out ...
0
votes
0answers
5 views

Prove $\langle x_0\rangle$ has only finitely many elements if and only if there exists $k_1$ and $k_2$ with $k_1 < k_2$ so that $x_{k_1} = x_{k_2}$

Prove that the orbit $\langle x_0\rangle$ has only finitely many (distinct) elements if and only if there exists $k_1$ and $k_2$ with $k_1 < k_2$ so that $x_{k_1} = x_{k_2}$ I know this to be true ...
-2
votes
1answer
22 views

Discrete Mathematics question regarding functions. [on hold]

Let $S = \{s_1,s_2,...,s_n\}$. How many functions are there with domain $S$ and target Z2? Of those functions, how many are one-to-one? How many are onto?
0
votes
2answers
16 views

Express each of the following statements as expression using quantified predicates and the domain“People.”

Here are two questions confused me. Express each of the following statements as expression using quantified predicates and the domain "People." 1) Some high school students are not enrolled in class ...
0
votes
1answer
17 views

Alternative methods to solve DLP for $GL_{3}(\mathbb{F}_2)$

Is there (or rather what is) a more elegant/efficient way to solve the DLP for $g^x=h$ in $GL_3(\mathbb{F}_2)$ where $$g=\begin{pmatrix}0 &1 & 1 \\ 1 &1 &1 \\ 1&0&1 ...
0
votes
0answers
50 views

Why are positive rational numbers countable but real numbers are not? [duplicate]

If we can say that any positive rational number is countable or listable by showing that every positive rational number is the quotient of p/q of two positive ...
2
votes
4answers
54 views

Prove the formula $\sum_{k=1}^n k\binom{n}{k} = n \cdot 2^{n-1}$ for all integers $n > 0$ [duplicate]

I just got to this question and I became a question mark. I wonder if anyone can help me with this one, because I don't even know how to begin to tackle this problem. The question: Prove the ...
0
votes
4answers
59 views

Explicit formula for $e_k = 4e_{k-1} + 5$

The sequence looks like this: $e_0 = 2$ $e_1 = 4(e_{1-1}) + 5 = 13$ $e_2 = 4(e_{2-1}) + 5 = 57$ $e_3 = 4(e_{3-1}) + 5 = 233$ $e_4 = 4(e_{4-1}) + 5 = 937$ How would I go about finding the ...
0
votes
0answers
3 views

Counting subgraphs of bounded extremal degrees

Let $m\leq n-1$. Is there a closed expression counting the subgraphs of minimum degree $\geq m$ (resp. maximum degree $\geq m$) on $n$ labelled vertices?
0
votes
1answer
24 views

Question regarding target space, one-to-one functions and onto

If I am understanding this correctly. We know $p_1$ has the domain of $A \times B$, where the first parameter of $p_1$ is an element of $A$, $p_1(a,b)=a$ where $a$ is an element of $A$. Since $B$ is a ...
3
votes
0answers
23 views

Properties of the Discrete Logarithm Problem

I am self-studying Hoffstein's An Introduction to Mathematical Cryptography, and this is problem 2.3 (p. 107-08). Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$. (a) Suppose that ...
2
votes
0answers
26 views

Distribution of distinct object problem

So i was given this question. How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room? So i asked this ...
0
votes
1answer
19 views

How can I find the maximum/minimum and maximal/minimal elements of a poset?

My teacher has given us really unclear definitions for all these terms, and now I have this assignment due where I have to find the maximum, minimum, and maximal/minimal elements of this poset: ...
4
votes
3answers
212 views

How many solutions for equation with simple restrictions

I'm working on an assignment in which I have to count the number of solutions for this particular equation: $$x_1+x_2+x_3+x_4=20$$for non negative integers with $x_1<8 $ and $x_2<6$ I'm aware ...
0
votes
1answer
13 views

Determining Whether or not a complex graph is bipartition?

So I asked a question earlier similar to this, and the solution made sense; however, the graph was very simple with only five vertices. If the graph is more complex like this one then how would you ...
0
votes
2answers
36 views

Algebraically transform logic expression

Algebraically transform: $\neg \forall x(P(x) \wedge Q(y) \implies \exists zR(z))$ to $\exists x\forall z(P(x) \wedge Q(y) \wedge \neg R(z))$ Justify each step with one or more ...
2
votes
2answers
51 views

How do I deal with a floor function is a system of equations?

How would one solve an equation with a floor function in it: \begin{cases} y=12(x-\lfloor x \rfloor) \\ x=12(y-\lfloor y \rfloor) \end{cases} Maybe an algebraic method could be used?
0
votes
0answers
22 views

License Plate Permutations

A state has changed its license plate numbering system for the three largest counties. Before the change, each plate had the number 1, 2, or 3, followed by either one or two letters, followed by 3 ...
1
vote
0answers
18 views

Determine whether or not $∀x[p(x) → q(x)]$ and $[∀xp(x)] → [∀xq(x)]$ are logically equivalent.

Determine whether or not $∀x[p(x) → q(x)]$ and $[∀xp(x)] → [∀xq(x)]$ are logically equivalent. I believe that they are not equivalent, but that is just an assumption. I am not sure how to go ...
0
votes
2answers
44 views

How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear?

So i was given this question. How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear? My solution below (not sure if correct) Let $A_i$ = set ...
5
votes
1answer
90 views

Why isn't finite calculus more popular?

I'm reading through Concrete Math, and learning about finite calculus. I've never heard of it anywhere else, and a Google search found very few relevant sources. It seems to me an incredibly powerful ...
0
votes
2answers
52 views

Prove or disprove: For non-negative integers $m$ and $n$, $m!n! = (mn)!$

I have rewritten the question as "If $m$ and $n$ are non-negative integers, then $m!n!$ = $(mn)!$" Here is my current attempt. I am not sure if I am on the right path. Proof. Let $m$ and $n$ be ...
1
vote
1answer
47 views

How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room?

So I was given this question. How many ways are there to place $10$ distinct people within $3$ distinct rooms with exactly $5$ people in the first room and $2$ people in the second room? I have ...
1
vote
1answer
41 views

Discrete Mathematics - Perfect square proof with non-constructive approach. [on hold]

The questions reads the following: Prove that either $2 * 10^{500} + 15$ or $2 * 10^{500} + 16$ is not a perfect square using the non-constructive approach.
2
votes
1answer
27 views

Determining Whether or not a graph is bipartition?

So I have been trying to do research on this online, and all I see are a bunch of graphs with multicolored dots, and telling me to use those to determine if the graph is bipartition. The ones in the ...
-2
votes
1answer
24 views

Discrete Math Sequences (Graph or No Graph) [on hold]

Determine if there exists a graph whose degree sequence is the one specified. Draw a graph, or explain why no graph exists. The sequence is 5,4,3,2,1,1
-1
votes
2answers
49 views

Number of words of length $n$ on the alphabet $a,b,c$ recurrence. [on hold]

Let $a_{n}$ be the number of words of length $n$ on the alphabet $a,b,c$ such that $b,c$ are not adjacent. What is the recurrence relation for $a_{n}$.
1
vote
2answers
37 views

Discrete math induction proof

I am trying to solve a induction proof and i got stuck at the end, some help would be great. This is the question and what i did so far: Statement: For all integers $n \geq 5$ we have $2^n \geq n^2$. ...
1
vote
0answers
21 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
3
votes
1answer
29 views

Inclusion exclusion principle questions i tried(doing it correct?)

$x_1+x_2+x_3\le10$ how many natural numbers solve this problem if $1\le x_1 \\ 2\le x_2 \\3\le x_3$ What i did: i created $y_1,y_2 , y_3$ so $\\ y_1=x_1-1 \\y_2=x_2-2\\ y_3=x_3 -3$ and then added ...
1
vote
1answer
34 views

How do I determine whether this relation is transitive?

I've been given this relation, and I'm supposed to determine whether it is transitive. I understand the definition of transitive (sort of, in theory) but I'm not sure how to put it in action here. ...
1
vote
3answers
62 views

How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ with restrictions

So i was Given this question. How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ $0 \leq x_i \leq 9$? I just assumed it would be ${21+4-4-1 \choose ...
2
votes
2answers
20 views

Why use C(n,r) instead of P(n,r) when considering how many strings can be formed in which a specific letter appears before another specific letter?

I am dealing with a problem in which I must determine how many strings can be formed by ordering the letters ABCDE subject to the conditions given. The condition that I am given is that A appears ...
1
vote
3answers
44 views

How do I go about determining whether a relation is reflexive?

I've been given these relations and I've been told to determine whether they're reflexive and I know the definition of reflexive but I don't really understand it. $R=\{(x,y)\ \in\ \mathbb Z^2\ |\ ...
1
vote
2answers
26 views

Let $B = {n \in \mathbb{Z} : n = 3j + 2; j \in \mathbb{Z}}, D = {n \in Z : n = 3j − 1; j \in \mathbb{Z}}$. Is $B = D$?

Let $B = {n \in \mathbb{Z} : n = 3j + 2; j \in \mathbb{Z}}, D = {n \in Z : n = 3j − 1; j \in \mathbb{Z}}$. Is $B = D$? How do I prove this? To me it looks to be true. But I don't know how to put it ...
0
votes
0answers
42 views

Definition of fixed point free relation

If we have such relation that for $\forall x$ $f(x)\ne x$ , how is it called in one word? I can come up with only "graph of this function is not a straight line:)" Thank you
-5
votes
2answers
62 views

Given any 40 people, at least four of them were born in the same month of the year [on hold]

Given any 40 people, at least four of them were born in the same month of the year. Why is this true?
2
votes
2answers
53 views

Write expressions w/out quantifiers (convert to AND/OR expressions)

A universe contains the three individuals $a,b$, and $c$. For these individuals, a predicate $Q(x,y)$ is defined, and its truth values are given by the following table: \begin{array}{c|ccc} ...
0
votes
1answer
24 views

How to prove that $(A \cup B) - C = (A - C) \cap (B - C)$ [on hold]

If true, prove else provide a counter example. This is a homework question and I cant figure it out. Please help.
-1
votes
2answers
46 views

Discrete math, proving sets [on hold]

I am studying discrete math and i stumbled upon a proof i couldnt proove, can someone help me with this one? "Assume that A,B,C are three sets with no elements in all three sets. Assume further that ...
1
vote
0answers
57 views

Mean distance of random points on a rectangular grid

I have a $N\times N$ grid of side $L$. Each gridpoint can be black or white and a ratio $r$ of the points is black. I want to predict the mean distance between two black points. The most appropriate ...
0
votes
1answer
43 views

Can someone explain and help me with propositional logic in discrete math?

Can someone explain to me in detail how to complete these two problems without using truth tables? I'm having a hard time understanding what to do. I know that I'm supposed to use the laws, etc. But ...
4
votes
2answers
67 views

Finding limit via Sandwich Theorem: $\lim_{n\to\infty} n\sum_{n+1}^{2n} \frac{1}{i^2}$

Question: Use the Sandwich Theorem to find $$\lim_{n\to ∞} n\sum_{n+1}^{2n} \frac{1}{i^2}$$ Appreciate any guidance.
-1
votes
4answers
69 views

Summation for $\sum\limits^5_{i=2}\:\left(3i\:-\:5\right)$

I know that the closed form of $\sum\limits^n_{k=1}\:k=\frac{n(n+1)}{2}$ But I'm not sure what the closed form for $\sum\limits^5_{i=2}\:\left(3i\:-\:5\right)$ would be. Any push in the right ...
1
vote
2answers
35 views

Simple expression for $\sum_{k=1}^{n-1}\:\frac{1}{k\left(k+1\right)}$

I know that $\:\:\frac{1}{k\left(k+1\right)}\:\:\:\:=\:\frac{1}{k}\:-\:\frac{1}{k+1}\:$ And that $\sum_{k=1}^{n-1}\:k$ $= \frac{n(n-1)}{2}$ But I'm not completely sure how to turn ...
-1
votes
2answers
24 views

How can I further simplify $(B^c ∩ (B ∩ A)^c)^c$

I'm pretty sure this is equal to B, but I'm not sure how to go about reducing this step by step. Could I use the double negative law to eliminate the complements? I'm not positive if that would work ...