Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

1
vote
3answers
61 views

Discrete structures Logic exercise

I am a beginner please help solve this What is the contrapositive of the statement: "If you understand the material, you will pass this test."
0
votes
1answer
60 views

Numbers of different ways to distribute $m$ balls into $n$ boxes?

So my question is this: assuming I have $m$ balls how many ways there is to divide them into $n$ boxes (at least one ball for each box)? For example if I have $7$ balls and I want to split them into ...
1
vote
5answers
52 views

Discrete structures exercise

I have this exercise in my worksheet I am a beginner. Prove or disprove that if $A,B$ and $C$ are sets such that $A\times B = A \times C$ then $B = C$.
5
votes
4answers
178 views

Prove $\binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a}$

I want to prove this equation, $$ \binom{n}{a}\binom{n-a}{b-a} = \binom{n}{b}\binom{b}{a} $$ I thought of proving this equation by prove that you are using different ways to count the same set of ...
0
votes
2answers
572 views

Prove for all sets A, B, and C, if A-B ⊆ C then A-C ⊆ B

I did a venn diagram and this statement is TRUE. Im just not too sure how to prove it.
0
votes
2answers
194 views

Discrete Math - Combinatorics question about number of paths in an m x n lattice from one corner to another

Explain why the number of shortest paths in an $m \times n$ lattice from one corner to another is $${s \choose r}$$ where $$s = \text{total # of steps$\qquad$ and $\qquad r= $ total # of right ...
1
vote
1answer
42 views

A recursively defined binary predicate for outcome $1$ in the Euclidean algorithm

So I have this problem which I can't seem to prove. Define the predicate $RP(a,b)$ for positive naturals $a$ and $b$ as follows. $RP(a,b)$ is defined to be true if and only if one of the ...
2
votes
1answer
28 views

calculating degenerancy

Given a function of two positive integers $n_x^2+n_y^2$. $n_x^2+n_y^2=50$ has three combinations of $n_x$ and $n_y$ that result in $n_x^2+n_y^2=50$: $$n_x=7,n_y=1$$ $$n_x=5,n_y=5$$ $$n_x=1,n_y=7$$ ...
0
votes
0answers
30 views

Prove that if $a \ge b$ then $C(a,b,m)$ is true if and only if $\exists r\colon a = rm + b$ where $r$ is a natural.

So I have this problem and I have no idea how to solve it. Define the following predicate $C(a,b,m)$ for naturals $a,b$, and positive naturals $m$. If $a<m$, $C(a,b,m)$ is true if and only if ...
2
votes
1answer
81 views

Discrete Math - Combinatorics - Trinomial Coefficients question

Let $k,l,m,n \in Z \geq 0$ be such that $n=k+l+m$. The trinomial coefficient ${n \choose k,l,m}$ is given by the rules: for $k+l=n$, ${n\choose k,l,0} = {n \choose k,0,l} = {n \choose 0,k,l} = ...
1
vote
1answer
35 views

Invertible Functions

In some mathematics texts, a function is invertible iff the function is one-to-one and onto. However, in some calculus texts (thomas's calculus, stewart's calculus, etc.), the only requirement for a ...
0
votes
1answer
25 views

function on a fixed length sequence of positive real number that induces lexicographic order

Let $S$ be the finite set of sequences of length $n$, whose entries are all real positive numbers. Can we define a function $f$ on $S$ such that the order $f$ induces on $S$ i.e $\le$ is the same as ...
0
votes
1answer
104 views

Discrete Math Combinatorics Homework Help

Find the value of ${n\choose0} + 3{n\choose1} + 9{n\choose2} + {27}{n\choose3} + \dots + 3^n{n\choose n}$ I know that ${n\choose0} = 1$, ${n\choose1} = n$ so $3{n\choose1} = 3n$, and ${n\choose ...
0
votes
4answers
520 views

Proving any product of four consecutive integers is one less than a perfect square

Prove or disprove that : Any product of four consecutive integers is one less than a perfect square. OK so I start with $n(n+1)(n+2)(n+3)$ which can be rewritten $n(n+3)(n+1)(n+2)$ After multiplying ...
2
votes
1answer
89 views

$n$ persons who make telephone calls

Lets say we have $n$ persons and everybody knows one specific thing which the other persons do not know. When two of the $n$ persons telephone they share their knowledge about the specific thing. How ...
0
votes
1answer
18 views

We have $T(n) \leq T(\lceil \frac{n}{5} \rceil) + T(\lceil \frac{7n}{10} \rceil)$. Show that $T(n) < c'n$.

We have $T(n) \leq T(\lceil \frac{n}{5} \rceil) + T(\lceil \frac{7n}{10} \rceil)$. Show that $T(n) < c'n$ for all $n$ and for some constant $c'$. Looks straightforward enough, but suprisingly I ...
1
vote
1answer
140 views

Proving union of functions

Does this proof look right? Suppose f: A → C and g: B → C.Prove that if A and B are disjoint, then f ∪ g: A∪B→C. Suppose x ∈ A. That means f(x)=c. Therefore, x ∉ B since A∪B=∅. Suppose x ∈ B. ...
1
vote
2answers
66 views

Dicrete Math Interesting question about Tromino

Prove that for a m$\times$n rectangle, if this rectangle can be covered completely by trominoes of the shape indicated in the picture, then mn is divisible by 3. I came up with a tentative way to ...
1
vote
3answers
90 views

How many numbers from 1 through 60100 are divisible by none of the numbers from 2 through 6?

My thoughts on doing this problem: total numbers is 60100 so from the total I subtract the numbers divisible by 2, 3, 4, 5, and 6. Yet my answer 60100-30050-20033-15025-12020-10016 is a negative ...
0
votes
1answer
26 views

Recurrence relation $g(n) = g( \lfloor {n/2}\rfloor) + \lfloor{log_2{n}}\rfloor $

$g(n) = g( \lfloor {n/2}\rfloor) + \lfloor{log_2{n}}\rfloor \\ g(0) = 0$ Series is like this: $0,0,1,1,3,3,3,3,6,6,6,6,6,6,6,6,10,...$ and it's changes similar as $\lfloor{log_2{n}}\rfloor $ ...
0
votes
1answer
46 views

Correct strong induction proof for series

I have a series like this: $$c_0 = 1, \quad c_n = \sum_{i = 0}^{n-1}c_i.$$ Here are the first few elements: \begin{align*} c_0 &= 1, & c_1 &= 1, & c_2 &= 2, \\ c_3 &= 4, ...
1
vote
0answers
65 views

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$. Here's my simple algorithm: We first check if $k=1$ or $k=2l$ or $k=2l+1$ for some $l ...
0
votes
2answers
75 views

Solve recurrence relation $ a_{n+1} = (n+1)a_n + 1 $

$a_0 = 1 \\ a_{n+1} = (n+1)a_n + 1 $ Could you help me solve this? And maybe someone know good source explaining how to solve recurrence relations?
0
votes
3answers
835 views

Show that if $A ⊆ C$ and $B ⊆ D$, then $A × B ⊆ C × D$ [duplicate]

Show that if $A ⊆ C$ and $B ⊆ D$, then $A × B ⊆ C × D$ Can anyone help me with this ?
0
votes
1answer
73 views

Find the next four largest 4-combinations

Find the next four largest 4-combinations of the set 1,2,3,4,5,6,7,8 after 1,2,3,5. Not sure how to do this, need some help~!
0
votes
1answer
123 views

For all sets $A$, $B$ and $C$, if $A=B\cup C$ then $A-B=C$

Prove or disprove the statement For all sets $A$, $B$ and $C$, if $A=B\cup C$ then $A-B=C$ I'm not too sure if it's true or not. Please explain your thinking and show your work. Thank you!
0
votes
2answers
41 views

Curiosity in a product

I have noticed the following curiosity for a product of integers. Given an ordered (decreasing) sequence of strictly positive integers $(a_i)_{i=1 \ldots n}$, that is to say, such that: $$\forall\ i\ ...
2
votes
2answers
107 views

Proving Wilson's theorem for $n=11$

Wilson's theorem establishes that if a $n$ number is prime then: \begin{align} (n-1)! &\equiv -1\ \textrm{mod}\ (n) \end{align} I have probed the theorem for the particular case where $n = 7$ ...
1
vote
1answer
44 views

discrete mathematics relations question 2

I am a little confused by this relation R3 is a subset of Z×Z defined by (x,y) in the set R3 if and only if x>2y is it reflexive? Symmetric? antisymmetric? or transitive? i say its NOT reflexive ...
1
vote
1answer
65 views

Discrete mathematics Relations Question

if r2 is in the set of N*N ( natural numbers) with (X,y) in the subset of r2, if and only if x+y=0 is it reflexive? is it symmetric? is it anti symmetric? is it Transitive? i said it is reflective ...
0
votes
1answer
39 views

Disc. Math Proof help?

I am enorolled in a community college level discrete mathematics course and am having problems with a proof I have for homework. Suppose a, b, c, and d are integers and a≠c. Suppose also that x is a ...
0
votes
1answer
316 views

Duality discrete math problem

This is the only answer I got wrong on my HW and the prof does not want to give us the correct answers before our midterm The dual of a compound proposition that contains only the logical operators ...
1
vote
0answers
36 views

For what $n$ do we have $ F_{n}=\lfloor \frac{1}{\sqrt{5}} ( \frac{1+\sqrt{5}}{2})^n +\frac{1}{2} \rfloor $

For what $n$ do we have $ F_{n}=\lfloor \frac{1}{\sqrt{5}} ( \frac{1+\sqrt{5}}{2})^n +\frac{1}{2} \rfloor $ where $F_{n}$ is the nth element of the Fibonacci sequence. Naturally I have to use the ...
0
votes
0answers
85 views

Discretization of a 2nd Order Differential Equation

Good Day to ALL! I want to UNDERSTAND the method of discretizing a 2nd order differential equation. I have tried the same, but my matlab model was a bust (it computes but the result is incoherent). I ...
2
votes
2answers
169 views

Straight-line embedding planar graph

I want to prove that every normal planar graph has a straight-line embedding. First I assume that the planar graph $G$ is maximal planar, i.e the number of edges is $3n-6$ for $|G|=|V(G)|\ge3$. If ...
0
votes
3answers
177 views

Prove the Number of Additions of Fibonacci Number Algorithm

I am studying for a final exam and I'm having trouble with this question: The following recursive algorithm FIB takes as input an integer $n \ge 0$ and returns the $n$-th Fibonacci number $F_n$: ...
1
vote
1answer
337 views

Boolean formula over 64 Boolean variables X

This question comes from this homework assignment from ECS20 at UC Davis. Chess is played on an 8 x 8 board. A knight placed on one square can move to any unoccupied square that is at a distance ...
1
vote
1answer
173 views

Question regarding translating English into first-order logic

Someone asked this question: "A language $L$ that is regular will have the following property: there will be some number $N$ (that depends on $L$) such that if $s$ is a string in $L$ (a $string$ is a ...
4
votes
1answer
77 views

Negating $(\forall a \in A)(\exists b \in B)(a \in C \leftrightarrow b\in C)$?

I'm not quite sure how to go about doing this. When negating I know the quantifiers themselves will be negated meaning that $\forall$ would become $\exists$ and vice-versa. Also I know that ...
2
votes
3answers
105 views

Cardinality: $\left|\Bbb N^{\Bbb N}\right| = \left|\{0,1\}^{\Bbb N}\right|$

Let $F$ be the set of functions from $\Bbb N$ to $\Bbb N$ and $G$ be the set of functions from $\Bbb N$ to $\{0,1\}$. Prove that $|F| = |G|$. What I tried doing is saying that every number in ...
0
votes
1answer
54 views

Graph Cut Problem

I have a problem as such: $2n$ players, each of whom has an odd number of friends, are distributed into two teams. A player is happy if more of his friends are on the other side than on his ...
1
vote
1answer
37 views

fundamental theorem of arithmetic help

Show that $\sqrt{10}$ is irrational using the Fundamental theorem of arithmetic. I know I can prove it by way of contradiction. But I also want to know how to do this with this method. By ...
3
votes
2answers
264 views

Translating English into First Order Logic

Translate the following into a formula of first-order logic. "A language L that is regular will have the following property: there will be some number N (that depends on L) such that if s is a string ...
0
votes
1answer
57 views

Divisiblity of a number by $(4k+3)$ in minimum time

Please suggest any algorithm with minimum time complexity to check whether a number $n$ is divisible by at least one $(4k+3)$ where $k>0$ is integer and $(4k+3)\le n$?
0
votes
0answers
33 views

Prove: If $c|ab$ and $gcd(a,b) = 1$, then $c =gcd(a,c)*gcd(b,c)$ [duplicate]

It says it all in the Title. I need to prove that if $c|ab$ and $gcd(a,b)=1$, then $c=gcd(a,c)*gcd(b,c)$. Thanks for any help!
0
votes
3answers
56 views

How to prove some statements about divisibility and the $\gcd$ function

Struggling with some number theory homework. Could use a helping hand. The two statements are as follows $\gcd(c, ab) \mid \gcd(c,a)\gcd(c,b)$ If $c \mid ab$ and $\gcd(a,b)=1$, then ...
1
vote
2answers
56 views

Discrete math question - nested quantifiers

question regarding nested quantifiers. $$\forall x \forall y\big((x < y)\to (x^2 < y^2)\big)$$ Determine the truth value for this question. I think this is false because if $x$ is $4$ and $y$ ...
0
votes
0answers
22 views

Prove that T comp (S comp R)=(T comp S) comp R

W, X, Y, Z are sets. R is the relation from W to X, S is the relation from X to Y, and T is the relation from Y to Z. Prove that T composition (S composition R)=(T composition S) composition R If ...
0
votes
2answers
34 views

Why is this relation transitive

Could someone explain why the relation $\lbrace {(1,1),(2,2),(3,3)}\rbrace $ on the set $\lbrace{1,2,3}\rbrace $ is transitive
0
votes
1answer
57 views

Number of functions in set

I'm studying for my discrete math midterm and having some trouble with this question: A{1,2,3,...,n} and B={a,b,c} A fixed integer k such that 0 =< k =< n and a fixed subset S of A having size ...