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

learn more… | top users | synonyms

2
votes
1answer
44 views

P(A) $\subset$ P(B) implies A $\subset $ B proof or disproof. [duplicate]

P(A) $\subset$ P(B) implies A $\subset $ B proof or disproof. I have a strange feeling this is false but I do not know. Something to do with P(A) $\subset$ P(B) seems strange since P(B) is itself a ...
1
vote
2answers
74 views

Pizza Topping combinations

I run a pizza joint in Seattle, USA, and would love to know how many different combinations of pie we can create. We have: 23 toppings 12 "house" pizzas 2 sizes (medium and large) two different ...
0
votes
1answer
27 views

Gradient equation problem

In gradient equations, does the sum of the partial derivatives have to be equal to zero or each derivatives has to be zero? As I have just started to understand gradient equations, if my question is ...
4
votes
1answer
58 views

What is the history of this theorem about the finite sum of a polynomial?

I discovered and proved the following theorem back in high school, and have waited patiently to hear something about throughout my college career (which is nearing it's end, hope to have finished my ...
1
vote
2answers
36 views

Discrete Math: Counting Problem with balls

A bowl contains 10 red balls and 10 blue balls.A woman selects balls at random without looking at them. a) How many balls must she select to be sure of having at least three balls of the same ...
0
votes
0answers
33 views

I have a test and I am currently doing revision, however the topics that I am asked to revise on are a bit vague

I have a test and I am currently doing revision, however the topics that I am asked to revise on are a bit vague and finding appropriate revision sites seems to be a bit of a problem here. Can anyone ...
0
votes
1answer
40 views

Number of ways to choose two disjoint subsets of a set

Let $A$ be a set of $n$ elements. Then, in how many ways, can we choose an ordered pair $(B,C)$, where $B,C$ are disjoint subsets of $A$? Let A={1}, then B can be {phi} and C can be {1}. So, one ...
5
votes
2answers
81 views

generating function for binary strings that don't contain $00100$ as a substring?

On an alphabet $\{0, 1\}$, what's the generating function for the set of strings that don't contain $00100$ as a substring? I've tried writing the set of strings that don't contain $00100$ in terms of ...
0
votes
1answer
41 views

Prove: same cardinality [closed]

I have a question.Here is the statement. f is bijective function, and have Z+ (positive integer) and Z have the same cardinality. How can I prove this statement? I already know that Z+ and Z have the ...
1
vote
1answer
25 views

Discrete Mathematics Proof odd degree

Show that for a graph letting r be the number of vertices with odd degree( with an odd number of edges) show that r is even. Is that about Euler's criterion or is there any other solution?
6
votes
4answers
96 views

Pigeon Hole. 80 numbered balls

We have $80$ numbered balls(From $1$ to 80).Among which are $45$ blue and $35$ orange. Prove that at least two blue balls differ by $9$. For example $13$ and $22$ or $69$ and $78$. So they can differ ...
1
vote
1answer
54 views

Prove $n! \geq n^2$ for $n \geq 4$

I am working through a discrete math course, and have come upon a question that I don't understand how the solution was obtained. The question is, prove $n! \geq n^2$ Hypothesis: $p(n): n! \geq n^2, ...
2
votes
2answers
65 views

Pigeon hole principle with sum of 5 integers

Prove that from 17 different integers you can always choose 5 so the sum will be divisible by 5. I tried with positive,negative numbers. Even, odd numbers etc but can't find the solution. Any ...
1
vote
0answers
16 views

Counting Surjective functions without using the formula

Ok, so suppose I have a Domain set A with 5 elements {1,2,3,4,5} that maps to CoDomain set B with 3 elements {A,B,C} How do I find how many surjective functions there are? My intuition was to take ...
2
votes
5answers
57 views

Prove that $A\setminus (B\setminus C) = (A\setminus B) \cup (A\setminus C^c)$ for sets $A,\ B,\ C$ in some Universal Set $U$.

I'm working on this proof for some students I am tutoring and I've gotten a little stuck. I want to show them how to do a proof in complete, extravagant detail and get them familiar with ''element ...
2
votes
2answers
47 views

Prove that $f(m,n)=(m+2n, m-n)$ is 1-1 and Onto. The domain and co-domain are $\mathbb R\times \mathbb R$

So I know how to prove injectivity $f(x)=f(y)\Rightarrow x=y$ and surjectivity but am not sure how to go about it in this case since there are multi variables.
0
votes
5answers
64 views

How do I prove that $\{3k+2 : k \in \mathbb{Z}\} = \{3k-1 : k \in \mathbb{Z}\}$?

