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

4
votes
7answers
799 views

the concept of Mathematical Induction

I am currently taking Discrete Mathematics and while I understand most of the topics covered, the one topic which I still don't quite understand is Mathematical Induction. The way the professor taught ...
4
votes
2answers
182 views

If $n$ is squarefree, $k\ge 2$, then $\exists f\in\Bbb Z[x_1,\dots,x_k] : f(\overline x)\equiv 0\pmod n\iff \overline x\equiv \overline 0\pmod n$

Starting from this question, we set $n=k=2$ and use the function $f\in\Bbb Z[x,y]$ where $f(x,y)=x\cdot y+x+y$, then the proofs applied to that question satisfy this case. Note that for $k=1$ the ...
4
votes
4answers
296 views

Prove that $\lfloor\lfloor x/2 \rfloor / 2 \rfloor = \lfloor x/4 \rfloor$

In class, we briefly covered what "floor" and "ceiling" mean. Very simple concepts. They were on one slide, and then we never heard about them again. But now the following homework problem has ...
4
votes
1answer
191 views

How does one prove that $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{2n}\leq \frac{1}{\sqrt{3n+1}}?$

I would like to show that $\frac{1}{2}\cdot\frac{3}{4}\cdots \frac{2n-1}{2n}\leq \frac{1}{\sqrt{3n+1}}$ holds for all natural numbers. I got stuck here: $\frac{1}{2}\cdot\frac{3}{4}\cdots ...
4
votes
2answers
879 views

Coupon Problem generalized, or Birthday problem backward.

I want to solve a variation on the Coupon Collector Problem, or (alternately) a slight variant on the standard Birthday Problem. I have a slight variant on the standard birthday problem. In the ...
3
votes
1answer
449 views

Using induction to prove an equality in harmonic numbers

Question: Prove that harmonic numbers satisfy the equality using induction $$ H_{1}+ H_{2} + · · · + H_{n} = (n + 1)H_{n} − n. $$ I have done the basis step: $(1 + 1)H_{1} − 1 = 1$. Correct. Done the ...
3
votes
1answer
246 views

combinatorics circular arrangement problem

If $n$ distinct things are arranged in a circle, then what are the number of ways selecting three of these things so that no two of them are next to each other?
3
votes
2answers
2k views

How to find whether it is possible for each vertex of a graph to have a different degree?

I want to prove whether it is possible for a graph to have different degrees for each vertex. I think that it can be possible with an example, but I can't prove it with mathematics.
2
votes
1answer
186 views

Applying derangement principle to drunken postman problem.

Two letters need to be delivered to each of n houses. How many ways can a postman deliver two letters to each house such that each house receives at least one incorrect letter? I got stuck and ...
2
votes
1answer
168 views

Number of horse races to determine the top three out of 25 horses [duplicate]

This is a short mathematical puzzle from mindciphers.com which says : The London racetrack needs to submit its top three horses to the Kentucky Derby next month in order to compete for a prize. ...
2
votes
2answers
313 views

Series of natural numbers which has all same digits

For which x exists sum 1 + 2 + 3 + ... + n, where n > 3, which has notation xxx...x? So I am looking for a sum of natural numbers which gives a result which has all same digits, e.g. 5555555 or ...
2
votes
8answers
495 views

Proving for every odd number $x$, $x^2$ is always congruent to $1$ or $9$ modulo $24$

A problem I have been presented with asks the following: Prove for every odd number $x$, $ x^2$ is always congruent to $1$ or $9$ modulo $24$. This seems odd and non-intuitive to me. Of course, it ...
2
votes
3answers
571 views

Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$

I haven't been able to do this exercise: Let $f: A \rightarrow B$ be any function. $f^{-1}(X)$ is the inverse image of $X$. Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$ where $X ...
2
votes
1answer
222 views

Intersection of Hamming balls of boolean vectors

I noticed that a similar question was asked with a little difference, an answer to this wasn't given certainly. Here is the problem: Given two Hamming balls of boolean vectors of size $n$ with centres ...
2
votes
3answers
468 views

Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer

Letting $f_n$ be the Fibonacci numbers, show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer. Just some homework help. Need to prove. Thank you in ...
1
vote
1answer
77 views

Assume $A,B,C,D$ are pairwise independent events. Decide if $A\cap B$ and $B\cap D$ are independent

Assume A,B,C,D, are pairwise independent events. Decide if $(A \cap B)$ and $(B \cap D)$ are independent events? Then repeat this assuming the four events are mutually independent. Well, what I'm ...
1
vote
1answer
149 views

