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
1 answer
19 views

Let $R=\{(x,y)∈ℝ^2; x^2 <= y^2\}$. Give an infinite subset of $X$ of $ℝ$, such that $R∩X^2$ defines a total order of X.

Hi can anyone help me with the following question? Let $R=\{(x,y)∈ℝ^2; x^2 <= y^2\}$. Give an infinite subset of $X$ of $ℝ$, such that $R∩X^2$ defines a total order of X.
user avatar
  • 9
0 votes
0 answers
42 views

Expected number of fixed points in a permutation by brute force

I'm trying to compute the expected value of fixed points in a permutation without using the linearity of expectation. I tried the following: $$\sum_{i=1}^{n} i\frac{(n-i)!\binom{n}{i}}{n!}$$ However, ...
user avatar
-1 votes
0 answers
32 views

how do i solve non linear equation? TOPIC IS PDE [closed]

Find a separated solution of the following nonlinear wave equation: ∂u/∂t=cu ∂y/∂x and What is a separated solution of the 2 -dimensional wave equation (∂^2 u)/(∂t^2 )=a (∂^2 u)/(∂x^2 )+b (∂^2 u)/(∂y^...
user avatar
0 votes
2 answers
37 views

How to prove the following statement regarding the successor function and addition of natural numbers?

Natural numbers (including 0) and the successor function are defined as per the Peano Axioms (you can check them on wikipedia). Addition is defined recursively as follows: $a+0=a$ $a+S(b)=S(a)+b$ With ...
user avatar
-2 votes
0 answers
27 views

Math struggles for discrete math and Linear algebra [closed]

I am a second year student at a community college. I have autism and obsessed with my grades. I am struggling heavily when comes to these mathematics. I have tried youtube, my classmates, and my ...
user avatar
-1 votes
0 answers
28 views

series development problem, binomial theorem. Need ideas how to solve it [duplicate]

Need ideas about how to solve this task. The problem is based on series development and I have a problem getting the idea of what to do in this task
user avatar
5 votes
1 answer
61 views

Using a generating function to solve a recursion

I know that the generating function for the sum of Fibonacci numbers with even index is \begin{align} F_e(z) &= \sum_{n \ge 0} F_{2 n} z^n \\ &= \frac{F(z^{1/2}) + F(- z^{1/2})}{2} \\ &...
user avatar
-2 votes
0 answers
24 views

Probability that at least $6$ of $10$ randomly drawn light bulbs are white [closed]

Out of $100$ bulbs produced by a manufacturing company, $35$ are white light bulbs and the rest are yellow light bulbs. If $10$ bulbs are randomly drawn without replacement, find the probability that ...
user avatar
5 votes
0 answers
62 views

Question about number of generating functions

I know that the generating function for the number of integer partitions of $n$ into distinct parts is $$\sum_{n \ge 0} p_d(n)x^n = \prod_{i \ge 1}(1+x^i)$$ I'm trying to use this generating function ...
user avatar
2 votes
0 answers
35 views

Help with finding analytical formula of a recurrence relation using iteration.

$$\displaystyle{\displaylines{g(0)=1}}$$ $$\displaystyle{\displaylines{g(n)=3^n-g(n-1)+1}}$$ Find the analytical definition of the recurrence relation using iteration $$\displaystyle{\displaylines{g_{...
user avatar
1 vote
2 answers
34 views

Showing that $x^3 + y = y^3 + x$ is an equivalence relation

I am asked to prove that: $x^3 + y = y^3 + x$ is an equivalence relation. So far I have the following: Reflexive: $m^3 +m = m^3 +m$ Symmetric: $m^3 + n = n^3 + m \rightarrow n^3 + m = m^3 + n$ ...
user avatar
3 votes
1 answer
55 views

Help finding mistake in proof involving the quotient map.

Consider the plane $\mathbb{R}^2=\mathbb{R}\times\mathbb{R}$ with the product topology which has basis consisting of all open squares of the form $$\tag{1} \left]a,b\right[ \times \left]c,d\right[ \...
user avatar
  • 157
-1 votes
0 answers
34 views

Can a Probability Distribution be made of Discrete Variables?

I have been trying to determine the popular "consensus" as to how mixed continuous and categorical data (e.g. a dataset that has variables on income and gender) is generally analyzed in the ...
user avatar
  • 1,698
-5 votes
0 answers
28 views

You will get an A in this class if and only if you either do every exercise in this book or you get an A on the final? [closed]

I need an answer for this question.
user avatar
1 vote
1 answer
91 views

Placing $n$ rooks peacefully on a board

We got $n\times n$ board colored in different colors. The count of cells with the same color is $\leq \frac{n-1}{16}$. Prove that we can manage to place $n$ rooks on different color cells, so they ...
user avatar
-1 votes
0 answers
24 views

Problem related with mathematical inductions [duplicate]

Show that n^2 > 2n +1 for n >= 3 by the mathematical induction I have tried (k+1)^2 > 2(k+1) + 1 and I am stuck hereafter
user avatar
  • 1
1 vote
1 answer
42 views

Number of functions under some conditions

let $A=\{0,1,2,\dots,8\}$ and $B=\{0,1,2,\dots\}$. How many function from $A$ to $B$ can be defined such that the following will be hold: $f(x+y \bmod{9}) = f(x)+f(y) \bmod{12}$ $f(x \cdot y \bmod{9}...
user avatar
  • 820
0 votes
0 answers
11 views

Calculate Treatment Effect for the Treated

This is from the paper 1991 Identification and Estimation of Local Average Treatment Effects by Angrist and Imbens. On p5, example 1 which says: Consider the following model: $Y_0 = \epsilon$ $Y_1 = ...
user avatar
-3 votes
0 answers
25 views

Absolute value on addition [closed]

Does the absolute value is distributive over addition or in other some way abs(3x)+abs(1-x)=abs(2-4x) can we here collect the terms on the left hand side inside on absolute value. i.e abs(3x+1-x)=...
user avatar
0 votes
0 answers
30 views

How to calculate the orthogonality error between sine and cosine wave?

As the picture below(assume the magnitude is the same),the zero-crossing points of the SIN and COS signals do not occur at the precise distance of 90°.So I want to figure out the φ which is φx-φy. ...
user avatar
0 votes
0 answers
63 views

Doubt from permutation [closed]

Let $Mn=(0.a1.a2....an-1.an)$ be set of fractions such that ai=0 or 1 for i belongs to (1,2,....n-1) and an=1. If Tn and Sn be number and sum of all elements inn Mn then find lim $n \to _\infty$ Tn/Sn ...
user avatar
  • 45
5 votes
2 answers
108 views

Show that $ \binom{n}{i\;j\;k} \le \binom{n}{m\;m\;m} $

Is it true that for integers $i+j+k= 3m = n$ where $i , j, k , m , n\ge 0$ the inequality holds ? $$ \binom{n}{i\;j\;k} \le \binom{n}{m\;m\;m} $$ I tried to show $$ \frac{n!}{m!m!m!} \Big/ \frac{n!}{...
user avatar
  • 335
4 votes
0 answers
30 views

What is the probability of two people of the same race randomly sitting next to each other in a room?

Imagine there are four people, two of them are white, and two of them are asian. There are 2 chairs on one side of a room and 2 on the other side. Everyone is randomly assigned a seat. What is the ...
user avatar
2 votes
1 answer
22 views

Does the filter, $F$, on $S$ exist such that $p,q\in S$ and $p,q\in \lim{F}$

Consider two points $p,q\in S$ with $p\ne q$. Is it possible to find a filter, $F$, on $S$ such that all neighborhoods of $p$ and $q$ are contained in $F$? I would assume that when $p\ne q$ then, in ...
user avatar
  • 157
0 votes
2 answers
45 views

Do two points have the same neighborhoods if all their neighborhoods intersect?

Consider a topological space $(M,\mathscr{M})$ and $p,q\in M$. We suppose that for any two neighborhoods $N_p$ and $N_q$ we have that $$\tag{1} N_p\cap N_q\ne\emptyset $$ But since this includes the ...
user avatar
  • 157
-3 votes
0 answers
52 views

Graph Theory example question [closed]

Question: A connected graph with 7 vertices and 7 edges that contains a cycle of length 5 but does not contain a path of length 6. Does this graph exist?
user avatar
  • 5
0 votes
0 answers
22 views

Determine the distribution of the number of cars in the highway during a two hour period. [closed]

In a highway vehicles are passing according to a Poisson process having a rate of $300$ per hour. Suppose each vehicle is a car with probability $86 \%$ and at truck with probability $14 \%$. $(a)$ ...
user avatar
  • 157
0 votes
0 answers
18 views

Similar Theorems to Hall's Theorem on Bipartite Graphs

By Hall's Theorem, a bipartite graph $G$ with vertex sets $V_1$ and $V_2$ contains a complete matching from $V_1$ to $V_2$ if and only if it satisfies Hall's condition $|\{v\in V_2: uv\in E ~\text{for ...
user avatar
0 votes
0 answers
59 views

Struggling with how to solve Proof by Induction [closed]

If we formally define the length function $f(w)$ of a string $w=w_1w_2\cdots w_n$ (where $n\in \mathbb{N}$ and $\forall i=1,\ldots ,n$, $w_i\in \Sigma$) as if $w=\varepsilon$, then $f(w)=0$. if $w=au$...
user avatar
3 votes
1 answer
43 views

A confusion on $\beta\eta$-reduction

Recently I've started exploring lambda calculus, and currently I'm tackling the next exercise: Prove that if $M =_{\beta\eta} N$, then $FV(M) = FV(N)$, Where $FV(P)$ stands for free variables in the ...
user avatar
0 votes
1 answer
52 views

Is the topological space Hausdorff ($T_2$)?

Consider the prime numbers $\mathbb{P}$ and the topology $$ T=\{\{\text{prime numbers not dividing }n\ \} | \text{ where } n\in \mathbb{N}\cup\{0\}\} $$ My lecture notes state that this topological ...
user avatar
  • 487
0 votes
1 answer
25 views

Is it possible to obtain rotation or transposition with following rules?

I have been trying to solve a problem in which I faced this question which I need to answer to solve my problem. Any help or suggestions or references would be helpful ? Given a sequence of length ...
user avatar
  • 62
-3 votes
0 answers
31 views

which X solves: $X \oplus 24 = X$ [closed]

which X solves the following equation? $X \oplus 24 = X$ I tried many numbers and nothing seems to solve it... Update: $X$ is a natural number and $\oplus$ is bitwise XOR
user avatar
  • 1
0 votes
0 answers
10 views

Z-score picking mean and standard deviation

I'm given a question where I need to find the z-score for number of school areas per 1000 people. I have a list of school areas and a sum of people living in each area. I'm struggling on what my mean ...
user avatar
1 vote
1 answer
42 views

Convergence of a series constructed from the elements of $\mathbb{Z}^k$

Let $\mathbb{Z}$ be the set of integers. For $z = (z_1, \ldots, z_k) \in \mathbb{Z}^k$, $k \in \mathbb{N}$, let $|z|_1 := |z_1| + \ldots + |z_k|$ denote the $l_1$-norm of $z$. Is it true that $$ \...
user avatar
  • 93
0 votes
0 answers
35 views

Are all connected graphs with degree sequence $(2,2,4,4,6)$ Hamiltonian?

Are all connected graphs with degree sequence $(2,2,4,4,6)$ Hamiltonian? I have the following few observations: Note that there are only $5$ vertices but the highest degree is $6$. Hence the graph is ...
user avatar
  • 11.9k
0 votes
0 answers
21 views

If asked to use the parity check equations to work out the minimum weight of Code word C. [closed]

So I know that there is 4 independent columns .I am trying to prove that all codewords except 00000000 and 11111111 has a weight of 4.The matrix below is my parity check matrix. I have coded something ...
user avatar
0 votes
0 answers
10 views

SHAP values for Binary Classification

I'm trying to understand the inner workings of how SHAP values are calculated for Binary Classification. The formula for calculating each SHAP value is: $$ \phi_i = \sum_{S \subseteq F \setminus {i}} \...
user avatar
  • 1
0 votes
1 answer
18 views

English to predicate- and vs imply [duplicate]

"Some student in this class hass taken a course in java". First we decided that U is domain. we defined S(x) to be x is student in class. And J(x) to be x has taken java. The solution is :$\...
user avatar
  • 1
0 votes
0 answers
11 views

What does it mean for a set of points to be affinely independent in the context of range spaces?

For some background, there are many range spaces with finite VC-dimension that arise naturally in discrete and computational geometry. One example is the set of all points in d-dimensional Euclidean ...
user avatar
0 votes
1 answer
35 views

Arranging Binaries!

Today I was working on a problem, for which I think there are two possible answers to it, the question is we need to Arrange five $0$'s and five $1$'s such that no two $0$'s come together and no two 1'...
user avatar
0 votes
1 answer
62 views

I want to find primes $p$ where $p-1$ is smooth [closed]

I'm using the Pollard's $p-1$ method but for some numbers this method won't work. For example for: $n = 436916347656251$. $$n - 1 = 2 \times 5^{10} \times 7^5 \times 11^3$$ But Pollard's algorithm ...
user avatar
1 vote
1 answer
61 views

Arrange N unit squares in form of a grid such that number of rectangle is maximum?

You are given N square tiles of dimension 1×1. You have to arrange them in form of a grid such that total number of rectangle (of all possible dimensions) is maximum. Hollows within the grid are not ...
user avatar
1 vote
1 answer
42 views

Why does the method of inclusion/exclusion give the wrong answer when finding the number of integers b/w 1 and 10 that are not divisible by 2,3 or 5?

Let $S=\{1,2,\dots, 10\}$. METHOD 1: I'm first counting the integers that are divisible by $2, 3$ or $5$ in $S$ and then subtracting from the total as follows: Let $A, B, C$ be the set of integers ...
user avatar
  • 672
4 votes
2 answers
63 views

Proving an identity relating the number of linearly ordered partitions to Stirling numbers

For $n,k\in N_0$, let $L(n,k)$ be the number of ways a set of $n$ elements can be partitioned into $k$ nonempty linearly ordered subsets. I want to prove that for $n,k\in N_0$, $L(n,k)=\sum_{i=0}^nc(n,...
user avatar
0 votes
0 answers
21 views

Barycentric rational interpolation

Could you explain me how this formula is applied and calculated with steps for nodes: {{1, 3}, {2, 5}, {4, 4}, {5, 2}, {7, 1}}, and row=2 Correct result is: f(2.5)=5.425 formula My algorithm is: ...
user avatar
3 votes
1 answer
106 views

Find the number of ways of tiling a $3\times n$ rectangular grid with $2\times 1$ dominoes

I'm trying to find the number of ways $(a_n)$ of tiling a $3\times n$ rectangular grid with $2\times 1$ dominoes, where rotation is allowed. I want to find a recurrence relation for $(a_n)$ and an ...
user avatar
8 votes
3 answers
145 views

Find the number of elements in $\{0,1\}^n$ with no more than three $1$'s or three $0$'s in a row

I'm trying to find a general formula for the number of elements $s_n$ in $\{0,1\}^n$ with no more than three $1$'s or three $0$'s in a row, where $n\geq1$. I calculated $s_n$ for small values of $n$ ...
user avatar
0 votes
1 answer
26 views

Why is this step required in the proof of sum of first $n$ odd numbers using the Well Ordering Principle?

I came across this question while doing $\text{6.042J}$ from MITOCW. I have a doubt in the part c, namely, why do we need to manipulate the formula in that way? Here is my solution so far to the ...
user avatar
  • 1,370
1 vote
1 answer
30 views

Why only odd cycles make problems when searching for augmenting paths to improve the matching(->blossom algorithm)?

I don't understand why only the odd cycles in a graph make problems, when searching for augmenting paths. As far as I understood in an odd cycle the search algorithm(bfs for example) kind of splits in ...
user avatar
  • 319

1
2 3 4 5
608