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

4
votes
2answers
86 views

What is the value of the following? $3^{302} \mod 5.$

I have to choose from a. 0 b. 1 c. 2 d. 3 e. 4 I think its e. 4 because $$3^{302} = 3^{300} \cdot 3^2 = 3^{4\cdot 75} \cdot 3^2 = (3^4)^{75} \cdot 3^2.$$ Applying Fermat's Little Theorem to ...
0
votes
1answer
41 views

How many exchanges to order n numbers.

Say I have n integers which are all different, in some random order. If I can only exchange two integers adjacent to each other, how many exchanges does it take to arrange them in ascending order? ...
1
vote
1answer
89 views

I'm searching for the formula of the series $ \sum_{n=0}^{\infty}a^{n^l} $

I'm searching for the sum-formula (if exists) of the following power series: $$ \sum_{n=0}^{\infty}a^{n^l} $$ where $l=2,3,....$, and $|a|<1$.
0
votes
1answer
169 views

Prove that $\lambda(v-1) = r(k-1)$

This is to do with balanced incomplete block design. Some homework exercise wants me to prove the relation $$\lambda(v-1) = r(k-1)$$ $v$ is the number of elements in your ground set. $r$ is the ...
1
vote
0answers
82 views

Ideal shrinking of discrete randomness source

I have a discrete randomness source that emits random integer numbers in range [0..N) with uniform distribution. I need to reduce this distribution, limiting it to ...
0
votes
1answer
175 views

Disjunctive Normal Form (DNF) of a boolean combination

Upon revisiting chapter 1 of Robert S. Wolf's "A tour though mathematical logic" I sumbled upon the following Proposition on page 13 : Suppose that $P$ is a Boolean combination of ...
1
vote
2answers
219 views

Proofs involving sets - True and False?

Can someone please help me with these True and False questions? I've tried them myself, but I'm not very good at discrete math... Thank you in advance! Any set $A$ and $B$ with $B\subseteq A$ and ...
0
votes
1answer
32 views

predicate logic ,writing in notation form

The statement below should be rewritten in the form “ for all · · · x, · · · .” "No computer scientists are unemployed" Answer Let computer scientists = CS unemployed=U for all x element of CS, x ...
2
votes
1answer
94 views

k-Nearest nodes: Average distance between connected nodes when search radius is non-integer

Say I have an infinitely large grid where the probability any given square contains a node is $p$. Each node makes a connection with its $k$ nearest neighbours. How do I calculate the average ...
0
votes
1answer
88 views

Properties of the relation R on the set of all real functions

So... I'm working on this and I'm supposed to figure out if each of these properties are pertinent. Can someone please help me? Thank you! Properties: Reflexive Symmetric Anti-Symmetric Transitive ...
2
votes
2answers
103 views

Time complexity (in Θ-notation) in terms of n?

Can someone please help me with this problem? Any help would be much appreciated? Thanks in advance!! ...
0
votes
1answer
30 views

How do I derive a contradiction from an assumption that is “not asymmetric”

Let $R$ be a transitive relation on a set $A$. Define another relation, $S$, such that, for any $x,y \in A$, $Sxy$ iff $Ryx$. Moreover, let $S$ be irreflexive. Prove: $S$ is asymmetric on $A$. ...
2
votes
1answer
163 views

What is the time complexity (in Θ-notation) in terms of n?

Consider the following algorithm, where $n$ is a parameter. ...
0
votes
1answer
25 views

Using binary arithmetic and computing for 'y'

Using binary arithmetic, a number y is computed by taking the n-bit two’s complement of x − c. If n is eleven, x = 101000010012 and c = 101012 then y =? How do we solve these type of questions? x = ...
1
vote
1answer
82 views

More questions on quantifiers

I have the following questions: Write the following statements in more abbreviated form, using quantifiers. Here the short phrases “is prime” and “is a line” are allowed, and the symbol $\Pi$ may be ...
0
votes
3answers
37 views

Question on quantifiers

The following question is taken from the Book "Introduction to Mathematical structures and proofs: Let $A = \{1, 2, π\}$, and let $P$ be the statement $x \in A$ and $x \in \Bbb Z.$ Determine the ...
0
votes
0answers
40 views

Prove that maximum 9 trailing zeroes in this summation

I am trying to prove that there are a maximum of 9 trailing $0$'s at the end of this summation: $$\sum_{k=1}^{k=m} k^n$$ for $1\le n\le 1000000$ and $m\le 100$. Any help on how to approach?
2
votes
3answers
44 views

Help with Set Theory/ Proofs

