Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
16 views

Optimal Strategy in a money compounding model where one's interest is only consolidated at a fee

Say I have my main account with $ \$ 10000$ that gains interest at a rate of .1% a day. The interest collects in a separate account and I have to pay a certain fee, say $\$1$, to consolidate this ...
0
votes
2answers
40 views

Elegant Proof that $m | xn \implies \frac{m}{(m,n)} | x$ [duplicate]

I have a proof that shows $m | xn \implies \frac{m}{(m,n)} | x$ which leans heavily on prime factorizations. Is there a more straightforward proof?
0
votes
2answers
19 views

Do I need to prove both directions of this if and only if statement for sets?

I need to show that $S{1} = S{2}$ iff $$(S1 \cap \bar{S2}) \cup(\bar{S1} \cap S2) = \emptyset$$ Ok So I'll show that $1.$ if $S{1} = S{2}$ then $(S1 \cap \bar{S2}) \cup(\bar{S1} \cap S2) = \emptyset$...
0
votes
0answers
18 views

laws of logic - having issues with identifying if some propositions and what law is used

(~q∨q)∧r⇔(q∨~q)∧r (q∨~q)∧r⇔r∧(q∨~q) To me looking over all the laws the only one that I think that makes sense to me is the Commutative law. Unless I am just way ...
0
votes
0answers
32 views

Proof of Leibniz formula for determinants

im trying to understand the following proof but it is not very clear for me, can someone walk me through it? Proof Thank you in advance
1
vote
3answers
29 views

Prove that a NxN grid can be colored using n colors such that each color appear once each row and column

Just like a simpler Sudoku game, given n, show that nxn grid can be colored using n colors so that each color appears once for each row/column. I see that each row/column forms a complete graph so ...
0
votes
0answers
25 views

Can someone explain how should i solve a multi variable chinese remainder equation

I have the following equations. $15x + 7y \equiv 46 \pmod {53}$ $ 34x - 10y \equiv 11 \pmod {67} $ $ x\equiv y\equiv0 \pmod 7$ I have no idea how to solve this, I have only solved one variable ...
0
votes
0answers
6 views

Way of predicting change in gradient of line following matrix transformation?

I recently learnt about dominant and repulsive eigenvectors. I noticed that the farther a line is initially from the dominant (though still closer than to the repulsive eigenvector), the more dramatic ...
0
votes
0answers
11 views

Directed Graphs

I'm currently struggling with directed graphs. What does it mean when an allocated graph has a minimal vertex of p E P? What's a minimal element? What does it mean if something is acyclic and has a ...
2
votes
2answers
90 views

For $(a + b + c + d)^{10}$, how many terms have coefficients that aren't divisible by $5$?

$(a + b + c + d)^{10}$ how many terms have coefficients that aren't divisible by $5$? I know that each of the following $a^{10}, b^{10}, c^{10}, d^{10} $, their coefficient is 1, which isn't ...
0
votes
1answer
26 views

Find the time gap between two vehicle based on km/h of the vehicle

I am currently researching on VANET for identifying the road capacity based on vehicle moving speed. Below is my question, If a car moving on 8km/h and distance to the next car is 15 meters, what ...
0
votes
2answers
26 views

Permutation from left to right of $140$ objects

I've been stuck on this problem for quite some time now, I can't seem to find a video or such where it references permutations in a specific order of left to right. I have no idea how to set this ...
3
votes
2answers
39 views

finding the equivalence classes of the relation R

Find the equivalence classes of the relation R = {(0, 0),(1, 1),(1, 2),(2, 2),(2, 1),(3, 3),(3, 4),(4, 3),(4, 4)} on the set A = {0, 1, 2, 3, 4}. How do i solve this question. I'm attempting to ...
0
votes
0answers
28 views

Build up a matroid using a “rank-like” function

It is not hard to show that given a matroid ($E, L$) and a defined rank function, $L$ is exactly those subsets whose rank is equal to the size. The following question is about how to build up a ...
2
votes
0answers
16 views

Construct a rank-3 matroid using rank-2 flat

Let $E$ be a finite set with size bigger or equal to 3. Let $L$ be a collection of subsets of $E$ such that: $2 \leq |A| < |E|$ for any $A \in L$ $|A \cap B| \leq 1$ for any $A, B \in L$ Now show ...
0
votes
1answer
28 views

Simple percentage problem driving me crazy

