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

What is the formula to find the number of one-one functions from A to B

let p = number or elements in A let q = number of elements in B if the number of functions from A to B is equal to q^p.... is their formula to find the number of one-one functions from A to B? how ...
1
vote
1answer
20 views

transitive closure and number of elements in relation?

I see an example as follows: in relation $R=\{(a,b), (b,c), (b,d), (c,e), (d,e), (c,f), (e,a) \}$, on set $\{a,b,c,d,e,f\}$. we have $30$ elements in the transitive closure of $R$. How number of ...
0
votes
0answers
22 views

non-homogenous linear recurrence relation general questions

what happens if you have both repeated and non-repeated roots? i know there are different forms for both, so if given roots say 5, -3, -3, -3 would it then be $A(5)^n + Bn(-3)^n + Cn^2 (-3)^n + Dn^3 ...
1
vote
2answers
28 views

How to prove this recurrence [on hold]

Been stuck on this problem for a good while. Not sure how to approach it any help would be great! It is problem 12.
0
votes
2answers
26 views

Help Showing a Relation is/isn't a Partial Order

Define the relation $\le$, as $(a,b)\le(c,d)$ if and only if $a+b\le c+d$ and $a\le c$. Is this a partial order? I know it's definitely not if we remove the $a\le c$ (because then it's not ...
-1
votes
0answers
11 views

p = X^2 and X = {a,b,c,d} [on hold]

Which ordered pairs need to be added to the universal relation p = X^2 on the set X = {a,b,c,d} to create the equivalence relation p* generated by p?
1
vote
0answers
16 views

Is a total order compatible with a partial order?

I was given the following multipart problem. Part 1: Consider the poset ({2,4,6,9,12,18,27,36,48,60,72},|), with the indicated integers and the divides relation. Find the following, if they exist; ...
0
votes
2answers
20 views

Is there a term for an “unbounded simplex”?

Is there a general term for regions like $\{(x,y):x>y\}$ and $\{(x,y,z): x>y>z\}$, i.e., regions which are simplexes with one open?
0
votes
0answers
25 views

4 cards are shuffled and placed face down. Hidden faces display 4 elements: earth, wind, fire, water. You turn over cards until win or lose.

Question: 4 cards are shuffled and placed face down in front of you. Their hidden faces display 4 elements: water, earth, wind, fire. You turn over cards until win or lose. You win if you turn over ...
0
votes
0answers
17 views

Partial Ordering and Hasse Diagram.

Draw the Hasse diagram for the partial ordering “x is a factor of y” on the following sets: S = {2, 3, 5, 7, 21, 42, 105, 210} I don't know how to find the partial ordering of this set. I know that ...
3
votes
5answers
52 views

Proving $2^n -1 = \sum_{i=0} ^{n-1} 2^i$ for all $n\geq 1$ by induction

I'm practicing proofs by induction, and equalities seem to be the toughest for me. Can somebody please help to prove that for all integers $n \geq 1$: $$ 2^n -1 = \sum \limits _{i=0} ^{n-1} 2^i\;? $$ ...
4
votes
5answers
95 views

Proving $6^n - 1$ is always divisible by $5$ by induction

I'm trying to prove the following, but can't seem to understand it. Can somebody help? Prove $6^n - 1$ is always divisible by $5$ for $n \geq 1$. What I've done: Base Case: $n = 1$: $6^1 - 1 = ...
-1
votes
0answers
24 views
0
votes
4answers
64 views

Proof by Induction $3^n > n^3$

I am trying to prove the following, however I'm stuck at the Induction hypothesis Prove by induction that, for all integers $n$, if $n\geq 5$, then $3^n>n^3$ What I have Done: Base Case: $n ...
-1
votes
1answer
30 views

Is this Event Mutally Exclusive?

I am trying to calculate the following, however I'm unsure on whether this event would be Mutally Exclusive or Independent. Can someone help with finding the probability of the Intersection? P(A) ...
-2
votes
0answers
34 views

question asks when is the birthday??? [duplicate]

Question asks how to find out Cheryl's birthday??
2
votes
1answer
25 views

Find generating functions for the Perrin and Padovan sequences

The Perrin sequence is defined by $a_0 = 3, a_1 = 0, a_2 = 2$ and $a_k = a_{k-2}+a_{k-3}$ for $k \ge 3$. The Padovan sequence is defined by $b_0 = 0, b_1=1, b_2=1$ and $b_k=b_{k-2}+b_{k-3}$ for ...
2
votes
2answers
44 views

Find the coefficient of $x^4$ in the expansion of $(1 + 3x + 2x^3)^{12}$?

