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
17 views

Why is the unique readability of wff's important?

I am reading Classical Mathematical Logic by Epstein. The author defines: $L(\neg, \rightarrow, \vee, \wedge, p_0, p_1, ...)$ i. For each $i=0, 1, 2, ..., (p_i)$ is an atomic wff, to which we ...
0
votes
0answers
4 views

PCA for antisymmetric matrix

PCA (Principle Component Analysis) is often used to convert a symmetric matrix to lower dimension one. My question is whether there is semiliar method for antisymmetric matrix? As we known, the ...
0
votes
2answers
29 views

Set theory: how to interpret multiple quantifiers

How does one interpret this ZFC Union axiom? I can't quite understand what is meant after "There exists some elements y for all elements z"? I'm also wondering if the x is a typo. $\exists y \...
1
vote
2answers
40 views

How to formally prove whether this function is onto or not?$ K(x) = x^ 2$ where $x \ge 0$.

$K(x) = x^2.$ The domain and range of this function comprise of non-negative real numbers. If it were real numbers instead of "non-negative" real numbers, then it seems easy to prove it by ...
1
vote
1answer
7 views

Spanning 2-regular subgraphs in even regular graphs.

Theorem: Every regular graph of positive even degree has a spanning 2-regular subgraph. This was taken from Corollary 5.10 of ETH Zurich's notes on graph theory. The proof constructs a Eulerian tour,...
2
votes
4answers
58 views

Probability that the second throw of a fair die exceeds the first

A player throws an ordinary die and records the score $A$. The player then throws the die again and again records the score, $B$. if $B>A$ then we set a score for this player. What is the ...
4
votes
3answers
3k views

Whats the difference between Antisymmetric and reflexive? (Set Theory/Discrete math)

Antisymmetric: $\forall x\forall y[ ((x,y)\in R\land (y, x) \in R) \to x= y]$ reflexive: $\forall x[x∈A\to (x, x)\in R]$ What really is the difference between the two? Wouldn't all antisymmetric ...
4
votes
1answer
1k views

Discrete Laplace transform

Yesterday ago I was reading how the Laplace Transform can be interpreted as the continuous analog of the discrete functional dependance of the power series $$f(x) = \sum a(n) x^n$$ This is to say, $$L\...
5
votes
5answers
7k views

What is the difference between discrete and continuous mathematics?

I am studying computer science and this has me absolutely flummoxed. The definition I can find is that discrete data is countable and that continuous is uncountable. Examples are given stating that ...
0
votes
1answer
33 views

Prove that in a tree #leaves + #nodes of degree 2 $\geq \frac{n}{2}$

I am trying to solve the following problem: Let $T = (V,E)$ be a Tree with $n = |V|$ nodes. Let $b$ denote the number of leaves and $z$ the number of nodes with degree $2$. I want to show that $$ ...
-1
votes
0answers
12 views

How many vertices will the following graph have?

35 edges Degree at least 3 Thought n(3+) = 70 5n=70 n=14 For an integer result. What if degrees range from 3 to something?
0
votes
0answers
22 views

Choosing values in a strong induction

The sequence s0,s1,s2... is defined by s0=1 and for all integers n>0, $s(n)=s(⌊n/2⌋)+s(⌊2n/5⌋) + n.$ Prove, using strong induction, that S(n) > 4n for all integers n>=3. To my knowledge, I only have ...
6
votes
1answer
76 views

Prime Factorization Question involving Product of Consecutive Terms

I came across this question while doing some research at an REU this summer. It was supposed to be just a small part of a larger proof, but we've been stumped on it for a while. I don't have much of a ...
0
votes
1answer
382 views

Suppose that A is a countable set. Show that the set B is also countable if there is an onto function f from A to B.

Is my logic correct/accepted? Let A be a countable set. Let f:A->B, surjective. $\exists$g:A->N, bijective. Using definition from 1. $\exists$h:N->B, surjective. $\therefore$B is countable by ...
2
votes
6answers
115 views

Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$

My question is: Prove by induction that $$3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$$ whenever $n$ is a nonnegative integer. I'm stuck at the basis step. If I ...
6
votes
4answers
161 views

Disprove that “if $p$ is a prime number, then $2^p-1$ is also a prime number”?

We can see manually that $2^p-1$ is not prime. As $2047$ is not a prime. $2^{11} = 2048$. But I'm unable to figure out a formal way of disproving the statement.
0
votes
1answer
32 views

Need help understanding a proof (Bipartite Graph)

I was reading lecture notes of graphs(from MIT 6042) and am having trouble understanding this proof: I can't understand ...
0
votes
1answer
27 views