Ok, so lets say to board a cruise ship it would usually take $60$ to $90$ minutes. Now it takes only $10$ minutes. In percentages this is: $60-10 = \frac{50}{60} = 83.3\%$ reduction (ie. from $60$ ...
0
votes
1answer
9 views

Proof - Possibility to transform all vertex’s value to 1

A big equilateral triangle is made up of smaller equilateral triangles. The relation is for n order of the bigger triangle, the number of inner triangles are n^2. Example of such a triangle with n = ...
1
vote
1answer
31 views

Expected value of the number of different numbers drawn in 37 rounds of roulette?

I need help with this problem. What is the expected value of the number of different numbers drawn in 37 rounds of roulette? Is this possible to interpret as the number of records? So the expected ...
2
votes
2answers
30 views

Logical Equivalences with English Statements

Showing two statements $p$ and $q$ are logically equivalent is to show $p \Longleftrightarrow q$. I understand this, however I think when looking at english statements showing whether or not they are ...
0
votes
1answer
21 views

Parity check matrix H given; justify that C can correct one error, does a word belong to C and correct an error. [on hold]

I'm trying to learn about error correcting codes, and I have this question from a previous exam. Now I'm a little bit confused because I can't seem to wrap my head around this one, could I please get ...
1
vote
1answer
34 views

Balls between boxes equation

I have a practice question I don't know how to answer past part (a) Consider nonnegative integer solutions of the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 26$ (a) How many different ...
0
votes
0answers
14 views

Placing books on shelves using generating functions of recursive relation

Let $t_n$ be the number of ways to arrange $n$ books on two bookshelves such that each shelf contains at least one book. Assume books are distinguishable and order matters. Find a recursion ...
1
vote
5answers
51 views

Prove that if $A \cap C \subseteq B \cap C$ and $A \cup C \subseteq B \cup C$ then $A \subseteq B$

I'm having trouble figuring out what to do in this problem. I know that if $A \subseteq B$ then $A \cup B = B$ and $A \cap B = A$, but I can't wrap my head around on what to do with the given ...
0
votes
1answer
38 views

What kind of math should I learn before I tackle policy search PEGASUS research paper by Andrew Ng?

I provided the link below https://ai.stanford.edu/~ang/papers/uai00-pegasus.pdf the paper was referenced in the AI: Modern Approach book, and I would like to dive in depth into it. But my math is ...
1
vote
1answer
29 views

Logical statements with multiple quantifiers - discrete math

So I have some questions below that I don't understand because I'm struggling with solving questions that involve multiple quantifiers. I was wondering if someone could walk me through how to do these?...
0
votes
1answer
28 views

Prove these differently written de morgan laws

We define $$\overline{\bigcup_{p\in P} Sp} =\bigcap_{p\in P} \overline{Sp}$$ and $$\overline{\bigcap_{p\in P} Sp} =\bigcup_{p\in P} \overline{Sp}$$ Which are just another way to write de morgans laws....
0
votes
5answers
41 views

Simplify (p v (r v q)) ∧ ~(~q ∧ ~r)

I understand that ~(~q ∧ ~r) simplifies down to (q v r), but I don't understand how the answer to this question is ...
6
votes
2answers
41 views

What would be the number of inequivalent $6$-colourings of the faces of a cube?

Consider the different ways to colour a cube with $6$ given colours such that each face will be given a single colour and all the six colours will be used. Define two such colourings to be equivalent ...
0
votes
0answers
26 views

When give number ranging from 1 to N. Find sum of left and right indices.

Considering a set. Now given numbers from 1 to N and Q queries. In each query a number p is added to the set and we have to output sum of left and right indices of all good ranges. Good Range - ...
0
votes
0answers
35 views

In an experiment of rolling a die $5$ times, event $A$ is considered success if you get number 5 or number 6. [on hold]

In an experiment of rolling a die $5$ times, event $A$ is considered success if you get number 5 or number 6. Calculate: a) Probability that event $A$ is success $4$ times. b) Probability of not ...
0
votes
0answers
14 views

Discrete State Space Representation

I'm looking at a continuous state space system and I want to discretize it. I've seen what others have done that works. However, I saw this method but the justification was not given. Please can ...
0
votes
0answers
9 views

Further reduce a sample size [on hold]

I have a total sample of 233 after applying the Krejcie and Morgan formula. How best I can further reduce that sample size down to somewhere between the range of 140 - 150
0
votes
0answers
37 views

Difference between 'Only' and 'Every' Keyword in Mathematical logic

Represent these two statement in first order logic: A) Only Alligators eat humans B) Every Alligator eats humans Is Every represents ≡∃ and Only represents ≡∀ ?? Can we differentiate it with ...
0
votes
2answers
27 views

Function design: “stateless” recursive asymptotic to 1

