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

Proving properties of the images and inverse images of functions

Let $f : X\to Y; \;\;g : Y\to Z;\,$ and $\;g \circ f : X\to Z.$ Prove or disprove a) For all subsets $\,A \subseteq X,\;\; f^{-1}(f(A)) = A$. b) For all subsets $\,B \subseteq Y,\;\; f(f^{-1}(B)) ...
8
votes
1answer
67 views

Probability that a clumsy boy eats $k$ out of 20 candies

A week or two (or maybe more) ago, the following question was posted and then deleted just as I was getting to the end of my solution. Unfortunately I have now forgotten what my solution was going to ...
3
votes
1answer
16 views

Matching in bipartite graph

Every student from a set of students applies for exactly three seminars among the seminars that are offered at their university. Two of the seminars are chosen by exactly 40 students, all others are ...
1
vote
1answer
58 views

binomial coefficients difference? [on hold]

I need a difference of 2 binomial coefficients that would be equivalent to the following sum: $12\choose5$+$11\choose5$+$10\choose5$+$9\choose5$+$8\choose5$ How to answer this?
1
vote
1answer
18 views

How can I find a DNF and Minimal Form for this boolean expression?

$Q(x,y,z)=(y′\vee z′ \vee 0\vee x′)\wedge1\wedge(z\vee x′\vee 0\vee y\vee z)′\wedge(z′\vee x\vee y\vee z′)$ I'm not supposed to use tables but only proprieties like De Morgan ecc. EDIT: So I ...
4
votes
1answer
37 views

Sum of nth powers of Fibonacci numbers

Is a closed form for $$\sum_{i=1}^n{F_i^k}$$ (where $F_i$ is the $i^{th}$ Fibonacci number and $k$ is constant) known?
2
votes
0answers
23 views

What is probability that a team reaches final if we know the probabilities of all opponents in the semi-final?

Our Discrete Math professor asked us a question as the Euros are going on. Given the following info, what is the probability that Portugal will make it to the final? Win Probabilities in quarter ...
0
votes
1answer
40 views

Checkers Board Problem

Here we consider a checkerboard expanded to size 12 × 12 instead of the ordinary 8 × 8 checkerboard. a) How many squares on this board contain more than a third of the total number of dark small ...
1
vote
1answer
34 views

Given a planar graph with minimum cycle length 8, show that $|E| \le \frac{4}{3}|V| - \frac{8}{3}$

Here's what I've got so far. I'm stuck on how to proceed. I believe I need to plug back into Euler's formula, but I'm not getting what I'm looking for by doing that. Where is the denominator of $3$ ...
2
votes
0answers
37 views

Definition of “Differentia” in Lewis Carroll's Symbolic Logic?

I am reading chapter $2$, and from what I understand, it seems like the differentia of a class is not well-defined. The book gives some definitions: The class "Things" here refers to the class ...
0
votes
0answers
15 views

Splitting a file into $m$ pieces of size $1/n$, such that any $n$ pieces allow you to recover the file?

Let's say we have a file (which we could define as a finite sequence of 0's and 1's (or any other two symbols)). For $m > n$, can you create $m$ pieces (which are themselves files), each $\frac 1n$...
2
votes
3answers
38 views

A number theory proof - how do I use these intuitions to prove $c^2 \mid ab$?

I've just been introduced to number theory and I had to admit it's a very cool math subfield. Solving problems is another matter entirely, however. Here is the problem: For positive $a, b, c \in \...
2
votes
6answers
91 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 ...
1
vote
2answers
10 views

Number of possible win-loss outcomes per round in an n team round robin tournament

I was thinking of the following problem related to discrete math. Assume that we have n teams scheduled for a round robin tournament. For any given round in the tournament, how many possible win-loss ...
1
vote
0answers
15 views

In graph theory, draw the graph corresponding to the matrix A

I am studying statistics but decided to have some classes in mathematics. This class is called optimization but apparently, the content is graph theory. This is my first time of taking such class and ...
3
votes
1answer
51 views

Maximum number of edges in a planar graph without $3$- or $4$-cycles

What is the largest possible number of edges in a planar graph without $3$- or $4$-cycles? I've been unsuccessfully trying to solve this problem from my book. I know that every planar graph without $...
1
vote
0answers
12 views

Finding optimal cyclic permutations

How can we find cyclic permutations $\prod_i$ to be applied to each of corresponding $i$'th rows of a square matrix $X$ of size $n \times n$ such that a given sum of pairwise costs $\sum_{ij}C\left[\...
-1
votes
1answer
42 views

