# Tagged Questions

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.

77 views

### x + y = y + x is not a statement in Discrete Mathematics?

I was reading my notes and i noticed something a little unusual. How is $$x + y = y + x$$ not a statement? The reason that was given in the notes was "we don't know what $x$ and $y$ are, so they ...
24 views

### prove graph G with n vertices, vertex of degree $n-1$ and rest of the vertices of degree $1$ is a tree graph

I'm a discrete math student and I've bumped into the following question. I tried to prove it and specifically in first part I thought of two ways of proving it. but in each of the ways the proof looks ...
91 views

### Prove that $\log(n!)\leq(\log(n))!$

Prove that $\log(n!)\leq(\log(n))!$ My attempt: I read somewhere that $n\leq\log(n!)\leq(\log(n))!$. But when I used calculator $\log(n!)$ can not be less than or equal to $(\log(n))!$. ...
23 views

### Universal and Existential quantifier in Propositional logic

The following paragraph is an excerpt from Discrete Mathematics book of Kenneth Rosen 7edition The restriction of a universal quantification is the same as the universal quantification of a ...
26 views

### Closure of a function

"Let $f: A \rightarrow A$ and let $X \subseteq A$. Then, in a ‘top down’ version, the closure f[X] of X under f is the least subset of A that includes X and also includes f(Y) whenever it includes Y. ...
57 views

### Prove for all $n\in \mathbb{N}$ ,$n ≥ 1, a(n)$ is odd.

Prove for all $n\in\mathbb{N}\backslash \{0\}$, $a(n)$ is odd. Consider the sequence defined as followed: $a(1)= 1$ $a(2)= 3$,where $n \in \mathbb{N}$ $$a(n)=a(n-2)+2a(n-1), n ≥3$$ Conjecture: ...
11 views

### Give aysmptotic bounds for T(n) in each of following recurrences. Make bounds as tight as possible.

T(n) = T(n-2) + 4 T(n) = 3T(n-1) + 3 T(n) = 2T(n/8) + 4n^2 I can't figure out how to do the first two, none of the examples on google or my lecture slides show how to do solve for anything about "+ ...
55 views

### Linear four-parameter recurrence from Concrete Mathematics

In the book Concrete Mathematics, there's an exercise (1.16) where you're asked to solve a general four-parameter recurrence using the Repertoire Method. The recurrence is defined as follows: \begin{...
234 views

### I derived a new formula related to arithmetic sequences, I think!

First of all, I am a 12th grader so I don't know how to write research notes. So please forgive me if my writing is not so impressive! I don't know what to do to tell the world about whatever I found....
19 views

### Regarding pedigrees

Here's a errrhmm.... a modelling problem. Applied math. Or something. We're given pair of sets $X,Y$ (for notational simplicity, assumed disjoint). Let $T_{X,Y}$ denote the following disjoint union:...
38 views

### Is there any formula to find the nth element in a sequence where common difference (d) is varying with a constant rate?

To explain my question, here is an example. Below is an AP: 2, 6, 10, 14....n Calculating the nth term in this sequence is easy because we have a formula. The common difference (d = 4) in AP is ...
54 views

### Expectation of Gaussian Ratios

Consider the following expression: $z = \frac{\mathbf{x}^H P \mathbf{x}}{\mathbf{x}^H \mathbf{y}}$, where $\mathbf{y}$ is fixed (not random) and $\mathbf{x}$ is a complex Gaussian vector of zero mean ...
65 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?
52 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 ...
60 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 ...
74 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$...
89 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 ...
15 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 ...
27 views

### In graph theory, draw the graph corresponding to the matrix A [closed]

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 ...
30 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 ...
81 views

44 views

### If $G$ and $H$ are two graphs, 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.
69 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 ...
126 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?
63 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 ...
38 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$ ...
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 ...
45 views

25 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 ...
18 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 ...
19 views

37 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 ...
94 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}}$...
26 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 ...
### 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 ...
### 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)$. ...