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
2answers
40 views

100 tickets numbered 1,2,3…,100, are sold to 100 different people for a drawing…

I found the answer for these questions but I want someone could give explain 100 tickets numbered 1,2,3...,100, are sold to 100 different people for a drawing. four different prizes are awarded, ...
1
vote
2answers
27 views

Long summation question, including sets

I have a really long question I'm absolutely stuck on, I don't even know where to begin: Given: $n \in \mathbb{Z}, \geq 2$ let $S$ be the set of all nonempty subsets of {2,3,...,n}. For each $S_i ...
3
votes
1answer
31 views

Verify question about complements

I have the following question: $$A = \big\{ x\in \mathbb{R} \mid x^3 < x^2\big\}$$ Write the set definition of $A^C$. If I understand correctly, the complement of $A$ would be anything not in ...
2
votes
1answer
21 views

recurrence relation sequence..stuck

Q-->Find a recursive solution for $S_n$ the number of sequences of length $n$, composed of the letters $a$, $b$ or $c$ in which no sequence contains consecutive b's. Give detailed explanations. what ...
0
votes
1answer
20 views

expression tree

I'm having some trouble understanding expression trees especially with putting this expression into a tree: S/P^Q^R Any help with how to do these is greatly ...
6
votes
2answers
102 views

Show by induction that $2!4!6!…(2n)! \geq ((n+1)!)^n$

Show by induction that $2!4!6!...(2n)! \geq ((n+1)!)^n$ I stuck at $((n+1)!)^n (2(n+1))! \geq ((n+1+1)!)^{n+1}$, but cant progress to next step It will be great in someone can demonstrate how to ...
1
vote
3answers
33 views

Suppose that R and S are reflexive relations on a set A. Show that R-S is irreflexive.

Suppose that R and S are reflexive relations on a set A. Show that R - S is irreflexive, i.e., $$\forall x \in A, (x,x) \notin R\setminus S$$ We have: $$\forall r\in R, (r,r) \in R\\ \forall s\in ...
0
votes
2answers
33 views

Number of ways to color a sequence of squares so that no two black squares are adjacent

A sequence of squares may be colored so that each square is black or white. Let $S_n$ be the number of ways of coloring the sequence so that no two black squares are adjacent. Find a recursive ...
0
votes
1answer
15 views

Construct equivalence classes for a relation R

Define relation R as follows: xRy if x and y are bit strings with |x| >= 2 and |y| >= 2 such that x and y agree in their first two bits. Show that R is an equivalence relation. Construct the ...
0
votes
2answers
37 views

Graph theory possibilities

Is it possible to have a simple graph(no loops or parallel edges), connected, six vertices, six edges? Is it possible to have a graph, connected, ten vertices, nine edges, nontrivial circuit? Is it ...
-1
votes
1answer
25 views

How many string of three decimal digits…?

How many string of three decimal digits have exactly two digits that $4$s ? I know the answer will be $27$, but I don't know why... ?
2
votes
3answers
111 views

Find the last non-zero digit of $30^{2345}$

Find the last non-zero digit of $30^{2345}$ Source: Athena Healthcare Interview Questions
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
35 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
30 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
39 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
29 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
73 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
46 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 ...