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

1
vote
3answers
23 views

Determine whether the following argument is valid

Premises: $p → r, q → r$, and $q ∨ ¬r$ Argument: $¬p$ I understand the answer but am having problems understanding how to construct this statement ie $(p → r)∧(q → r)∧(q∨ ¬r)$ where does the argument ...
1
vote
1answer
60 views

prove that $p(n) := n^2 + n + c$ is not prime

The question is in MIT Mathematics for CS assignments but unfortunately there is no solutions. -> I do understand that it is false if we use $n = c$ or $n = c-1$ but cannot formally write it as ...
1
vote
3answers
33 views

Discrete metric means all sets are countable?

I was working on a proof of "Show that if $A \subseteq \Re^2$ is discrete, then A is a countable set." and I thought about using the discrete metric ($d(x,y)=\delta_{xy}$) on the set as an example ...
-3
votes
0answers
30 views

Write a recurrence relation [closed]

Write a recurrence relation for the value of a binomial coefficient, and explain why it makes sense. I was getting: Using a Pascal's triangle looking at row 5 that (x + y)5 = 1 x5 + 5 x4y + 10 x3y2 + ...
0
votes
0answers
23 views

Comparison of books that teach proof techniques

I have to take discrete math and want to learn proof techniques both to get ahead in it as well as open up the possibility of understanding higher math. I've seen several books recommended such as How ...
1
vote
1answer
45 views

What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?

