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.

learn more… | top users | synonyms

1
vote
1answer
23 views

Order of statements in implication

The question is from Excercise 13 of part 1.4 in Rosen's "Discrete Mathematics and Its Applications" (5th edition): "let M(x,y) be "x has sent y an e-mail message", where the universe of discourse ...
1
vote
4answers
35 views

Discrete Maths Set Theory: Prove that $\left|(X^Y)^ Z\right|=\left|X ^{Y \times Z}\right|$.

I need to prove that $(X^Y)^ Z$ and $X ^{Y \times Z}$ are in bijective correspondence. Can anyone please help? EDIT: Chuks's version said: prove that $(X\times Y)\times Z\sim X\times(Y\times Z)$. ...
4
votes
3answers
45 views

Discrete math - Set theory - Symmetric difference: Proof for a given number.

I can't find anything on this topic elsewhere. I'd like to know what keywords/sites I should be using to find what I'm looking for if this is to elementry of a question. (been using discrete math, set ...
-4
votes
2answers
39 views

License Plate problem [on hold]

A license plate contains 7 characters (order matters). Each character may either be an upper-case letter A–Z or a number 0–9. How many license plates. . . (a) contain the string ABC? (b) have at ...
1
vote
5answers
51 views

Proving that that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$

How might I prove that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$? I am not sure the best place to start other than assuming $x\in(R \setminus S)\setminus T$ and trying to ...
0
votes
0answers
15 views

DFT of subdomain of periodic domain

$f(t_i,x_j)$ is a solution of stochastic differential equation on grid. $j=[0,N+1]$, $i=[0,\infty]$ and boundary conditions are periodic: $f(t_i,x_0) = f(t_i,x_N)$ and $f(t_i,x_{N+1}) = f(t_i,x_1)$ ...
0
votes
0answers
21 views

Asymptotical stability of a discrete dynamical system

There is a linear time invariant discrete system, \begin{align} x_{k+1}&=\tilde{A}x_k, \end{align} where $\tilde{A}$ is a block matrix represented by \begin{align} \tilde{A}= ...
-1
votes
1answer
66 views

What is the inverse function of gcd? [on hold]

Let $a,x,c \in\mathbb{Z}$. If $\gcd(a,x)=c$ where $a, c$ are constants and $x$ is a variable, then what values can $x$ take and how to find those values ?
0
votes
1answer
76 views

Find the number of flags of different types using induction

A flagpole is $n$ feet tall. On this pole we display flags of the following types: red flags that are $1$ foot tall, blue flags that are $2$ feet tall, and green flags that are $2$ feet ...
-1
votes
1answer
98 views

Injections, Surjections, Bijections [on hold]

So i was given a question that asks me to determine whether the function is injective, bijective, or surjective. If you answer bijective than determine the functions inverse, domain, and target space. ...
0
votes
0answers
20 views

Repertoire method in solving recurrence [duplicate]

I don't know, how should I start solving this: $$a_1 = 2 \\ a_n = 2a_{n-1} +7$$ using the repertoire method. Could anyone give me an algorithm or explain, how to use this method in this case?
0
votes
3answers
29 views

Proving $a=b \bmod 19$ is an equivalence relation

My question is: $a \equiv b \bmod {19} \iff aRb$ (prove that $R$ is an equivalence relation) Before that, I already know that equivalence relation is when $R$ is reflexive, symmetric and ...
-1
votes
0answers
69 views

Determine whether it is injective, surjective, bijective or neither injective nor surjective [on hold]

The question i was given asked (a) Determine whether it is injective, surjective, bijective or neither injective nor surjective. (b) If you answered "bijective" in part (a) determine the ...
0
votes
0answers
29 views

Application of Havel- Hakami Theorem [on hold]

Definition :Given a sequence $d_1 \geq d_2 \geq \cdots \geq d_n$ called graphical if it is degree of a possible graph. need a proof of the question below. Question : The above sequence is graphical ...
0
votes
1answer
25 views

defining a sequence of numbers L n≥1, and prove something about it

So i was given this question just to try for practice to test our knowledge and i'm really confused on how to go about this question. How should i go about this question, i'm confused with the greek ...
3
votes
4answers
117 views

Proving that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even.

Here is the proof: Let $a,b \in \mathbb{Z}$. Prove that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even. When working these problems, I do try to set them up logically. My ...
-4
votes
0answers
44 views

prove that for any 2n≥2 and any \a ​1 ​​ ,…,a ​n ​​ ∈N, we have the following: [on hold]

So the question I was given goes like this we will introduce a mystery function,P:N→N. We don't know a formula for P (and we won't be able to determine one!) but we do know that P satisfies the ...
2
votes
3answers
74 views

