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
0answers
12 views

Logic-Calculating Cd Failures

I am working on homework and have the problem At a company every 4th CD is tested, the testing consists of 4 testing programs and the probability that they fail are as follow Program 1 : .01 Program ...
1
vote
2answers
45 views

Sum over Binomial mass function

In Casella and Berger Book (Statistical Inference), exercise 2.40 is $$\sum_{k=0}^x {n\choose k}p^k(1-p)^{n-k}=(n-x){n\choose x}\int_0^{1-p}t^{n-x-1}(1-t)^xdt.$$ If I replace $x$ by $n$ then LHS ...
-2
votes
2answers
44 views

$[2,5] = \{2,3,4,5\}$ T or F?

I am trying to understand this problem. Is $[2,5] = \{2,3,4,5\}$ true or false. What I think: $[2,5] = \{x: 2 \leqslant x \leqslant 5\}$. So this includes 2,3,4, and 5. Therefore it is equivalent so ...
-1
votes
0answers
33 views

i dont understand how theorem calculation proofs work please help [closed]

I do not understand hilbert style proofs and how they work. Can someone please explain them to me? some things i need to know are: • Write theorem-calculations from Γ (equivalently, Γ−...
0
votes
2answers
77 views

Discrete Math Pigeon-Hole [closed]

How can we solve below problem? Let $X = \{1,2,3,\dotsc,100\}$. If eleven numbers are selected from $X$, show that there are at least two numbers $u$ and $v$ such that $$0 \lt \left| \sqrt{u} - \...
0
votes
3answers
71 views

Very confused by recurrence relations as a concept

We've been introduced to recurrence relations as a concept in my Discrete class. One question asks: Given the recurrence: $S(1) = 1$, $S(n) = 2S(n − 1) + 3 (for \ n > 1)$ prove ...
0
votes
3answers
107 views

Find all N in $\phi(N)=98$ [closed]

Solve the equation $\phi(N)=98$ I have no idea how to do it. How to find all N?
0
votes
2answers
19 views

c*(log 2n) is the same as c + c*log n?

I am reading a chapter of my data structures book that is about big O notation and have come across an example where I do not understand the Algebra behind it: " On the other hand, if a search ...
0
votes
1answer
44 views

Probability book choosing questions

So I am doing homework and have the following question If 3 books are picked at random from a shelf containing 5 novels, 3 books of poems, and a dictionary. What is the probability that (a) the ...
3
votes
1answer
52 views

Combinatorial proof for a non obvious binomial identity

I think I got some serious problem with those combinatorial proofs. Why would the following be true ($1\leq r\leq k\leq n$): $$\sum_\limits{j=r}^{n+r-k}\binom{j-1}{r-1}\binom{n-j}{k-r} = \binom{n}{k}?...
2
votes
1answer
27 views

Finding a recurrence for number of paths in a certain tree

I have a graph which looks like this: The question is to find a recurrence for $a_n$ - the number of paths of length $n$ that start in vertex $A$. How do you tackle these kind of problems? There is ...
0
votes
1answer
53 views

Size of family $\mathcal F = \{F_1, \ldots, F_m\}$ is at least $\lceil \log_2n\rceil$.

A family $\mathcal F = \{F_1, \ldots, F_m\}$ of subsets of $\{1,2,\ldots,n\}$ is said to be separating if for any two elements $1 \leq i < j \leq n$, there is some set $F \in \mathcal F$ such ...
0
votes
2answers
56 views

A soccer squad contains $3$ goalkeepers, $7$ defenders, $9$ midfielders and $4$ forwards.

A soccer squad contains $3$ goalkeepers, $7$ defenders, $9$ midfielders and $4$ forwards. So I understood the first part of the question: $(i)$ In how many ways can a team of $1$ goalkeeper, $4$ ...
5
votes
1answer
123 views

Given sets A and B such that A ⊆ B, write down A ∪ B in a simplified form.

Here's how I did it: Let A = {1,2,3} Let B = {1,2,3,4,5} Since A ∪ B, everything in A would also be in B thus the simplified form would be B? If it's wrong, please let me know how to go about this, ...
1
vote
3answers
41 views

Propositional calculus - I can't get why the answer for this test question is what it is

Consider the following premises. If A = B then B = C. B != C. If C > D then D < E. F != G and A = B. A = B or C > D. Alternatives: a) F != G b) F != G and D < E c) A = B d) B = C or D &...
7
votes
4answers
150 views

Find the probability that a word with 15 letters (selected from P,T,I,N) does not contain TINT

If a word with 15 letters is formed at random using the letters P, T, I, N, find the probability that it does not contain the sequence TINT. (I just made up this problem.)
2
votes
2answers
45 views

logical equivalence statements in discrete math

Construct another English form sentence, which is logically equivalent to that which was given. "Susan goes to school or Susan does not talk on the phone or Susan does not go to school."
3
votes
1answer
125 views

How many possible functions?

