Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
10 views

Inverse of a circulant matrix via DFT

I am trying to do some practice in computing the inverse of a circulant matrix via the formula Inverse of a circulant matrix. I got that the first row of the inverse is \begin{equation}\label{a}\begin{...
Vladimir's user avatar
5 votes
2 answers
316 views

If we choose a line segment at random, then what is the expected number of paths that pass through it?

I was trying to solve this question. To find the expected number of paths that pass through a randomly chosen line segment: I observed that for different line segments the probability is different. Do ...
user5210's user avatar
  • 451
0 votes
1 answer
18 views

Find $K_r$-subdivisions in random graphs

I saw the following exercise in Shapira's note, page 22-23. Prove that with high probability, $G(n,1/2)$ does not contain a $K_t$-subdivision (also called topological minor) with $t=10\sqrt n$, but ...
Lanchao Wang's user avatar
1 vote
0 answers
27 views

Derive Centerpoint theorem from Helly's theorem

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. Proof: We're given that ...
D. S.'s user avatar
  • 306
0 votes
1 answer
59 views

How to Arrange 21 Uniquely Sized Squares to Form a Perfect Square?

I’m tackling a geometric puzzle where I have 21 squares, each with a different integer side length. The goal is to arrange these squares so that they perfectly fill a larger square without leaving any ...
Saucitom's user avatar
  • 317
0 votes
0 answers
36 views

What are the preferred steps to solve an exercise that involves finding all possible combinations/solutions for a string with constraints?

I have an exercise divided in two parts: a.) How many ( $x \in \mathbb{Z}$ ), with ($ 104050607080 \leq x \leq 908070605040$ ), can be formed using the digits of ( $106506506503$ ), such that ( $x$ ) ...
zaxunobi's user avatar
  • 141
0 votes
0 answers
38 views

Nested Mathematical Induction [closed]

I have a result saying that "for all $s\geq 7$ and for all $V_J=\{v_{5j+1},v_{5j+2},v_{5j+3},v_{5j+4},v_{5j+5}\}$ for $J=j \in \{0,1,2, \cdots,\lfloor{\frac{s}{5}}\rfloor\}$, the property $P$ is ...
Murad khan's user avatar
5 votes
0 answers
129 views

Finding non-repeating 9-digit numbers [closed]

Suppose that you are asked to find out a 9-digit number, consisting of numbers from 1 to 9 without repeating. Each time you may initiate a guess attempt of the number, and you will get a value of how ...
Alexander Callahan's user avatar
1 vote
0 answers
42 views

Steps on solving point to plane exercises

I just want confirmation that the steps I've took to solve these two exercises are correct Exercise 1 Consider in R3 the line $l$ defined by: \begin{cases} x = 2 + 3t \\ y = 2 - 2t \\ z = 1 + t \\ t \...
zaxunobi's user avatar
  • 141
0 votes
1 answer
55 views

Binomial identity involving square binomial coefficient [closed]

I want to prove this identity, but I have no idea... Could someone please post a solution? Thank you. $$\sum_{k=0}^{n} \binom{-1/2}{n+k}\binom{n+k}{k}\binom{n}{k}= \binom{-1/2}{n}^2$$ (Maybe -1/2 can ...
anonymoususer's user avatar
3 votes
2 answers
102 views

Show that $\sum_{k=1}^n{2^{2k-1}\binom{2n+1}{2k}B_{2k}(0)}=n$

Lately, I've been working on a proof (whose context is not necessary to discuss) and I only need one last thing in order to finish it. To be more specific, for completeness it would suffice to show ...
Vaskara_GRek_O's user avatar
-1 votes
0 answers
10 views

Column/Digit blind solution for the "Number of possible combinations of x numbers that sum to y"

What formula will give me "the total number of possible combinations of x digits that sum to y". This is a branch question from the original question entitled Number of possible ...
MB Billdx's user avatar
0 votes
1 answer
50 views

Regarding the question of translating the verbal descriptions of definitions and theorems into propositional logic

I am studying discrete mathematics and recently trying to describe mathematical definitions or theorems in the form of propositional calculus or predicate calculus. I am not sure if my approach is ...
咪苦力怕's user avatar
2 votes
0 answers
83 views

Number of Tverberg Partitions [closed]

Tverberg's Theorem: A collection of $(d+1)(r-1) +1$ points in $\mathbb{R}^d$ can always be partitioned into $r$ parts whose convex hulls intersect. For example, $d=2$, $r=3$, 7 points: Let $p_1, p_2,...
D. S.'s user avatar
  • 306
1 vote
1 answer
46 views

Helly's theorem for $n\geq d+3$

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. Proof: We're given that ...
D. S.'s user avatar
  • 306
3 votes
1 answer
65 views

Steps on solving part b of the bit-string exercise?

This is the exercise: How many bit strings of length $77$ are there such that a.) the bit string has at least forty-six $0$s and at least twenty-nine $1$s, and also the bit string corresponding to ...
zaxunobi's user avatar
  • 141
0 votes
0 answers
39 views
+50

Construction of a graph on even number of vertices with required eccentricities.

