Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

0
votes
1answer
56 views

Prove that the set $B = \{0,1\}^8$ forms a group

Prove that the set $B = \{0,1\}^8$ forms a group under the composition operator: $g \circ f$ is defined by $(g \circ f)(x) = g(f(x))$
-2
votes
1answer
60 views

Show that $∼$ satisfies the three properties of an equivalence relation. [closed]

Given sets $A$ and $B$, say that $A\sim B$ (the sets are equicardinal) if $\lvert A\rvert\sim\lvert B\rvert$ (that is, there exists a bijection $f$ from $A$ to $B$.) Show that $\sim$ satisfies the ...
1
vote
2answers
74 views

Which is the mathematical theory that talks about these structures?

Let's define $\sigma(n)$ as the sum of the digits of the integer $n$ modulo $9$, having posed that $\sigma(9) = 9$. Now consider 2 number $a$ and $b$ in the set $\{1, \cdots, 9\}$. Which is the value ...
1
vote
3answers
75 views

Prove that *BIG'* = *BIG* - *Little* (set difference) is uncountable.

Let BIG be an uncountable set and let Little be a countable one. Prove that BIG' = BIG - Little (set difference) is uncountable.
1
vote
1answer
50 views

Determining whether function is a bijection onto its range and if it is finding $f^{-1}(5)$

Answer if each of the following functions is a bijection onto its range. For any function that is a bijection, identify $f^{-1}(5)$. Justify all of your answers. a) $f(n)$ = $2n$ mod 10. The domain ...
3
votes
1answer
93 views

Proving whether functions are one-to-one and onto.

I'm doing some practice problems and am having trouble answering these problems: Prove or disprove each statement. (a) If $f : A \rightarrow A$ is one-to-one, then $f$ is onto. (b) If $A$ is finite ...
0
votes
0answers
371 views

Palindrome Decidable by DFA

Here's a problem a professor I was talking with gave to me to see how people solve. How would you solve this? A string in {a,...,z}* is said to be a palindrome if it is equal to its own reversal. Is ...
0
votes
1answer
45 views

Order of dodecahedron automorphism group.

I need to find out how many elements are in the automorphism group of a regular dodecahedron. So Using Orbit-Stabilizer theorem I get $|G|=|G_x||O_x|$ If we pick a point on the wall of the ...
0
votes
2answers
101 views

Solve discrete Math Problem using abstract algebra, postage problem?

The question I am looking at is not very hard: Determine which amounts of postage can be written with $5$ and $6$ cent stamps. To determine the amount, use a brute force way to solve it. Counting ...
-1
votes
1answer
67 views

prime number related proof

I want to prove if following is true for every integer a,b and c $$a^2 - b^2 = cp $$ then p|(a+b) or p|(a-b) where p is a prime number. Any suggestion, help would be highly appreciated. Thanks ...
5
votes
3answers
152 views

How to tell if a function is onto or one-to-one

I'm practicing what we learned in lecture today and unfortunately I have little to no understanding about the material. I only know the difference of these functions only when a diagram is present ...
-2
votes
1answer
41 views

Below question is on set theory also please tell venn diagram also [duplicate]

In a locality with 1250 houses,975 families have radio set and 450 have T.V sets .How many possess radio sets only?How many possess both? As it is not possible to draw the venn diagram here please ...
0
votes
1answer
33 views

Committee selection with no two consecutive people.

Assume that $10$ people are sitting around a round table. Determine the number of ways to choose a committee, where the committee is made up of two people who are NOT sitting next to each other. ...
1
vote
1answer
317 views

How many permutations (bijections) are there on the set B = {0,1}^(8) of bytes? How can there be permutations if there is no function?

I know that B would be the set {00000000, 00000001, ..., 11111111}, and there are 256 elements on this set. I don't know how there can be a bijection on the set, though...I thought that you needed a ...
1
vote
1answer
85 views

Help understanding solution to growth of partition function

I'm currently a Combinatorics student trying to parse through this solution. I do not understand the proof currently. Any help understanding it is greatly appreciated. Question Let the number of ...
1
vote
0answers
86 views

How many permutations (bijections) are there on the set B = {0,1}^(8) of bytes?

How many permutations (bijections) are there on the set B = {0,1}^(8) of bytes? Prove that this set forms a group under the composition operation: g • f is defined by (g •  f)(x) = g(f(x)).
1
vote
1answer
62 views

