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
3answers
32 views

Showing that a series solves a recurrence relation

Let: $a_n = a_{n-1}+2a_{n-2} +3\cdot 2^n$, $\displaystyle b_n=4\sum_{k=0}^nk\binom n k$ Show that $b_n$ solves $a_n$ There are no starting conditions for the recurrence, that is how the ...
1
vote
1answer
62 views

If $G$ is simple and $deg^+(v)\geq k \geq 1 \space \forall \space v \in V$ there is a simple cycle of at least size $k+1$

I have the following proof but it is tough could someone help me to understand it, Proof: Start at an arbitrary node $v$ and mark it, and so on until you have marked all nodes in the series then a ...
0
votes
2answers
53 views

Proof that if all vertices have degree at least two then G contains a cycle

Here is the proof, but please correct me if wrong : We assume $G$ is simple and let $P$ be the longest path $=v_0v_1v_2\ldots v_{a-1}v_a$. As it is given that the degree of $v_a$ is even ,then $v_a$ ...
0
votes
0answers
13 views

Discrete grid: random points with radial probability distribution

I have a cubic 3D grid of $N^3$ points. I randomly choose a certain point to be the centre. Now I want to generate random points which obey a certain probability distribution $\rho(r)$ which depends ...
0
votes
2answers
58 views

Applying Inclusion-Exclusion principle

How to apply principle of inclusion-exclusion to this problem? Eight people enter an elevator at the first floor. The elevator discharges passengers on each successive floor until it empties on ...
1
vote
2answers
41 views

Why are these ways of choosing guests to a party the same?

You are having a party, and of your n friends you can invite only k guests. Why are the same number of guest lists as there are of ways of choosing whom not to invite?
0
votes
1answer
56 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
69 views

Empty set question [closed]

$$ | \{ \{ \} \} | = 0. $$ Is this true or false?
1
vote
1answer
31 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
44 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
47 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
38 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
9 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
53 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
41 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
41 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
42 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
23 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
85 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
25 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
36 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
55 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
30 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
22 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
20 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 ...
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
23 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
41 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 ...
2
votes
5answers
108 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
42 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
52 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
44 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
38 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
116 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
28 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
36 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
48 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 ...