I was trying to construct a graph on an even number of vertices $n$ such that center and periphery contain an equal number of vertices, i.e. $|C(G)|=|P(G)| =\frac{n}{2}$. Till now, I was able to draw ...
monalisa's user avatar
  • 4,420
0 votes
0 answers
58 views

Is the law of non-contradiction part of formal mathematics?

I am seeking hereby to clarify whether the law of non-contradiction is part of the framework in which mathematicians work or not. Wikipedia says only that this is a principle in "logic", ...
Princess Mia's user avatar
  • 3,029
1 vote
0 answers
71 views

The number of ways of writing $k$ as a sum of the squares of "not so big" two elements

This question arises from the attempt to compute the Euler characteristic of a space using a Morse function. We fix a positive integer $n$. For each integer $k$ which satisfies the condition $$1\leq k ...
Yasuhiko Kamiyama's user avatar
0 votes
2 answers
55 views

Sequences of cyling digits [closed]

Have been wrestling with this one: Given five policy numbers (rows of integers like on an insurance policy). The 2nd is 2X the first when the first #'s one's digit is moved to its front; similarly for ...
Ken Bannister's user avatar
0 votes
3 answers
148 views

Confused about a counting problem

This question is reproduced from a text by Sheldon Ross: Example 5k. A football team consists of $20$ offensive and $20$ defensive players. The players are to be paired in groups of $2$ for the ...
Vacation Due 20000's user avatar
1 vote
1 answer
46 views

Does any permutation "cover" a permutation with less inversions?

Let $\mathcal{S}_n$ be the symmetric group on $n$ objects. For any permutation $\pi\in\mathcal{S}_n$, define $E(\pi)=\{(i,j):\ i<j,\ \pi(i)>\pi(j)\}$ as the set of reversed pair of indices ...
Johnson's user avatar
  • 13
0 votes
0 answers
22 views

I dont understand how to solve this Boolean Algebra question Help

Let S be a set and let F UN(S, {0, 1}) be the set of all functions with domain S and codomain {0, 1}. Define the Boolean operations on F UN(S, {0, 1}) as follows: Let F, G ∈ F UN(S, {0, 1}), then (a) ...
G21's user avatar
  • 1
0 votes
0 answers
12 views

Removing vertices from rooted tree to make it balanced

The question says, what is the least number of vertices that must be deleted from T to yield a balanced tree. The correct answer is 1. But how, i see the graph is already balanced and doesn’t need ...
kic srx's user avatar
  • 11
-1 votes
1 answer
80 views

Probability that at least one option is selected exactly once [closed]

I'm having trouble with the following question: Suppose $n$ persons each select, uniformly and independently, one of $k$ options. Show that the probability that at least one option is chosen exactly ...
user675763's user avatar
0 votes
2 answers
38 views

Simple paths in a graph [closed]

Im confused, the question says how many simple paths are there from vertex a to vertex d, I only see 2 and that’s wrong. The correct answer is 5. And it’s not clear to me why. if someone could please ...
kic srx's user avatar
  • 11
0 votes
3 answers
98 views

How to phrase the proof of $m \lt n$ if and only if $m \le n-1$

I have been reading Knuth's "The Art of Computer Programming" and in the mathematical preliminaries chapter of volume 1 there is on page 476 the answer to an exercise where he states ... ...
branco's user avatar
  • 3
-2 votes
0 answers
32 views

How to verify whether a graph under some given conditions cannot be labeled through distance magic labelling? [closed]

Okay so I've been stuck on this question for a while now:Prove that if G contains two vertices xi and xj such that |NG (xi) ∩ NG(xj)| = deg(xi) − 1 = deg(xj) − 1, then G has no labeling. I realized ...
Arya Hariharan's user avatar
1 vote
0 answers
55 views

Confusion for algorithm for finding (a div d) and (a mod d), where a is an integer and d positive integer.

From Rosen's discrete Math textbook. I'm confused on 3 things regarding this algorithm (as can be seen via the screenshots) Why do we need an algorithm for finding $a$ div $d$ and $a$ mod $d$ when we ...
Bob Marley's user avatar
0 votes
0 answers
22 views

If sub-universe $S$ of lattice has congruence $\theta$, does the lattice have a congruence $\lambda = \theta \cap S^2$? [duplicate]

Let $(L, \lor , \land )$ be a lattice and $S$ a sub-universe of the lattice. A sub-universe of a lattice will be any subset of the lattice set that is non-empty and closed under $\land$ and $\lor$. ...
lafinur's user avatar
  • 3,468
0 votes
0 answers
41 views

Understanding the definition of congruences over a lattice

