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
0answers
6 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
1answer
17 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 ...
0
votes
0answers
14 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 ...
0
votes
0answers
9 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
1answer
15 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 ...
-1
votes
0answers
14 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
0answers
17 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
28 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. ...
0
votes
1answer
16 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
2answers
18 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 ...
1
vote
2answers
33 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 ...
-1
votes
1answer
18 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
0
votes
0answers
26 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), (...
3
votes
2answers
85 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 ...
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 ...
0
votes
2answers
26 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 ...
0
votes
0answers
14 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
15 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}$ ...
2
votes
0answers
35 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 \...
1
vote
4answers
63 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
15 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 ...
1
vote
0answers
48 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 ...
0
votes
2answers
25 views

How do I find the powerset of $A\cap B$?

$A = \{0,1\}$ $B = \{1,2\}$ My Working : $P(A\cap B)= P(\{\varnothing, \{1\}\}) = \{\varnothing,\{1\},\{\varnothing,\{1\}\}\}$ But the correct answer is $P(A\cap B)= \{\varnothing , \{1\}\}$.
1
vote
0answers
16 views

Derivative of quadratic form involving singularity

This might be a silly question, but i have been really curious about the following: Consider the following function seen thru a single variable, say $\alpha$: \begin{equation} f(\alpha) = \mathbf{x}^...
1
vote
2answers
41 views
+50

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 ...
-1
votes
0answers
26 views

Bound on binomial summation

The bound for $\sum_{i=1}^n\binom{n}{i}2^i$ is $O(3^n)$ but what will be the bound for $\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i$. Any idea how should I proceed.
0
votes
4answers
37 views

Let $R$ be a relation on a set $A$. Show that if $R \circ R \subseteq R$, then $R$ is transitive

On a recent quiz I encountered the problem: Let $R$ be a relation on a set $A$. Show that if $R \circ R \subseteq R$, then $R$ is transitive. I gave the following answer: Assuming $R$ is a relation ...
0
votes
0answers
27 views

How to remap continued fractions from $\mathbb{R}$ to a discrete set of integers