Can you conclude that $A = B$ if $A$, $B$, and $C$ are sets such that (a) $A \cup C = B \cup C$ No, the sets $A=\{1,2\}, B=\{3,4\}, C=\{1,2,3,4,5\}$ disprove this, because $A \cup C = B \cup C$ but ...
0
votes
3answers
88 views

Translating a sentence into a logical expression.

I am having trouble understanding the solution given for a problem in my discrete mathematics text book. Any help would be much appreciated. Question: Let L(x, y) be the statement "x loves y", where ...
-1
votes
3answers
35 views

Solving Boolean functions and changing to simplified form

How is the truth table for $(p \lor q) \lor (p \land r)$ e same as the truth table for $p \lor q$? Using formular such as De Morgans n etc.. And can anyone tell me how to start of with this type of ...
2
votes
0answers
42 views

Computation of a 3-dimensional game matrix

For natural numbers $n_1 \leq n_2 \leq n_3$ we define $\beta(n_1,n_2,n_3)$ recursively to be the smallest natural number which is not among the numbers $\beta(m_1,m_2,m_3)$, where $m_1 \leq n_1 \leq ...
3
votes
0answers
35 views

question in product

can any expert just check my solution You bought a car for $\$2500$ down and made payments of $\$299.50$ each month for $36$ months. (a) Find the amount of the payments over the $36$ months. (b) Find ...
1
vote
1answer
45 views

question application product

can any one help me in this questions The perimeter of a square is equal to four times the length of a side of the square. Find the perimeter of a square whose side $s$ measures $2.7$ meters? thank ...
2
votes
2answers
134 views

Pigeonhole principle and finite sequences

Suppose we have $75$ boxes that are labeled from $1$ to $75$ and that in each box there is at least one ball, but there are not more than $125$ balls total. I'm trying to find the largest number $n ...
1
vote
1answer
36 views

Manipulating and simplification of Boolean functions