I have to prove that $$\{3k+2 : k \in \mathbb{Z}\} = \{3k-1 : k \in \mathbb{Z}\}$$ I don't want anyone to prove it for me but to suggest a way to start it. I have no idea at this point which method ...
3
votes
6answers
99 views

Prove that $(B - A) \cup (C - A) = (B \cup C) - A$ by showing that each side is a subset of the opposite side.

A big problem is that I never even know where to start with proofs. Then I panic and get absolutely nowhere. To reiterate: Prove that $(B - A) \cup (C - A) = (B \cup C) - A$ by showing that each side ...
1
vote
2answers
32 views

Sets, subset relations, and elements in a set

I can't quite get a handle on subsets. Are the following true or false? $ \{\{\emptyset\}\}\subset\{\emptyset,\{\emptyset\}\} $ $\{\{\emptyset\}\}\subset\{\{\emptyset\},\{\emptyset\}\}$ $\{x\} ...
0
votes
0answers
33 views

Calculate number of combinations & permutations for job assignment to machines

There are 12 machines (M). Each machine can execute for 20 slot (S) of time per session. We have 8 jobs (J) to be done. Each job requires 2 continuous slots (T). There is a fixed timeframe between the ...
1
vote
1answer
79 views

what is the cardinality of each of these sets?

I am confused on these questions I feel like that are too easy. I just need to find the cardinality of each of the 3 problems. I believe that the first one and third one is a zero with a slash through ...
1
vote
2answers
116 views

Statistics-Math-Probability

An urn is filled with 10 green balls, 4 red balls, and 2 orange balls. Three balls are selected without replacement. Calculate the following probabilities: (a) P(at least one ball is red) I think ...
0
votes
2answers
33 views

Proving convergence to a certain limit

Suppose that the sequence $(X_n)$ has the following property: there is a real number $a$ such that there are infinitely many $n$ for which $X_n = a$. Prove that, if $X_n$ converges at all, its limit ...
0
votes
1answer
67 views

Independence of flipping a coin

I have a coin that lands on heads with probability $N$ and tails with probability $1-N$. How do I explain the outcomes of the successive flips of the coin are independent of each other, knowing only ...
-1
votes
1answer
18 views

Problem involving Integers and Proof

Compute the following sums: a) 1 + 2 + 3 + ... + n; b) 1 + 3 + 5 + ... + 2n-1; c) 2 + 5 + 8 + ... + 3n-1 d) a + (a+d) + (a+2d) + ... + (a+(n-1)d) I have found that the sum of a) = -1/12. I have no ...
0
votes
1answer
54 views

Sample space of possible outcomes for a knockout tournament

I would like to confirm if my answer is correct for the following question: A conventional knock-out tournament begins with $2^n$ competitors and has $n$ rounds. There are no play-offs for the ...
1
vote
3answers
64 views

For the Fibonacci sequence prove that $\sum_{i=1}^n F_i= F_{n+2} - 1$

For the Fibonacci sequence $F_1=F_2=1$, $F_{n+2}=F_n+F_{n+1}$, prove that $$\sum_{i=1}^n F_i= F_{n+2} - 1$$ for $n\ge 1$. I don't quite know how to approach this problem. Can someone help and ...
1
vote
2answers
67 views

Find a closed form for the sum $∑(x^3 - 2x)$ from $x=1$ to any number $n$

Find a closed form for the sum $∑(x^3 - 2x)$ from $x=1$ to any number $n$. Can someone explain to me what a closed form is and how to approach this problem?
4
votes
2answers
188 views

Expected Value of Local Maxima and Local Minima