A new combinatorics identity— similar to Catalan number

I find a combinatorics identity during my study, but fail to prove it.$$\sum_{i=0}^{[M/2]}(-1)^i\frac{(3M-1-2i)!}{(M-2i)!i!(2M-i)!} = \frac{1}{2M}\big(_{M}^{2M}\big)$$ where $M=1,2,3\cdots$. Note than ...
1
vote
2answers
515 views

List of calculation rules for asymptotic notation?

Background: I am working my way through CLR/CLRS's proof of the master theorem (section 4.4 in the 1st and 2nd editions of Introduction to Algorithms), and I'm doing my own write-up of this proof1 ...
1
vote
3answers
452 views

Proving statement - $(A \setminus B) \cup (A \setminus C) = B\Leftrightarrow A=B , C\cap B=\varnothing$

I`m trying to prove this claim and I need some advice how to continue, $$(A \setminus B) \cup (A \setminus C) = B \Leftrightarrow A=B , C\cap B=\varnothing$$ what I did is: $$(A \setminus B) \cup (A ...
0
votes
1answer
63 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
5answers
289 views

Derive Closed form sum of N^2

Can anyone explain to me how you would derive this ? I have this question asked in a CS class and can't figure out how to derive it. it has to be derived as you would with sum of N ex ...
0
votes
2answers
103 views

Mathematical Induction

I've gotten to the final step and believe my problem lies within my algebra. Prove the following: $1 \times 3 + 2 \times 4 + 3 \times 5 + ... + N(N+2) = \frac{N(N+1)(2N+7)}6$ Here is my show that ...
15
votes
1answer
1k views

True or false: {{∅}} ⊂ {∅,{∅}}

Note: Actually there's no error in the book and the manual. I actually misread it. The answer is of a different question : True or False: {0} ⊂ {0} This question is from Discrete Math Book by Rosen. ...
8
votes
2answers
202 views

What is the right way to define a function?

Most authors define functions this way: Given the sets $A$ and $B$. A relation is a subset of $A\times B$. Then given a relation $R$, we define $Dom_R=\{x|(x,y)\in R\}$ and $Img_R=\{x|(y,x)\in R\}$. ...
7
votes
1answer
1k views

How many possible arrangements for a round robin tournament?

How many arrangements are possible for a round robin tournament over an even number of players $n$? A round robin tournament is a competition where $n = 2k$ players play each other once in a heads-up ...
6
votes
2answers
662 views

Distribution of points on a rectangle

Let $R$ be a rectangular region with sides $3$ and $4$. It is easy to show that for any $7$ points on $R$, there exists at least $2$ of them, namely $\{A,B\}$, with $d(A,B)\leq \sqrt{5}$. Just divide ...
6
votes
1answer
530 views

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi. Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
5
votes
1answer
178 views

Strange Recurrence: What is it asymptotic to?

So I have the following recurrence relation for the growth rate of an algorithm: $T(n)$ = time taken by algorithm to solve problem of size n: $$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$ Clearly this ...
5
votes
3answers
6k views

Expected number of runs in a sequence of coin flips

A coin with heads probability $p$ is flipped $n$ times. A "run" is a maximal sequence of consecutive flips that are all the same. For example, the sequence HTHHHTTH with $n=8$ has five runs, namely H, ...
4
votes
2answers
197 views

Counting the numbers with certain sum of digits.

The question : In how many different numbers between $1$ and $100000000$ have the sum of their digits equal to $45$? I'm thinking about using the stars and bars formula but I'm not sure if it's ...
4
votes
2answers
2k views

Choosing numbers without consecutive numbers.

In how many ways can we choose $r$ numbers from $\{1,2,3,...,n\}$, In a way where we have no consecutive numbers in the set? (like $1,2$)
4
votes
1answer
447 views

Showing that a root $x_0$ of a polynomial is bounded by $|x_0|<(n+1)\cdot c_{\rm max}/c_1$

I have doubts about the following problem (Problem 3.21 from Sipser's "Introduction to the Theory of Computation"): Let $c_1 x^n + c_2 x^{n-1} + \cdots + c_n x + c_{n+1}$ be a polynomial with a ...
4
votes
1answer
394 views

Efficiently evaluating the Motzkin numbers

So I made an error on the question here: $T_N = 1 + \sum_{k=0}^{N-2}{(N-1-k)T_k}$ The correct formula I'm trying to solve is more complicated and as follows: $$T_0 = T_1 = 1 $$ $$T_{N+1} = T_N + ...
3
votes
3answers
94 views

In how many ways can a $31$ member management be selected from $40$ men and $40$ women so that there is a majority of women?

Here's the question: In an organization there are $80$ people, $40$ men and $40$ women. In how many ways can we choose, from those $80$ people, a $31$ member management so that there is a ...
3
votes
1answer
79 views

Calulating the Ramsey number $R(T, K_{1,n})$ of a tree $T$ and bipartite graph $K_{1,n}$

Let $m,n \ge 2$ be such that $m-1$ is a divisor of $n-1$. Let $T$ be a tree with $m$ vertices. Calculate the Ramsey number $R(T,K_{1,n})$. Thoughts: I'm having trouble approaching this question. ...
3
votes
2answers
65 views

Number of permutations of a word taking four at a time

Take the letters $NNAAARRGGTTSE$. I have written my answer below to find out the number of permutations of four letters chosen from the given set of letters. 3 of the same kind and 1 other = $\left( ...
3
votes
2answers
233 views

Choosing $15$ out of $100$ whole numbers with difference of any $2$ divisible by $7$

How can we prove with the pigeonhole principle that having $100$ whole numbers, one can choose $15$ of them so that the difference of any $2$ is divisible by $7$?
3
votes
2answers
173 views

to clear doubt about basic definition in graph theory

Can anybody help me in clearing the doubt about hierarchical product of graphs. Its quite different from other graph products. Here is the screenshot and link how it is done. I know the rooted graph, ...
3
votes
3answers
6k views

Finding the parity check matrix for $(15, 11)$ Hamming Codes

I understand how Hamming Codes and their error detection works, but I'm confused how the parity check matrix is found. How exactly is this computed?
3
votes
1answer
156 views

finding the minimal property of a graph

While working out on a problem, I found that cycles $C_n$ are minimally self-centered graphs, as if we remove any edge then it is paths $P_n$ and $P_n$ are not self-centered graphs. My question is ...
3
votes
3answers
307 views

Are these two predicate statements equivalent or not?

$\exists x \forall y P(x,y) \equiv \forall y \exists x P(x,y)$ I was told they were not, but I don't see how it can be true.
3
votes
2answers
191 views

Showing $24|(n+1)\implies24|\sigma_0(n)$

Question: Show that if $n$ is a positive integer such that $24$ divides into $n + 1$, then $24$ divides the sum of all divisors of $n$ (denoted in number theory by $\sigma_0(n)$). For example ...
3
votes
2answers
7k views

Free resources to start learning Discrete Mathematics

Can anyone recommend good, free online articles or books to learn Discrete mathematics? When I google'd for them, I came across few resources..but don't know whether they are good to start learning ...
2
votes
2answers
163 views

Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 1}$?

I have the sum $$ \sum_{i=0}^{n} \binom{n}{i}\cdot (i+1)^{i-1}\cdot(n - i + 1) ^ {n - i - 1},$$ but I don't know how to compute it. It's not for a homework, it's for a graph theory problem that I try ...
2
votes
2answers
142 views

A Proof for Prime Numbers

Show that among k-digit numbers, one in about every 2.3k is a prime. How can we prove this question? Thanks.
2
votes
2answers
57 views

feedback on my solution regarding eqivalence relations. [duplicate]

For all $x, y \in \mathbb{R}$ define that $x \equiv y$ if $x^2 = y^2$. Then $\equiv$ is an equivalence relation on $\mathbb{R}$, there are infinitely many equivalence classes, one of them consists of ...
2
votes
1answer
839 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 ...
2
votes
3answers
82 views

Prove that $\frac{1}{1*3}+\frac{1}{3*5}+\frac{1}{5*7}+…+\frac{1}{(2n-1)(2n+1)}=\frac{n}{2n+1}$

Trying to prove that above stated question for $n \geq 1$. A hint given is that you should use $\frac{1}{(2k-1)(2k+1)}=\frac{1}{2}(\frac{1}{2k-1}-\frac{1}{2k+1})$. Using this, I think I reduced it to ...
2
votes
1answer
104 views

Planar Realization of a Graph in Three-Space

We call a planar graph one that we can draw in two-space such that no two edges intersect. I was told that we're not so interested in drawing graphs in three-space, because it is "intuitively obvious" ...
2
votes
1answer
192 views

pigeonhole principle divisibility proof

Let n be some positive odd number, prove that there exists some positive integer k such that n|(2k-1), prove in terms of the pigeonhole principle