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
34 views

Finding Recursive Definition for the following:

How would i start off to find a recursive definition for $X_{0}$=.19 $X_{1}$=.1919 $X_{2}$=.191919 ... $X_{n+1}$= what goes here?
0
votes
2answers
52 views

Fewest operations on an algorithm?

I'm very stumped on this problem I have and was wondering if anyone could lend me a hand here? Suppose that you have two different algorithms for solving a problem. To solve a problem of size $n$, ...
0
votes
1answer
44 views

How many integer solutions are there to $x_1 + x_2 + x_3 + x_4 + x_5 = 31$ with $x_i \leq i$

So i was given this question How many integer solutions are there to $x_1 + x_2 + x_3 + x_4 + x_5 = 31$ with $x_i \leq i$ So i looked at it and decided i have to use the inclusion exclusion ...
1
vote
1answer
26 views

Show that F(A−B) is not necessarily a subset of F(A)−F(B).

Let $U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$, and $f$ be a function from $U$ into $U$. Finally, let $F : P(U) \to P(U)$ be the function defined by $$F(X) = \{f(x) | x \in X\}$$ For ...
-3
votes
1answer
49 views

Prove that for every two subsets [duplicate]

I am very lost in this, can anyone explain this to me please? Let $U = \{1,2,3,4,5,6,7,8,9,10,11,12\}$, and $f$ be a function from $U$ into $U$. Finally, let $F : P(U) → P(U)$ be the function ...
1
vote
2answers
32 views

chinese remainder theorem problem in one of the steps

I need to calculate the following: $$x=8 \pmod{9}$$ $$x=9 \pmod{10}$$ $$x=0 \pmod{11}$$ I am using the chinese remainder theorem as follows: Step 1: $$m=9\cdot10\cdot11 = 990$$ Step 2: $$M_1 = ...
1
vote
4answers
44 views

n-cents stamp (Strong induction)

Imagine that your country's postal system only issues 2 cent and 5 cent stamps. Prove that it possible to pay for postage using only these stamps for any amount n cents, where n is at least 4. My ...
0
votes
1answer
25 views

Understanding Kleene star in relation to regular expressions

I have a homework problem for my intro computation class where I have to write a regular expression for an NFA. In order to help understand if my language is correct- I want to post some example ...
0
votes
0answers
12 views

NFA's regular expression

Which of the following is not a correct regular expression for this λ-NFA? ( it uses ε instead of λ.) Select one: a. (λ + a + ab)(a + b) b. a + (ab + a)(a + b) c. a + aa + ab + aba + abb d. ...
7
votes
4answers
3k views

There are 31 houses on north street numbered from 1 to 57. Show at least two of them have consecutive numbers.

I thought to use the pigeon hole principle but besides that not sure how to solve.
0
votes
0answers
45 views

Finding non-recurrent sequences

I am trying to figure out the non-recurrent and recurrent sequences. I can give many examples to recurrent sequences but it seems like i cannot find any other examples of non recurrent sequences ...
0
votes
1answer
33 views

Combinatorics: Using binomial coefficients to figure out playing card combinations

I have this sample problem from my notes about how to find different 5-card poker hands from a standard 52-card deck. Can someone explain to me what's going on? I don't get why the ...
1
vote
1answer
29 views

What is the probability of drawing a hearts when the first card you draw was spade? Please check the description

Intuitively we know that when the first card drawn was Spade, it left $13$ hearts and $51$ cards so the probability is $13/51$. I was trying to solve it by the formula of conditional probability ...
0
votes
0answers
16 views

Hasse diagrams (2 options)

Is it possible to draw more then one Hasse diagram for one/same poset ? $$ R = \{(1,1);(2,2);(3,3);(4,4);(1,3);(1,4);(2,4);(3,4)\} $$ There is no the smallest element, the greatest element is $4$. ...
2
votes
3answers
57 views

Finding the sum of n terms $S_n$ starting from sigma $k=0$

$$\sum_{k=0}^{n} ((4k-3)\cdot 2^k)+4=(2^{n+3}+4)n-7\cdot2^{n+1}+15$$ How? I've tried everything but i don't see it. Any equivalent solutions are also welcome, thanks.
3
votes
4answers
75 views

Recurrence relation $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$?