Assuming that I have a continuous fraction \begin{equation} x = a_0 + k_1 \cfrac{x_1}{a_1 + k_2 \cfrac{x_2}{a_2 + k_3 \cfrac{x_3}{a_3 + k_4 \cfrac{x_4}{a_4 \ddots } } } } \end{...
0
votes
1answer
17 views

How to read partial ordering in a set?

Let $X$ be a partially ordered set with partial order $\preceq$. Then how can we read $x\preceq y$. Is it $x$ less than or equal l to $y$.?
0
votes
0answers
20 views

A graph is said to be in Hamiltonian cycle. Then the travelling salesman problem is? [on hold]

The graph ‘g’ with vertices {A, B, C, D, E } is said to be in Hamiltonian cycle. Then the travelling salesman problem is Heuristic NP-complete minimal spanning tree triangle inequality My ...
0
votes
1answer
21 views

Having trouble proving Inequality [duplicate]

I am having trouble proving this inequality: $2ab\leq a^2+b^2$ I can transpose the equation and change around signs. But I am not sure If I need to use k+1 here or just prove the inequality. In ...
0
votes
0answers
19 views

Which of the statements are true for travelling sales man problem of a greedy algorithm [on hold]

Which of the statements are true for travelling sales man problem of a greedy algorithm work’s for in complete graph also Krushkal’s algorithm gives a sub-optional solution in general Both $(1)$ and ...
0
votes
0answers
7 views

Evaluating scalar functions of vectors in multidimensional simplices part II

In this question we want to generalize the result from Evaluating scalar functions of vectors in multidimensional simplices. . To be precise we consider a following multivariate sum: \begin{equation} {...
0
votes
2answers
29 views

Solving a nonlinear equation $\sum_{z=0}^{s} \frac{(\lambda(l-x))^z}{z!} e^{-\lambda(l-x)}=p$

I would appreciate it if someone helps me with solving the following equation. Suppose $\lambda,l \in R^+$, $p\in[0,1]$, and $s\in N_{0}$. How can we find an $x\in [0,l]$, which satisfies the ...
1
vote
1answer
19 views

Matrix-Tree Theorem: proof with graph characteristic polynomial

This is a follow-up question regarding my previous one. I went through the sections: 1.1 and 1.2 of the following script. I am in the middle of the section 1.3 but I do not understand what is ...
0
votes
0answers
20 views

Given S={0,1,2,3,4,5}, find the partition induced by the equivalence relation R where…

Given S={0,1,2,3,4,5}, find the partition induced by the equivalence relation R where R={(0,0),(0,4),(1,1),(1,3),(4,5),(0,5),(5,4),(5,0),(5,5),(2,2),(3,1),(3,3),(4,0),(4,4)}. Hey guys, after reading ...
0
votes
1answer
27 views

What is difference between $O(|V|+|E|)$ and $O(|V+E|)$?

Perform DFS over the entire graph. The linear time taken by a size of graph as visiting each node finished is put it on the head of initially empty list is $O(|V|+|E|)$ $O(|V+E|)$ $O(|V|^k)$ $O(\...
-4
votes
1answer
37 views

A simple discrete math riddle [on hold]

Let P be a set of integers. Let N be the number of the elements in P. Prove that there must be a subset of P that it's sum is divided by N. Any idea?
3
votes
4answers
445 views

Discrete Math Understanding a proof involving the definition of divisibility

In this first course on discrete mathematics, the instructor provided this following solution to a question. The question was asked us to prove the following (the solution is provided as well): My ...
0
votes
1answer
29 views

Mapping finite discrete numbers to the infinite set

This is an extension of my earlier question: Mapping discrete numbers Given that we can "map" $\mathbb{N}$ to $\mathbb{Z}$ via a bijection, I then wondered if it is possible to map a small subset of $\...
0
votes
2answers
19 views

Mapping discrete numbers

I would like to find a way to map the natural numbers, $\mathbb{N}$, to integers, $\mathbb{Z}$, and vice-versa. An analogous solution for continuous numbers would be using the $\log()$ and $\exp()$ ...
1
vote
2answers
29 views

Negation of “some” logic statement

I need to negate the following statement : "Some integers are not odd" I have the below, where O(x) is "odd" $$ \exists x (\neg O(x)) $$ Would the negation be $$ \forall x (O(x)) $$ I'm confused, ...
3
votes
2answers
45 views

Help me understanding what actually i counted with inclusion-exclusion

I tried to solve following task: Count number of $8$-permutations from $2$ letters $A$, $2$ letters $B$, $2$ letters $C$ and $2$ letters $D$ where exactly one pair of same letters are adjacent in ...
1
vote
2answers
25 views

Subgroup of order 12

Question: Suppose that $H$ is a normal subgroup of a group $G$. If $\left | H \right |=4$ and $gH$ has order $3$ in $G/H$, find a subgroup of order $12$ in $G$. By the property of cosets: $\left |...
1
vote
1answer
62 views

Need to prove that there is a continuous sequence which contains 100 cup of coffee , i.e. a man drinks one cup of coffee at the day.

A man can drink at least one cup of coffee at the day. After one year he drinks 500 cup of coffee. Need to prove that there is a continuous sequence which contains 100 cup of coffee, i.e. a man drinks ...
-3
votes
0answers
20 views

Let K be an integer between $800,000$ and $900,000$ so that (Greatest Common Divisor) [on hold]

Let K be an integer between $800,000$ and $900,000$ so that,$\gcd(K,271)>\gcd(K,2016)>100$. List all values of K. Need serious help with this!!! Respond asap, please!
1
vote
2answers
78 views

Help solving this recurrence relation

I wanted to resolve the determinant of the next (nxn) matrix via recurrence relations: $$ \begin{vmatrix} a & 1 & 0 & 0 & 0 & 0 &.... 0 & 0 & 0 & 0 & 0\\ 1 &...
1
vote
0answers
20 views

maximum number of edges given diameter and number of vertices [on hold]

Let us assume that $G = (V,E)$ is an undirected unweighted simple graph. Let $d$ is the diameter of the graph $G$, $n$ is the number of vertices, and $m$ is the number of edges. Now I am looking for ...
0
votes
1answer
14 views

Evaluating scalar functions of vectors in multidimensional simplices.

In question Multivariate sum over a simplex we deal with certain functions of vectors defined in multidimensional simplices. To be specific we are interested in evaluating a following sum: \begin{...
-4
votes
0answers
28 views

Set theory of poset [closed]

Let $S$ be the set of all positive divisors of $30$. Prove that $(S,\le)$ a poset where $a\le b$ means a is a divisor of $b$, for $a,b \in s$.