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
2answers
158 views

Probability between two dice games

Two games, both use un-biased 6 sided dice. game A, Sam throws one die 4 times. He wins if he rolls at least a 6 game B, he has 24 turns, and each time he rolls two dice simultaneously. He wins if ...
1
vote
2answers
53 views

Recurrence problem with a game of probability [duplicate]

Fair coin flipping (50% on both sides) $P_1$ and $P_2$ plays a few games of fair coin flipping. Assume player $A$ starts with $x$ coins and player $B$ with $y$ coins. Let $P_n$ denote the ...
1
vote
2answers
93 views

$p ⇒ (q∨r) ≡ (p∧(\neg r)) ⇒ q$ are logical equivalent?

I have determine whether the following equivalence is true or not $$p ⇒ (q∨r) ≡ (p∧(\neg r)) ⇒ q$$ using logical equivalences definitions. I am never able to do these sorts of questions correctly no ...
1
vote
2answers
75 views

Well Ordering Principle for a sum and why we only care about the set less than the smallest in our counter example set?

I was trying to prove: $$ \sum_{i=1}^n{i} = \frac{n(n+1)}{2}$$ using the WOP. I think the part that is confusing me about this proof is a more general pattern for proofs by WOP. To prove it we ...
1
vote
2answers
236 views

How can I use modus ponens or modus tollens to produce valid arguments? [closed]

I know this one is: $(1)$ If logic is easy, then I am a monkey’s uncle. I am not a monkey’s uncle. ∴ ? My answer: $\therefore$ Logic is not easy. (2) Can someone help me with this one? If ...
1
vote
2answers
122 views

Understanding Inclusion-Exclusion principle

Problem: You have $20$ employees. $4$ of them are women. You have $50$ different jobs to give for your employees, but each women should get at least one job. The Proof: The author split the ...
1
vote
1answer
154 views

Prove this recurrence relation? (catalan numbers)

$$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ Where $C_n$ denotes the number of ways of writing a valid list of open and closed parentheses of length ...
1
vote
1answer
126 views

How many ways can we color a $7$-cycle with $3$ colors so that no three consecutive nodes are of the same color

I have to paint graph We have three colors. The constraint is that there are no three consecutive nodes of the same color. And my idea is: All ways to paint is $3^7$ I'm going to count ...
1
vote
1answer
245 views

How can I write negations for this statement?

Are these negations correct using De Morgan's laws for this statement: This computer program has a logical error in the first ten lines or it is being run with an incomplete data set. Negation: This ...
1
vote
2answers
125 views

nth convolved Fibonacci numbers of order 6 modulo m

Problem: Find the coefficient of xk in (1−x−x2)-6 modulo m. Constraints: k≤264 m≤105, m can be a composite number. I have 10^5 such queries to process in 2 sec, so O(log k) for each query ...
1
vote
7answers
141 views

Error in proving of the formula the sum of squares

Given formula $$ \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6} $$ And I tried to prove it in that way: $$ \sum_{k=1}^n (k^2)'=2\sum_{k=1}^n k=2(\frac{n(n+1)}{2})=n^2+n $$ $$ \int (n^2+n)\ \text d ...
1
vote
1answer
62 views

Permutation and combination 4 digits number

I know how to compute the number four-digits strings: $10^4$, but I'm stuck on how to qualify this with the condition that at least two digits are different. Can anyone help?
1
vote
1answer
107 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
1
vote
2answers
105 views

Why relations are defined as the smallest

Often relations are defined as follows: The xxxxx relation is the smallest relation satisfying... My question is why relations are defined as the smallest ...
1
vote
2answers
80 views

Proving that any common multiplication of two numbers is a multiplication of their least common multiplication

Im trying to prove that if there are to numbers $n,m$ (natural numbers), and their smallest common multipe is $k$, so that $k = n·i$ and $k = m·j$ for some $i,j$ natural numbers, any common multiple ...
1
vote
2answers
658 views

If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
1
vote
3answers
37 views

The range of function in Discrete Math

