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
2answers
20 views

Composition of onto and one-to-one functions

Question : Let f: X → Y and g: Y → Z be two functions. Is it possible that f is not onto and g ο f is onto? Justify your answer. If the answer is "yes", give a specific example for f and g. Not ...
0
votes
1answer
30 views

Question regarding supremum of partially ordered sets

I have encountered a question while i was practicing the topic 'upper and lower bound of partially ordered sets'. Let $\mathbb{Q}$ be the set of rational numbers. Let $$ B = \{ x \in \mathbb{Q} : x ...
1
vote
1answer
13 views

Well ordering principle proof

Following is from MIT OCS Mathematics for Computer Science book Every positive integer greater than one can be factored as a product of primes. The proof is by well ordering. Let $C$ be the ...
1
vote
2answers
28 views

Prove that every 3-regular (simple) graph has Vertex bipartition s.t. each vertex has at most deg=1 within partition class

Given a $3$-regular graph $G$, I want to show that I can partition the Vertex set into sets $A,B$ such that each vertex has at most one neighbor within its partition class. I have come up with two ...
0
votes
0answers
17 views

Study for Ternary and N-ary relations: books and practice material recommendations?

I have learnt the topic binary relations and its types and i am curious about ternary and N-ary relations and i want to learn about there properties. So please can I be recommended books and online ...
-1
votes
2answers
54 views

Rewriting expressions using $\Sigma$

How would you write the following using sigma $\Sigma$ notation? $$\dfrac{1}{5^4} + \dfrac{1}{8^9} + \dfrac{1}{11^{16}} + \dfrac{1}{14^{25}} + \cdots + \dfrac{1}{29^{100}}$$
-2
votes
1answer
33 views

Rewriting expressions using ∑?

How would you write this expression using $\sum$ notation? $(x + 1)(x − 3)(x + 5)(x − 7)· · ·(x + 101)$ Thanks!
0
votes
1answer
15 views

Inclusion-exclusion with anagrams

How many are the permutations of the letters of the word PROPOR in which are not consecutive letters equal? How to approach this problem through the principle of inclusion-exclusion?
0
votes
1answer
26 views

Inclusion-exclusion with distribution

In how many ways can we distribute $15$ different books to $15$ children (one for each one) then collect the books and again distribute so that no child will get the same book previously received? ...
0
votes
1answer
33 views

Principle of inclusion exclusion

In a class of 30 children, 20 studied Portuguese, 14 studied English and 10 studied French. If 8 study none of these 3 languages ​​and none study the 3 languages, how many children study English and ...
1
vote
1answer
20 views

Calculate a function using the fact that is multilinear and alternant

I'm currently working in the following excercise: Be $f$ defined in $\mathbb{R}^4 \times \mathbb{R}^4 \times \mathbb{R}^4 \times \mathbb{R}^4$ a function, calculate it in $$ \begin{pmatrix} ...
2
votes
1answer
44 views

University clubs - Counting two ways

Consider a university with 2000 male and 2000 female students. Suppose that none of the 4000 students signed up for 100 or more clubs (Each student signed up for at most 99 clubs). You also know that ...
0
votes
1answer
31 views

Areas of Applied Combinatorics

I love combinatorics, but do not really want to do pure math exclusively. I like the format of pure math (that is the theorem-proof-theorem-proof format), but would also like what to do research that ...
0
votes
0answers
18 views

Flipping coins - Counting in two ways [duplicate]

There are 100 coins, all of them showing heads. One turn consists of flipping exactly 93 coins (from heads to tails or the other way around). How many turns are needed so that all coins are showing ...
0
votes
0answers
18 views

Simultaneous system of recurrence… [on hold]

Solve the simultaneous system of recurrences $$a_n = a_{n−1} + b_{n−1}$$ $$b_n = b_{n−1} − a_{n−1}$$ with initial conditions $a_0 = 1$ and $b_0 = 2$.
1
vote
1answer
60 views

$\,m = {\rm lcm}(a,b)\iff a,b\mid m\ \, \& \ \gcd(m/a,m/b)=1$

For $a \in\Bbb N$, $b\in\Bbb N$, $μ \in\Bbb N^*$, we have $μ = \operatorname{lcm}(a,b) \iff μ = αa\text{ and }μ= βb$ and $\gcd(α,β)$ is $1$ Till now I succeeded to prove the left $\Rightarrow$ ...
0
votes
2answers
49 views
3
votes
2answers
28 views

Circular permutation with constraints

If four boys and four girls play tricks, how many ways can they join hands, provided that at least two girls are together? My plan is to determine the circular permutation of the eight (boys + girls),...
2
votes
4answers
154 views

Question in discrete mathematics about group permutations

So I have this question and i got pretty much stuck. Let $\pi$ be the permutation $$\pi= (1 2 3 4 5 6 7)\circ(1 3 5 7)\circ(2 4 6)$$ of the set $\{1,2,3,4,5,6,7\}$. Write $\pi$ as a product of ...
-1
votes
6answers
37 views

How to prove that $ (A \cap B) \cup (A \cap \overline {B}) = (A \cup B) \cap (A \cup \overline {B}) = A $

I got stuck trying to prove that $ (A \cap B) \cup (A \cap \overline {B}) = (A \cup B) \cap (A \cup \overline {B}) $ and vice versa.
2
votes
2answers
45 views

Question regarding partially ordered sets

I have encountered few questions while reading the book 'Modern Algebra'. Let $\mathbb Q$ be the set of rational numbers. Let $B = \{ x : x\in\mathbb Q,\sqrt2 < x < \sqrt3 \}$. How it can ...
0
votes
0answers
24 views

Number of eulerian paths in an undirected connected graph between two given vertices?

Given a undirected connected graph G(V, E). Provide an optimal algorithm, which finds the number of eulerian paths between vertex 1 and vertex |V|. I was thinking about matrix multiplication, but I ...
0
votes
1answer
22 views

Cardinal number of a set comprised of the multiplication of 2 other sets.

I have the following question in my assignment: Find the cardinal number of the following set: $\{a \cdot b \mid a \in \{1, 2, 3\}, b \in \{1, 2, 3\} \}$ I am wondering if this is asking for the ...
0
votes
1answer
42 views

Pigeonhole Principle: Showing that there are at least two holes with the distance between their centres less than $10\sqrt{2}~\text{cm}$

I'm having trouble regarding the application of the Pigeonhole Principle. I understand $f:A \to B$ but I don't know how to apply it in questions that require it. Example: Ten bullets are all shot on ...
1
vote
0answers
25 views

Polynomials in the Pancake problem

I noticed something interesting in this table. The columns can be expressed by polynomials of order k. I can't check if it is still a polynom for $k=7$. $$k=0: 1$$ $$k=1: n-1$$ $$k=2: n^2-3n+2$$ $$k=3:...
1
vote
6answers
90 views

Show that $2 - \sqrt{2}$ is irrational

I suppose $2 - \sqrt{2} $ is rational. so $$2- \sqrt{2} = {a/b} $$ where a,b are integers and gcd(a,b) = 1. $$\text{Step 1. } 2 = (a/b)^2 \text{ //squared both sides }$$ $$\text{Step 2. } 2b^2 = a^2 \...
0
votes
2answers
22 views

Uniform discrete distribution - time to draw

I have a question about the basic definition of discrete normal distribution. Let's assume I have a machine that draws a number ranging from 1 to 3 from a uniform discrete distribution (the ...
0
votes
0answers
42 views

Prove that every planar graph is the union of at most $5$ acyclic graphs.

Prove that every planar graph is the union of at most $5$ acyclic graphs. Reminder: As union of two graphs $G_1(V_1, E_1)$ and $G_2(V_2, E_2)$ we consider the graph $G(V_1\cup V_2,E_1\cup E_2)$ ...
-3
votes
1answer
25 views

Help! How to solve the problem [on hold]

Have no clue how to solve this
0
votes
1answer
26 views

Counting combinations for specified requirement

i want to know the regular way to count something like this assuming i have 2 of Xs and 2 of Ys. I want to know the total number of combination for these input. For this example it should be xxyy ...
1
vote
2answers
32 views

$ S = \{(x,y) \in B \times B | (\exists a,b \in A)[f(a)=x, f(b)=y, (a,b) \in R ] \} $ with R transitive, is S transitive?

Be the funtion $ f: A \to B $ and $ R \subseteq A \times A $ a transitive relation. Be the relation $ S \subseteq B \times B $ defined as: $ S = \{ (x,y) \in B \times B | (\exists a,b \in A)[f(a)=x, ...
0
votes
0answers
27 views

Cartesian product of R2 x R2 [on hold]

I need to work with a relation on $\mathbb{R}^2$ defined by $(x_1,y_1)R(x_2,y_2)$ with some condition. So far I've only done relations and Cartesian Products with single-dimension data (e.g., a ...
0
votes
0answers
26 views

Collection of subsets with more than $n\choose n/2$ elements must have set contained in another

I have a set $A$ of size $n$. I have a collection of subsets of $A$ that contains $k>{n\choose n/2} $ elements. I want to prove that there are two sets $B, C$ in this collection such that $B\subset ...
0
votes
3answers
24 views

Countability of set of binary strings of finite length

So I was thinking about the countability of the set of binary strings of finite length. I approached using two ways. The worst thing is I am getting different answers in both approaches. Here is the ...
0
votes
1answer
32 views

Show that the second player can always achieve a draw in the defined game

currently at it working on my discrete mathematics assignment, where I now have one assignment, that I just can't crack. I feel like I am very close, but miss something critical to it. So, I have the ...
0
votes
0answers
42 views

How do we solve this disassembled rainbow bagel puzzle? [on hold]

https://www.janestreet.com/puzzles/disassembled-rainbow-bagel/ I have been trying to solve this vehemently but to no avail.
0
votes
1answer
34 views

We have a sequencing problem

We have a competition with $9$ different teams (team $1$ to team $9$). They are competing in a round robin contest using $2$ different (venues $A$ and $B$). So every team will play the others once. ...
0
votes
0answers
13 views

Discretizing a function with 0 indexing

I have already asked this question and got it answered : Discretizing a mathematical equation. Now i want to adjust the indexes, i.e originally it was asked for natural numbers correspondence i.e $\{x,...
1
vote
0answers
24 views

What units is my mean squared error if I center and scale my training data?

I have a KNN model that I used to predict the close price on houses. ...
0
votes
1answer
22 views

Show that if A is a Subset of B, then A is dominated by B

Definition of A is dominated by B: There is an injective function from a to B. Remark: For finite sets A,B A is dominated by b is equivalent to the cardinality of A is less than or equal to B Proof: ...
7
votes
1answer
56 views

Graph with the condition that every vertex is connected to at least n other vertices.

Problem: (Adrian Tang) $G$ is a graph with $2n+1$ vertices. In $G$, for every set $S$ of at most $n$ vertices, there is one vertex outside of $S$ that is adjacent to every vertex in $S$. ...
2
votes
3answers
99 views

Prove that $\sqrt{5521}-1$ is an irrational number

I'm stuck on a textbook problem where I'm asked to prove that $\sqrt{5521} − 1$ is an irrational number by contradiction and prime factorization. I tried following steps the teacher did in her class ...
1
vote
4answers
70 views

Mathematical induction proof $n^4-1$ is divisible by $16$ for all odd integers $n$

I'm stuck towards the end of proving this, here's my attempt: $P(3) = 80/16 = 5$, True $P(k) = k^4-1$ $P(k+1)= (k+1)^4-1$ Expanded $= k^4+4k^3+6k^2+4k+1-1$ This is where I am stuck at. Sorry for ...
2
votes
1answer
46 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 ...
1
vote
2answers
53 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? Edit With this question, I was looking for a proof ...
0
votes
2answers
26 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
20 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
38 views

Proof of Leibniz formula for determinants [on hold]

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
0
votes
1answer
18 views
1
vote
3answers
45 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 ...