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
1answer
55 views

What is the wrong in proving this Assumption?

In the famous case of proving that total number of degrees in a graph $G$: $\sum \deg(v_G) =2m$. By Using Proof by induction:- for: $$m=0: 2m= 2*0 =0 \tag 1$$ is true .. $(2)$...We add a new edge to ...
3
votes
1answer
68 views

Empty set question [closed]

$$ | \{ \{ \} \} | = 0. $$ Is this true or false?
1
vote
1answer
30 views

What are the cycles in this graph, and what are their sizes?

I have the following graph $G$. I'd like to find how many cycles there are and what their sizes are. Please correct me if I am wrong: in this graph there are $2$ cycles, $\text{1-2-3-4-5-1}$ with ...
1
vote
1answer
41 views

Proving that between each pair of vertices there is a path length $2$ at most

Let $G=(V,E)$ be a graph with $n$ vertices such that $\forall v,w\in V$ that doesn't have a common edge we have: $\text{deg}(v)+\text{deg}(w)\ge n-1$. Prove that for each pair of vertices ...
2
votes
4answers
46 views

Solve recurcion using generating function

I have got a problem with solving this equation using generating functions. $$ P_{n}=2nP_{n-1}-10n+5 $$ $$ P_{0}=5 $$ I started like that: $$ ...
0
votes
2answers
16 views

The difference between $[n]^k$ and $\begin{pmatrix} [n]\\ k \\\end{pmatrix}$

as the title suggests, I am not able to clearly distinguish between these 2 sets. To avoid confusion over notation, my notes define them as follows: i) For any integer $r \ge 0$, the family ...
2
votes
1answer
35 views

Expanding summation $\sum_{i=1}^{k+1}i(i!)$

Expand the summation: $\sum_{i=1}^{k+1}i(i!)$ My solution is: $\sum_{i=1}^{k}i(i!)+k(k+1)$ But I think it is wrong. Please help. Thanks
0
votes
1answer
34 views

If $G$ is simple and $deg_+(v) \ge k\ge 1$ , then there is a simple cycle of at least size $k+1$

I am going to show you my proof/ and please correct me if wrong: Begin with some node $v$, and mark it. Follow one of its outgoing edge $(v,w)$ to next unmarked node, and mark it, by doing this ...
0
votes
0answers
8 views

Using the algebraic expression ((x-2)+3) / ((2-(3+y))*(w-8)) show the results of performing a preorder, an inorder, and a postorder search.

Using the algebraic expression ((x-2)+3) / ((2-(3+y))*(w-8)) show the results of performing a preorder, an inorder, and a postorder search. Preorder is root, left, right. Inorder is left, root, ...
0
votes
1answer
19 views

Generating function for $2n$ distinct balls to $n$ bins such that each bin will hold exactly two balls

Find the number of ways for having $2n$ distinct balls in $n$ distinct bins such that each bin will hold exactly two balls using a generating function The generating function (exponential) would ...
1
vote
3answers
18 views

How is multiplication in a counting subsets problem justified?

Consider a set of $12$ people: $5$ men and $7$ women. To count all the $5$ people teams consisting of $3$ men and $2$ women, we choose $3$ men out of $5$ and $2$ women from $7$: $ {5 \choose 3} {7 ...
0
votes
3answers
52 views

Can someone explain what this theorem and proof is saying

can someone please explain what the following theorem and proof is saying. Thanks in advance
0
votes
2answers
40 views

Find coefficient of $X^{12}$

I need to find coefficient of $X^{12}$ in $({1-2X})^{19}$. What is the formula to solve it?I only know about $$\frac{1}{a-X}=\frac{1}{a}\sum_{r=0}^\infty \frac{X^r}{a^r}$$ ...
0
votes
1answer
61 views

Ways to have exactly $n$ nominees out of $2n$ voters

There are $2n$ voters, each write his name on a paper as the voter and the name of his nominee. How many ways there are such that there are exactly $n$ different nominees and each of the nominees ...
0
votes
1answer
38 views

Strong Induction: Prove that sqrt(2) is irrational

This question comes directly out of Rosen's Discrete Mathematics and It's Applications pertaining to Strong Induction. Use strong induction to prove that $\sqrt{2}$ is irrational. [Hint: Let $P(n)$ ...
2
votes
2answers
41 views

Proofs utilizing the Well-Ordering Property

This question comes directly from as an example in Chapter 5.2 of Rosen's Discrete Mathematics and It's Applications textbook on page 341. Use the well-ordering property to prove the division ...
1
vote
0answers
27 views

Questions about counting subsets

To me it seems like counting multiset permutations is the same as counting subsets with dependent events. For example, to count all the permutations of the word MISSISSIPPI, we simply count all the ...
0
votes
1answer
21 views

Determine whether the given relation is an equivalence relation

Problems: 1.) R = {(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2)} 2.) R = {(x, y) ¦ y - x is an odd integer} 3.) R = {(x, y) ¦ y - x is a multiple of 3} Attempt: By definition, a relation is ...
0
votes
0answers
16 views