If A = {1,2,3} and B = {w,x,y,z},then the domain of f is A and codomain is B. However what about the range? Why is the range f=f(A)={w,x}, why cant it be {w,z}? Edit: f ={(1,w),(2,x),(3,x)}
1
vote
2answers
72 views

Discrete Math and non-empty relations

Let $A=\{a,b,c,d\}$ and $B = \{w,x,y\}$, then a non-empty relations on $A$ is: $\{ (b,c), (b,d)\}$ Can someone explain why this is true? I thought that the requirements for any relations of a set ...
1
vote
1answer
119 views

chinese remainder theorem constructive proof

I am trying to understand CRT constructive proof from wikipedia [http://en.wikipedia.org/wiki/Chinese_remainder_theorem#A_constructive_algorithm_to_find_the_solution] I am unable to follow it from ...
1
vote
1answer
432 views

Rules of inference: The Rules of Disjunctive Syllogism and Double Negation

I have a question about the use of Double Negation in relation to this problem I found in my textbook examples. Problem: $\;¬(r \land t) \lor u$ $\;r \land t$ Therefore, $u$. In my textbook it ...
1
vote
2answers
114 views

How can I solve this problem without having to do it by hand?

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement without forcing me to do it ...
1
vote
2answers
106 views

Is there any way to solve this problem without having to do it by hand? [duplicate]

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement. Is there any way to group ...
1
vote
2answers
280 views

Prove that n!+1 contains a prime factor greater than n and use this to prove that there are infinte many primes

Prove that $n!+1$ contains a prime factor greater than $n$ and use this to prove that there are infinitely many primes. I said assume that $n!+1$ contains a prime $p$ which is less than or equal to ...
1
vote
1answer
54 views

Cartesian Product of $\emptyset \times \emptyset$

A bit of homework that I'm not sure on. The question reads: Let $A=\{a\}$ and $B=\{1,2\}$. Find the following: $$\mathcal{P}(A) \times \mathcal{P}(B)$$ The worked out solution is as follows. $\{ ...
1
vote
1answer
91 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$.
1
vote
1answer
152 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 ...
1
vote
2answers
61 views

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers. Progress: $F_{11}=89$ . I believe you should find the period of $F_n \bmod 89$ and use that to solve it. But I'm not not ...
1
vote
3answers
54 views

Question regarding Strong Principle of Induction

I'm currently studying Discrete mathematics from a book by Normal L. Biggs and i don't understand the thinking about an example on Strong Principle of Induction, The example i need help ...
1
vote
2answers
86 views

problem with GCD/Euclidean algorithm

This problem is in a chapter on the Greatest Common Divisor: The Euclidean Algorithm. Apparently I managed to arrive at one of the 3 possible solutions. Problem goes 'man at a casino wins \$1020 in ...
1
vote
1answer
41 views

Probability distritubion of linear function

Given a variable X belongs to gaussian distribution $N(\mu, \sigma)$. How to find the distribution of linear function $y=ax+b$? My answer is that the linear distribtion will belong the ...
1
vote
1answer
122 views

Prove or find a counterexample: if $A \subseteq B, B \subseteq C, C \subseteq A$, then $A = B = C$

Proof or find a counterexample:For all sets A;B;C if $A \subseteq B$, $B\subseteq C$, and $C\subseteq A$, then $A = B = C$. I tried doing this but not sure whether going in the right way Let $x\in ...
1
vote
1answer
147 views

Summation with absolute value

How can I solve $\sum_{k=-2}^{\infty}(\frac{1}{2})^{k}\alpha^{|n-k|}$ for every whole number n? Note that $-1<\alpha<1$ Thank you
1
vote
1answer
33 views

Graph Isomorphism with Same Degree Sequece

How do I prove that two tree graphs with the same degree sequence are isomorphic (or non isomorphic)? Thanks for the help!
1
vote
1answer
44 views

$(A \lor B) \implies (((A \lor B) \implies A) \lor ((A \lor B) \implies B))$?

Is the implication in the title true? I haven't studied logic formally yet, so I can't precisely say what A, B exactly are. Perhaps "predicates in first-order logic"?
1
vote
1answer
75 views

Packing 5 identical books into 5 identical boxes

How many ways are there to pack $5$ identical books into $5$ identical boxes with no restrictions placed on how many can go in a box? No restrictions means some boxes can be empty. Would it be ...
1
vote
1answer
173 views

Need help with recurrence relation

So the question is: "Find a recurrence relation for the number of ways to pick $n$ objects from $k$ types with at most 3 of any one type" I think I figured out what it would be excluding the last ...
1
vote
1answer
31 views

put numbered balls in four similar boxes of a specific capacity…

With how many ways can we put $12$ numbered balls in $4$ similar(not numbered) boxes of capacity $3$ each one? Is it maybe $3^4$ ?
1
vote
1answer
100 views

put balls in boxes with specific capacities

We have $10$ numbered balls and $3$ boxes with capacities: $5$, $3$ and $2$ balls. With how many ways can we put the balls in the boxes? The boxes are distinguished. I thought that it is like that: ...
1
vote
1answer
30 views

how many different choices exist?

If we choose $k$ objects from $n$ with replacement and we don't ignore the order of the choices(e.g if we choose $3$ objects of $A,B$ with replacement,the results $AAB$ and $ABA$ are considered as ...
1
vote
1answer
45 views

Are every prime (except 2,3,5) divisor of some of 10^n+1?

Referring to Is it true, that every prime (except 2) can be found as a divisor of enough long series of 1-s? , I have the same question. I have the intuitive hyptohesis, that every prime can be found ...
1
vote
4answers
50 views

Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...
1
vote
2answers
140 views

Chromatic polynomial of a graph - might take a while

I'm currently struggling with graphs that require either adding edges, or removing them. Problem here being that the graphs I'm working on takes forever to complete and I don't really know if adding ...
1
vote
1answer
60 views

Permutations and Combinations

What is the probability that a 3-element subset selected at random from the set {1,2,3, … , 10} a) contains the integer 7? b) has 7 as its largest element? I know this deals with permutation and ...
1
vote
2answers
166 views

