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

Prove that sets $A$ and $B$ are disjoint iff $A \cup B = A \bigtriangleup B$

I'm studying for my exam and I came up with this little proof, but I'm wary because the professor took a much longer approach. Am I right in saying that a symmetric difference is the same as the ...
0
votes
1answer
34 views

algorithmic complexity in Big O notation

Here is the function that is meant to be analyzed f1(n) 1 v ← 0 2 for i ← 1 to n 3 do for j ← n + 1 to 2n 4 do v ← v + 1 5 return v I was wondering if my ...
9
votes
14answers
2k views

Using set notation, define the set of even natural numbers between 100 and 500.

Using set notation, define the set of even natural numbers between 100 and 500. This is what I have so far: $P$ is even numbers so the set of natural numbers between 100 and 500 would be $$P = ...
1
vote
1answer
29 views

Combinatorics: Using a Generating Function to Count the Number of Ways of Selecting a Hand From a Triple Deck

Use a generating function to determine the number of ways to select a hand of m cards from a triple deck, if there are n distinct cards in a single deck. Verify that your expression produces the ...
0
votes
4answers
56 views

How to get $(n+1)!(n+2) = (n+2)!$

I mean it makes sense when I look at it that the two are equal, but I don't entirely understand how you get from one to the other - I presume there's some basic algebra involved - but I'm not sure ...
2
votes
1answer
38 views

Combinatorics: Number of Six-Card Hands That Can Be Dealt from r Combined Decks

I am having trouble solving this combinatorial problem dealing with the number of different card hands possible from multiple decks of identical cards. Here is the exact question: Use a combinatorial ...
0
votes
1answer
40 views

How many cards must be drawn unseen from a set of 52 playing cards to guarantee that at least 2 of them are the same suit?

I am having trouble starting this. I know a can use a $nCr$ method but I don't know how to apply it here.
0
votes
2answers
23 views

Laws of Logic Negation Simple

I cant quite remember, when you are using the laws of logic to simplify an argument or an argument about sets. Do you start on the outside of the brackets with the outer most negation? Or the inner ...
1
vote
2answers
28 views

Every power of adjacency matrix contains zeroes

I need to find connected graph $G = (V, E), |V| \geq 3$ such that every power of his adjacency matrix contains zeroes. I know that that graph will be path and adjacency matrix for even and odd powers ...
0
votes
0answers
26 views

ALGORITHM Multiplication of Integers from “discrete math and its applications 7th edition ” book

Please can you help me to understand the "italic text" How many additions of bits and shifts of bits are used to multiply a and b using Algorithm 3"see the the attached photo"? Solution: ...
4
votes
3answers
315 views

Need help to prove (A∪B) - (C - A) = A ∪ (B - C)

Having trouble with a discrete math question involving sets. Have been asked to prove: (A∪B) - (C - A) = A ∪ (B - C) This is what I have so far: x ϵ A or x ∈ (B - C) x ∈ A or (x ∈ B and x ∉ C ) ...
3
votes
1answer
71 views

Can the wolves catch the hare?

Say you have 7 positions. 1 Hare and two Wolves in the following starting positions:    H o     o W   W  o   o The hare can take a step of size 2. The ...
2
votes
1answer
48 views

Lovasz Extension of the Product of Functions

Let $f$ and $g$ be submodular functions, and let $\widehat{f}$ and $\widehat{g}$ be the Lovasz extensions of $f$ and $g$, respectively. What can we say about the Lovasz extension of $f \times g$, ...
-1
votes
1answer
31 views

Describing a discrete dynamic system

Model There are three types of animals: $Y$, young (0-5 years old) $A$, adult (5-10 years old) $O$, old (10 years old or more) The initial conditions of the system are $Y_0=2500$, $A_0=1200$, ...
0
votes
1answer
27 views

How to arrange 3 rectangles in a big rectangle

I have a big rectangle of 100x100. I want to arrange 3 rectangle whose original size is 40x40, 40x40 and 10x10 in a 100x100 rectangle. Here we can increase any width or height or both by specific ...
0
votes
1answer
27 views

Number of possible solutions to equation

I am trying to solve $$x+y+z = 32$$ Where $x$, $y$, and $z$ are positive integers I believe the answer is: $C_{2}^{31}=465$ but I am not sure why. Can someone please explain?
1
vote
0answers
33 views

Does each element of $D4$ have an inverse in $D4$?

We are just starting the concept of permutations of objects in my class and I'm having trouble to grasp this particular question. I'm assuming it does have an inverse because of all the different ...
0
votes
1answer
45 views

Inclusion and Exclusion Principles

In a scientific study of 233 imaginary people, each eats at least one meal every day. Of these, 91 eat breakfast, 152 eat lunch and 177 eat dinner. Also, 190 eat either breakfast or 1 lunch, 205 eat ...
13
votes
11answers
3k views