Recently I came across this question: Given a random permutation of integers 1, 2, 3, …, n with a discrete, uniform distribution, find the expected number of local maxima. (A number is a local maxima ...
1
vote
1answer
76 views

Use generating functions to determine how many four-element subsets of S = {1,2,3,4,…15} contain no consecutive integers?

Use generating functions to determine how many four-element subsets of $$S = {1,2,3,4,...15}$$ contain no consecutive integers? How do you approach this problem?
0
votes
1answer
28 views

Circuits using KVL and Voltage Divison

In the image below, the top is the problem and the bottom circuit is my modified drawing. I'm unsure on where to start solving it. I used Ohm's Law to find $40$ V and then used Voltage Division to ...
4
votes
1answer
43 views

Counting Relation Functions

I have a set $S = \{ 1,2,3,4,5,6,7 \} $ I know that the number of bijective functions $S\rightarrow S$ without any restrictions is $7!$, but how can I count the number of bijective functions $ \phi : ...
1
vote
0answers
35 views

discrete math/ probability question

We have two sets of numbers: $v_1 \cdots v_N$ and $v_1' \cdots v_N'$. $v_i \geq 0 \forall i $ and $v'_i \geq 0 \forall i$ We know two things about them: $\sum v_i = \sum v_i' = 1 $ and ...
0
votes
1answer
36 views

Logical form of this statement?

In logical form, how would you express : Take any two fractions, add them together, and the result will be an integer
0
votes
1answer
27 views

Proving set identities

Are these sets identical? How do you disprove or approve this set identity? Is it saying $A - B$ and $A\text{ or }B$ is equal to nothing? little confused, help would be appreciated.
0
votes
2answers
28 views

Math Induction to prove recursion

This is a problem from a practice test. I don't understand how the answer was produced using math induction. And yes, math induction is required for this problem. Define a function f: $\mathbb{N}$ ...
3
votes
2answers
102 views

I'm not understanding what a reflexive set is

I'm not quite getting the concept of a reflexive set in my discrete math class. I think I understand that a reflexive set is the product of set $\mathit{A} \times \mathit{A}$ the idea that we're ...
0
votes
0answers
14 views

Transitive closure of Relation

We know that $$R^* = R \cup R^1 \cup R^2 \cup \cdots \cup R^n$$ $\text{Where R is a relation from set A with n elements}$ My problem is, why we had limited to $R^n$ ? There can be more paths of ...
2
votes
1answer
35 views

Why do we use another variable in the inductive step of mathematical induction?

I tried to find this answer on google and stackexchange but did not find any clue. Why is it that we use another variable like $k$ in $P(k)$ rather than the original $P(n)$ in the inductive step of ...
2
votes
1answer
48 views

Differentiation for least squares method?

Is there any reason that we use mathematical differentiation of least squares method for regression analysis? The theory say we use differentiation supposing the sum of errors is 0. I I don't really ...
-3
votes
1answer
53 views

Discrete Math Problems [closed]

Let $n =p^a$ for some prime $p$ and positive integer $a$. How many divisors does $n$ have? Let $n = p^a q^b$ for some primes $p$ and $q$, and positive integers $a$ and $b$. How many divisors ...
1
vote
3answers
141 views

Prove or disprove that if one root of a quadratic equation is rational, then the other root must be rational as well.

I'm taking an introduction to discrete math course and I'm having some trouble with this homework problem. I think we're supposed to assume that the coefficients are integers based on other examples ...
2
votes
3answers
184 views

Pigeonhole Principle -

Let $n$ be an odd integer and let $f$ be an $n$-permutation of length $n$. Show that the number \begin{equation}x = (1-f(1))\cdot(2-f(2))\cdot...(n-f(n))\end{equation} is even. I don't understand ...
0
votes
2answers
27 views

What's the maximum deviation from loan amortization

Suppose you have a loan with principle P and fixed interest rate i compounded daily. Suppose you make fixed payments every month, but not on the same day. The only constraint is that you make every ...
1
vote
2answers
35 views

Number of triangles in a Graph/Network

Given An undirected graph/Network, and its adjacency matrix A, and 1 (A column vector with all elements as 1). How do we represent the problem of finding the number of triangles in the network ...
0
votes
1answer
21 views

How Can This Antecedent Be Evaluated to True?

I've a couple of questions. From MIT notes: $\frac{NOT(P)\;IMPLIES\;NOT(Q)}{P\;IMPLIES\;Q}$ is not sound: if P is assigned T and Q is assigned F, then the antecedent is true and the ...
2
votes
1answer
87 views

Chromatic polynomial for a bipartite graph

I need to get the chromatic polynomial for the complete bipartite graph: $K_{2,3}$ Im using the Fundamental Reduction Theorem, and the picture below shows mi attempt to it. I omitted vertex names ...
1
vote
1answer
23 views

Is it possible to prove an argument is not satiable with equivalences?

I am trying to prove is this argument: (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) is satiable with equivalence. Is what I said below valid for this? (p ∨ q) ∧ (¬p ∨ q) ∧(p ∨ ¬q) ∧(¬p ∨ ¬q) q ∨ (p ∧ ¬p) ...
0
votes
1answer
64 views

Propositional Logic with rules of inference problem.

$$ \begin{array}{l} 1.\>\>\>\> (r ∧ ¬s) ∨ (q ∧ ¬s)\\ 2.\>\>\>\> ¬s → ((p ∧ r) → u)\\ 3.\>\>\>\> u → (s ∧ ¬t)\\ ...
1
vote
2answers
31 views

Intersections/Reunions of power sets

Let $P_i$ be the power set of $A_i=\{1,2,3,\cdots ,i\}$. What is: $$\bigcap_{i=1}^{n}(P_{i+1} - P_{i})$$ $$\bigcup_{i=1}^{n}(P_{i+1} - P_{i})$$ The problem asks you to find those two sets ...