How many strings of 8 digits end with an even digit?

So there are $10$ combinations for each digit except the last which has 5 possibilities ($0,2,4,6,8$). Thus $10*10*10*10*10*10*10*5=50000000$ combinations right? As a follow up, how many strings of 8 ...
1
vote
2answers
58 views

Solving a Linear Non-Homogeneous Recurrence

How can I solve the following recurrence? $$a_n = 121a_{n-2} + 14400 n$$ I derived this: $$\frac{1228}{11} (-11)^n + \frac{-4044}{11}11^n + 4800n$$
1
vote
2answers
102 views

Finding mathematical relation of matrices with reverse indices

I am designing a simple game, I have faced this problem to get the mathematical relation between two kind of tables: MATRIX A MATRIX B As you can see the table A (or Matrix A) is the normal ...
1
vote
1answer
56 views

Is a relation induced by a partition always an equivalence relation?

Is a relation induced by a partition always an equivalence relation? I'm having some serious trouble understanding this concept and I was wondering if this is true.
1
vote
4answers
134 views

Show that if $p$ is a prime number $> 3$ then $24 \mid p^2-1$ [duplicate]

Hi guys can someone help me with this ?(Without using Modular arithmetic) Show that if $p$ is a prime number $>3$ then $24$ $\mid$ $p^2-1$
1
vote
2answers
216 views

What subject in mathematics investigates the type of problems that constitute the LSAT “logic games” (example given)?

For my own curiosity, I read part of an LSAT study guide yesterday. The "logic games" section comprised questions like, An advertising executive must schedule the advertising during a particular ...
1
vote
1answer
104 views

How to prove a set must have a specific number of elements?

Trying to understand sets but having a hard time. Could someone help me through this one? Let A be a set of six positive integers each of which is less than 13. Show that there must be two distinct ...