Take $f:\{1,2,3,4,5,6,7\}$ to $\{0,1,2,3,4\}$ How many such functions satisfy the cardinality of the pre-image of the set $\{3\}$ is equal to $3$. I thought it would be $35$, i.e :$7\choose{3}$ ...
1
vote
2answers
33 views

What is the negation of ∀x∃y¬P(x,y) without using ¬?

Found it to be ∃x∀yP(x,y). Is this right?
1
vote
2answers
38 views

Finding integers $x$ and $y$ such that $633x + 255y = 6$

The first bit of the question asks to find the gcd of $633$ and $255$ which I did and found that it's $3$. However, the next bit asks this: Find integers $x$ and $y$ such that $633x + 255y = 6$, or ...
0
votes
1answer
29 views

Determining if a function is onto

If our range such as in the question below is all the real numbers excluding $0$, to determine if a function is onto we must ask if all real numbers excluding $0$ can be mapped to at least one value ...
1
vote
1answer
24 views

# of bit strings of length n (even>2), with n/2-1 zeros and n/2+1 ones, zero followed by one

case 1: What is the number of bit strings of length 4, with 1 zero and 3 ones, zero must be followed by one Answer: 3 case 2: What is the number of bit strings of length 6, with 2 zeros and 4 ones, ...
2
votes
1answer
71 views

Strange Algebra

I am working on a mathematical induction worksheet and my professor gave us the key and I have run across something that makes zero sense to me so please explain if you can. Additional info: $k \ge2$ ...
0
votes
1answer
52 views

Set-builder notation

How do I determine the size of the following set with set builder notation? $$\{𝑥 \in \mathbb{Z}_+\mid 4<𝑥<5\}$$ I don't know where to start and what integer value is usable.
0
votes
2answers
51 views

Venn Diagrams in Discrete Structures

I'm hoping someone can explain how I go about drawing up venn diagrams in my discrete structures class. The book this class uses doesn't explain much at all, and gives only two examples.. My homework ...
2
votes
3answers
89 views

Group theory - prove that $\forall x((x^{-1})^{-1}=x)$

so I got this question for homework: Prove that this property can be deduced from group theory: The inverse of an inverse is the identity: $\forall x((x^{-1})^{-1}=x)$ I tried building this ...
0
votes
0answers
34 views

Probability mass function meeting the expectation of distributions of independent Bernoulli variables

Suppose there are $n$ objects that have probabilities $p_1, p_2, \ldots, p_n$ of being selected, respectively. The sum of these probabilities is not necessarily $1$. Also assume that the first $k < ...
1
vote
1answer
57 views

Is my proof to show that $\mathcal{P}(A) \subseteq\mathcal{P}(B) \implies A \subseteq B$ correct? $\mathcal{P}$ refers to the power set.