How can I encode this?

Let say I have 7 integers: 1, 2, 3, 4, 5, 6, 7. Among the 7 integers, I choose 3 integers. For example, my choice is (1,2,3). Note1: The order of the integers in the choice doesn't matter. This means ...
0
votes
1answer
26 views

Probability of packages

Suppose mail is delivered 6 days each week. Someone sent you ten packages, all of which are scheduled to arrive this week. But you don't know what day any of the packages will arrive. What is the ...
-1
votes
1answer
36 views

Prove that for every integer m, 2m +1 and 3m+1 are relatively prime [closed]

Prove that for every integer m, 2m+1 y 3m+2 are relatively prime numbers
0
votes
2answers
42 views

Probability of seven coins

Flip seven fair coins. Describe the state space for this situation. define a random variable corresponding to the number of heads that show when the coins land. What is the probability that this ...
0
votes
2answers
60 views

Probability of lightbulbs

There is a bank of four lightbulbs, each has a probability of 0.02 of being out when you flip the switch. The workingness of each lightbulb is independent of the others. Describe the state space of ...
1
vote
1answer
56 views

How many strings of letters, where all of $a,b,c$'s don't create a continuous block.

I need to find out, how many string made out of $\alpha$ $a$'s, $\beta$ $b$'s and $\gamma$ $c$'s where all of $a,b$ or $c$'s are not packed together, meaning that for $2$ $a$'s and $3$ $b$'s and $2$ ...
3
votes
5answers
46 views

$\sum_{i=1}^n \frac{1}{i(i+1)} = \frac{3}{4} - \frac{2n+3}{2(n+1)(n+2)}$ by induction.

I am wondering if I can get some help with this question. I feel like this is false, as I have tried many ways even to get the base case working (for induction) and I can't seem to get it. Can ...
3
votes
2answers
138 views

bags of chocolate problem

I have $4$ different types of chocolates. How many unique bags of chocolate can I make with $10$ items per bag that has at least one type of each chocolate in each bag? I don't know if this is ...
0
votes
2answers
35 views

Discrete math promblem

Suppose that a department contains 10 men and 15 women. How many ways are there to form a committee with six members if it must have more women than men?
1
vote
4answers
245 views

Why is $2^n$ the maximum number of subsets of a set of size $n$? [duplicate]

There is a set with $n$ elements. Why is the maximum number of subsets that can be formed out of it $2^n$?
1
vote
0answers
60 views

Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
4
votes
4answers
131 views

Prove that $1+a+a^2+\cdots+a^n=(1-a^{n+1})/(1-a)$.

I have problem. Prove this using Mathematical Induction. I am a newbie in Mathematics. Please help me. $$1+a+a^2+\cdots+a^n = \frac{1-a^{n+1}}{1-a}$$ This is my way for get the proof Basic ...
1
vote
1answer
224 views

Frobenius coin problem, 5 and 9

I am hoping to get some help with two problems related to Forbenius coin problems. A) A fictional government has decided to issue currency in only 5 and 9 value denominations. Prove that there is a ...
0
votes
1answer
110 views

Growth of functions (Discrete math)

a) Show that $ \frac{x^3 + 2x}{2x+1} \; is \; O(x^2) $ b) Find witnesses $ C \; and\; K $ My answer was : $ x^3 + 2x \le c(x^2)(2x+1) $ $ x^3 \le c(x^2)(2x+1) , \; when \;c=1 , x>1 $ $ 2x \le ...
1
vote
1answer
47 views

Completion of the square

Prove that for all $r \in \mathbb{R}$ $2^r + 3^r + 6^r - 4^r - 9^r \leq 1$ I have stared at it for quite sometime.. My prof suggested to use the completion of the square.
3
votes
1answer
127 views

Arithmetic and Geometric Mean Inequality

Use the AM - GM inequality (no other method is acceptable), to prove that for all positive integers $n$: $$\left(1 +\dfrac{1}{n}\right)^n \leq \left(1 + \dfrac{1}{n+1}\right)^{n+1}$$ I see that it ...
0
votes
3answers
136 views

The sequence 1,11,111,… and the prime factorization of its elements

I have been recently investigating the sequence 1,11,111,... I found, contrary to my initial preconception, that the elements of the sequence can have a very interesting multiplicative structure. ...
0
votes
2answers
69 views

