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
1answer
24 views

Which one of the following is true of this relation?

Consider the set of A all the people who are living down Italy."x lives in the same house as y" is a relation on the set A.Consider the following properties of a relation on a set: a)Symmetric b)...
1
vote
1answer
22 views

What is $(A∪C)-(B∩D)$, when $A=[3,8),B=[2,6],C=(1,4),D=(5,∞)$

So the problem is asking for $(A∪C)-(B∩D)$, when $A=[3,8),B=[2,6],C=(1,4),D=(5,∞)$ My try at this: $A∪C = (1,8)$ $B∩D = (5,6]$ $(1,8)-(5,6] = (1,5)∪(6,8)$ Would this be correct? Edit: There's ...
0
votes
2answers
19 views

Equivalence Relation, transitive relation

Reading about Equivalence Relation, I understand that for a equivalence relation of a set, it must be reflexive, symmetrical, and transitive, but i'm still a little fussy on transitive to be honest! ...
2
votes
7answers
75 views

$x$ is odd if and only if $3x+6$ is odd

Prove the following proposition. Let $x\in\Bbb Z$. Then $x$ is odd if and only if $3x+6$ is odd. I'm currently not seeing a way to transform $3x+6$ into the format of $2k+1$ in order to prove odd. ...
0
votes
0answers
46 views

How many strings of 12 lowercase letters with repetitions

Consider strings of 12 lowercase letters, such as aksdjmnuuyio. How many strings either are a repetition of 2 strings of 6, such as aksdjmaksdjm, or a repetition of three strings of 4, such as ...
0
votes
0answers
13 views

Show by any method of construction that the language A = {a^i b^j} is regular.

Show by any method of construction that the language A = {a^i b^j} is regular. restrictions: 1) i is a multiple of any given integer n 2) j is a multiple of any given integer m 3) n,m >= 0 I ...
1
vote
3answers
78 views

Is there a possible mathematical solution for this? [closed]

I have what might be considered an odd question. I want to see if I can find a formula/equation to help me with the following. I'm working in a software package that we are using to calculate fees. ...
0
votes
0answers
21 views

Is there a faster way of computing the probability of a sum $S$ when $n$ dice are rolled? [duplicate]

So far, I've only had to deal with $2$ dice or $3$ dice problems. For example, if the problem asks to find the probability that a sum of $8$ will be achieved from rolling $3$ dice, I just list all the ...
0
votes
0answers
22 views

number of inversions in permutation if subarray of permutation is reversed?

I have permutation(P) of numbers 1 to N (<=10^5) . Suppose I can reverse the subarray of ...
0
votes
0answers
27 views

Another nasty multiple sum.