How is the function ((p v (r v q)) ^ ~(~q ^ ~r) is equal to the function (q v r). Can anyone show how is this simplified using formulas asuch as De Morgans ans etc???
2
votes
3answers
77 views

In how many options can one cast 10 game cubes in different colors so that all the digits 1,2,3,4,5,6 will apear?

I study discrete and I missed some lessons. Can you help? The problem: We have 10 game cubes, each in a different color. The question is what is the number of options to throw all the 10 cubes and ...
2
votes
1answer
50 views

Relations counting in two sets

I have two sets $A=\{1,2,3, 4\}, \ B=\{5,6,7,8,9\}$. I wanted to count the relations from $A$ to $B$ that didn't include $1$ in their domain. First i did it like this: $2^{20} - 2^5 + 1 = ...
2
votes
2answers
78 views

Algebra. Permutations with composition proof.

Set $X := \lbrace 1,2,3 \rbrace$. Denote the idenity $\text{id}_X$ of $X$ by 1. Define $1\phi :=1$, $2\phi :=3$, $3\phi = 2$, $1\psi =2$, $2\psi = 1$, $3\psi = 3$. Prove that $\phi \psi \phi= \psi ...
1
vote
2answers
48 views

how many x contain atleast one y

Description A group of 5 animals is to be chosen from 6 cats and 4 dogs. Question how many groups contain at least one dog? Working Out There are at most 4 dogs, so a group of 1 dog and 4 cats ...
1
vote
1answer
52 views

Boolean Functions and using rules ..

Is the function $p \wedge (~\neg(\neg p \vee q) \vee (p \wedge q))$ equal to the function $p \wedge q$? Do I need to provide a truth table for this, or do I have to use the rules (for Manipulating ...
2
votes
1answer
40 views

Need help with discrete mathematics (two player games)

I am having trouble with this Tac Tix game.Any help or hints would be greatly appreciated.
3
votes
1answer
53 views

idempotent rule, distributive rule, and the absorption rule

Show that $p\vee(p\wedge q)=p$ follows from the idempotent rule, distributive rule, and the absorption rule $p\wedge(p\vee q)=p$. for this question i have spent 2 hours but still don't understand ...
1
vote
1answer
96 views

Show that if the diameter of an undirected graph is $d$ then there exists some vertex separator $S\subseteq V$ of size $|S| \leq { n\over d-1} $

Show that if the diameter of an undirected graph is $d$ then there is some set $S\subseteq V$ with $|S| \leq \frac{n}{d-1} $ such that removing the vertices in S from the graph would break it into ...
1
vote
2answers
82 views

Is this proof of $\sum_{i = 1}^n a_i^k \leq (\sum_{i = 1}^n a_i)^k$ correct?

I came across the following proof, and although I believe the result, something seems fishy and I can't put my finger on it. The base case might not be enough, or we might have to consider various ...
2
votes
3answers
83 views

Discrete Mathematics - Is my answer correct?

$x_1 + x_2 + x_3 = 15$ where $x_1$ and $x_2$ and $x_3$ are non negative integers. How many solutions are there when $1\le x_1\le 6$? the solution i came up with is = $\binom{15+3-1}{15} - ...
1
vote
2answers
65 views

Discrete mathematics: meaning of “g” in finite-state machines with output

I'm looking on an example from my book of discrete mathematics and I've been reading a lot about these finite-state machines with output, however there is one thing I just still can't figure out. The ...
0
votes
2answers
103 views

Using DeMorgan’s rule, state the negation of the statement

Using DeMorgan’s rule, state the negation of the statement: “The car is out of gas or the fuel line is plugged.” Let C stand for “The car is out of gas” and let F stand for “the fuel line is ...
2
votes
2answers
52 views

Using DeMorgan’s rule …

Using DeMorgan’s rule, state the negation of the statement: “Mary is a musician and she plays chess.” Answer Let m stand for “Mary is a musician” and let c stand for “she plays chess”. then the answer ...
3
votes
2answers
781 views

Adding combinations

Show non-numerically that: $${2\choose2} + {3\choose2} + {4\choose2} + {5\choose2} = {6\choose3}$$ The answer is as follows, but I have no idea how it was done: $$ \begin{eqnarray} ...
0
votes
2answers
38 views

How many of these numbers contain the digits $3$ and $5$?

Suppose that repetitions are not allowed. There are $6 \cdot 5 \cdot 4 \cdot 3 $ numbers with $4$ digits , that can be formed from the digits $1,2,3,5,7,8$. How many of them contain the digits $3$ ...
0
votes
2answers
58 views

With how many ways can we put $2t+1$ similar balls in $3$ distinct boxes?

With how many ways can we put $2t+1$ similar balls in $3$ distinct boxes,so that each couple of boxes contains more balls that the third one. I thought that these relations should stand: ...
2
votes
2answers
110 views

With how many different ways can Adriana be dressed…????

Adriana will be examinated in $5$ subjects, one at each day.She has $5$ dresses in different colors: red-blue-green-white-yellow. On Monday she does not want to wear the blue or green one. On ...
2
votes
1answer
80 views

How many numbers with $3$ digits can be formed with the digits $1,2,3,4,5$?

How many numbers with $3$ digits can be formed with the digits $1,2,3,4,5$ if there is no restriction at the repetition of the digits how many if no digit can be repeated more than twice and how ...
0
votes
3answers
112 views

Prove a function is surjective or injective

so I'm having trouble figuring out why this question is surjective / where $0$ comes from. $f : \mathbb{N} \longrightarrow \mathbb{N}$ where $f(x) = x + 1$. so given N begins from $0$ it goes: ...
2
votes
0answers
66 views

an “alternate derivation” of Poisson summation formula and discrete Fourier transformation

Inspired by this post, I am trying to do a derivation of a Poisson summation formula. My starting point is this: $$ \frac{1}{2\pi} \int^{\infty}_{-\infty} e^{i k x} dx=\delta(k) $$ I simply wish ...
0
votes
1answer
26 views

Proving the following bijection

Let $F = \lbrace S_1, S_2, \dots, S_n \rbrace$, where $S_i \subset \lbrace 1, 2, \dots, 3m\rbrace$ and define a function $f: F \to \mathbb{N}$ by $$ f(S_i) = \sum_{j \in S_i} (n+1)^{3m-j} $$ then ...
1
vote
1answer
78 views

A naive example of discrete Fourier transformation

We know a discrete Fourier transformation with discrete $n$ and continuous $x_1,x_2$: $$ \sum_{n\in\mathbb{Z}} e^{-in(x_1-x_2)\frac{2\pi}{L}}=L\delta(x_1-x_2) $$ with Dirac delta function $\delta$. ...
6
votes
2answers
846 views

Proof that no polynomial with integer coefficients can only produce primes [duplicate]

Doing a discrete math review and am trying to solve problem 1.6 in the text found here: http://courses.csail.mit.edu/6.042/fall13/ch1-to-3.pdf - I believe I've gotten parts (a) and (b) correctly, but ...
0
votes
1answer
23 views

Classifying relations as functions

so I'm having a bit of trouble actually working out the relation here, I'm fine with determining whether its a function/partialfunction etc I just don't understand how to produce the relation and get ...
0
votes
2answers
75 views

Intro to Discrete Math: compound interest calculation

The following is from an intro to discrete mathematics page. It's on compound interest. http://www.cs.odu.edu/~toida/nerzic/content/intro2discrete/intro2discrete.html[1] Scroll to the part with the ...