Proofs By Induction Help

Hey I'm having some problems on these proofs. I think Im doing right but if anyone can show me the right way to do them that would be great! 1) ∑ i=1, n of (2i) = n^2 + n ...
0
votes
0answers
30 views

Iterated logarithm exercise

I have to solve the following exercise: "Find the largest integer $n$ such that $log^{*}n = 5$. Determine the number of decimal digits in this number." I have already seen an answer but I need an ...
0
votes
3answers
50 views

Give an example of a function that when composed with itself is a bijection

My question: Is it possible to have a function $f: A\to B$ so that $f\circ f$ is a bijection if $A \neq B$?? I was asked to give two examples where the above is true. Both of my examples ...
0
votes
1answer
82 views

Proving that $\sum \deg(v) = 2m$ for any Graph $G$

Here is My proof, please correct me if wrong, I try to be formal. Proof by Induction: Let $\sum \deg(v)=2m$ assumption... when #of nodes is $n=0$. so here the equation is $\sum \deg(v)=2(0)=0$ ...
1
vote
0answers
23 views

Expected number of rolls to roll every number [duplicate]

If I am rolling I die until I roll every number at least once, what is the expected value of times that I will need to roll the die? After a brief computer simulation, I got 15. But why is this the ...
1
vote
1answer
35 views

Solving the recurrence $T(n) = \sqrt n T(\sqrt{n}) + \sqrt{n}$

A former student of mine was TA-ing an algorithms class last quarter and asked students to solve this famous recurrence relation: $$T(n) = \sqrt n T(\sqrt{n}) + n$$ There are several ways to solve ...
0
votes
0answers
53 views

How to find the number of subsets of a set $X$ such as the sum of their elements is divisible by 3?

Let $X$ be a set with $N$ numbers ($N$ is less than 1000). The problem is to find the number of subsets of $X$ such that the sum of their elements is divisible by 3. Lets denote this number by ...
2
votes
1answer
29 views

Determining if two sets are equal, subsets of one another, or neither

Problems: 1.) $A = \{x \mid x^4 - 3x^2 = 4\}$, $B = \{x \mid x^2 - 4 = 0\}$ 2.) $A = \{x \in \mathbb{C} \mid x^3 = 1\}$, $B = \{x \in \mathbb{C} \mid x^2 + x +1 = 0\}$ 3.) $A$ = The (real) domain ...
1
vote
2answers
21 views

Permutation with constrained repetititons

The question is as follows: How many ways can 12 identical white and 12 identical black pawns be placed on the black squares of an 8 x 8 chessboard My answer was $\frac{32!}{12!*12!}$ But the ...
2
votes
0answers
19 views

Falling factorial counts permutations, what does rising factorial count?

Rising factorial example: Let $x = 7$ and $r = 4$. Then $7^{(4)} = 7(8)(9)(10) = 5040$. If we divide $7^{(4)}$ by $4!$ it counts multisubsets. But what kind of combinatorial problem does rising ...
1
vote
1answer
18 views

Generating function for a bin that has either no elements or 2 only?

What is the generating function for a bin that has either zero elements or 2 only? We start with: $(1+x^2)$ which if it had an $x$ it would translate to $\frac {1-x^3}{1-x}$ So I thought maybe I ...
1
vote
1answer
26 views

generating function as english statement

An ordinary enumerator is given as $(1+x+x^2)^p$. This is being understood as follows: There are 2 each of p kinds of objects.The ordinary enumerator for selecting none (or) one (or) both the ...
-1
votes
0answers
41 views

Colouring of Cycles - Cn

How many different ways are there to colour the cycle graph $C_n$ using only $3$ colors?? I know the chromatic polynomial: $ C_n = (t-1)^n + (-1)^n(t-1) $
0
votes
0answers
23 views

Constructing any function $\{1 \dots n\} \rightarrow \{1 \dots k\}$ using functions $\{1 \dots n \} \rightarrow \{1,2\}$

This is: i'm having some function $\{1 \dots n\} \rightarrow \{1 \dots k\}$ is it possible to show bijection between functions of type $\{1 \dots n\} \rightarrow \{1 \dots k\}$ and some function (or ...
0
votes
1answer
22 views

Smallest odd $n$ for which there exists a proper linear cyclic code of dimension $5$

Find the smallest odd value of $n$ for which there is a proper linear cyclic code of length $n$ and dimension $k = 5$. For a proper code, $k < n$. So $n \geq 7$. My notes say we need a proper ...
1
vote
1answer
39 views

Exclusive OR a set with itself