Relations: How to prove $R^2R^3 = R^5$?

Relations: How to prove $R^2R^3 = R^5$ ? I tried to go by this definition but I'm not quite sure I'm in the right path. $RS = \{(x,y) | \exists z, (x,z) \in R$ ^ $(z,y) \in S\}$
0
votes
1answer
41 views

Binomial coefficient paths?

Here's a problem and my attempt to answer it: We want to get a binomial coefficient identity depending on grid walking. Starting from the bottom left corner and going to the top right corner. You can ...
1
vote
2answers
37 views

Compound propositions as assertions?

According to comments on my previous question, compound propositions are not assertions; i.e. the statement "$p \vee q$" does not mean "$p$ (is true) or $q$ (is true)", and it does not mean "$(p$ or $...
2
votes
1answer
27 views

Can I use negations in the rules of inference?

For example, modus ponens is $p \land (p → q) \therefore q$. If I had $¬p$ and $¬q$, could I do $¬p \land (¬p → ¬q) \therefore ¬q$?
2
votes
3answers
51 views

Different kind of infinitesimals or zeros

If there are different kind of infinities (aleph0 aleph1 and so on) then are there different kind of infinitesimals? Or should I consider zero the "opposite" of infinity if there is such a thing and ...
0
votes
0answers
11 views

Can fourier transform be considered as a sum of a discrete series? [on hold]

For a non periodic function in x domain, I think the difference between fourier transform and fourier series lies in the coefficients ,if I don't pull T out of the coefficient which makes it dw in ...
-1
votes
1answer
31 views

If G and H are two gaphs then what does $G \Delta H$ indicate in graph theory?

I came across this notation in a book titled " Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen.
4
votes
1answer
68 views

Is the set of all trees currently on earth finite, countably infinite, or uncountable?

I'm not sure how to prove this as my professor has not shown any proofs involving real world objects, but I believe that it is finite since we know that there exists an integer k = the number of trees ...
0
votes
2answers
416 views

Determine the number of positive integer x where x<= 9,999,999 and the sum of the digits in x equals 31.

Determine the number of positive integer x where $$x\le 9,999,999$$ and the sum of the digits in x equals 31 How do you approach this question? TEXTBOOK SOLUTION: Let x be written in base 10. ...
6
votes
2answers
100 views

probability of sorted array with duplicate numbers

Suppose I have a sequence of n numbers {a1,a2,a3,...an} where some of the numbers are repeated. What is the probability that the sequence is sorted?
-1
votes
0answers
28 views

MAthematical notation for sorting submatrix and replacing it back

I need help in expressing the following paragraph in mathematical form as much as possible. I have a matrix $A$ which is $N\times M$. For each element of $A$, $A(i,j)$, I consider a submatrix of $A$ ...
1
vote
3answers
48 views

Is $B$ finite, countably infinite, or uncountable? $B = \{ x \in \mathbb{R} \mid \mathrm{floor}(x)=5) \}$

$B = \{ x \in \mathbb{R} \mid \mathrm{floor}(x)=5) \}$ I'm assuming this is the interval $[5,6)$. My first idea of a proof is the Cantor's Diagonalization Argument. But I'm not sure if that is the ...
2
votes
5answers
87 views

How to find remainder when $ 975^{40153}$ is divided by $14$? [duplicate]

I still find tricky this kind of problems. I tried to do solve it by factoring $14$ in $2*7$. Then, with Fermat's Little Theorem, I find that: $975^6\equiv 1\pmod 7$ $975^1\equiv 1\pmod 2$ How can ...
1
vote
2answers
17 views

Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
0
votes
1answer
29 views

Construct a weighted graph under the following conditions:

I need to construct a weighted graph of which neither of the Greedy Algorithms produces a correct answer to the Traveling Salesman Problem. Greedy Algorithms 1) Nearest Neighbor Works as ...
0
votes
0answers
16 views

Compute the time it would take to solve the Traveling Salesman Problem for a graph with 12 vertices…

I need to compute the time it would take to solve the Traveling Salesman Problem for a graph with 12 vertices where it takes 10 minutes to compute the length of a single Hamilton Circuit. A ...
2
votes
1answer
70 views

Maximum number of edges in a subgraph of hypercube

Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. Prove that ...
0
votes
1answer
36 views

Would these witnesses satisfy this big-O function?

I'm trying to determine if $f(x) = \lceil x/2 \rceil$ is $O(x)$. I know that this is true, and the textbook answer is: $|\lceil x/2\rceil|\leq |(x/2)+1| \leq C|x|$ for all $x > 2$, with ...
2
votes
4answers
67 views

