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

learn more… | top users | synonyms

0
votes
1answer
88 views

8 dice and probability of distinct values [duplicate]

NOT HW just practrice question If eight distinct dice are rolled what is the probability that all six numbers appear ? The chapter is INclusion and exclusion and the answer in the back of the text ...
0
votes
1answer
105 views

How to solve this minimization (maximization)?

I'm facing this problem: $$ \large \min_{x \in \mathbb{R}_+^3} \max \left\{ { \sum_{i=1}^3 x_i^2-2 x_1 x_3 \over \left(\sum_{i=1}^3 x_i \right)^2} , { \sum_{i=1}^3 x_i^2 + 2 (x_1 x_3 - ...
0
votes
1answer
30 views

Substring Occurrence in a String of Size $5$

Question: How many strings can be formed by ordering the letters $ABCDE$ so that each string contains the substring $DB$ or the substring $BE$ or both? Attempt: There are four possible ways ...
0
votes
1answer
88 views

Parseval's Theorem on a Random Signal

I'm struggling with Parseval's Theorem. I'm trying to relate variation in the time domain to the average value in the frequency domain. To do this, I'm performing the Fourier Transform on an arbitary ...
0
votes
1answer
29 views

equivalence relation and lexicographic order

This is a HW question Let $A = \mathbb{Z}^+ \times \ \mathbb{Z}^ +$. Define $R$ on $A$ by $(x_1,x_2)R(y_1,y_2)$ iff $x_1+x_2=y_1+y_2$. Is $R$ an equivalence relation on A. I dont think It is as ...
0
votes
1answer
19 views

Equivalence relation and restriction

This is a HW question Suppose $B \subseteq A$ and $R_a$ is an equivalence relation on A. Let $R_b$ the restriction of $R_a$ to B; that is, $R_b = {(a,b) \in R_a : a,b \in B} $ Is $R_b$ an ...
0
votes
1answer
102 views

Tutte's Theorem for infinite graphs

Can Tutte's theorem be extended for infinite graphs? If so, what is the proof? The theorem: A graph G = (V, E) has a perfect matching if and only if for every subset U of V, the subgraph induced by ...
0
votes
3answers
93 views

permutations containing a specific digit

Is there a formula to determine how many permutations of a certain set contain a specific value? For example, of all 4-digit PIN numbers, how many contain the digit 2 (assuming there are 10,000 ...
0
votes
1answer
62 views

Find the number of bytes that begin with 10 or end with 01.

A sequence of digits where each digit is 0 or 1 is called a $binary\ \> number$. Each digit in a binary number of a component of the number. A binary number with eight components is called a ...
0
votes
2answers
328 views

Discrete Math Help

Please help with these 2: For sets $A, B, C$, prove or disprove (with a counterexample) the following: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$. and Using Venn diagrams, ...
0
votes
1answer
99 views

What are the best ways to solve discrete divide and conquer recurrences? [duplicate]

What is the best way to solve discrete divide and conquer recurrences? The "Master Theorem" is one way. What other ways are available?
0
votes
1answer
327 views

Ceiling to Floor Function Conversion Proof

I am working on a proof to convert a ceiling of a fraction to a floor of a fraction. I found this: \begin{aligned} q=\left\lceil \frac{n}{m} \right\rceil \;&\Leftrightarrow\; \frac{n}{m} \leq q ...
0
votes
1answer
165 views

$G$ is 2-vertex-connected graph if and only if every 2 vertices from $G$ lie on a simple cycle.

$G$ is $2$-vertex-connected graph if and only if every $2$ vertices from $G$ lie on a simple cycle. $\implies$ If $G$ is $2$-vertex connected graph it means for every $ v \in V(G), \deg(v) ...
0
votes
1answer
57 views

Let $G(V,E)$ be an un-directed, un-connected graph. Prove that $\bar G$ is connected, And its Diameter is at most $2$. [duplicate]

Let $G(V,E)$ be an un-directed, un-connected graph. Prove that $\bar G$ is connected, and that its diameter is at most $2$. I've started by writing myself some guidelines: Two vertices will be ...
0
votes
2answers
293 views

Recurrence relations and generating functions question

Let $A_n$ be the set of different paving of a $2\times n$ using $2\times 1$ or $1 \times 2$ tiles. We'll define $a_n$=$|A_n|$. 1] Find recurrence relation: I found it -> $a_n=a_{n-1}+a_{n-2}$ with ...
0
votes
1answer
67 views

A small question about generating functions

just a small question: When should I use infinite geometric sequence and when should I use finite geometric sequence when solving problems involving combinations? For instance, for the problem: How ...
0
votes
1answer
86 views

distinguishable and indistinguishable people and ticket offices

In how many ways we can arrange p people in the queue to the 5 ticet offices a) people are distinguishable ticket offices are distinguishable b) people are distinguishable ticket offices are ...
0
votes
1answer
102 views