What is the combinatorial proof for the formula of Stirling numbers of the second kind ? i.e. S(n,k) where n is the number of objects and k is the number of parts $${n\brace ...
-3
votes
2answers
64 views

$n! \le n^n$, $\forall$ $n \ge 1$. [closed]

Prove that $n! \le n^n$, $\forall$ $n \ge 1$. It is so difficult, please help me solve it. Thank you.
0
votes
0answers
19 views

How is floor(x) + j/A between x and y, and how the proof is related to the well-ordering property?

I am having trouble with a proof by well-ordering property exercise. Use the well-ordering principle to show that if x and y are real numbers with $x \lt y$, then there is a rational number r with $x ...
2
votes
1answer
30 views

a Maximum of Discrete Function 2

I have asked a question about a maximum of discrete function yesterday at a Maximum of Discrete Function. I want to generalize the question. Let $X=\{(x_1,\ldots ,x_n)\mid x_i=\pm 1,1\leq i\leq n\}$. ...
0
votes
1answer
51 views

Is the game fair or unfair?

In a box there are 20 balls, 10 are red and 10 black. An automaton draw randomly successively the 20 balls. The player wins if at any time during the drawing of 20 balls more black than red balls are ...
0
votes
1answer
13 views

Giving change - what denominations guarantees an optimal greedy algorithm?

I was thinking about how giving change is a greedy algorithm for the optimal result, where the optimal result is getting the lowest amount of bills and coins possible. The algorithm I am referring to ...
9
votes
2answers
208 views
+50

How do I prove this combinatorial identity using inclusion and exclusion principle?

$$\binom{n}{m}-\binom{n}{m+1}+\binom{n}{m+2}-\cdots+(-1)^{n-m}\binom{n}{n}=\binom{n-1}{m-1}$$ Note that we can show this with out using inclusion and exclusion principle by using Pascal's Identity ...
0
votes
2answers
45 views

proof that power set A union B doesnt equal powerset A union powerset union B

Why is this equation: \begin{equation} \mathbb{P}(A \cup B) = \mathbb{P}(A) \cup \mathbb{P}(B) \end{equation} false with: $A = \{0\}$ and $B = \{1\}$? Are they not both $\{ \emptyset,0,1\}$?
0
votes
1answer
21 views

Generating function of Language is rational

Let W be the set of all words over an alphabet $\Sigma$. Let $$L=\{w\in\Sigma^* | w\neq uvu',\text{ with }u,u'\in\Sigma^*,v\in W\}$$ I have to show that the generating function of L is rational. My ...
3
votes
1answer
37 views

a Maximum of Discrete Function

Define a set $$X=\{(x_1,\ldots ,x_n)\mid x_i=\pm 1,1\leq i\leq n\}$$ Fix $a$, $b\in X$. Consider the discrete function $$F(x_1,\ldots,x_n)=(x_1a_1+\cdots+x_na_n)^2+(x_1b_1+\cdots+x_nb_n)^2$$ ...
0
votes
1answer
21 views

Proof If a tree is not trivial, then there are at least two pendant vertices?

I have the following Proof but could not understand it Proof. If a tree has $n(≥ 2)$ vertices, then the sum of the degrees is $2(n − 1)$. If every vertex has a $degree ≥ 2$, then the sum will be $≥ ...
2
votes
1answer
50 views

Transfer Matrix Method to determine the generating function

Let $G = (V,E,\Phi)$ be a weighted directed graph and $\mathcal{W}' : E \rightarrow \mathbb{C}$ the weighting. Let additionally $m = \# V$, $E_m$ the $m \times m$ identity matrix. Let $v,w \in V$ ...
1
vote
1answer
20 views

Onto (surjective) functions of 2 variables [closed]

I have a couple of functions I'm curious about: $f(m,n)=m^2 -n^2$ and $f(m,n)=|m|-|n| $, for $m,n\in \mathbb{Z} $. The codomain also consists of all integers. My understanding is that for this ...
0
votes
3answers
34 views

Logic Problem with truth tables

According to a truth table, if "p is false, and q is false" then "p implies q" is true. However, when studing inverses, we see that the inverse of a conditional statement may or may not be true. For ...
0
votes
0answers
8 views

Is lognormal distribution a class of radial distribution?

Is lognormal distribution a class of radial distribution? P.S Gaussian, truncated Gaussian are all classes of radial distribution.
1
vote
1answer
20 views

Exlamation about a claim of an existing such cycle in a simple Graph

Suppose the following situation: this is found at (Let G be a graph of minimum degree k > 1. Show that G has a cycle of length at least k+1) Let $P=v_0v_1 \dots v_l$ be a longest path in $G$. ...
1
vote
1answer
40 views

Linear extension of a set

I have to find a linear extension of the poset $(X,P)$ where the set $X = \{2,3,10,21,24,50,210\}$ iff $x$ divides $y$. For the answer, I got ...
0
votes
1answer
55 views

Very Basic Logic Question

Given a set $S=\{-1,0,-5,-4\}$.Then is the following proposition true? $\forall x, (x>0 \implies x^2>0)$.
0
votes
2answers
51 views

How can I prove if these are (or not) possible solutions for the following recurrence?

So I'm presented with no initial conditions and the following recurrence relation: $8a_{n+2}+4a_{n+1}-4a_n=0$ I need to determine if these can are possible solutions, and if they are, which initial ...
4
votes
0answers
64 views

About two combinatorial counting problems.

Here are the problems: Suppose $X$ is a set of $n$ elements, and $S_1,...,S_m$ are $m$ subsets of $X$ of average size at least $n/w$. Show that if $m\geq 2kw^k$, then there are $k$ distinct ...
2
votes
1answer
67 views

Summation by Parts to Evaluate $\sum_{k=1}^{\infty}(2k+1)x^{2k}$

I need to evaluate $\sum_{k=1}^{\infty}(2k+1)x^{2k}$ using the Summation by Parts (SBP) method. It is given that $0 < |x| < 1$. The notation our class uses for SBP is as follows: $$ \sum_{i} ...
0
votes
3answers
31 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
58 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
48 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
11 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
52 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
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 ...
0
votes
1answer
31 views

what are all types of Graphs ? [closed]

As I know there are many types of graphs: 1- Simple Graph 2- Completed Graph 3- Directed Graph 4- UnDirected Graph 5- Strongly Connected Graph 6- Weakly Connected Graph 7- Euler Graph 8- Cubic ...
1
vote
1answer
60 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
40 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
45 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
-2
votes
1answer
26 views

Puzzle - Sinbad and the 100 jewels [closed]

Sinbad the adventurer is in a foreign vizier's court, who makes him a proposition: he will be allowed to sample 100 of the court's finest jewels and take home one of them, but with certain conditions. ...
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 ...