Let $s \ge 0$ be an integer, let $a_\xi \ge 1$ for $\xi=0,\cdots,s$ and let $t$ and $\beta$ be parameters. Also defines $l:= a_0+\cdots+a_s$. Consider a following multiple sum: \begin{equation} {\...
0
votes
1answer
31 views

Solving a Linear Recurrence with a Cubic Characteristic Equation

I've been learning Linear Recurrences in my Discrete Math course and I've learned how to solve them when the characteristic equation is a quadratic. Is solving a linear recurrence with a cubic ...
1
vote
1answer
30 views

If deg$(v) \geq k$ for all $v \in V(G)$, then G contains a matching of cardinality $\min \{k,\lfloor{\frac{|V|}{2}}\rfloor\}$

Let$G = (V; E)$ be an undirected graph. Show that if deg$(v) \geq k$ for all $v \in V$, then G contains a matching of cardinality $\min \{k,\lfloor{\frac{|V|}{2}}\rfloor\}$. I have no idea how to ...
0
votes
2answers
47 views

Prove that a graph has a cycle of length no more than $14$

A graph contains $2016$ vertices, its chromatic number is $5$, prove that this graph has a cycle of length $\leq 14$. Where do I start?
-1
votes
1answer
59 views

If a student who received an A in probability is chosen at random, what is the probability that he/she also received an A in calculus?

This question has been asked before but the solution given was incorrect.(see here) A prerequisite for students to take a probability class is to pass calculus. A study of correlation of grades for ...
1
vote
4answers
42 views

Empty Sets question [closed]

I need some help understanding empty sets being elements vs subsets to another set. This ask if it is true or false. {{∅}} ∈ {∅,{∅}} {{∅}} ⊆ {∅,{∅}} I know that they are both false but could ...
0
votes
4answers
37 views

Why doesn't this alternative method work? Chance of getting four of a kind in a hand of $5$ cards?

Please note: This is not a duplicate since it is asking about an alternative method of solving the question What is the probability of getting four of a kind in a hand of $5$ cards from a standard ...
0
votes
1answer
25 views

Can we draw a graph with N vertices of degree M where N = M?

More specifically: Can we draw a graph with 1 vertex of degree(1), 2 vertices of degree(2), 3 vertices of degree(3), and 4 vertices of degree(4)? *Assume there are no other conditions/...
2
votes
2answers
33 views

Identity relation vs Reflexive Relation

So we're starting relations in my discrete structures class this week, and I've probably read this over 10 times by now...I believe I have a good understanding of Identity Relations, but Reflexive ...
0
votes
1answer
30 views

Understanding why this simple recurrence relation is structured in this manner

Given this question: Find a recurrence relation for the number of bit strings of length $n$ that contain a pair of consecutive $0$s. And this textbook answer: Let $a_n$ be the number of bit ...
2
votes
0answers
39 views

The number of partitions of $n$…Subbarao

(Subbarao) The number of partitions of $n$ in which each part appears two, three, or five times equals the number of partitions of $n$ into parts congruent to $2, 3, 6, 9,$ or $10$ modulo $12$. ...
1
vote
1answer
42 views

Complicated probability question [closed]

There are 20 empty present boxes numbered from 1 to 20 are placed on a shelf, there are 4 men standing in front of the shelf. Each one asked to pick in his mind 3 numbers without telling any one then ...
6
votes
3answers
58 views

In how many ways can an inspector visit $4$ normal sites and $1$ “suspicious” one?

I cannot figure out why my answer to the following question is wrong: Suppose that a weapons inspector must inspect each of five different sites twice, visiting one site per day. The inspector is ...
0
votes
0answers
12 views

Logic-Calculating Cd Failures

I am working on homework and have the problem At a company every 4th CD is tested, the testing consists of 4 testing programs and the probability that they fail are as follow Program 1 : .01 Program ...
1
vote
2answers
45 views

Sum over Binomial mass function

In Casella and Berger Book (Statistical Inference), exercise 2.40 is $$\sum_{k=0}^x {n\choose k}p^k(1-p)^{n-k}=(n-x){n\choose x}\int_0^{1-p}t^{n-x-1}(1-t)^xdt.$$ If I replace $x$ by $n$ then LHS ...
-2
votes
2answers
44 views

$[2,5] = \{2,3,4,5\}$ T or F?

I am trying to understand this problem. Is $[2,5] = \{2,3,4,5\}$ true or false. What I think: $[2,5] = \{x: 2 \leqslant x \leqslant 5\}$. So this includes 2,3,4, and 5. Therefore it is equivalent so ...
-1
votes
0answers
33 views

i dont understand how theorem calculation proofs work please help [closed]

I do not understand hilbert style proofs and how they work. Can someone please explain them to me? some things i need to know are: • Write theorem-calculations from Γ (equivalently, Γ−...
0
votes
2answers
76 views

Discrete Math Pigeon-Hole [closed]

How can we solve below problem? Let $X = \{1,2,3,\dotsc,100\}$. If eleven numbers are selected from $X$, show that there are at least two numbers $u$ and $v$ such that $$0 \lt \left| \sqrt{u} - \...
0
votes
3answers
71 views

Very confused by recurrence relations as a concept

We've been introduced to recurrence relations as a concept in my Discrete class. One question asks: Given the recurrence: $S(1) = 1$, $S(n) = 2S(n − 1) + 3 (for \ n > 1)$ prove ...
0
votes
0answers
29 views
-1
votes
0answers
17 views

Eulerian and Hamiltonian Graphs [closed]

Can someone help me with this? To verify that every Eulerian graph is Hamiltonian and vice versa
0
votes
3answers
107 views

Find all N in $\phi(N)=98$ [closed]

Solve the equation $\phi(N)=98$ I have no idea how to do it. How to find all N?
0
votes
2answers
19 views

c*(log 2n) is the same as c + c*log n?

I am reading a chapter of my data structures book that is about big O notation and have come across an example where I do not understand the Algebra behind it: " On the other hand, if a search ...
0
votes
1answer
43 views

Probability book choosing questions

So I am doing homework and have the following question If 3 books are picked at random from a shelf containing 5 novels, 3 books of poems, and a dictionary. What is the probability that (a) the ...
3
votes
1answer
51 views

Combinatorial proof for a non obvious binomial identity

I think I got some serious problem with those combinatorial proofs. Why would the following be true ($1\leq r\leq k\leq n$): $$\sum_\limits{j=r}^{n+r-k}\binom{j-1}{r-1}\binom{n-j}{k-r} = \binom{n}{k}?...
2
votes
1answer
27 views

Finding a recurrence for number of paths in a certain tree

I have a graph which looks like this: The question is to find a recurrence for $a_n$ - the number of paths of length $n$ that start in vertex $A$. How do you tackle these kind of problems? There is ...
0
votes
1answer
50 views

Size of family $\mathcal F = \{F_1, \ldots, F_m\}$ is at least $\lceil \log_2n\rceil$.

A family $\mathcal F = \{F_1, \ldots, F_m\}$ of subsets of $\{1,2,\ldots,n\}$ is said to be separating if for any two elements $1 \leq i < j \leq n$, there is some set $F \in \mathcal F$ such ...
-1
votes
0answers
37 views

Find out a probability from a set [closed]

I have set A = [ 1 0 0 1 0]; in this set, the number of 1's is two and the number of 0's is three. Question: How to calculate probability of randomly selecting a 1 from set A? (without replacement of ...
0
votes
2answers
56 views

A soccer squad contains $3$ goalkeepers, $7$ defenders, $9$ midfielders and $4$ forwards.

A soccer squad contains $3$ goalkeepers, $7$ defenders, $9$ midfielders and $4$ forwards. So I understood the first part of the question: $(i)$ In how many ways can a team of $1$ goalkeeper, $4$ ...
5
votes
1answer
123 views

Given sets A and B such that A ⊆ B, write down A ∪ B in a simplified form.

Here's how I did it: Let A = {1,2,3} Let B = {1,2,3,4,5} Since A ∪ B, everything in A would also be in B thus the simplified form would be B? If it's wrong, please let me know how to go about this, ...
-5
votes
1answer
62 views

What would be the solution to this logic puzzle? [closed]

This is the puzzle I am having trouble in understanding Also, do explain me the question along with the answer. Thank You
1
vote
3answers
41 views

Propositional calculus - I can't get why the answer for this test question is what it is

Consider the following premises. If A = B then B = C. B != C. If C > D then D < E. F != G and A = B. A = B or C > D. Alternatives: a) F != G b) F != G and D < E c) A = B d) B = C or D &...
7
votes
4answers
149 views

