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

learn more… | top users | synonyms

1
vote
2answers
44 views

Proving that a function from $N\times N$ to $N$ is bijective.

I am stuck on this problem: Define $f: N\times N \rightarrow N$ by $f(i,j)=\frac{(i+j-1)(i+j-2)}{2}+i$. How do you prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically ...
0
votes
1answer
16 views

How many way can 7 friends line up if there are certain conditions?

How many ways can 7 friends line up if Ann, Beth, and Chris have to stand next to each other where Ann is ahead of Beth and Beth is ahead of Chris? Would it simply be $5*4*3*2*1=120$ ways? Expanding ...
0
votes
0answers
36 views

Proving that the set of irrational numbers is uncountable [duplicate]

Work: Assume that the set of irrational numbers is countable. Since $Q$ is infinite, it is therefore denumerable. Therefore, there exists a bijective function $f: N \rightarrow Q$. From here I am ...
0
votes
2answers
27 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
1answer
50 views

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$ is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I ...
-1
votes
0answers
18 views
2
votes
3answers
27 views

Find the formula for the given sum of series

Find the sum of the series: $$\sum_{i=2}^{n}\binom{i}{2}= \,^{2}C_{2}+\cdots+\,^{n}C_{2}$$ I did try expanding it and see if I could simplify it further.I am unable to find a formula for it? Can ...
0
votes
0answers
14 views

Simplify the following summation involving the Floor function

