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.

1
vote
1answer
25 views

Prove that the group of moves of the Rubik’s cube is not abelian.

I'm currently working in the following excercise: Remember that $G$ is the group of moves of the Rubik’s cube. Prove that this group is not abelian. I'm starting from picking two moves $M_1$ and $...
0
votes
1answer
11 views

Graphs and Networks - A Walk

As a walk can repeat an arc, i was wondering if it could repeat an arc consecutively and still be classed as a walk, e.g. A-B-A-C is this a walk?
0
votes
1answer
15 views

Arrangements and Grouping

Find the number of ways in which a team of 3 men and 2 women can be selected from a group of 6 men and 5 women? Would the answer just be 6C3 x 5C2 ?
1
vote
1answer
28 views

Showing that generating function coefficients agree with recurrence relation

I have the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with $a_0 = 1, a_1 = 0$. The solution to this is $a_n = \frac{4^n}{5} + \frac{4(-1)^n}{5}$. The generating function is $g(x) = \frac{1-3x}{1-...
0
votes
2answers
17 views

Find number of different strings that can are formed from {a,b,c}

I need to find the number of different strings that need to be formed from {a,b,c} in which there needs to be at least one from each letter. The question is to find the number of strings with length 5....
1
vote
0answers
30 views

Solve recurrence with characteristic polynomial

The equation $$a_n=7\cdot a_{n-1} -7\cdot a_{n-2}+175\cdot a_{n-3}+450\cdot a_{n-4}+(5+13\cdot n)\cdot9^n \enspace,$$ where $a_0=148, a_1=144, a_2=-55, a_3=-61$. I assume that a solution will look ...
0
votes
1answer
28 views

A string of odd and even numbers to group in three sets using combinatorics?

I need help with combinatorics problem. The task is this: There are 9 numbers which are: 1,3,5,2,4,6,8,10,12. I need to group these numbers in 3 sets with 3 elements in every set, but there is one ...
-2
votes
2answers
34 views

A question on the properties of a relation

Suppose we have some relations on the set [1,2,3,4]. $R_{1}=\{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)\}$ $R_{2}=\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$ $R_{3}=\{(2,4),(4,2)\}$ $R_{4}=\{(1,1),(2,2),(3,3),...
0
votes
0answers
42 views

Where can I find examples of absolutely detailed formal mathematical proofs?

I know that many mathematical proofs omit many explanatory logical rules of inference and principles of deduction for the sake of conciseness (for example, most proofs refrain from expressing the use ...
1
vote
1answer
38 views

What is the name of the rule that allows us to infer the truth of an equation from the truth of another equation?

I am wondering if there is a particular named rule or principle in mathematics/formal logic (that can be listed as justification in a formal proof) that allows one to conclude the truth of an equation ...
1
vote
2answers
27 views

Discrete mathematics - understanding proof by induction

So I have an example of a proof that my teacher used induction to solve, but I'm having trouble understanding the inductive step in the second slide. So I get the part where they substitute k+1 in the ...
0
votes
2answers
48 views

A contradiction arising due to set-builder form.

I have noticed a kind of contradiction arising due to set-builder form involving universal set$(U)$ while I was performing operations on set theory. Here it is - Let us consider an arbitrary non-...
0
votes
2answers
22 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
56 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{...
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
29 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
20 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
57 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
34 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
36 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
21 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
2answers
52 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
65 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
50 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
155 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
38 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
51 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
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
43 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
30 views

Polynomials in the Pancake problem

I noticed something interesting in this table. The columns can be expressed by polynomials of degree k. I toke the first $k+1$ numbers from each column and used Lagrange's interpolation. Surprisingly, ...
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
23 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
47 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
47 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. ...