Prove that 1 + 4 + 7 + · · · + 3n − 2 = n(3n − 1)/ 2

Prove that $$1 + 4 + 7 + · · · + 3n − 2 = \frac{n(3n − 1)} 2$$ for all positive integers $n$. Proof: $$1+4+7+\ldots +3(k+1)-2= \frac{(k + 1)[3(k+1)+1]}2$$ $$\frac{(k + 1)[3(k+1)+1]}2 + ...
1
vote
2answers
69 views

Review Question Help; Discrete Math

Let p be a real number with 0 < p < 1. When and have a child, this child is a boy with probability p and a girl with probability 1 − p, independent of the gender of previous children. Lindsay ...
1
vote
2answers
32 views

Discrete Math: Array-Pointer Representation

I am confused as to how the table is filled in for a pointer-array representation of a graph, and I can't find anything online that talks much about array-pointer representation. My book does not ...
2
votes
3answers
28 views

Cardinality with a Bijection

Suppose that $a, b \in \mathbb{R}: a<b$. Show that $(a, b) ≈ℝ$ by finding a bijection between the sets. I think this might work but am not certain: $g(x) = \frac{2x-b-a}{b-a}$ I was also told ...
1
vote
1answer
45 views

Indicator random variable review question help

Having a bit of trouble with this review question. A run of ones in a bitstring is a maximal consecutive of ones. For example, the has four runs of ones: , , , and . Let n ≥ 1 be an integer and ...
1
vote
1answer
37 views

Expected Value Review Question Help; Discrete Mathematics

I'm studying for my discrete exam and I can't figure out this problem in the review, any help is appreciated. When Jane and Bob have a child, this child is a boy with probability 1/2 and a girl with ...
0
votes
2answers
31 views

Show whether a relation R is transitive for xRy iff 3|(2x+y)

Define a relation $$R : Z^+ \rightarrow Z^+$$ by xRy iff (2x+y)mod3=0. R is reflexive: Let x=y. So (x,x) is in R. Then we have 2x+x=3x, and since x is an integer, it must clearly be divisible by 3. ...
1
vote
1answer
46 views

Discrete Math Probability and Random Variable review question

I can't solve this question on my review. If anyone can give me some help to start it, it would be appreciated! Consider an experiment that is successful with probability 0.8. We repeat this ...
4
votes
3answers
91 views

How many $2$'s are needed?

There is a positive integer $N$. $N$ is made up of only two distinct digits- $2$ and $3$. $N+18$ is divisible by $37$. What is the minunum amount of times the number $2$ can appear in $N$? I'm pretty ...
2
votes
2answers
28 views

Solve the recurrence relation by taking the logarithm of both sides and making the substitution $b_n = \lg a_n$

Solve this recurrence relation: $$a_n = \left(\frac{a_{n-2}}{a_{n-1}}\right)^{\frac{1}{2}}$$ by taking the logarithm of both sides and making the substitution $$b_n = \lg a_n$$ A couple years ago ...
1
vote
1answer
41 views

Recurrence relation to find ternary strings that do not contains 3 consecutives 0's

I'm stuck and I can't find this recurrence relation which is : Find a recurrence relation that count the number of ternary strings $(0,1,2)$ of length n that do not contains three consecutives 0's. ...
1
vote
2answers
28 views

Solve the linear homogeneous recurrence relation with constant coefficients

$$9a_{n} = 6a_{n-1}-a_{n-2}, a_{0}=6, a_{1}=5$$ So $$x^n = (6x^{n-1}-x^{n-2})\div9$$ thus $$[x^2 = (6x-1)\div9] \equiv [x^2 - \frac{2}{3}x + \frac{1}{9} = 0], x=\frac{1}{3}$$ also ...
0
votes
1answer
47 views

Is relation a partial order?

can you give me few hints how to solve this problem ? Relation R on the set P(A) A = {a,b,c,d} is a set of four elements. We also have relation R on the set P(A), which is defined R={(A,B)│A ⊆ B. ...
0
votes
1answer
17 views

Let E1, E2 Equivalence relations on A, Prove or disprove :

Let E1, E2 Equivalence relations on A, Prove or disprove : 1) E1 ∩ E2 an equivalence relation on A 2) E1 ∪ E2 an equivalence relation on A
0
votes
1answer
41 views

Combinatorics, marks to students

please am I right in my solutions for these problems ? There was a test in a school, but teacher lost all the completed tests. He has to give some points to studens. a)How many possibilities are ...
0
votes
0answers
55 views

Prove the following properties of binary relations

I'm so confused and don't have a clue what I'm doing anymore so any help would be great thanks, I have to Prove the following properties of binary relations. 1 ◦ R = R R ◦ (S ∪ T) = R ◦ S ∪ R ◦ T R ...
0
votes
1answer
49 views

