Questions tagged [discrete-mathematics]
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.
33,173
questions
0
votes
0
answers
22
views
Fixed quantities in Big O notation
Consider the following description of a random graph generation algorithm with parameters $n$ (number of vertices) and $m$ (number of edges).
All iterations add an edge except those where a ...
- 3,408
0
votes
1
answer
29
views
Understanding of Separation theorem
Separation theorem:
Let $P, Q⊆\mathbb{R}^d$ be disjoint compact convex sets. Then there exist $v∈ \mathbb{R}^d$ and $c_1, c_2∈\mathbb{R}$ with $c_1<c_2$ such that
$x.v≤c_1$ for every $x∈P$
$x.v≥...
- 41
1
vote
1
answer
41
views
Helly's theorem for $n=d+1$
Helly's theorem : Let $C_1,\ldots,C_n$, $n\geq d+1$, be convex sets in $\Bbb R^d$. Suppose every $d+1$ have a common intersection. Then they all have a common intersection.
I can find the proofs for $...
- 135
0
votes
1
answer
17
views
Why is the determinant of the Jacobian of symplectic integrators always 1?
My numerics books says that a symplectic integrator has the property that the determinant of $det \frac{\partial F}{\partial \xi}=1$ for the state vector $\xi = (X,V)$ for $F_\epsilon: \xi _t \...
- 1
4
votes
0
answers
28
views
Remove two vertices such that there are no 3-cliques in the resulting graph
The question is: A graph G contains no 5-cliques and every two 3-cliques intersect in at least one vertex. Show that we can delete two vertices such that the resulting graph contains no 3-cliques.
I ...
- 41
2
votes
0
answers
43
views
writing regular expression for exactly once $111$ in binary strings for finding Generating functions
I am looking for the regular expression for binary strings consisting of $1$ and $0$ and containing $111$ exactly once to find their generating functions. For example, $101100001110,000111000,01010111,...
- 21
-1
votes
0
answers
24
views
Average cluster size of a n-size vector
Given a vector of $n$ cells and $k$ elements in it, we can define a cluster of elements as a contiguous sequence of elements inside the vector.
My goal is to calculate the average cluster size for all ...
- 113
0
votes
0
answers
32
views
Counting matrix paths for (n,m>2) matrices
Given a $n\times m$ matrix with $k$ elements inside it, I need to calculate the number of arrangements of those $k$ elements that form at least 1 path from the top to bottom matrix row composed of the ...
- 113
-3
votes
0
answers
48
views
Summation of a $x^5$ [duplicate]
What is the summation of the series $x^5$ for $x=1$ to $x=n$?
I want the actual formula for it and also the proof.
I would also like to know how we can use the proof of summation of $x^5$ to find the ...
0
votes
0
answers
20
views
Define grid of points with two angles with respect to horizontal plane
Friends,
My apologies if this question finds you uncomfortable. I'm not a mathematician so I need help with my problem. Basically I need to define a coordinates of the points in the rectangular shape ...
-5
votes
0
answers
49
views
Expected Cardinality [closed]
Can you tell me the main idea/theory behind finding expected cardinality.
I know it's the average of the cardinalities in a random set.
But how to calculate it? And if I get to know the main theory ...
0
votes
0
answers
15
views
FFT for the Estimation of Power Spectra (Welch's Method) - DFT Definition
I was reading Peter Welch's famous paper "The Use of Fast Fourier Transform for the Estimation of Power Spectra: A Method Based on Time Aver. aging Over Short, Modified Periodograms" the ...
- 1
0
votes
1
answer
32
views
This statement is false right? Susanna Epp Exercise Set 3.3, Question 19
Link to Question
Exist real number X, such that for every real number Y,X+Y = 0
This statement should be false right? The book did not tell us to show whether it ...
- 9
1
vote
1
answer
57
views
Derive the closed-form expression of Delannoy Numbers
I am trying to derive the closed-form expression of Delannoy Numbers, as the one in the wikipedia: https://en.wikipedia.org/wiki/Delannoy_number#cite_note-7
The closed-form expression looks like this:...
- 35
-4
votes
0
answers
13
views
Reducing propositions using laws [closed]
Could someone help me to simplify nv(s^s) to n by using laws? I tried using all the laws that is available for this problem.