venn diagram category help.

For each list of categories, draw a venn diagram that shows the relationship among the categories. One of the categories describe the universal set, and the others describe the various loops inside ...
0
votes
1answer
905 views

Disjunctive normal form (BOTH dnf and cnf) example help

T or ( not x and y ) or ( x and y ) In class we went over examples of how many things can be both DNF and CNF... eg. (not z) or y can be thought of as both (not z) or y .... dnf ((not z) or y)...
0
votes
0answers
30 views

Prooving reflexivity and antisymmetry [on hold]

Good day. I have to prove reflexivity and antisymmetry for integers a and b. I understand that reflexivity is a≤a and antisymmetry is if a≤b and b≤a then a=b. However, aside from stating simple ...
0
votes
1answer
24 views

Counting the number of Eulerian trails in a connected, directed graph

I can't find anything about this online, and I'm beginning to suspect it's a hard problem. I know that counting the number of circuits is #P-complete, but I don't need the number of circuits; I need ...
0
votes
0answers
22 views

Disjoint subset problem

Show there exists two disjoint subset A, B of $\{1, 2, 3, \cdots , 10\} = [10]$ such that $$s(A) = \sum_{i\in A}i = \sum_{i\in B}i=s(B)$$ namely, the sum of elements in A equals that of B. Really not ...
1
vote
1answer
22 views

Distribute 20 million $ among 4 companies with some constraints

20 million is to be invested in 4 companies A, B, C, D. The minimum amount for investments are 1, 2, 3, 4 million respectively. How many different investment strategies are available if An ...
3
votes
1answer
38 views

In how many ways we can arrange 12 people in a row if 5 men are constrained to sit next to each other together?

In how many ways we can arrange $12$ people in a row if $5$ are men and they must sit next to each other? My approach I consider $5$ men as one entity and so now there are $8$ people to be seated ...
0
votes
2answers
56 views

Prove that ∀n≥1, (1/(1⋅3))+(1/(3⋅5))+(1/(5⋅7))+…+(1/(2n−1)(2n+1)) =( n/(2n+1))| [on hold]