Given set A is a finite set, then $ A\oplus A=\emptyset $ and $A\oplus \emptyset = A$. These make perfect sense to me, since the XOR operator requires only one "True" Condition for the output to be ...
1
vote
0answers
38 views

Feedback on Set Theory Questions - Study Help

I am doing some previous exams on Discrete Math as practice and I am just looking for some feedback on the answers as I don't think they are available publicly. I am reasonably confident on some, but ...
1
vote
5answers
90 views

Prove that $ a^2-4b \neq2$ if $ a,b \in \mathbb{ Z}$

My solution : We suppose that is true. Then by contradiction: $a^2-4b-2=0$ $a^2=4b+2$ $a=2(b+1/2) ^{0.5}$ then $(b+1/2)$ is fraction and rooted by $0.5$ so the square root of any fraction $+$ ...
2
votes
2answers
40 views

Difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$

Existential quantifier confusion: what is the difference between $(\exists z)[z > 0 ∧ z^2 = 2]$ and $(\exists z )[z > 0 \Rightarrow z^2 = 2]$? What are the differences between those two ...
2
votes
1answer
49 views

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$

Universal quantifier question: $(\forall x)[x < 0 \Rightarrow x^2 > 0]$. Given the above expression, For all of $x$ [ if $x$ is less than zero, then $x^2$ is greater than zero]. Is that a ...
2
votes
2answers
42 views

Solution to Fibonacci Recursion Equations

Let the sequence $(a_n)_{n\geq0}$ of the fibonacci numbers: $a_0 = a_1 = 1, a_{n+2} = a_{n+1} + a_n, n \geq 0$ Show that: i) $$a^2_n - a_{n+1}a_{n-1} = (-1)^n \text{ for }n\geq1$$ I try to show ...
1
vote
2answers
37 views

Linear Recurrence Problem

$f(0)=3, f(1)=1, f(n)=4f({n-1})+21f({n-2})$ Thought linear recurrence problems usually have subsets of things, and this seems like a new type for me. Can anyone help me out with hints?
-4
votes
1answer
112 views

I have proved that 1 + 1 = 0 [closed]

I have proved that 1 + 1 = 0 in one of my questions where a field was given. I was wondering if it is true in every field we have 1 + 1 = 0. Also i was wondering (i know how to prove 1 + 1 = 0) can ...
-1
votes
1answer
27 views

What is transpose multiplier and forward multiplier?

For linear system X = A*s, we define the forward and transpose multiplies Af and At as follows: Af = @(s) A*s; At = @(s) A'*s; I want to know what is forward ...
0
votes
0answers
35 views

How to proceed with this simple proof?

If $$\alpha_k = \sum_l a_l \ \ g((k-l)T-l\Delta T)$$ $$s_k = \sum_l \alpha_l \ \ q((k-l)T+k\Delta T)$$ where $a_l \in \pm1$ and $g(t) = \frac {\sin(\pi t/T)}{\pi t/T}$ and $q(t) = \frac {\sin(\pi ...
-1
votes
2answers
47 views

Every field has at least two elements

I got a question saying in every field (F, +, ⋅, 0, 1), the set F has at least 2 elements. It asks if it is true prove it or if false provide a counterexample. I understand the idea of finite fields ...
5
votes
1answer
30 views

Prove that given graph consisting of vertices numbered with composite numbers is not eulerian

We have the following graph definition: $$V(G_n)=\{1\leq m\leq n : m = pq\}$$ (so vetices of $G_n$ are composite numbers) $$E(G_n)=\{\{i,j\}:i\perp j\}$$ (so vertices $i,j$ are connected if and only ...
2
votes
3answers
41 views

Discrete Math: Unions, Intersections, Complements

Are these answers correct? The union and intersection only include the elements in the universal set? $U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$ (where $U$ is only a subset of the Universe) $A ...
2
votes
1answer
32 views

How many triangles can be made from $n$ points on a line and not on a line

We have a plane with $n$ points $(n\ge 34)$. $17$ points are on one line, and the rest are positioned such that no three points are on one line. How many triangles can we make from the $n$ points? ...
0
votes
1answer
36 views

Suppose A and B are disjoint, while B and C are disjoint as well.

I am currently trying to understand this example in the textbook and it's not really making any sense to me. Lets say A and B are disjoint, while B and C are disjoint as well. According to the ...
0
votes
0answers
30 views

Determining if two bounds are true

Question says assume $f$ and $g$ have a domain of the integers, and target space of the real numbers. $f$ and $g$ are bounded. Prove if the following statements are true or give a counterexample: if ...
0
votes
0answers
29 views

How to predict intuitively the recurrence relations of josephus problem?

i have studied the Josephus problem from the concrete mathematics book.I have understand all related calculations discussed on that book.However i have some difficulties regarding to recurrence ...