I'm trying to design a function with the following requirements: it will be implemented in an electronic device, where it will be called a discrete number of times. However, it will only be given the ...
1
vote
1answer
30 views

Question regarding ternary relation

How can the type of the following ternary relation $R$ on $\mathbb{N}$ (set of all integers) be determined whether it is reflexive, transitive or symmetric ? $$ R = \{ a, b, c \in \mathbb{N} : a \...
1
vote
1answer
26 views

$G$ is a forest if and only if every connected subgraph is induced

G is a forest -> every connected subgraph of G is induced Definition of a induced subgraph: for x,y in V(F), xy is in E(F) if and only if xy is in E(G) Proof: Be F a connected subgraph of G. Suppose ...
3
votes
3answers
49 views

Do i need to find the elements of all powerset to answer such questions?

Let $M = \{\{2\},2,5,7,0,\{23\}\}$ . Q1. $\{7, \{23\}\} \in \mathcal{P}(M)$? A1. Since they are elements in m then they are true. Q2. $\{\{2\},\{5,7\}\} \subseteq \mathcal{P}(M)$? However here I am ...
1
vote
0answers
16 views

Number of permutation matrices within a distance of a given matrix

Given a matrix $M$, and a permutation $P_0$, is it possible to easily count, or easily approximately count, the number of permutation matrices $P$ that satisfy $\|P - M\| = \|P_0 - M\|$? What about ...
1
vote
1answer
35 views

Convert a real range to an integer range.

Let's say that we have a set of integers in the range $[1, 4]$. Now, I have a function that will calculate a distance between two vectors, and this function returns a real number in the range $[0, 1]$....
0
votes
2answers
30 views

Set representing The positive integers which are a multiple of 6?

I know this is a very trivial question, but I'm probably missing something So the set is: $\{n\mid n=2m\, \mathrm{for \,some} \,m \in \Bbb N,\mathrm{and}\,n=3k\, \,\mathrm{for \,some}\, k \in \Bbb N\...
1
vote
1answer
46 views

I don't understand one line in problem to prove $|2^S| = 2^{|S|}$

Problem to prove by induction: If $ S $ is a finite set, then $\vert 2^S \vert = 2^{\vert S \vert}$ Proof: Induction on size of $S$, call it $n$ , $n \ge 0$. Base case: Suppose $n=0$. Now, $|2^S| =...
2
votes
0answers
21 views

Formation of commissions

Of a group of seven women, Mary is one of them, and of four men, John is one of them. How many commissions can be formed with any number of people, provided there are the same number of men and women? ...
2
votes
6answers
70 views

What is the coefficient of $x^5$ in $(1+x+x^2+x^3+x^4+x^5)^{17}$?

I figured that $(1+x+x^2+x^3+x^4)^{17} = (1-x^6)^{17}*(1-x)^{-17}$ but don't know what else to do. I would really appreciate any help
1
vote
1answer
25 views

Binomial coefficients with variable in exponent

I need to calculate the coefficient of a specific term in a binomial, but how do I do that if the exponent has a variable in it? For example: Find the coefficient of $x^n$ in the expansion of $(4x + ...
1
vote
1answer
23 views

Let $P(n)$ be : the sum of the first odd natural numbers equal $n^2$. Express in summation notation and use induction.

I presented the first odd $n$ natural integers as $2n+1=n^2$. In summation notation I just factored this into $(n-1)(n-1)$. I am unsure whether this is correct and also I don't know how to carry out ...
0
votes
2answers
48 views

What are sets, matrices, …etc?

I am writing a CS research paper where I'm using sets, matrices, and vectors to solve a particular problem. I have two sets, $R$ and $T$, that will be used throughout the entire solution, and a couple ...
1
vote
1answer
33 views

Determine whether the following expression is a tautology, a contingency, or a contradiction by using the logical equivalences

As a practice problem, I'm asked to determine whether the following proposition is a tautology, contradiction, or contingency through the use of logical equivalences. I get how to determine what ...
0
votes
1answer
35 views

Demonstration with Vandermonde's Identity

VANDERMOND’S IDENTITY: Let m, n, and r be nonnegative integers with r not exceeding either m or n. Then $${m+n \choose r} = \sum_{k=0}^{r}{ {{m}\choose{r-k}} { {n} \choose {k} } }$$ The exercise ...
2
votes
2answers
49 views

In each cell of $n$x$n$ is a number so that in every $3$x$3$ subtable the sum of numbers is negative and the sum of all numbers is positive.

In each unit cell of a $n\times n$ table we have a number so that in every $3\times 3$ subtable the sum of numbers is negative and the sum of all numbers is positive. For which $n\geq 4$ we can have ...