What tools should be used to prove that a real function is one-to-one and onto?

Let $A = \mathbb R \setminus \{−1/2\}$ and $B =\mathbb R \setminus \{2\}$. Define $f : A \to B$ by the rule $$f(x) = \frac{4x − 3}{2x+1}$$ for all $x \in A$. Show that $f$ is one to one and onto. Find ...
0
votes
1answer
57 views

Find a formula for the recurrence relation $x(n) = x(\lfloor n/2 \rfloor) + n\,a\,x(1) = 1$

Do you know how to find a formula for a sequence below? $$\begin{align*} x(n) &= x(\lfloor n/2 \rfloor) + n\\ x(1) &= 1 \end{align*}$$ What is $x(2^k)$? What is $x(n)$ when $2^k \leq n < ...
0
votes
1answer
15 views

Transitive closure relation

I have a following relation on the set {A,B,C,D} R = {(a,a);(a,c);(b,d);(c,d);(d,c)} What is the smallest number of tuples that has to be added in order for the relation to become transitive? It is ...
1
vote
3answers
61 views

Amount of binary strings

i `ve got this problem, can you help me ? I can solve subquestion a) but i really don`t have a clue how to find recursive formula. S_n is the amount of binary strings with size n, which don’t ...
0
votes
1answer
49 views

Digit sum of natural numbers in interval

can you help me with this problem ? How many natural numbers $n$, $1 ≤ n ≤ 10^4$, with digit sum $= 7$, can you find ?
1
vote
2answers
31 views

Proofs with Relations and functions

I need help with setting up a homework problem. I am having trouble finding where to start. Problem: Suppose A is a set. Show that $i_A$ is the only relation on A that is both an equivalence relation ...
1
vote
1answer
39 views

Arithmetics of cardinalities: if $A=C$ and $B=D$ then $A\times B=D\times C$

Suppose that $A, B, C$, and $D$ are sets with the cardinalities related as $A=C$ and $B=D$. Prove that the cardinality of $A\times B$ is equal to the cardinality of $D\times C$. I know that I must ...
0
votes
1answer
9 views

Discrete Structures : predicate logic (negation)

I got part 1 wrong but can't seem to figure out why. All farmers -> not all farmers, grow corn -> grow only corn. When I put it together it made sense. Am i missing something? Write the negation of ...
1
vote
1answer
16 views

Solve linear homogeneous recurrence relation?

The relation to solve is this: $$ a_{n} = 7a_{n-1} - 10a_{n-2}, a_{0} = 5, a_{1} = 16$$ So $$ a_{2} = 62, a_{3} = 274, ...$$ So I thought I was supposed to be able to do this to solve: $$ x^n = ...
1
vote
6answers
44 views

Solving recurrence relations?

How do I solve $$ a_{n} = a_{n-1} + n, a_{0} = 1$$?? I solved for n=1 thru n=5: 1: 2 = a0 + 1 2: 4 = a0 + 1 + 2 = a0 + 3 3: 7 = a0 + 3 + 3 = a0 + 6 4: 11 = a0 + 6 + 4 = a0 + 10 5: 16 = a0 + 10 + 5 = ...
1
vote
3answers
22 views

Discrete Structures : predicate logic (negations)

Could someone please explain why the negation makes "nobody" into "someone" and not "everyone" Which of the following is the correct negation for “Nobody is perfect.” 1. Everyone is imperfect. ...
1
vote
1answer
18 views

John sold some books at $24 each, and used the money to buy some concert tickets…

John sold some books at 24 dollars each, and used the money to buy some concert tickets at $50 each. He had no money left over after buying the tickets. What is the least amount of money he could have ...
0
votes
2answers
21 views

Discrete Structures : predicate logic

Can anyone help me understand why this might be wrong? You can’t fool all of the people all of the time. (∀x) [P(x) /\ (∀y)(T(y)-> ~ F(x,y))]
0
votes
1answer
26 views

BigOh Complexity: $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$?

Show $\frac{x^{3} + 2x}{2x + 1}$ is $O(x^2)$ Can I do it like this? Since exponent rules/laws allow this: $\frac{x^{3} + 2x}{2x + 1}$ $=$ $\frac{1}{2}x^{2} + 2x$ Must show a constant c>0 and k ...
0
votes
2answers
23 views

A rental car agency has 12 identical cars available and 7 identical vans…

My question is: A rental car agency has 12 identical cars available and 7 identical vans a) If the group needs to rent four cars and two vans, in how many different ways can they select their ...
1
vote
2answers
61 views

How can the sniffer dog find the bag of drugs?

There are $n$ bags. In one of the bags are drugs. There is a dog that when given a group of bags, can tell whether there are drugs in the group or not. Each sniff counts as a "turn". What is the best ...