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

1
vote
0answers
10 views

Distribution of distinct object problem

So i was given this question. How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room? So i asked this ...
0
votes
1answer
18 views

How can I find the maximum/minimum and maximal/minimal elements of a poset?

My teacher has given us really unclear definitions for all these terms, and now I have this assignment due where I have to find the maximum, minimum, and maximal/minimal elements of this poset: ...
3
votes
3answers
123 views

How many solutions for equation with simple restrictions

I'm working on an assignment in which I have to count the number of solutions for this particular equation: $$x_1+x_2+x_3+x_4=20$$for non negative integers with $x_1<8 $ and $x_2<6$ I'm aware ...
0
votes
1answer
13 views

Determining Whether or not a complex graph is bipartition?

So I asked a question earlier similar to this, and the solution made sense; however, the graph was very simple with only five vertices. If the graph is more complex like this one then how would you ...
0
votes
1answer
22 views

Algebraically transform logic expression

Algebraically transform: $\neg \forall x(P(x) \wedge Q(y) \implies \exists zR(z))$ to $\exists x\forall z(P(x) \wedge Q(y) \wedge \neg R(z))$ Justify each step with one or more ...
2
votes
2answers
47 views

How do I deal with a floor function is a system of equations?

How would one solve an equation with a floor function in it: \begin{cases} y=12(x-\lfloor x \rfloor) \\ x=12(y-\lfloor y \rfloor) \end{cases} Maybe an algebraic method could be used?
0
votes
0answers
20 views

License Plate Permutations

A state has changed its license plate numbering system for the three largest counties. Before the change, each plate had the number 1, 2, or 3, followed by either one or two letters, followed by 3 ...
1
vote
0answers
17 views

Determine whether or not $∀x[p(x) → q(x)]$ and $[∀xp(x)] → [∀xq(x)]$ are logically equivalent.

Determine whether or not $∀x[p(x) → q(x)]$ and $[∀xp(x)] → [∀xq(x)]$ are logically equivalent. I believe that they are not equivalent, but that is just an assumption. I am not sure how to go ...
0
votes
2answers
39 views

How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear?

So i was given this question. How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear? My solution below (not sure if correct) Let $A_i$ = set ...
5
votes
1answer
85 views

Why isn't finite calculus more popular?

I'm reading through Concrete Math, and learning about finite calculus. I've never heard of it anywhere else, and a Google search found very few relevant sources. It seems to me an incredibly powerful ...
0
votes
2answers
48 views

Prove or disprove: For non-negative integers $m$ and $n$, $m!n! = (mn)!$

I have rewritten the question as "If $m$ and $n$ are non-negative integers, then $m!n!$ = $(mn)!$" Here is my current attempt. I am not sure if I am on the right path. Proof. Let $m$ and $n$ be ...
1
vote
1answer
39 views

How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room?

So I was given this question. How many ways are there to place $10$ distinct people within $3$ distinct rooms with exactly $5$ people in the first room and $2$ people in the second room? I have ...
1
vote
1answer
39 views

Discrete Mathematics - Perfect square proof with non-constructive approach. [on hold]

The questions reads the following: Prove that either $2 * 10^{500} + 15$ or $2 * 10^{500} + 16$ is not a perfect square using the non-constructive approach.
2
votes
1answer
26 views

Determining Whether or not a graph is bipartition?

So I have been trying to do research on this online, and all I see are a bunch of graphs with multicolored dots, and telling me to use those to determine if the graph is bipartition. The ones in the ...
-2
votes
1answer
24 views

Discrete Math Sequences (Graph or No Graph) [on hold]

Determine if there exists a graph whose degree sequence is the one specified. Draw a graph, or explain why no graph exists. The sequence is 5,4,3,2,1,1
-1
votes
2answers
45 views

Number of words of length $n$ on the alphabet $a,b,c$ recurrence. [on hold]

Let $a_{n}$ be the number of words of length $n$ on the alphabet $a,b,c$ such that $b,c$ are not adjacent. What is the recurrence relation for $a_{n}$.
1
vote
2answers
36 views

Discrete math induction proof

I am trying to solve a induction proof and i got stuck at the end, some help would be great. This is the question and what i did so far: Statement: For all integers $n \geq 5$ we have $2^n \geq n^2$. ...
1
vote
0answers
20 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
3
votes
1answer
26 views

Inclusion exclusion principle questions i tried(doing it correct?)

$x_1+x_2+x_3\le10$ how many natural numbers solve this problem if $1\le x_1 \\ 2\le x_2 \\3\le x_3$ What i did: i created $y_1,y_2 , y_3$ so $\\ y_1=x_1-1 \\y_2=x_2-2\\ y_3=x_3 -3$ and then added ...
1
vote
1answer
33 views