Find the probability that a word with 15 letters (selected from P,T,I,N) does not contain TINT

If a word with 15 letters is formed at random using the letters P, T, I, N, find the probability that it does not contain the sequence TINT. (I just made up this problem.)
2
votes
2answers
45 views

logical equivalence statements in discrete math

Construct another English form sentence, which is logically equivalent to that which was given. "Susan goes to school or Susan does not talk on the phone or Susan does not go to school."
3
votes
1answer
125 views

How many possible functions?

Take $f:\{1,2,3,4,5,6,7\}$ to $\{0,1,2,3,4\}$ How many such functions satisfy the cardinality of the pre-image of the set $\{3\}$ is equal to $3$. I thought it would be $35$, i.e :$7\choose{3}$ ...
1
vote
2answers
33 views

What is the negation of ∀x∃y¬P(x,y) without using ¬?

Found it to be ∃x∀yP(x,y). Is this right?
1
vote
2answers
38 views

Finding integers $x$ and $y$ such that $633x + 255y = 6$

The first bit of the question asks to find the gcd of $633$ and $255$ which I did and found that it's $3$. However, the next bit asks this: Find integers $x$ and $y$ such that $633x + 255y = 6$, or ...
0
votes
1answer
29 views

Determining if a function is onto

If our range such as in the question below is all the real numbers excluding $0$, to determine if a function is onto we must ask if all real numbers excluding $0$ can be mapped to at least one value ...
1
vote
1answer
24 views

# of bit strings of length n (even>2), with n/2-1 zeros and n/2+1 ones, zero followed by one

case 1: What is the number of bit strings of length 4, with 1 zero and 3 ones, zero must be followed by one Answer: 3 case 2: What is the number of bit strings of length 6, with 2 zeros and 4 ones, ...
2
votes
1answer
70 views

Strange Algebra

I am working on a mathematical induction worksheet and my professor gave us the key and I have run across something that makes zero sense to me so please explain if you can. Additional info: $k \ge2$ ...
0
votes
1answer
52 views

Set-builder notation

How do I determine the size of the following set with set builder notation? $$\{𝑥 \in \mathbb{Z}_+\mid 4<𝑥<5\}$$ I don't know where to start and what integer value is usable.