How do you prove that $p → q$ is equivalent to $p \lor q ↔ q$?

I gotta draw $p \lor q ↔ q$ from $p → q$, logically. not by a truth table. While it seems obvious, I cannot find a formal proof. This is how far I came up to: $\quad p \lor q$ $\equiv (p \land T) \...
1
vote
0answers
22 views

Statistical calculation of value of coins in a box

I woke up from a dream today that made me consider the following scenario: A grocery store has an electronic donation box. Good Samaritans slide coins into the donation box, and the donation box ...
0
votes
1answer
16 views

How can I translate this sentence into predicates and quantifiers?

sentence : Every cube is larger than something else. My Working: P(x) = x is larger than something else ∀xP(x) But the answer is something completely different. ∀x (A(x) → B(x)) : the answer ...
6
votes
3answers
88 views

Probability of choosing $n$ numbers from $\{1, \dots, 2n\}$ so that $n$ is 3rd in size

We uniformly randomly choose $n$ numbers out of $2n$ numbers from the group $\{1, \dots, 2n\}$ so that order matters and repetitions are allowed. What is the probability that $n$ is the $3^{\text{rd}}$...
1
vote
1answer
17 views

Find union and intersection of family or index

For each $n∈ℕ$, let $βn = \{\ldots, -3n, -2n, -n, 0, n, 2n, 3n,\ldots\}$, and let $β=\{βn:n∈ℕ\}$. My attempt: For union, it would be all integers. As for intersection, $βn1=\{\ldots, -3, -2, -1, ...
1
vote
2answers
50 views

Proof/Reasoning why the sgn function which counts inversions has the following property?

$\mathrm{sgn}(\pi\circ\sigma)=\mathrm{sgn}(\pi)\cdot \mathrm{sgn}(\sigma)$ I am familiar with how to count inversions and any insight for why this formula holds true would be very helpful.
1
vote
1answer
25 views

Indexed Family of Sets Union and Intersection

So I have a problem with understanding indexed family of sets. The problem is: For each number $n$, let $\beta n=\mathbb N-\{1,2,3,\ldots,n\}$ and let $β=\{βn:n∈ℕ\}$. I need to find the union and ...
0
votes
0answers
29 views

Is the determinant of the following class of matrices non-zero?

For a positive integer $n$, let $c$ be the number of ordered integers tripartitions $(a_j,b_j,c_j)$ of $n$. Now consider the $c \times c$ matrix $M$ in which the value of the $M[i,j]$ is $M[i,j]={(...
1
vote
3answers
78 views

How to get the correct angle of the ellipse after approximation

I need to get the correct angle of rotation of the ellipses. These ellipses are examples. I have a canonical coefficients of the equation of the five points. $$Ax ^ 2 + Bxy + Cy ^ 2 + Dx + Ey + F = 0$...
6
votes
2answers
201 views

Cardinality of the set of all infinite monotonically decreasing sequences of naturals

Find the cardinality of the set of all infinite monotonically decreasing sequences of naturals. I think it's $\aleph_0$. I marked this set in $A$, and said that $\forall n\in\Bbb N \ (n,n,n,...)\in ...
1
vote
2answers
33 views

Find an example such that $X$ with the lexicographic order is not well-ordered.

Let $\{A_n\}_{n\in\Bbb N}$ be a collection of well-ordered sets. $X$ is defined by $X=\prod_{n\in\Bbb N}A_n$. Find an example such that $X$ with the lexicographic order is not well-ordered. I know ...
1
vote
1answer
26 views

Counting the number of subsets with at least one specific element.

Let $X = \left\{x_1, \dots , x_n \right\}$. I'd like to count the number of subsets of $X$ that have at least one of $k$ elements from $X$. For example, how many subsets of $X$ contain $x_1$, or $x_2$...
2
votes
1answer
339 views

Find the minimum number of tickets to guarantee the win of a n-bit binary lottery?

Here's the problem. I just don't know how to approach it. If the 'one error tolerance' were removed, then this would be a simple binomial distribution problem. But now I can't figure it out. In ...
0
votes
1answer
25 views

Is $R$ an equivalence relation?

Let $X,Y$ be infinite sets. Define $F$ as $F=\{f:X\rightarrow Y\}$ . We define a binary relation $R$ on $F$: $fRg$ if there is no countable $S\subseteq X$ such that $\forall x\in S \ f(x)\neq g(x)$. ...