How do I determine whether this relation is transitive?

I've been given this relation, and I'm supposed to determine whether it is transitive. I understand the definition of transitive (sort of, in theory) but I'm not sure how to put it in action here. ...
1
vote
3answers
61 views

How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ with restrictions

So i was Given this question. How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ $0 \leq x_i \leq 9$? I just assumed it would be ${21+4-4-1 \choose ...
2
votes
2answers
20 views

Why use C(n,r) instead of P(n,r) when considering how many strings can be formed in which a specific letter appears before another specific letter?

I am dealing with a problem in which I must determine how many strings can be formed by ordering the letters ABCDE subject to the conditions given. The condition that I am given is that A appears ...
1
vote
3answers
44 views

How do I go about determining whether a relation is reflexive?

I've been given these relations and I've been told to determine whether they're reflexive and I know the definition of reflexive but I don't really understand it. $R=\{(x,y)\ \in\ \mathbb Z^2\ |\ ...
1
vote
2answers
26 views

Let $B = {n \in \mathbb{Z} : n = 3j + 2; j \in \mathbb{Z}}, D = {n \in Z : n = 3j − 1; j \in \mathbb{Z}}$. Is $B = D$?

Let $B = {n \in \mathbb{Z} : n = 3j + 2; j \in \mathbb{Z}}, D = {n \in Z : n = 3j − 1; j \in \mathbb{Z}}$. Is $B = D$? How do I prove this? To me it looks to be true. But I don't know how to put it ...
0
votes
0answers
40 views

Definition of fixed point free relation

If we have such relation that for $\forall x$ $f(x)\ne x$ , how is it called in one word? I can come up with only "graph of this function is not a straight line:)" Thank you
-5
votes
2answers
59 views

Given any 40 people, at least four of them were born in the same month of the year [on hold]

Given any 40 people, at least four of them were born in the same month of the year. Why is this true?
2
votes
2answers
41 views

Write expressions w/out quantifiers (convert to AND/OR expressions)

A universe contains the three individuals $a,b$, and $c$. For these individuals, a predicate $Q(x,y)$ is define, and its truth values are given by the following table \begin{array}{c|ccc} ...
0
votes
1answer
22 views

How to prove that $(A \cup B) - C = (A - C) \cap (B - C)$ [on hold]

If true, prove else provide a counter example. This is a homework question and I cant figure it out. Please help.
-1
votes
2answers
43 views

Discrete math, proving sets [on hold]

I am studying discrete math and i stumbled upon a proof i couldnt proove, can someone help me with this one? "Assume that A,B,C are three sets with no elements in all three sets. Assume further that ...
1
vote
0answers
55 views

Mean distance of random points on a rectangular grid

I have a $N\times N$ grid of side $L$. Each gridpoint can be black or white and a ratio $r$ of the points is black. I want to predict the mean distance between two black points. The most appropriate ...
0
votes
1answer
42 views

Can someone explain and help me with propositional logic in discrete math?

Can someone explain to me in detail how to complete these two problems without using truth tables? I'm having a hard time understanding what to do. I know that I'm supposed to use the laws, etc. But ...
4
votes
2answers
66 views

Finding limit via Sandwich Theorem: $\lim_{n\to\infty} n\sum_{n+1}^{2n} \frac{1}{i^2}$

Question: Use the Sandwich Theorem to find $$\lim_{n\to ∞} n\sum_{n+1}^{2n} \frac{1}{i^2}$$ Appreciate any guidance.
-1
votes
4answers
68 views

Summation for $\sum\limits^5_{i=2}\:\left(3i\:-\:5\right)$

I know that the closed form of $\sum\limits^n_{k=1}\:k=\frac{n(n+1)}{2}$ But I'm not sure what the closed form for $\sum\limits^5_{i=2}\:\left(3i\:-\:5\right)$ would be. Any push in the right ...
1
vote
2answers
34 views

Simple expression for $\sum_{k=1}^{n-1}\:\frac{1}{k\left(k+1\right)}$

I know that $\:\:\frac{1}{k\left(k+1\right)}\:\:\:\:=\:\frac{1}{k}\:-\:\frac{1}{k+1}\:$ And that $\sum_{k=1}^{n-1}\:k$ $= \frac{n(n-1)}{2}$ But I'm not completely sure how to turn ...
-1
votes
2answers
24 views

How can I further simplify $(B^c ∩ (B ∩ A)^c)^c$

I'm pretty sure this is equal to B, but I'm not sure how to go about reducing this step by step. Could I use the double negative law to eliminate the complements? I'm not positive if that would work ...
0
votes
3answers
22 views

Finding the complement of a set

I have the sets A, B, and C: $A = \{x\in\mathbb{Z} | 2 < x < 5\}$ $B = \{x\in\mathbb{Z} | 4 ≤ x ≤ 7\}$ $C = \{x\in\mathbb{Z} | 2 ≤x< 6\}$ What is $B ∩ C^c$? If the complement of C is all ...
0
votes
1answer
11 views

Finding the smallest exponent $k$ for a non-cyclic permutation $\sigma$, so that $\sigma^k = id$.

What I am aware of (1) A cyclic permutation is a permutation that consists of a single nontrivial cycle (cycle of length $> 1$). Let $k$ be the length of the cyclic permutation $\tau$. Therefore ...
1
vote
1answer
37 views

Why is this predicate false?

I am stumped at my professor's answer to this predicate logic. all x and y are natural numbers. ∃y∃x(x >= y) I think it is true, since there is a pair ...
2
votes
2answers
44 views

Prove by contradiction Irrational number

I Need to prove this by contradiction : If $a$ is Irrational then $\frac{2a-3}{2a+3}$ is Irrational. I did: Iff $p$ is Irrational, then $\frac{2a-3}{2a+3}$ is Rational and a Rational number can ...
-4
votes
1answer
68 views

Difficuly in proving inequality [on hold]

I have trouble solving this inequality can some one please give solution to this? $$\left( n+\frac{1}{n} \right) ^{n+1} > e$$
7
votes
9answers
2k views

What do we actually prove using induction theorem?

Here is the picture of the page of the book, I am reading: $$P_k: \qquad 1+3+5+\dots+(2k-1)=k^2$$ Now we want to show that this assumption implies that $P_{k+1}$ is also a true statement: ...
0
votes
2answers
63 views

How do I calculate $\sum_{k=1}^{33}\binom{33}{k} k$

I started studying about binom's and sums, How do I calculate $$\sum_{k=0}^{33}\binom{33}{k} k$$ Note: I do know that it is $\binom{33}0\cdot0 + \binom{33}1 \cdot 1 + ... + \binom{33}{33} \cdot 33$, ...
0
votes
1answer
17 views

Chance of drawing 4 red marbles out of a big bag.

In a bag with an infinite number of marbles, where a third are red, a third are green and a third are blue. Given that you pick $10$ marbles, of which $3$ are blue, what are the chances of picking $4$ ...
-1
votes
5answers
79 views

Is it accurate to say that multiplication of two integers yields an integer?

I am reading a book in discrete mathematics and it assumes that a multiplication of two integers yields an integer. Although that this book's saying is justifiable since the book is making an ...
-1
votes
1answer
29 views

If $A⊆B∪C$ and $B⊆A∩C$, then disprove that $A≠B$ [on hold]

If $A⊆B∪C$ and $B⊆A∩C$, then disprove that $A≠B$ Need really quick help on this. I am really stuck on this, and I have a quiz on it tomorrow morning. Please help!
-1
votes
0answers
24 views

How many different ways can $6$ chocolate bars be selected in such a way that each type is chosen at least once? [on hold]

In a shop five different type of chocolates are sold. How many different ways can $6$ chocolate bars be selected in such a way that each type is chosen at least once? I know the answer is $5$. ...
-3
votes
1answer
14 views

Proving or disproving set statements. [on hold]

I'm not sure how to approach proving or disproving these statements. I don't know where to begin, or more specifically, what it's asking me to prove or disprove. If $ A \cap B \subseteq C$ and $A ...
1
vote
7answers
68 views

Proving $\frac{n}{n+1} < \frac{n+1}{n+2}$ by induction?

I have the inequality $\frac{n}{n+1} < \frac{n+1}{n+2}$ I'm not sure how to go about proving it. I've started by testing with n = 1, which results in $\frac{1}{2} < \frac{2}{3}$ which is true ...
0
votes
1answer
28 views

How can i find equation that does not have a solution?

An operation $*$ is defined on the set $\Bbb{Z} \times \Bbb{Z}$, ie. the set containing all pairs of integers by: $$ (u,v) * (x,y)=(u+x,v \cdot y) $$ if $(\Bbb{Z} \times \Bbb{Z}, *)$ is not a group ...
1
vote
1answer
37 views

Discrete math: What is the difference between false and inverse in conditional statemensts?

Let's say there is this conditional statement: If I am in Paris, then I am in France. So, p = 'I am in Paris', and q = 'I am in France' I do not understand when p and q are false, how would that ...