Consider the following recurrence relation $T(1)=1$ $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$ for all $n≥1$ The value of $T(m^2)$ for $m≥1$ is $(m/6) (21m – 39) + 4$ $(m/6) (4m^2 – 3m + 5)$ $(m/2) (m^{2.5} – ...
-1
votes
2answers
40 views

Prove using induction or strong induction.

Let the sequence $G_0, G_1, G_2, . . .$ be defined recursively as follows: $G_0 = 0, G_1 = 1$, and $$G_n = (5 G_{n-1}) − (6 G_{n-2})$$ for every n belongs to N, n ≥ 2. Prove using induction or strong ...
1
vote
1answer
27 views

Combinatorics - # of ways to choose people to 2 groups with condition

In a class there are 30 students, we need to choose 2 groups of 11 students so they can play against each other. Josh, one of the pupils has to be in one of the groups. What I did is this: We'll put ...
1
vote
3answers
44 views

Combinatorics - arranging people in a circle with a condition

Adam has 12 children In how many ways we can arrange his children around a circle table if Josh cannot sit next to Mark? My solution to this is: The total number of permutations for a circle is: ...
0
votes
2answers
39 views

How can I determine the arguments that make the matrix be one, no solution.

I'm studying for my final and encountered with this problem. Basically, the question asks that Let $$\left[\begin{array}{ccc|c} a&0&b&2\\ a&a&4&4\\ ...
-2
votes
1answer
59 views

Find the distinct equivalence classes

Let $B = \{0,1,2,3,4\}$ and let $\{0\},\{1,3,4\},\{2\}$ be a partition of $B$ that induces a relation $Q$. Find the distinct equivalence classes of $Q$.
-1
votes
1answer
38 views

Let $X = \{−1,0,1\}$ and $A =\mathcal{P}(X)$, and $R$ is defined on $A$ as for all sets $S,T \in A$, $\ldots$

Let $X = \{−1,0,1\}$ and $A = \mathcal{P}(X)$, and $R$ is defined on $A$ as for all sets $S,T \in A$, $$ SRT \Longleftrightarrow \text{the sum of the elements in $S$ equals the sum of the elements in ...
0
votes
1answer
20 views

Big-Omega: $\forall x, y \in N: y \in \Omega(x) \rightarrow y^3 \in \Omega(x^3)$

I am currently stuck on the following question: $$\forall x, y \in N: y \in \Omega(x) \rightarrow y^3 \in \Omega(x^3)$$ $$ x^3: x^3(n) = x(n) * x(n) * x(n) $$ $$ y^3: y^3(n) = y(n) * y(n) * y(n) $$ ...
0
votes
2answers
45 views

When will this multinomial coefficient be the largest?

Consider the multinomial coefficient $\left( \begin{array}{ccc} & 2015 & \\n& n& 2015-2n \end{array}\right)$. For what value of $n$ will this multinomial coefficient be the ...
0
votes
1answer
34 views

Sampling with replacement and frequency functions

You have 7 keys in your pocket, one of which opens your front door. You sample them with replacement until you get in. Let $W$ be the number of tries it takes. Find (and graph) the frequency ...
0
votes
1answer
21 views

Give an example that satisfies the following bijection, surjection, and injection requirements

Give an example of sets $X, Y$ and functions $f: X \rightarrow Y$ and $g: Y \rightarrow X$ that satisfy the following... $g \circ f$ is a bijection $g \circ f$ is different from the identity ...
1
vote
0answers
83 views

How many Strings of 6 letters contain: Exactly one Vowel, At least one Vowel?

I'm asked the following two questions: How many Strings of 6 letters contain a) Exactly one Vowel b) At least one Vowel a) This is what I know: The English alphabet has 21 consonants and 5 vowels. ...
3
votes
2answers
31 views

Prove: if $a \equiv b \pmod 5$ then $2a \equiv 2b \pmod{5}$?

Prove only using of the definition of congruence: if $a \equiv b \pmod 5$ then $2a \equiv 2b \pmod{5}$? I have thought about the solution as follows: $2a \equiv 10k+2r \equiv 5 (2k) +2r$ ......(1) ...
0
votes
2answers
84 views

Finding the nth term of 1, 6, 24, 76,212,…

What different methods of recursion can I use to find the nth term of this recursion? This should be simple but I don't know what I'm missing. Could you demonstrate the method? $n(0)= 1$, $n(1)= 6$, ...
2
votes
1answer
85 views

Find a recurrence relation and generating function of…

Model the amount of crab being caught per year based on the assumption that the # of crab caught in a year is the average of the # caught in the 3 preceding years. a.) Find a recurrence ...
0
votes
1answer
26 views

Is there an isomorphism between these two groups?

[Z6,+6] Z6={0,1,2,3,4,5},+6 is addition mod 6. [S6,o] S6 is a permutation group. Is there an isomorphism between these two groups? I have no ideas to figure out isomorphism between such two groups. ...
1
vote
1answer
47 views

In how many ways can you split 100 identical coins to 5 people, so that no one gets more than 50 coins?

In how many ways can you split 100 identical coins to 5 people, so that no one gets more than 50 coins? I know the general formula : $\binom{n+k-1}{n-1}$ Can someone give me some directions?I was ...
0
votes
0answers
32 views

Generalized induction proof

Prove using general induction that: $$\forall m\geq 0\,\,\,\,\,\ \forall l\geq m+1:\qquad f_l=f_{m+1}*f_{l-m}+f_m*f_{l-(m+1)}, \qquad\qquad (1)$$ where $f_l$ is the $l$-th Fibonacci number, where ...
0
votes
2answers
18 views

Unable to create spanning tree with the given diagram

I've been trying to figure out this question, but no matter how many times I try to answer the question, the end result will always be a circuit. Can anyone help me?
3
votes
4answers
199 views

Convincing Myself of Stamp Induction Induction Proof?

Use mathematical induction (and proof by division into cases) to show that any postage of at least 12 cents can be obtained using 3 cent and 7 cent stamps. So for this I understand that it can be ...
0
votes
4answers
57 views

Prove: If $A \subseteq B$ and $C \subseteq D$, then $A - D \subseteq B- C$

Prove that for every four sets A, B, C and D, if $A \subseteq B$ and $C \subseteq D$, then $A - D \subseteq B- C$ Assume $A \subseteq B$ and $C \subseteq D$ Since $A - D \subseteq B- C$ then $x \in ...
0
votes
1answer
40 views

There are 5 cubes, each cube has a different color and on each cube the numbers 1-6. Someone throws the cubes

There are 5 cubes, each cube has a different color and on each cube the numbers 1-6. Someone throws the cubes. How many combinations are there, in which the set of the numbers that appear on the cubes ...
1
vote
2answers
42 views

Two different answers - cubes and colors

If there are 5 cubes in 5 different colors (on each cube the numbers 1-6), and I want all the ways to choose the cubes so that at least 1 cube shows the number '3'. I can think of two different ways ...
2
votes
2answers
87 views

A connected simple graph G has 14 vertices and 88 edges. Prove G is not Eulerian.

A connected simple graph G has 14 vertices and 88 edges. Prove G is not Eulerian. -This was a two part question, and for the first part I had to prove why the graph is Hamiltonian, but now i am ...
0
votes
1answer
26 views

How is the relationship antisymetric

I have $R={(1,2),(2,3),(3,4),(4,5)}$. My book tells me that $R$ is antisymmetric. Antisymmetric is if $(x R y)$ and $(y R x)$ then $x = y$. Shouldn't I see something like ${(1,2),(2,1)}$ or ...
1
vote
3answers
55 views

Why must an inverse function be bijective?

Explain why $f^{-1}$ is a function if and only if $f$ is a bijective function. My attempt: $f^{1}$ is the inverse relation from B to A $\equiv$ function from B to A By definition of a function ...
0
votes
0answers
46 views

set of permutations of set $\lbrace 1,2,..,n \rbrace$ [duplicate]

Prove the following lemma for set of permutations of $\lbrace 1,2,\dots,n \rbrace$ $(n\geq2)$ and a fixed number $k\neq1$: $\textbf{lemma: }$The number of permutations where 1 and $k$ are in the same ...
4
votes
1answer
49 views

There are 5 cubes, each cube has a different color and on each cube the numbers 1-6

There are 5 cubes, each cube has a different color and on each cube the numbers 1-6. Someone throws the cubes. a. How many results are there? I was thinking: $6^{5}$ ways for the throws regardless of ...
1
vote
1answer
41 views

Prove that a simple graph with $2n$ vertices and $n^2 +1$ edges contains a triangle for $n \ge 2$

Prove that a simple graph $G$ with $2n$ vertices and $n^2 +1$ edges contains a triangle for $n \ge 2$. I see it for $n = 2$ or $n = 3$ ... , but I fail to generalize it.
2
votes
0answers
15 views

Within the number of different ways to order in line the letters of the word NOVATOLOGY, in how many ways G and N are not successive?

Within the number of different ways to order in line the letters of the word NOVATOLOGY, in how many ways G and N are not successive? I was thinking - let's put aside N and G. There are ...
1
vote
3answers
86 views

Prove by induction that $3^n +7^n −2$ is divisible by $8$ for all positive integers $n$…

Prove by induction that $3^n +7^n −2$ is divisible by $8$ for all positive integers $n$. So far I have the base case completed, and believe I am close to completing the proof itself. Base ...
1
vote
1answer
10 views

Within the number of different ways to order in line the letters of the word LOVEPONIXO, in how many ways there are no two O's one after another?

Within the number of different ways to order in line the letters of the word LOVEPONIXO, in how many ways there are no two O's one after another? I was thinking - there are $\frac{10!}{3!}$ different ...
0
votes
1answer
59 views

Find a recurrence relation that counts the number of off-diagonal elements of an $n+1 × n+1$ matrix…

Find a recurrence relation that counts the number of off-diagonal elements of an $n+1 × n+1$ matrix. Solve this recurrence relation for an expression of the number of off diagonal entries as a ...
2
votes
1answer
98 views

A connected simple graph $G$ has $14$ vertices and $88$ edges. Prove $G$ is Hamiltonian, but not Eulerian…

A connected simple graph $G$ has $14$ vertices and $88$ edges. Prove $G$ is Hamiltonian, but not Eulerian. -I almost feel like you have to prove these two parts separately. I understand that to be ...
0
votes
3answers
41 views

Inside a card deck there are 52 cards with 4 colors, 13 cards for each color

I could not edit the last post - if someone can delete it please do... This is the question (I fixed the number of colors): Inside a card deck there are 52 cards with 4 colors, 13 cards for each ...