Can somebody explain why the interval $\left ( 0,1 \right )$ is not countable? [duplicate]

I cannot seem to understand the proof of why the interval $\left ( 0,1 \right )$ is not countable. The proof that is written in my book using the method of Reductio ad absurdum. It starts with the ...
0
votes
1answer
37 views

Asymptotic equality proof with $a_n^2 \ln a_n ~ n$

Given $a_n^2 \ln a_n \sim n$, prove that $a_n \sim \sqrt{\frac{2n}{\ln n}}$. How do I approach this?
1
vote
0answers
23 views

Invalid operator in sequences

$V_n = n! + 2$ $n \ge 1$ Find $V_3$. I am just wondering what does the "!" operator after "$n$" mean?
2
votes
1answer
315 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
1
vote
0answers
250 views

Big-O Notation question

Use the definition of $ "f(x) is O (g(x)) $ to show that $ x^4+9x^3 + 4x+7 is O(x^4) $ My answer was : I used divide and conquer $ x^4 \le cx^4 , when\; c = 1 $ $ 9x^3 \le cx^4 , when \; c=9 \; ...
1
vote
1answer
42 views

Induction Proofs

C1 = 0, Cn = 4C$\lfloor n/2 \rfloor + n$ Prove that $Cn$ less than or equal to $4(n - 1)^2$ What I did: Base step: n = 1 $C1$ <= $4(1 - 1)^2$ 0 <= 0 therefore true how do you do the ...
2
votes
0answers
42 views

Ultrametric matrices and their inverse

A non-negative square matrix $A$ is ultrametric iff: $A(i,i)>\{A(i,k),A(k,i)\}\forall k,i$ $A(i,j)\geq\min\{A(i,k),A(k,j)\}\forall i,j,k$ It is well-known that the inverse of non-negative ...
3
votes
2answers
175 views

When do repeated intervals of time overlap?

I have two time intervals A and B that occur in time at a start time and occur until an end time. These time intervals however repeat in time from their start time until another end time. So each ...
0
votes
1answer
35 views

Discrete Math need some help!

I'm taking discrete math course now and need some help on this question. THX!! T/F or unknown? There is a function that is both $O(n^2)$ and $\Omega(n^3)$. Given two functions $f(n)$ and $g(n)$, ...
1
vote
2answers
61 views

If There are four 2's three 1's and two 0's how many was can you arange them in a 9 Digit number!

If There are four 2's, three 1's and two 0's, in how many was can you arrange them in a 9 Digit number! Using Permutations only. Show your answer is corrrect by counting it in three different ways and ...
-3
votes
2answers
81 views

Prove that $3\mid n^3 +n$ for all positive integers $n$ [closed]

Please can any one solve this Prove that $3\mid n^3 +n$ for all positive integer n
1
vote
2answers
40 views

I have confusion while translating propostions to logical expressions

I have following propositions: p:Grizzly bears have been seen in the area. q:Hiking is safe on the trail. ...
1
vote
1answer
162 views

Finding recurrence relation given the generating function

So I'm given the generating function $F(x)={1+2x\over1-3x^2}$ I'm supposed to find the recurrence relation satisfied by fn. I managed to get it into 2 separate geometric series and derive $f_n = ...
1
vote
0answers
43 views

Help Solving a Recurrence Relation with an Inverse Term

I am having a hard time generating a characteristic polynomial for a recurrence relation I thought of the other day, $a_n = a_{n-1} + \frac1{a_{n-1}}$. I am pretty familiar solving basic recurrence ...
0
votes
4answers
55 views

Formula's for Product Notation(Rewriting of Product Form)

Find a formula for the sequence $z$ defined by $$z_{y+1}= \prod_{i=1}^y z_i $$ Can someone show me the steps on how to find this formula?
0
votes
2answers
30 views

multiplying a non-square number to get a square

I have a theory that the only way how can I get a square from a non-square is to multiply it by some power of itself. For example 3 multiplied by 27 gives 81. Is this always true? If yes, how would ...
0
votes
1answer
218 views

understanding the proof of even-odd handshake problem

I´d like to know if I understand correctly the argument behind the even-odd handshake problem. Basically the theorem says that the number of persons who have shaken an odd number of hands is even. My ...