Let $(L, \land, \lor)$ a lattice and $\theta$ a binary relation over $L$. We say $\theta$ is a congruence iff $$ x_0\theta x_1, y_0 \theta y_1 \Rightarrow (x_0 \lor y_0)\theta(x_1 \lor y_1) $$ (and ...
lafinur's user avatar
  • 3,468
1 vote
0 answers
34 views

Solution of recurrence relation with summation

I have the following recurrence relation: $b(n,k)=\sum _{\text{i}=0}^{2 n-1} \left(b(n-1,k-\text{i})+\frac{\text{i} (2 n-\text{i}) \binom{2 n-1}{\text{i}} \binom{(n-2)^2}{k-\text{i}}}{2 n-1}\right)$ ...
Cardstdani's user avatar
1 vote
2 answers
84 views

Which statement is not a mistake that Reina has made?

"A survey done at a certain high school found that any student who liked tennis also liked swimming. They also found that students only liked swimming if they could swim." Reina: If 30 ...
Bacterigerm's user avatar
0 votes
0 answers
23 views

Variance of asymptotic Travelling Salesperson Problem

Consider N realisations of a uniform distribution on a bounded area in R^2 (e.g., the circle (0,1)). I know that when N is large, the length of a TSP visiting all of those points becomes "...
Andres Fielbaum's user avatar
1 vote
2 answers
121 views

Closed form for the recurrence $S_n = 1 + S_{n-1} + \frac{2}{n} S_{n-2}$, where $S_1=1$ and $S_2=2$?

How would you go about getting an expression for $S_n$ where $S_1=1$, $S_2=2$, and $S_n = 1 + S_{n-1} + \frac{2}{n} S_{n-2}$? I'm using this to try and solve a separate problem which involves the ...
ojt's user avatar
  • 75
5 votes
5 answers
226 views

Closed formula for probability of n-digit numbers containing three consecutive sixes

I'm trying to find a closed formula $f(n)$ for the probability of choosing a number with $n$ digits that contains at least three consecutive sixes. Ideally, the formula should not depend on $f(n-1)$. ...
Aldo Roberto Pessolano's user avatar
0 votes
1 answer
46 views

Number of lattices over a finite set

I'm interested in finding a general formula for the number of lattices possible over a finite set $S$ as a function of the set's cardinality. For instance, how many lattices over $\{1, 2, 3\}$ are ...
lafinur's user avatar
  • 3,468
-1 votes
2 answers
39 views

Simplify the following using logical equivalence, and prove equivalence: ~(~p ∧ q) ∧ (p ∨ q) ≡ p

Simplify the following using logical equivalence, and prove equivalence:$\newcommand{\lsim}{\mathord{\sim}}$ $$\lsim((\lsim p) \wedge q) \wedge (p \vee q) \equiv p$$ Just to specify this is the ...
Anonymous's user avatar
5 votes
0 answers
209 views

An arrangements of the hyperplanes.

Consider a finite set L of lines in the plane. They divide the plane into convex subsets of various dimensions, as is indicated in the following picture with 4 lines: The intersections of the lines, ...
D. S.'s user avatar
  • 306
-1 votes
0 answers
25 views

Number of graphs with $n$ vértices, $m$ edges, and more than one connected components [duplicate]

The title pretty much sums up the question. I have succeeded at establishing that there are $K := \binom{n(n-1)/2}{m}$ possible graphs of $n$ vertices, $m$ edges. (We assume the graphs are labeled). ...
lafinur's user avatar
  • 3,468
0 votes
0 answers
26 views

Calculating number of trees of $n$ vertices by counting edges that can be removed from $K_n$.

Let $K_4$ be the complete graph of $4$ vertices. $K_4$ has $6$ edges. Assume vertices are labeled. Any tree of $4$ vertices can be formed by removing three edges from $K_4$. There are $\binom{6}{3}$ ...
lafinur's user avatar
  • 3,468
2 votes
1 answer
163 views

Reasoning about the Collatz conjecture, multiple infinitely growing trees that never overlap? [closed]

I have been pondering the Collatz conjecture recently as a mental exercise, and have run into a problem that has to do with proving that an iteratively growing tree of odd positive integers will ...
Jookos's user avatar
  • 55
2 votes
1 answer
64 views

Solving equations involving the floor and ceiling function

The following conversion equation appears to work for all positive integers. I verified this experimentally. $$ x=\left\lfloor\left\lceil x\cdot \frac{412}{256}\right\rceil\cdot \frac{256}{412}\right\...
user150497's user avatar
0 votes
3 answers
124 views

What is the correct term for maximal/minimal "thickness" of convex hull in ℝ³?

Let me explain what I mean with thickness. In this JSCAD example I use 3x3 linear transformation matrix G for ternary quadratic form Q from Dirichlet 1850 … … to transform convex hull of points in ℤ³ ...
HermannSW's user avatar
-1 votes
0 answers
32 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 ...
lafinur's user avatar
  • 3,468
1 vote
1 answer
90 views

When does $n$ divide $u_n$ if $u_1=1$, $u_n=(n-1)u_{n-1}+1$? [duplicate]

I'm working through the Background section to 'The Mathematical Olympiad Handbook' by A. Gardiner, OUP, 1997, and this appears on page 17: (***) Let $u_1=1$, $u_n=(n-1)u_{n-1}+1$. For which values of ...
John1970's user avatar
  • 441
0 votes
1 answer
49 views

Understanding the 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≥...
D. S.'s user avatar
  • 306
0 votes
1 answer
26 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 \...
alo bre's user avatar
  • 13
6 votes
1 answer
84 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 ...
user1546320's user avatar
2 votes
0 answers
59 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,...
user avatar

1
2 3 4 5
664