Proving $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$ using strong induction

The question says $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$. Here is my proof by strong induction: Base case: $10\cdot0=0$. Let $k\geq 0$, and suppose that for any $m\leq k$ we have ...
-2
votes
1answer
18 views

Determine the number of strings that can be formed by ordering the letters given. [on hold]

How many strings can be formed by ordering the letters SALESPERSONS if the four S's are consecutive?
3
votes
2answers
41 views

number of triangles determined by a rectangular grid

Suppose we are given an $m\times n$ rectangular grid of lattice points, such as $S=\{(k,l): 0\le k\le n-1,\; 0\le l\le m-1, \;k,l\in\mathbb{Z}\}$, and we want to determine the number of ...
0
votes
0answers
26 views

Is there a theory for cellular automata propagating signals in straight lines?

Is there a theory explaining how a cellular automata can propagate signals in straight lines? For example, this video shows how some "signals" travel down at a diagonal, even though they are composed ...
0
votes
0answers
27 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
0
votes
1answer
47 views

consider a graph of a gameboard

Consider a graph of a game board. Rounds in the game result in a token moved from a game board location to a game board location, possibly returning to the same one. Let the game board location at the ...
0
votes
1answer
43 views

Compose $(1243)$ and $(5)$

Checking my work. In either direction: $(1243)[1] = 2$ and $(5)[2] = 2$, so far we have $(1, 2,\ldots$ $(1243)[2] = 4$ and $(5)[4] = 4$, so far we have $(1, 2, 4,\ldots$ $(1243)[4] = 3$ and ...
0
votes
1answer
12 views

About cycles and the values in the range of a permutation function

Let $f = \{(x_1 y_1), (x_2 y_2), \ldots, (x_n y_n)\}$ be a permutation. A cycle of $f$ is given by $g = (1, f(1), f^2(1), f^3(1) \ldots)$. When counting permutations, we usually drop $1$ and count ...
0
votes
1answer
27 views

Length of substring if we just consider a subdivision in $\log n$ substrings

Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
-2
votes
0answers
39 views

What is elnekiti's triangle? (edited) [closed]

Elementary ceĺular automata shows amazing complex systems such as pascal's triangle is similar to " wolfram rule 90 " , so i looked over youtube searching for extra content and i found this video Here ...
1
vote
0answers
16 views

Multigraphic Degree Sequences

Given a degree sequence $\{d_1,d_2,\ldots,d_n\}$, can I determine in polynomial time in $n$ whether this sequence is multigraphic AND can be realized by a connected multigraph? Looking at this ...
0
votes
0answers
17 views

Integer problem to minimize cuttings

A company has to make 4 items in the given quantities. item1 =4 item 2=2 item3=1 item 4=1 Te surfaces has to be covered in plywood.The company has got 3 ...
0
votes
0answers
31 views

Let $(12)$ and $(23)$ be cycles. Then is $(12)(23)$ a permutation?

The reason I ask this is because sometimes we talk about non-disjoint cycles, for example: $(ab)(bc) \neq (bc)(ab)$. Do we consider $(ab)(bc)$ a permutation where $f(b) = a$ and $f(b) = c$?
-4
votes
1answer
57 views

Prove that there doesn't exist any integer $x \ge 3$ such that $x^2-1$ is prime. [closed]

Prove that there doesn't exist integer $x \ge 3$ such that $x^2-1$ is prime.
-1
votes
2answers
25 views

Properties of a certain binary relation [closed]

$R$ is a binary relation function $(x,y) \in \mathbb R^2$. If $$ R = \{(x, y)\in\mathbb R^2\mid \lfloor x\rfloor = \lceil y\rceil\} $$ then: Is $R$ reflexive, irreflexive or neither Is $R$ ...
1
vote
1answer
26 views

Countability of the set of weighted graphs

Could you help me find the solution for this problem that consists in finding out wether the set of all weighted and finite graph is countable of not? As a reminder, a weighter graph can be seen as a ...
-2
votes
2answers
27 views

Induction problem [closed]

Fibonacci sequence $f_0 = 1~~ f_1=1$ and for every $n >=2 ~~ f_n= f_{n-1} + f_{n-2}$. Prove for all $n >=0$, $f_n <= 2^n$. Currently working on a self taught book but this problem doesn't ...
1
vote
1answer
21 views

Graphically representing relations of ordered pairs

I am having problems trying to picture what this relation of ordered pairs 'looks' like: Let R be the relation on the set of ordered pairs of positive integers such that ((a, b),(c, d)) ∈ R if and ...
1
vote
1answer
14 views

Recurrence Relations for Sequence Counting Hamming Weights

Define $a(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=0, ||x||=k\}|$ and $b(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=1, ||x||=k\}|$ where $||\cdot||$ denotes the Hamming weight of $x$ (i.e. number of non-zero ...
0
votes
3answers
46 views

Proving ${\sum}^n _{i=1}i = \frac {n(n+1)}{2}$ by induction

I am having problems understanding how to 'prove' a summation formula. I have the equation: $ {\sum}^n _{i=1}i = \frac {n(n+1)}{2} $ Basis Step when: $ n=1 $ $ {\sum}^1 _{i=1}i = \frac ...
-1
votes
3answers
52 views

$2^n < (n+2)!,$ for $n \geq 0$ [closed]

Prove by induction I'm working on a self thought book but the solution isn't available. Can someone explain please?
2
votes
1answer
31 views

Property of maximum matching

Let $G=(V,E)$ be a graph with no perfect matching. Then there exists a vertex v such that every incident edge is part of a maximum matching. I'm not sure how to prove this. How can every edge that ...
0
votes
1answer
25 views

Projection of a discrete subgroup of $R^n$ [duplicate]

Let $A$ be a discrete subgroup of $\Bbb R^n$ and let $V$ be a $m<n$ dimensional $\Bbb R$-subspace of $\Bbb R^n$. Is the projection of $A$ onto $V$ a discrete subgroup? I am most interested in the ...
-1
votes
0answers
35 views

A fair die is tossed twice. Let Z be the sum of the tosses and W be the difference.

A fair die is tossed twice. Let Z be the sum of the tosses and W be the difference. Are Z and W independent? Explain.
2
votes
2answers
24 views

Shortcut for composing cycles

Let $\pi = (15)(14)(13)(12).$ To compose the cycles of $\pi$, I rewrite $(15)(14)(13)(12)$ as $[(15)(2)(3)(4)][(14)(2)(3)(5)][(13)(2)(4)(5)][(12)(3)(4)(5)]$ which is tedious. Is there any way to ...
-4
votes
1answer
65 views

Prove that $D = \{3n: n \in \mathbb{Z}^+ \}$ [closed]

Let $D$ be the set whose members are defined as follows: Basis Step: The number $3 \in D$. Recursive Step: If $x \in D$ and $y \in D$, then $x + y \in D$. Prove that $ \{3n: n \in \mathbb{Z}^+ \} ...
0
votes
2answers
17 views

Verifying the reasoning is true for the following deductive arguent

Identify the premises and conclusions of the following deductive arguments and analyze their logical forms. Do you think the reasoning is valid? Either John or Bill is telling the truth. Either Sam ...
2
votes
1answer
28 views

Smallest integer

I encountered an intriguing problem and I think I have a solution, but I want to run it by some of the smarter people around here: Find the smallest integer $n, n>1$ such that $C(n)=n, C(n)$ is ...
0
votes
1answer
29 views

Finding a twin prime in binary expansion

Numbers from 1 to 63 are placed on 6 cards according to the following 6 rules: The 1st digit in the binary expansion of each number on card 1 is a one. The 2nd digit in the binary expansion of each ...
0
votes
1answer
49 views

3 men and a cold night [duplicate]

$3$ guys, each with $\$10$ a piece, go to a hotel hoping to get a room to stay in for the night. A room costs $\$60$. The men go in, and ask to rent a room, only having $\$30$ between them. The mater ...
2
votes
0answers
44 views

Sum taken over the specified set of integer: $\sum_{3 \mid n} a_n$

Let's consider a sum $$S_{m}=\sum_{ 3 | n}^{m} {a_{n}}$$ where the sum is taken over all the integers $3t$, where $0 \leq 3t \leq m$. Assume that $G(z)$ is a generating function of the sequence ...
1
vote
1answer
30 views

General methods of solving non-linear recurrences

Let's consider a sequence $$ \{a_{n} \} _{n=0}^{\infty}, a_{0}=1, a_{n+1}=\frac{a_{n}}{1+na_{n}}$$. Taking $$b_{n}=\frac{1}{a_{n}},$$ we bring the exact reccurence to the following one: $$b_{0}=1, ...
1
vote
4answers
80 views

For each natural number $n$, let $A_n = \{nx \mid x\in \Bbb Z\}$. What is $\bigcap^∞_{i=1} A_i$?

The universe of discourse is the set of all integers. Let $A_n = \{nx \mid x\in \Bbb Z\}$ for each natural number $n$. What is $\bigcap^∞_{i=1} A_i$?