Gambling expected value riddle [duplicate]

A friend of mine gave me this probability riddle i couldn't solve, Maybe you could help me. Say i go to a casino playing roulette. I always gamble that a black number would pop (probability is: ...
0
votes
1answer
43 views

A $20$-degenerate graph on $1000$ vertices has to have at least $501$ vertices whose degree is at most $80$.

I'm seriously at a loss here... I'm asked to prove or disprove the following statement: A $20$-degenerate graph on $1000$ vertices has to have at least $501$ vertices whose degree is at most $80$. I'd ...
0
votes
3answers
3k views

Venn diagram problem solving question

In a class of $63$ students, $22$ study biology, $26$ study chemistry and $25$ study physics. $18$ study both physics and chemistry, $4$ study both biology and chemistry and $3$ study both physics and ...
0
votes
2answers
148 views

Probability density/mass function

I am a bit confused as to the difference between the probability mass function and the probability density function for a distribution of discrete variables. I understand there would be no mass ...
0
votes
1answer
81 views

Why is this summation formula wrong?

This is the alternate form of the summation formula: $$ \sum^{n}_{k=0} a(c)^k = \frac{ac^{n+1} - a}{c - 1} $$ so why is this wrong? $$ \sum^{n}_{k=0} (-\frac{1}{2})^k = \frac{(-\frac{1}{2})^{n+1} - ...
0
votes
2answers
43 views

Ways of solving recurrence relation for $a(15)$

I have this recurrence relation: $$ R(1)=1, RE(1)=0, EE(1)=0$$ $$a(n)=R(n) + RE(n)$$ $$R(n)=EE(n-1)+RE(n-1),$$$$ RE(n)=R(n-1),$$$$ EE(n)=RE(n-1) $$ How do I get $a(15)$? What kind of method do I ...
0
votes
3answers
158 views

number theory: Let $m>n$ for $m,n\in\mathbb{Z}$, prove if $k$ divides $m$ and $k$ divides $n$ then $k$ divides $m\bmod{n}$

Let $m>n$ for $m,n\in\mathbb{Z}$, prove if $k$ divides $m$ and $k$ divides $n$ then $k$ divides $m\bmod{n}$. How should I approach this question? I only got $m=qk$ and $n=pk$ if ...
0
votes
2answers
158 views

If $a \mid c, b \mid c, \gcd (a,b)=1$ then $ab \mid c.$ [duplicate]

If $a \mid c, b \mid c, \gcd (a,b)=1$ then $ab \mid c.$ I understand that given problem is true. however im struggling with writing to prove. I let A=2 , B= 3 , C= 6 2 l 6= 3 3 I 6=2 3*2 l 6=1 ...
0
votes
1answer
138 views

Can any planar graph have 4 vertices and 4 regions?

This actually homework question which my professor has assigned few days ago. Question originally says that: Prove that any planar graph cannot have 4 vertices and 4 regions? I have found that $K_4$ ...
0
votes
1answer
69 views

Suppose $(A, \le)$ is a partially ordered set. Define a relation $\preceq$ on $A\times A$ by $(a,b)\preceq (c,d)$ if

if and only if 1) $a\le c$ and $a \ne c$ 2) $a = c$ and $b\le d$ Prove that $(A\times A,\preceq)$ is also a partially ordered set. So to prove this I would start with trying to find 1) ...
0
votes
1answer
109 views

I don't know where to begin with this functions question (one-to-one, onto)

a) Suppose that $f:\Bbb Z\to \Bbb Z$ is a one-to-one function. Define a function $g:\Bbb Z\to \Bbb Z$ by: for all integers $x$, $g(x)= -f(x)$. Prove that $g$ is also one-to-one. b) Suppose $f:\Bbb ...
0
votes
1answer
65 views

is this symmetric

A is the set of all functions $\mathbb{R}$ $\to$ $\mathbb{R}$ f is related to g if and only if f(x) $\le$ g(x) for all x $\in$ $\mathbb{R}$ I said its reflexive since it is less than OR equal, so ...
0
votes
1answer
81 views

Reflexivity, Transitivity, Symmertry of the square of an relation

$\def\p{\mathrel p}$If $\p$ is a relation on a set $A$, define $\p^2$ by $a \mathrel{\p^2} b$ if and only if there exists $c$ with $a \p c$ and $c \p b$. If $p$ is reflexive/symmetric/transitive ...
0
votes
1answer
24 views

Similar statements for expressions

Is there an easy way to find out which 3 are similar from the left and right side, it will be nice with some tricks to find it out, or if you have some rules that can be followed. $$ {lg\,n +\frac12} ...
0
votes
1answer
175 views

Venn diagram related question