Let $x,y,n \in \mathbb{Z}$ and $a\in [0,1/3).$ Further assume that $x<0,$ and $y>-2x.$ Is there any significant way to simplify the following: $\left(\sum\limits_{i=\lceil 1/3-(x+a) ...
0
votes
1answer
35 views

How to come up with a probability distribution knowing the mean value? [on hold]

I would like to know about some algorithms or techniques to find a discrete probability distribution knowing the mean value. Let's say given the mean=2.5. The probability distribution can be $x_1=2, ...
0
votes
1answer
47 views

help in approaching this problem

This is a new scheme started by AirTel in Karnataka which allowed institutions to host websites on their servers by paying for only 4 of the 7 days per week. However, the service cannot be ...
-4
votes
0answers
19 views

In how many ways can i build this String : abbcccdddd? [on hold]

In how many ways can i build this String : abbcccdddd ?
2
votes
1answer
51 views

Confusion regarding steps in bipartite matching proof

Can someone please explain how it follows that $|N(S)|x \geq |S|x$? What I'm asking is why is it necessary to use the value of x to derive the inequality? Theorem 5.2.7. Let G be a bipartite graph ...
1
vote
2answers
41 views

How to find the Equivalence class for a given set?

I'm really having trouble understanding these equivalence classes. Could someone please guide me through the following problem step by step, and help explain this. I have a final exam next week, and ...
1
vote
2answers
40 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$$
0
votes
2answers
19 views

Solving Linear Recurrences

I have the following recurrence: $$a_n = 49 a_{n-2}, n \geq 2, a_0 = -8, a_1 = 14$$ I was able to derive the following: When $n$ is even then, $a_n = -8(7^n)$, and for the odd values of $n$, $a_n = ...
1
vote
1answer
35 views

Proving that $f: N\times N \rightarrow N$ is surjective [duplicate]

I am having trouble proving that the function $$f: N\times N \rightarrow N, \ \ f(i,j)=2^{i-1}(2j-1)$$ is surjective. Work: I know that using the theorem in which $n$ is the product of prime numbers ...
0
votes
2answers
45 views

Proving that $f$ is a bijection from $N$x$N$ to $N$.

I am having trouble with the following problem: $f: N\times N\rightarrow N$ and $f(i,j)=2^{i-1}(2j-1)$. Prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically equivalent. Work: I ...
0
votes
1answer
35 views

Determining the total degree of a tree

At the start of the solution, I understand that any tree with four vertices has three edges. I don't understand the next statement: "Thus the total degree of a tree with four vertices must be 6." ...
1
vote
1answer
33 views

Expected number of rolls when repeatedly rolling an $n$-sided die

Suppose I roll an $n$-sided die once. Now you repeatedly roll the die until you roll a number at least as large as I rolled. What is the expected number of rolls you have to make? I know the answer ...
0
votes
1answer
27 views

Chromatic Equivalence Requirements

I have searched and searched and am unable to find the answer that I am looking for. I am trying to determine the conditions required for two graphs to have the same chromatic polynomial. On both ...
0
votes
2answers
28 views

How many bit strings of length $7$ either begin with two $1's$ or end with three $1's$?

So for the first case (beginning with 2 $1's$) there are: $2*2*2*2*2=32$ ways Second case (end with three $1's$): $2*2*2*2=16$ And then we can just sum it $32+16=48$ different bit string of length 7 ...
0
votes
2answers
12 views

Combinations questions

a. How many different 4 letter codes can there be? b. What if letters cannot be repeated? c. What if, in addition, 2 of the letters are x and y? For a, it would simply be $26*26*26*26=456976$ For ...
1
vote
1answer
15 views

Question over combinations

A t-shirt is being sold in 8 colors, 4 sizes, collared or tee, and long sleeve or short sleeve. a. How many different shirts are being sold? b. What if collared shirts only come in 5 colors and 2 ...
1
vote
1answer
37 views

feedback on my answer regarding set intersections.

Prove or find a counter-example to the claim that for all sets $A,B,C$ if $A\cap B = B \cap C = A \cap C = \emptyset$, then $A \cap B \cap C=\emptyset $. the above statement is not true so i need a ...
0
votes
2answers
29 views

proving discrete mathematics or giving counter example

Prove or find a counterexample: For all real numbers x and y it holds that x + y is irrational if, and only if, both x and y are irrational. can anyone explain to me or give a hint on how to start ...
0
votes
3answers
43 views

proving or providing counter example in disrete mathematics

Prove or find a counterexample: The product of any three consecutive natural numbers is divisible by 6. if we take a few consecutive natural numbers such as 1 ,2 ,3. and multiply i get 6 which is ...
1
vote
0answers
23 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
votes
0answers
37 views

Write a non-recursive algorithm to compute n! [on hold]

I am having problems writing a code in java to compute n! without recursion. I know how to do it in loops, but I am not sure how to do it non-recursively. Thanks. ...
-1
votes
0answers
23 views

Write a recursive algorithm to calculate the number of ways the robot can walk n meters. [on hold]

I am having problems trying to solve these two questions. I am writing the code in java to produce this and have not gotten very far. Can someone please help? Thank you. a) A robot can take steps of ...
2
votes
5answers
631 views

Explanation of recursive function

Given is a function $f(n)$ with: $f(0) = 0$ $f(1) = 1$ $f(n) = 3f(n-1) + 2f(n-2)$ $\forall n≥2$ I was wondering if there's also a non-recursive way to describe the same function. WolframAlpha tells ...
1
vote
3answers
41 views

Proof by Direct Method

If $(3n+2)$ is odd then, prove $n$ is odd. $$3n+2 = (2n+1)+(n+1)$$ We already have a fact that $2n+1$ is always odd. So, for $3n+2$ to be odd, $n+1$ should be even (For $x+y$ to be odd then ...
-2
votes
0answers
27 views

Coefficient question in generating functions [on hold]

In each of the following, find the coefficient of $x^{2005}$ in the generating function $A(x)$. (a) $A(x) = (1 – 2x)^{5000}$ (b) $A(x) = \frac{1}{1 + 3x}$ (c) $A(x) = \frac{1}{(1 + 5x)^2}$ (d) ...
0
votes
1answer
30 views

terms/names for these *things* [on hold]

So I am having difficulty finding the correct terms to describe the following things. multiple planes make up a space multiple spaces make up a universe (maybe? if not, what is it?) multiple ...
-3
votes
1answer
34 views

Closed form questions [on hold]

Please could you help me to find the generating functions of the following sequences in closed form: (a) 1, 0, 1, 0, 1, 0, … (b) 2, –4, 6, –8, 10, –12, …
0
votes
1answer
39 views

Number of Solutions in counting problem [on hold]

Find the number of solutions to the equation a + b + c + d = 50 if each variable is: (a) a non-negative integer (b) a positive integer (c) an odd positive integer (d) an integer between 4 and ...
4
votes
3answers
565 views

Proof about prime numbers

Can we prove that every prime larger than 3 gives a remainder of 1 or 5(edited) if divided by 6 and if so, which formulas can be used while proving?
1
vote
2answers
77 views

Generating Functions for collection of balls

There are 10000 identical red balls, 10000 identical yellow balls and 10000 identical green balls. In how many different ways can we select 2005 balls so that the number of red balls is even or the ...
1
vote
2answers
40 views

What is the difference between a simple graph and a complete graph?

I might be having a brain fart here but from these two definitions, I actually can't tell the difference between a complete graph and a simple graph.
1
vote
4answers
33 views

Find $m$ and $n$

Two finite sets have m and n elements. Thew total number of subsets of the first set is 56 more than the two total number of subsets of the second set. Find the value of $m$ and $n$. The equation ...
0
votes
2answers
40 views

finding a boolean function with specific property

The problem I am trying to solve is: Prove that not every boolean function is equal to a boolean function constructed by only using $\wedge$ and $\vee$. My solution is $$\left(p\wedge\thicksim ...
0
votes
1answer
45 views

What is the statement |x+y|≤|x|+|y| saying

|x+y|≤|x|+|y| I know that |x| means the cardinality of x for example. But it looks to me like its saying the cardinality of x plus y is less then or equal to the ...
0
votes
1answer
13 views

Proving Boolean Function

Can anyone help me if I am right....!! The Question Reads: Prove that not every boolean function is equal to a boolean function constructed by only using ^ and v. This is my answer by the double ...
-1
votes
1answer
25 views

list all the equivalence relation [duplicate]

list all the equivanlance relations in the set A={1,2,3,4) so there should be 15 right? so what I got so far (1 1) (22) (33) (44) (12) (13) (14) (21) (23) (24) (31) (32) (34) (41) (42) (43) these ...
1
vote
3answers
31 views

Which discrete mathematics book to read for a software engineer?

I'm a computer science student, but I lack a good mathematics background. So I decided to start working on that. I was searching in the topic and I found that for computer science a good knowledge of ...
0
votes
5answers
53 views

Find the solution to the recurrence relation: $a_n=3a_{n-1}+1; a_0=1$

$$a_n=3a_{n-1}+1; a_0=1$$ The book has the answer as: $$\frac{3^{n+1}-1}{2}$$ However, I have the answer as: $$\frac{3^{n}-1}{2}$$ Based on: Which one is correct? Using backwards substitution ...
0
votes
3answers
37 views

Need to check if this function is bijective

I don't understand how $f : \mathbb N \to\mathbb N$ (where $0$ isn't included in the natural numbers set), $f(n) = n^2$ is not bijective. It seems both injective and surjective to me? Thanks got it!
1
vote
1answer
22 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
1answer
42 views

Find the generating function for a series , given a recurrence relation

I am solving a problem on an Online Judge. The problems solution boils down to find the solutions to the following recurrence relation: ...
1
vote
1answer
18 views

Proving a relation is a total order relation

Consider question #21 part a: Here is the solution: However, consider the definition of a total order relation: The solution didn't prove that the relation is a partial order relation. This ...
4
votes
0answers
25 views

Subsets of cyclic group with distinct pairwise differences

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a ...