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
-1
votes
1
answer
36
views
No. of squares formed from 10 evenly spaced line with each vertex on a distinct line
PuMAC Combinatorics A 2022 Problem 2
Ten evenly spaced vertical lines in the plane are labeled ℓ1, ℓ2, . . . , ℓ10 from left to right. A set
{a, b, c, d} of four distinct integers a, b, c, d ∈ {1, 2, ...
- 69
0
votes
1
answer
45
views
Solving $a = x \mod b$ without congruences [duplicate]
I have never dealt with congruences, and I want to stay as pragmatic as possible here.
Using a similar approach to trigonometric equations, where the solution is rather a set of answers that fulfil ...
- 322
-1
votes
0
answers
16
views
Scalar product of two derivated kernels (RKHS) [closed]
I have W a RKHS (Reproducing Kernel Hilbert Spaces) embedded in $C^1(\mathbb{R}^d,\mathbb{R})$ spanned by fundamental functions $k(x,\cdot) : \mathbb{R^d} \rightarrow \mathbb{R}$.
I would like to ...
- 9
0
votes
1
answer
61
views
What is $\sum_{m=0}^{\lfloor k/3\rfloor}{2k\choose k-3m}$ [closed]
With the floor function, I am not sure how to approach this.
Edit: I have a formula $\frac{1}{6}\left(4^k+2+3\frac{(2k)!}{(k!)^2} \right)$, but I got it purely from guess work.
- 99
2
votes
2
answers
45
views
Determining the witnesses (constants $C_0$ and $k_0$) when showing $c^n \in O(n!)$ ($c > 1$)
I'm having a hard time finding the constants/witnesses $C_0$ and $k_0$ that show $c^n \in O(n!)$. That is $|c^n| \leq C_0|n!|$ for $n > k_0$ ($c > 1$).
To be clear, I understand we can prove the ...
- 865
1
vote
1
answer
38
views
Determining the witnesses (constants $C_0$ and $k_0$) when showing $n^d \in O(b^n)$ ($b > 1$ and $d$ is positive)
I'm having a hard time finding the constants/witnesses $C_0$ and $k_0$ that show $n^d \in O(b^n)$ ($b > 1$ and $d$ is positive). That is $|n^d| \leq C_0|b^n|$ for $n > k_0$
I understand you can ...
- 865
1
vote
1
answer
77
views
How to show $(\log_2 x)^4 \leq x^3$ for $x > 1$?
In Rosen's discrete Math textbook, they mention in the solutions for one problem that $(\log_2 x)^4 \leq x^3$ for $x > 1$. However, I'm not sure how to exactly derive that myself, nor does the ...
- 865
1
vote
0
answers
39
views
Equivalence relation on Boolean functions
Let us say that two Boolean functions $f,g:\mathbb F_2^n\to\mathbb F_2$ are equivalent if there exists a vector $u\in\mathbb F_2^n$ with the following property:
$$\forall x\in\mathbb F_2^n:g(x)=f(x+u)....
- 4,753
0
votes
1
answer
46
views
Determining the witnesses (constants $C_0$ and $k_0$) when showing $(log_b n)^c$ is $O(n^d)$ (b > 1 and c,d are positive)
I'm having a hard time finding the constants/witnesses $C_0$ and $k_0$ that show $(\log_b n)^c$ is $O(n^d)$. That is $|(\log_b n)^c| \leq C_0|n^d|$ for $n > k_0$ (b > 1, and c,d are positive).
I ...
- 865
0
votes
1
answer
67
views
Examining whether the relation "$aRb$ iff $a + 2b \equiv 0 \pmod 3$" is reflexive, symmetric, antisymmetric, or transitive [duplicate]
Have I shown correctly which properties the relation fulfills?
$$aRb \text{ iff } a + 2b \equiv 0 \pmod 3$$
$(1)$ Reflexivity
Set $b=a$
$a + 2a = 3a \equiv 0 \pmod 3$
Hence, the relation is reflexive....
2
votes
2
answers
79
views
The number of strings of length $n$ consisting of symbols $A,B,C$ not containing substring $CC$
So I'm wondering what is wrong with my reasoning.
Let $a_n$ be the number of strings of length $n$ in letters $A,B,C$ not containing substring $CC$.
I want to solve it like this. Let $b_n$ be the ...
- 857
-1
votes
1
answer
34
views
in an $m \times n$ grid, prove that if $m$ and $n$ are odd, then there is no hamiltonian cycle [duplicate]
Let a simple undirected graph $G=(V,E)$ be defined by $V=\{1,2,...,m\} \times \{1,2,...,n\}$ and $E=E_1 \cup E_2$ where
$$\begin{split}
E_1 &= \{((a,b),(a+1&,b&)) &\; | 1 \leq a \leq m-...
2
votes
2
answers
46
views
Given a set of integers, and the number of summations find the resulting frequencies
Given a set $X = \{x_1,x_2,...x_m\}\subset \mathbb{Z}$ and the number of allowed addends $N$. How can I find the frequency of every possible sum?
Example: $X = \{-1, 2\}$ and $N=3$ then every ...
- 389
0
votes
1
answer
139
views
Pigeon Hole Principle Proof
Prove using PHP that in any arrangement of the numbers $1,2,\ldots,20$ exist a sequence of $4$ numbers with sum of at least $42$.
I know there are $17$ different ...
- 17
0
votes
2
answers
71
views
Finding the optimal offset for periodic signals to minimize concurrent transmissions
I have a system with discrete time, that sends periodic signals with the following periods: [10, 20, 30, 40, 50, 100, 200, 500, 1000, 5000]. The number of signals belonging to each period is as ...
- 103