An analysis of the survey of $320$ school pupils highlighted the following facts: • $50$ pupils live in New Town, travel to school by bus and have canteen lunch. • $110$ pupils live in New Town ...
0
votes
3answers
76 views

Pigeon holes principle

Let $P$ be a group that it's elements are 257 sentences in which only atomic sentences from $A,B,C$ exist (i.e. $A \iff B,\space\space A \wedge B \wedge C, \space\space...$) Show that there exists two ...
0
votes
2answers
133 views

find recursive solution $T(n)=2T(n/2)+n-1$

I want to solve this: $$T(n) = 2 T\left(\frac{n}{2}\right) + n - 1 $$ I try : \begin{align*} n &= 2^m \\ T(2^m) &= 2T(2^{m-1}) + 2^m -1 \\ 2 ^ m &= B \\ T(B) ...
0
votes
1answer
87 views

Is there a formula to calculate the minimum height of an n-nary tree with L leaves?

I'm trying to figure out if there is a way to calculate the minimum height of an n-nary tree with L leaves. Is there such a formula?
0
votes
1answer
18 views

Clues to prove average in T is minor or equal than average in a smaller inner interval.

Suppose I want to prove (or disprove) this assertion Let $f$ be a discrete function, $T,h,k$ are constants So these terms are averages over $T$ and over $h$ $\sum\limits_{i=0}^{T}\frac {f(i)}{T}$ ...
0
votes
1answer
866 views

Do “cut set” and “edge cut” mean the same thing?

The definitions I have are: A cut set of a graph $G$ induced by a partition of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in ...
0
votes
2answers
112 views

Prove that if $A\triangle B = C\triangle B$, then $A = C$

I am working with proofs in discrete math. Help to prove: For the sets $A$ and $B$, we define the symmetric difference of $A$ and $B$ to be $A \triangle B = (A-B)\cup(B-A).$ Prove that if $A ...
0
votes
1answer
29 views

How can i bound the largest edge length of an $n$-point metric in $O(n)$?

For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
0
votes
4answers
117 views

the probability of guessing a number [closed]

Choose any natural number. For example I would choose: 3852011231231280130218920382342312420234801232321241231212131234 (and so for for another few bilions of digits) What's the probability that ...
0
votes
1answer
93 views

Graph with 5 vertices - # of spanning trees

If a graph has 5 vertices, all of them connected to each other vertex, how many different spanning trees exist? I'm thinking the answer might be $4*3*2$, because the first point has 4 options to go ...
0
votes
1answer
59 views

Proving recurrence relations

So, I initially proved the theorem that if $a != b^d$ and $n$ is a power of $b$, then $f(n) = C_1n^d + C_2n^{log_b a}$, where $C_1 = b^dc/(b^d − a)$ and $C_2 = f(1) + b^dc/(a − b^d )$. This is seen ...
0
votes
1answer
59 views

Using The Pigeon-Hole Principle

Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n. Here is the solution: Let $a,~a+1,...,a+n-1$ be the integers in the sequence. ...
0
votes
1answer
51 views

Help proving and counting functions.

Let $\mathscr F$ denote the set of all functions from $\{1, 2, 3\}$ to $\{1, 2, 3\}$. a) Of the two following statements, one is true and one is false. Prove the true statement. Write out the ...
0
votes
1answer
106 views

Let $A$ be a set of size $4$. How many reflexive relations are on $A$?

Let $A$ be a set of size $4$. How many reflexive relations are on $A$? Let $n = |A| = 4$ Number of reflexive relations = $ 2^n $ Is that correct? I think so because I imagine I only want to ...
0
votes
1answer
120 views

Denomination problem

Suppose that the only denominations of the available bills are 11 and 19 dollars. In a convenience store, what amounts can be paid? Justify your solution in full detail.
0
votes
2answers
101 views

Finding Integers With Certain Properties.

How many positive integers between 100 and 999 inclusive e) are divisible by 3 or 4? For this problem, I understand that one has to employ the inclusion-exclusion principle. Those integers ...
0
votes
3answers
291 views

Relations: Reflexive, symmetric, transitive

I am having difficulties determining if this relation is reflexive, symmetric, transitive, or none of these. Let A be the set of all strings of $0's$, $1's$, and $2's$ of length $4$. Define a ...
0
votes
3answers
78 views

Recurrence relation of two next terms

For the recurrence relation, $a_{n+2}=3a_{n+1}-2a_n$ with $a_0=2$ and $a_1=3$, compute the first six terms of the sequence and derive a closed form formula for this sequence. So I'm totally lost with ...
0
votes
2answers
75 views

Create a Generating function

Let $P$ be the set of permutations all of whose cycles are of even length. Prove that the exponential generating function for $P$ is $\dfrac{1}{\sqrt{1-x^2}}$.