Prove that ∀n≥1, (1/(1⋅3))+(1/(3⋅5))+(1/(5⋅7))+...+(1/(2n−1)(2n+1)) =( n/(2n+1))| So, I understand that the proof must display that (1/(2n−1)(2n+1) is equivalent to (1/(2n−1)(2n+1). Would I solve ...
1
vote
1answer
21 views

Spanning trees of the complete graph minus two edges

Here is the following problem: What two edges should one remove from the complete graph $K_n$ so that the number of the spanning trees of the new graph is as small as possible? One can solve this ...
0
votes
2answers
23 views

Bijective/Injective function mapping

I have a quick question about bijective functions. Let's say I want a function that maps $$f:(0,1] \rightarrow [0,\infty)$$ I can say $$f(x) = 1- \frac1x$$ right? And if I want an injective ...
1
vote
1answer
388 views

Sums of consecutive odd integers, positive or negative

While supervising a student competition, my colleague and I ran across an interesting problem. Deobfuscated, it boils down to this Given a limit value $M$, which integers in the range $1,\dotsc,M-...
2
votes
1answer
58 views

probability of rank of a number

Suppose I have 10 sample means. I want to find the probability of rank of the population means using sample means. Therefore, I want to perform two experiments. First experiment: I pick one of the ...
3
votes
3answers
273 views

Explanation: In how many ways can 6 things be divided between 2 people?

I have a question in a book which says in how many ways can 6 different things be divided between 2 boys and (my understanding of) the explanation goes something along the lines of: Items: 1 1 1 1 1 ...
0
votes
1answer
26 views

Predicate Calculus help

Working on predicate calculus this week, and was hoping I've got these correct, but I'm sure I've made some mistakes for sure.. All programmers enjoy discrete structures not all integers are ...
1
vote
2answers
59 views

Proportionally Distributing $N$ items across $B$ bins.

My question is similar to this: Proportional Distribution My problem follows: I have $N$ items that cannot be broken up into fractional components, but should be distributed across $B$ bins where ...
0
votes
0answers
23 views

Calculus for Proving Properties of Discrete Objects

I posted a question earlier about a proof in graph theory I was trying to figure out. In my attempt I used Calculus to prove a part of the theorem. In the comments people kept saying how you shouldn't ...
3
votes
2answers
104 views

What are “words”?

Related but not duplicate. I am reading Classical Mathematical Logic by Richard L. Epstein, page $3$: B. Types When we reason together, we assume that words will continue to be used in the ...
-1
votes
0answers
16 views

recursive definition for two mutually exclusive events [on hold]

How do we write recursive definitions for two mutually exclusive events ? Can anyone explain with some examples as how do we come up with solutions in case of exclusive events ? SO finally i add ...
0
votes
1answer
20 views

Showing properties of a function and its inverse image

I tried proving the following question but did not get too far. Let $\ f:A \to B$ be a function and $\ f^{-1}(Y)$ be the inverse image of $\ Y\subseteq B$ on $\ f$. Consider the following ...
0
votes
0answers
26 views

What algebra of propositions will prove the obvious?

I am trying to use the algebra of propositions to prove the following. It is obviously true but I am stumped as to what algebra of proposition to use to show a sound mathematical explanation as a ...
0
votes
2answers
29 views

If $f:A\to P(A)$, show that $Z_f := \{x \in A | x \notin f(x)\}$ is not in the Image of $f$

How can I prove that for a function $f: A \to P(A)$, $Z_f := \{x \in A | x \notin f(x)\}$ is not in the Image of f? It can be shown using Russel's Paradox, but i have really no clue on how to start. ...
1
vote
2answers
34 views

Simplifying $(A \cup E) \cup E$.

For example $$(A^c\cap B^c)^c\cup E$$ First of all, De Morgan is definitely a must to simply this to $$\big((A^c)^c\cup(E^c)^c\big)\cup E$$ Then double negation to remove the double complement to ...
0
votes
2answers
25 views

Proving set theory subsets using element argument

How do you even prove a set theory subset statement using element argument? I simply just can't find any relevance to the question with the notes i was studying. Any guidance would be much ...
0
votes
2answers
27 views

proving set theory union statements

I just started learning set theory in discrete mathematics and it's soon enough before i get stuck at my first supplementary question. Prove $( A \cap B) \cup ( A \cap B^c ) = A$ How do i even ...
-1
votes
1answer
23 views

A question in set theory about intersection of two groups.

I've reached the answer, that Cn = to all prime numbers, but i really didnt know how to put it on paper and how to prove its right. I would thank your help.(question below) Question
1
vote
4answers
71 views

what does “a set of sets that are not members of themselves” of Russell’s Paradox mean

Russell’s Paradox begins with a statement of "Let $R$ be the set of sets that are not members of themselves", i.e. $R=\{S\mid S\notin S\}$. I'm a little bit confused with the statement, for example, ...
0
votes
0answers
27 views

When can $S \times S$ be partitioned by triples?

Let $S$ be a finite set of $n$ elements. For which $n$ can the Cartesian Product $S\times S$ be partitioned in such a way that elements of the partition are of one of the following forms: $\{(a,b), (...
2
votes
2answers
40 views

Algorithm for multiplying infinite decimals?

What is the (best) algorithm for multiplying two real numbers based on their decimal expansions? Obviously the algorithm can't be completed but I mean an algorithm that will successively approximate ...
2
votes
0answers
39 views

Eigenvalue perturbation of singular matrix

Consider a Hermitian matrix $\mathbf{A_0} \in \mathbb{C}^{N \times N}$ with one singularity, i.e. its eigenvalues in increasing order are: \begin{equation} 0 < \lambda_2 \leq \lambda_3 \leq \cdots \...
0
votes
0answers
16 views

How to draw prefix and postfix binary tree?

I have drawn these two binary trees. The ordered set of numbers is [-9, -5, 0, 1, 5, 7, 8, 10, 11] The first one is in prefix order and the second is in postfix order, but I'm not sure if my ...
0
votes
0answers
16 views

Discretization of an EXP function

I have a function in the form of $V = a[1-exp(t-t_0)]$ and $V_0=0$. I'm using this formula in discrete system and I need to discretize this formula and solve it every T seconds and get the $V_{k+1}$ ...
0
votes
1answer
398 views

Growth of functions (Discrete math)

a) Show that $ \frac{x^3 + 2x}{2x+1} \; is \; O(x^2) $ b) Find witnesses $ C \; and\; K $ My answer was : $ x^3 + 2x \le c(x^2)(2x+1) $ $ x^3 \le c(x^2)(2x+1) , \; when \;c=1 , x>1 $ $ 2x \le ...
0
votes
0answers
16 views

oblath's result in perfect powers

What do you mean by this statement? Obl\'ath proved that the only perfect powers all of whose digits are equal to a fixed one $ a \neq 1$ in decimal representation are 4, 8 and 9. This is equivalent ...