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,603 questions
3
votes
0
answers
97
views
Number of integer solutions to $\sum_{i=1}^{10} x_i = 100$ with $2 \le x_i \le 21$
I am trying to solve a combinatorial problem involving finding the number of integer solutions to the following equation:
$$ x_1 + x_2 + \dots + x_{10} = 100 $$
Subject to the constraints:
$$ 2 \le ...
2
votes
2
answers
197
views
Maximum Travelling Salesman Problem on the integer line
I am trying to solve the following problem:
Let's say a "frog" is jumping on the numberline starting at $0$, jumps randomly on every integer from $1,\dots,n$ and then comes back to 0. What ...
- 225
-3
votes
0
answers
62
views
Is it valid to compare solving vs checking NP problems using average time per logical step?
I’ve been exploring a measurement approach for NP and NP-complete problems based on average time per logical step.
I define:
...
0
votes
1
answer
109
views
Solutions to $x^n \equiv x \pmod{n}$ for composite $n$.
By Fermat's Little Theorem we know that if $p$ is some prime number, the congruence $x^p \equiv x \pmod{p}$ is solved by any integer $x$, but can we say something about the solutions to $x^n \equiv x \...
- 7,746
-1
votes
0
answers
37
views
Proof of Linearly independece set [duplicate]
Let $L_S:F^n→F^m$ be a linear map which has null space $O$.
Prove: if $H^1,\dots,H^k$ are linearly independent elements in $F^n$, then $L_S (H^1 ),\dots,L_S (H^k )$ are linearly independent elements ...
3
votes
0
answers
97
views
Integer sequence with largest prime factor
Consider the function $F:\mathbb{N}\to\mathbb{N}$ such that $F(n)=\tfrac{n^2-n}{\delta(n^2-n)}$, where $\delta$ returns the biggest prime factor of its input. I wonder if this function always ...
- 965
5
votes
1
answer
189
views
Arrangements of 10 Balls Chosen from Red and Blue, Where Every Blue Ball Has a Blue Neighbor(need pure combinatorics solution)
Question
Consider a linear arrangement of $10$ balls selected from an infinite supply of blue and red balls.
Determine the total number of distinct arrangements that satisfy the following condition:
...
0
votes
1
answer
88
views
How many odd numbers are there in one row in Pascal's triangle?
I was looking at the pattern of odd entries in Pascal’s triangle and noticed that every row contains an even count of odd numbers. This is easy to justify, but it led me to wonder how the exact count ...
- 9,329
0
votes
0
answers
32
views
The Homotopy and Homology type of Hyperplane arrangements
This is a theorem in "Homotopy Types of Subspace Arrangements
via Diagrams of Spaces" by Ziegler and Zivaljevic. I would be interested in if we can say more in the Case where $\mathcal{A}$ ...
- 885
3
votes
3
answers
345
views
How many ways to arrange BOOKKEEPER where two E’s appear consecutively but not three.
Q: How many ways to arrange BOOKKEEPER where two E’s appear consecutively but not three.
Here What I've got : a) We can consider the two consecutive E’s as one block say X. Hence, we get a new string: ...
- 33
12
votes
5
answers
553
views
Non-recursive, explicit rational sequence that converges to $\sqrt{2}$
Is there a non-recursive, explicit sequence of rational numbers that has $\sqrt{2}$ as a limit?
I know of rational sequences such as $x_{n+1}=(x_n+2/x_{n})/2$ and $q_n=[10^n\sqrt{2}]/10^n$ that have $\...
1
vote
0
answers
38
views
VC exponent of a set system
I would like to prove that the VC dimension of a set system $(X,\mathcal{R})$ never takes values in $(0,1).$
For the sake of completeness, I'll define some basic ideas in this context.
Definition: A ...
- 354
-1
votes
1
answer
53
views
Justification for Definition of Directed and Undirected Graph
It is commonly known that directed graphs are defined as a double $G_d:=(V,E)$ such that $E \subseteq V^2$, and that undirected graphs $G_u:=(V,E)$ such that $E \subseteq \left\{ \{a,b\}\Big\vert a \...
- 71
-1
votes
1
answer
105
views
Counting permutations where each element is the maximum or minimum of the prefix [duplicate]
I am trying to solve a combinatorial problem regarding a specific class of permutations.
The Problem:
Consider a permutation $\sigma$ of the set $\{1, 2, \dots, n\}$, where $n=13$.
The permutation ...
0
votes
1
answer
114
views
Defining ordinal multiplication for infinite families of ordinals without transfinite recursion
In Naive Set Theory p.82-83, Halmos defines ordinal addition by defining the ordinal sum of an infinite family ${A_i}$ of well-ordered sets, indexed by some well ordered set $I$. He then proceeds to ...
- 23