Suppose $A$ and $B$ are sets, and that $x$ is an arbitrary element of $A$. The definition of the given $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ means $$\forall y[(y \in \mathcal{P}(A) \rightarrow y \...
0
votes
0answers
24 views

Optimal number of operations in the given scenario?

Suppose $$A_1=\{x_1+x_2+x_3,\quad x_2+x_3+x_4,\quad x_3+x_4+x_5\} \\ A_2=\{x_0+x_1+x_2, \quad x_0+x_1+x_8, \quad x_0+x_7+x_8\} \\ A_3=\{x_{10}+x_{11}+x_{12}, \quad x_{11}+x_{12}+x_7, \quad x_7+x_8+x_{...
-1
votes
1answer
23 views

Code theory question

An RSA crptosystem has modulus $n = 253$, and you wish to send a message m = 31 to your friend whose public encoding key $e = 17$. What encoded message $m'$ do you send? No clue how to do this ...
0
votes
2answers
40 views

Listing real numbers as countable like listing rational numbers [closed]

like proving the set of positive rational numbers are countable, where we list the rationals as the following list, why can't we represent real numbers like the same? If positive Rational numbers (p/...
1
vote
1answer
37 views

Finding the combination where p of the items are identical.

Suppose we have $n$ objects in which $p$ items are identical. Of course, $n-p$ elements are distinct. Then what is the combination of $n$ objects taken $r$ at a time? That is, what is $C(n,r)$, but ...
0
votes
0answers
29 views

I cannot figure out the relation of this class! Please help

Let $S = \{0, 1, 2, 3, 4, 5, 6\}$ and define the relation $R$ on $S$ as follows: $m R n$ if $m^2= n^2 \pmod 5$ for any $m$ and $n$ in the set $S$. (a) Show that $R$ is an equivalence relation on $S$ ...
7
votes
3answers
143 views

How many integer solutions are there of the equation $|x_{1}|+|x_{2}|+\cdots +|x_{k}|=n$?

How many solutions are there to the equation $$|x_{1}|+|x_{2}|+\cdots +|x_{k}|=n$$ for $n,k\in \mathbb N$ and $\forall\ 1\leq i\leq k,\ x_{i}\in \mathbb Z$? Any ideas? I don't know how to ...
-1
votes
1answer
12 views

Notation of discrete functions with variables that only exist for certain multiples of all natural numbers

I have a question about adding two discrete functions, one of which is an exact copy, but dilated. Imagine function x[n]. This function exists for all n in the set of natural numbers (1,2,3,etc.). ...
1
vote
1answer
52 views

Find the chromatic polynomial of a graph

My answer: $p(g,k) = k(k-1)^4(k-2)(k-3) $ I'm new to this subject so was hoping if one of you could check my answer. Thanks. Vertices:
0
votes
1answer
39 views

Solving sets involving equations $\text{{z | $ 3z = n^ 2$, z and n are natural numbers}}$

I tried to solve the following sets: $\text{ {y | $2y^2$= 50, y is an integer} }$ So as I understand this means: $y$ such that $2y^2 = 50$ and $y$ is and integer. I tried to solve it this ...
7
votes
2answers
127 views

Prove that if fewer than $n$ students in class are initially infected, the whole class will never be completely infected.

During 6.042, the students are sitting in an $n$ × $n$ grid. A sudden outbreak of beaver flu (a rare variant of bird flu that lasts forever; symptoms include yearning for problem sets and craving for ...
0
votes
1answer
44 views

Where have I gone wrong in this Extended Euclidean Algorithm?

1. "Use the Euclidean algorithm to find the greatest common divisor of 633 and 255" 633 = 2 x 255 + 123 255 = 2 x 123 + 9 123 = 13 x 9 + 6 9 = 1 x 6 + 3 6 = 2 x 3 + 0 Therefore gcd is 3. 2. "...
6
votes
1answer
85 views

Order statistics for discrete uniform random variables

Let $X_i, i=1,\cdots,N$ be i.i.d. discrete uniform random variables, taking values in the range $\{0,1,...,M-1\}$. Let $X_{(i)}$ denote the $i$-th order statistic. What are the values of $\...
1
vote
1answer
46 views

Veryfing a proof without a truth table

I have the following proof to verify without using truth tables but rather to use the laws or theorems of logical equivalence. I am suppose to prove $(p\wedge q)\vee p\equiv p$, but I am stuck at$(p\...
2
votes
1answer
46 views

In how many ways can these people be arranged for a photograph?

Jessie and Casey are getting married. In how many ways can a photographer at their wedding arrange 6 people in a row from a group of 10 people, where the spouses are among these 10 people, if both ...
0
votes
3answers
47 views

Number of ways to select men and women to a committee?

A committee to contain $5$ members and have at least one woman. There are $7$ women and $9$ men. I think that we can fix one woman as one of the $5$ members, and randomly select the rest from a ...
0
votes
0answers
37 views

Simplify $\sum_{\sum_{i=1}^{2^{n-r}}m_i\ =\ 2^{n-1}\ and\ m_i\ is\ even}\prod_{j=1}^{2^{n-r}}\binom{2^{r}}{m_j},$ where $n$ and $r$ are given.

I need to simplify the following formula: $$\sum_{\sum_{i=1}^{2^{n-r}}m_i\ =\ 2^{n-1}\ and\ m_i\ is\ even}\prod_{j=1}^{2^{n-r}}\binom{2^{r}}{m_j},$$ where $n$ and $r$ are given. I know that: when ...
1
vote
2answers
76 views

Simplify $\sum_{i=0}^{m}(-1)^{i}\binom{n}{i}\binom{2n}{2m-2i}$

I have to simplify $\sum_{i=0}^{m}(-1)^{i}\binom{n}{i}\binom{2n}{2m-2i}$. That because when $n$ and $m$ get large (eg. $n = 2^{64}$, $m = 2^{60}$), the computation complexity is too high. Could ...
1
vote
2answers
32 views

How do I compute the generating function for this number sequence?

I am trying to compute the generating function for the number sequence given by $a_n = (-1)^n$. I know that the solution is $A(x) = \frac{1}{1+x}$ but when I try to solve it using the procedure of ...
1
vote
2answers
53 views

Number of solutions in non-negative integers question (Stars and bars)

Q How many solutions are there in non-negative integers $a, b , c, d$ to the equation: $$ a + b + c + d = 79 $$ with the restrictions that $a \geq 10$, $b \leq 40$ and $20 \leq c \leq 30?$ If ...
1
vote
3answers
60 views

Proving that $3 + 3 \times 5 + 3 \times 5^2 + \cdots+ 3 \times 5^n = [3(5^{n+1} - 1)] / 4$ whenever $n \geq 0$

Use induction to show that $$3 + 3 \times 5 + 3 \times 5^2 + \cdots+ 3 \times 5^n= \frac{3(5^{n+1} - 1)}{4} $$whenever $n$ is a non-negative integer. I know I need a base-case where $n = 0$: $$3 \...
0
votes
2answers
77 views

Number of words with length 8 with certain restrictions

How to find number of words with length 8 such in which every letter A, B, C, D occurs exactly 2 times and exactly one pair of same letters occurs on neighbouring positions? Maybe inclusion–exclusion ...
0
votes
2answers
20 views

Strong Induction issue

I am trying to prove a statement using strong induction but I seem to be getting stuck. I don't know if did something wrong or I am just not recognizing an opportunity for factoring/how to factor ...