I have not learnt the multinomial theorem yet, and was trying to approach this using the binomial theorem. I divided the terms as $a$ being $(1+3x)$ and $b$ being $2x^3$. I then used $${12\choose ...
1
vote
2answers
41 views

Summation Proof Dealing With 3s Multiples [duplicate]

So the problem is as follows: Prove that if the sum of digits of a decimal $n$ is three's multiple, then n is three's multiple by direct proof. For example, $11234567$ is 3's multiple because ...
3
votes
2answers
39 views

Multiple part problem concerning the proof that $\sum_{k=1}^n k^3=\left(\frac{n(n+1)}{2}\right)^2$ by induction

So I'm having trouble with $c,d$ and $e$. For $c$ so far I have: Inductive Hypothesis: $(\frac{n(n+1)}{2})^2 = (\frac{(k+1)(k+2)}{2})^2$ is that correct?
-1
votes
0answers
27 views

Combinatorics: Password consisting of 13 characters. Must contain at least one odd digit, and at most two even digits. How many passwords?

I'm really trying here. I just need help where to go next. Each character is one of the 10 digits 0, 1, 2, ... , 9 What I have so far is that there are 10^13 possible passwords. I'd have to subtract ...
-2
votes
0answers
47 views

Summation Direct Proof Help [on hold]

Prove that if the sum of digits of a decimal n is three's multiple, then n is three's multiple by direct proof. For example, 11234567 is 3's multiple because 1+1+2+3+4+5+6+7=24, and in fact, 11234567 ...
1
vote
1answer
22 views

Derive an exact formula (solve the recurrence definition) for the following recursive sequence:

Derive an exact formula (solve the recurrence definition) for the following recursive sequence: $s_n = 2_{s_n-1} - s_{n-2}$ where $n \ge 2$, and $s_0 = 4$, $s_1 = 1$. So I saw someone solving this by ...
1
vote
2answers
35 views

Proving $10^n \equiv 1 \pmod 3$ for all $n\geq 1$ by induction

Prove that $10^n \equiv 1 \pmod 3$ for all positive integers $n$ by mathematical induction. Can someone please help me in solving this problem and explain what's going on? Any guidance would be ...
2
votes
1answer
49 views

Combinatorics Question VS CS solution!

I was wondering for some conceptual understanding to a question of this form: In how many ways may we choose three distinct integers from [1, 2, ..., 80] so that one of them is the average of the ...
1
vote
2answers
28 views

Verify that $\alpha(a)\neq2$ for all $a$ where $\alpha(x): (2x + 1)/(x + 2)$

If $A= \mathbb{R} \setminus \{-2\}$ and $B = \mathbb{R} \setminus \{2\}$, let $\alpha: A \to B$ by $\alpha(x): (2x + 1)/(x + 2)$. Verify that $\alpha(a)\neq2$ for all $a \in A$. As a hint, I was ...
3
votes
3answers
38 views

You are making cookies and add N chips to dough randomly, and split it into 100 equal cookies, again at random. How many chips should go into dough?

Question: You are making chocolate chip cookies. You add N chips randomly to the dough and you randomly split the dough into 100 equal cookies. How many chips should go into the dough to give a ...
-4
votes
3answers
73 views

Proving that $2^n+1\leq 3^n$ by induction

I need to prove the following using mathematical induction: $$2^n+1\leq 3^n\qquad\forall n\in\Bbb{Z^+}$$ Been working on this problem for a while and cannot figure it out. Any guidance or help would ...
0
votes
2answers
27 views

How do you compute a 90% and 95% confidence interval for a guesstimation problem?

Question: How would you estimate the weight of Mount Everest? Give a 90% and 95% confidence interval. I would define what Mount Everest is. Including its boundaries (length, width) and estimate the ...
3
votes
2answers
15 views

A linear non homogeneus recurrence relation

Im using the minimax algorithm for a very simple game and when counting the tree nodes found the recurrence $T(n)=T(n-1)+T(n-2)+1$, with $0$ and $1$ as initial values. I tried generating functions: ...
1
vote
2answers
60 views

Proving $A$ is a subset of $B$

I'm trying to understand the proof behind showing a set is a subset of another set, but I'm struggle to do so. Can some one help using this example to show: $A \subseteq B$? Here $A = \{x | x = 4n ...
2
votes
1answer
44 views

Proving $(p\to q)\land(p\to r) \equiv p\to(q\land r)$ using logic laws — short cut or incorrect?

Working through this problem: Using logic laws, show that the following are logically equivalent: $$(p\to q)\land(p\to r)\qquad\text{and}\qquad p\to(q\land r).$$ The way I did the problem is ...
2
votes
1answer
19 views

How many subsets of $S$ are there that contain $x$ but do not contain $y$?

Let $S$ be a set of size $37$, and let $x$ and $y$ be two distinct elements of $S$. How many subsets of $S$ are there that contain $x$ but do not contain $y$? This question is on a practice exam ...
-4
votes
2answers
51 views

Power Set Of a Complement of an Infinite Set?

In order to find a Power Set of (B \ A), an infinite Set, would you keep finding elements until both sets have one in common? For example: $$\begin{align} A &= \{x \mid x = 2n, n \in \mathbb ...
2
votes
2answers
50 views

Calculate Intersection with a Non Finite Set?

What is the best way to answer Intersection or Union based questions with a set that is not finite? such as this: Calculate: $A \cap B$ $$\begin{align} A&=\{x\mid x=n+9, n\in\mathbb N\}\\ ...
0
votes
0answers
11 views

Hasse diagram of cartesian product?

I have been looking at how to draw Hasse diagrams, and I have found examples of divisibility. I understand these and how to construct them, but is it possible to draw a Hasse diagram for a cartesian ...
0
votes
1answer
58 views

Proving 'All multiples of 10 are even numbers'

I made 2 equations: $A = \{n:n=10k \text{ for some } k∈N\}$ $B = \{n:n=2j \text{ for some } j∈N\}$ I solved for the equation if it is possible, so I wrote: $2j = 10k$ I used an arbitrary value ...
2
votes
1answer
39 views

Prove that any group of 14 people must contain either 5 mutual friends or 3 mutual strangers.

So I think I have the answer to this problem, but there's something about it that's bothering me: Suppose we choose a fixed point with $13$ edges coming out of it. There must be at least $a)$ $9$ ...
-1
votes
2answers
47 views

How do I simplify just using 2 logic operations?

I need simplify the following proposition to 2 logic operations using the laws of the algebra of propositions. Write each step on a separate line with the algebra law you used as a justification. ...
2
votes
0answers
25 views

Determine the possible grouping

Consider I have a set of $3$ object $1,2 $ and $ 3.$ What is the possible grouping? I'll have either $\{(1,2,3)\}$ or $\{(1),(2),(3)\}$ or $\{(1,2),(3)\}$ or $\{1,(2,3)\}$ or $\{(2,(1,3)\}.$ So, I'll ...
-1
votes
2answers
55 views

Expected values of a dice game with a 30-sided die and a 20-sided die.

Two people, $A$ and $B$, have a $30$-sided and $20$-sided die, respectively. Each rolls their die, and the person with the highest roll wins. ($B$ also wins in the event of a tie.) The loser pays ...
2
votes
1answer
21 views

Possibilities of license plates with special rules

I have looked all over the web for some additional information on this matter with no results. Lets say a new form of license plate have 4 letters followed by 3 digits and all sequences are possible. ...
1
vote
2answers
42 views

Probability that every player is dealt a heart

We've got a standard, 52-card deck. We're playing Bridge with 4 players, so every player is dealt 13 cards. There are $\frac{52!}{13!13!13!13!}$ ways to deal the cards to the four players. (Intuition ...
0
votes
0answers
7 views

Using Fleury's algorithm to find a semi-eulerian trail

Firstly, when using Fleury's algorithm to produce a semi-Eulerian trail can there be multiple answers, secondly how would I check if the answer that I obtained is correct? Is it enough to check if I ...
2
votes
1answer
34 views

Solve congruence using fermat's theorem [duplicate]

Hi I am given this problem and I am supposed to use fermat's theorem. Here is it is: Prove that $$24^{31} \equiv 23^{32} \pmod{19}$$ We are supposed to solve it by setting up the congruence like ...
1
vote
2answers
77 views

Fibonacci Numbers

I am supposed to solve these questions, I started when number 10 , in a traditional way , I computed the number of different hopscotch games when we have 5 squares , and I got 8 ways, when we have ...
1
vote
1answer
16 views

Counting Operations in the context of an Urn Problem

I was tasked with the following question, regarding the counting of operations in the pseudo code provided that has nested for loops: Let U ={B1,B2,...,Bn} with n >= 3. Interpret the following ...
0
votes
3answers
59 views

Birthday problem with 3 people

I have the following problem. It is a simple birthday probability problem with 3 people but I can't crack it Annie, Boris, and Charlie have random and independent birthdays. (We ignore leap years, so ...
0
votes
0answers
24 views

Real World Example for the Generalized Vehicle Routing Problem.

I’m writing my master thesis in applied mathematics and I need some help finding a real world application to the problem that I’m studying. My thesis deals with the Generalized Vehicle Routing ...
0
votes
2answers
35 views

Prove if the following is true or provide a counterexample if it is not

For all sets A and B, |P(A × B)| $\ne$ |P(A) × P(B)| My first instinct is that it is false and I picked sets like A = {1}, B = {2} but when you write out the power set of these sets you end up with ...