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

0
votes
4answers
50 views

show that in a group of five people (where any two people are either friends or enemies)…

Show that in a group of five people (where any two people are either friends or enemies), there are not necessarily three mutual friends or three mutual enemies. I am completely lost on this problem ...
1
vote
2answers
91 views

How to find sum of infinite series of non-geometric series?

I am familiar with radius of convergence, power series, Taylor series/Maclaurin series, and fundamental infinite series convergence tests (ratio, root, integral, comparison, etc.) introduced in a ...
0
votes
2answers
39 views

How to represent a verbal compound statement correctly?

In one of the problems for checking validity of a statement, i came across a compound statement.The compound statement is: "We will go for swimming only if it is sunny". So the statements are: ...
0
votes
1answer
21 views

Let $n > 0 \in \mathbb Z$. Prove that $a, c$ leave the same remainder when divided by $n$ iff $a - c = nk$ for some $k \in \mathbb Z.$

Suppose $a - c = nk$ for some integer $k$. Then $- c = nk - a$ and $a = nk + c = nk + (nk - a) = n(2k) -a$. Let $c = a - nk$ and $a = nk + c$. Then $a - c = nk + c - a + nk = c - c + nk = nk.$ Does ...
2
votes
2answers
38 views

Various set operations and the empty set…

Let A = { {}, {{}}, 1, a, cat, {1, a, cat} }. Determine the sets. (a) A \ { a, b, c } = { {}, {{}}, 1, cat, {1, a, cat} }. (b) A ∪ { x } = { {}, {{}}, 1, a, cat, {1, a, cat}, x }. (c) A ∩ { cat, ...
1
vote
1answer
43 views

Counting no. of way 2 people who do not own a dog, and at least 2 people who don't own a cat given the info. below.

100 people have come to the annual pet owner's meeting. A quick show of hands demonstrates that 60 people own cats and 55 own dogs. Give the numerical answer and a brief explanation for the ...
5
votes
1answer
63 views

Counting the expected number of strings with a given contiguous substring.

Question: Let a random bit string $x$ of length $n$ be given. What is the expected number of bit strings $w$ of length $2n$ that contain $x$ as a contiguous substring? What I know: For any bit ...
1
vote
1answer
91 views

Number of increasing functions from $\{1,2,\dots, n\}$ to itself.

Let $f$ be a function from $X=\{1,2,3,...,n\}$ to itself. We say $f$ is increasing if $a\le b$ then $f(a)\le f(b)$. How do we find the number of increasing functions? I think if we can define ...
2
votes
3answers
36 views

Correct Form of a Logical Statement

I ran across a problem which has stumped me involving existential quantifiers. Let U, our universe, be the set of all people. Let S(x) be the predicate "x is a student" and I(x) be the predicate "x is ...
1
vote
1answer
45 views

Possible number of combinations from a subset

Let's say I have an set of elements like this: [0,1,2,3,4,5]. I want to figure out the max number of possible combinations using a max of 4 elements. Meaning using 2 or 3 is also a possibility: [0] ...
1
vote
2answers
36 views

Give recursive definition of sequence $a_n = 2^n, n=2,3, 4… where $ $a_1 = 2$

Give recursive definition of sequence $a_n = 2^n, n = 2, 3, 4... where $ $a_1 = 2$ I'm just not sure how to approach these problems. Then it asks to give a def for: $a_n = n^2-3n, n = 0, 1, 2...$ ...
2
votes
2answers
59 views

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$?

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$ , I don't have an idea for solve the question. My attempt : $\frac{T(n)}{\sqrt {n}}^2 =99T(\sqrt {n})+100 $ and $\ s(k)= ...
2
votes
5answers
53 views

Showing that $\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$ for all $n\geq 1$

Show that $$\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$$ for all $n\geq 1$ I need this in order to complete my proof that $1 + \frac{n}{2} \leq H_{2^n}$, but ...
3
votes
1answer
97 views

Can we prove that set of irrational numbers is a set using Zermelo-Fraenkel axioms?

To remove paradoxes of naive set theory, We started with the axioms of Zermelo-Fraenkel and developed a set theory. Where we are building sets starting from a empty set. How to construct set of ...
1
vote
1answer
30 views

What is a transfer function?

If: $N$ is a set of nodes in a program dependence graph, which is a graph with two type of edge $L$ is a lattice of security levels What does the following mean: "For every $x\in N$, a so-called ...
0
votes
0answers
17 views

Clarification of conditional propositions [duplicate]

I am studying first order logic and we have been introduced to conditional propositions.$(p \Rightarrow q)\;$ The truth table for $p \Rightarrow q$ is this: ...
-4
votes
2answers
56 views

rearranging the digits of 7524693 [closed]

In the number 7524693, how many digits will be as far away from the beginning of the number if arranged in ascending order as they are in the number?
1
vote
1answer
55 views

Runs of white balls in sampling without replacement

There are $m$ white balls and $n$ black balls in a box. Balls are randomly drawn from the box with no return. Denote $X_1$ : number of white balls that been drawn before the first black. For $2 \leq i ...
-2
votes
1answer
51 views

Bijective correspondence between $X$ and $X \cup \{a\}$ for an infinite set $X$ [closed]

Let $X$ be an infinite set, and $a\notin X$. I need to prove that $|X \cup \{a\}| = |X|$. Preferably using bijective correspondence or Schröder–Bernstein theorem. Thank you.
2
votes
2answers
68 views

Order of statements in implication

The question is from Exercise 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
51 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
60 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 ...
1
vote
5answers
61 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
18 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
28 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
69 views

What is the inverse function of gcd? [closed]

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
83 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 ...
0
votes
0answers
21 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
31 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 ...
0
votes
1answer
26 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
122 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 ...
2
votes
3answers
76 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 ...
3
votes
2answers
46 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
1answer
35 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
32 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
51 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
45 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
14 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$ ...
1
vote
0answers
17 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
33 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
58 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
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 ...
1
vote
1answer
23 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
19 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
47 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 ...
2
votes
1answer
32 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 ...
2
votes
2answers
32 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 ...