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

8
votes
3answers
4k views

What's the difference between a contrapositive statement and a contradiction? [duplicate]

I keep mixing them up, because they are very similar. Some contrapositives resemble some contradictions.
8
votes
3answers
955 views

Cardinality of a discrete subset

If I am correct, a discrete subset of a topological space is defined to be a subset consisting of isolated points only. This is actually equivalent to that the subspace topology on the subset is ...
7
votes
3answers
14k views

How many options are there for 15 student to divide into 3 equal sized groups?

How many options are there for 15 student to divide into 3 equal sized groups? Now i know the soultion is $\;\dfrac {15!}{5!5!5!3!}\;$ but i can't understand why. Can anyone please enlighten me?
6
votes
3answers
262 views

Number of point subsets that can be covered by a disk

Given $n$ distinct points in the (real) plane, how many distinct non-empty subsets of these points can be covered by some (closed) disk? I conjecture that if no three points are collinear and no four ...
6
votes
3answers
462 views

What does the notation $\binom{n}{i}$ mean?

What do the parentheses next to the summation involving the binomial coefficients mean? Like this: $$\sum _{i=0}^{n} \binom{n}{i}a^{(n-i)}b^i=\left(a+b\right)^n $$
5
votes
2answers
1k views

number of strictly increasing sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$?

What is the number of strictly incremental sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$ ? Is there any exact value? How about approximations?
4
votes
7answers
854 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
930 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
2answers
87 views

Hashing upper bound?

I am hashing $n^2$ objects into $n$ slots and all slots have equal probabilities of taking in the values, and I am trying to find an upper bound on the expected maximum number of objects in any slot. ...
3
votes
2answers
165 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 ...
3
votes
1answer
478 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
256 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?
2
votes
1answer
188 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
175 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
333 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
525 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 ...
1
vote
1answer
85 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
1k views

How many nonnegative integer solutions are there to the pair of equations $x_1+x_2+…+x_6=20$ and $x_1+x_2+x_3=7$?

How many nonnegative integer solutions are there to the pair of equations \begin{align}x_1+x_2+\dots +x_6&=20 \\ x_1+x_2+x_3&=7\end{align} How do you find non-negative integer solutions?
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
394 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
107 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 ...
17
votes
1answer
2k 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. ...
9
votes
2answers
223 views

How find that $\left(\frac{x}{1-x^2}+\frac{3x^3}{1-x^6}+\frac{5x^5}{1-x^{10}}+\frac{7x^7}{1-x^{14}}+\cdots\right)^2=\sum_{i=0}^{\infty}a_{i}x^i$

let $$\left(\dfrac{x}{1-x^2}+\dfrac{3x^3}{1-x^6}+\dfrac{5x^5}{1-x^{10}}+\dfrac{7x^7}{1-x^{14}}+\cdots\right)^2=\sum_{i=0}^{\infty}a_{i}x^i$$ How find the $a_{2^n}=?$ my idea:let ...
8
votes
2answers
206 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 ...
5
votes
1answer
102 views

All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
5
votes
2answers
211 views

Counting non-isomorphic relations

On a set $X$ of $n$ elements, how many non-isomorphic relations are there? The number of relations on a set of $n$ elements is $|\mathcal{P}(X \times X)|=2^{n^2}$, but is there any way to give a ...
5
votes
3answers
2k views

prove $n$-cube is bipartite

prove $n$-cube is a bipartite graph for all $n\ge1$ This is a problem in my textbook and I cannot figure it out at all and have a test on graph theory tomorrow any help would be appreciated since I ...
5
votes
3answers
819 views

Help with combinatorial proof of binomial identity: $\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1}$

Consider the following identity: \begin{equation} \sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2{2n-2\choose n-1} \end{equation} Consider the set $S$ of size $2n-2$. We partition $S$ into two sets $A$ ...
5
votes
3answers
7k 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
99 views

How many different strings can be made from letters in CHICAGOLAND, subject to constraints? [closed]

How many different strings can be made from the letters in CHICAGOLAND, using all letters, and such that no two vowels are adjacent to each other?
4
votes
2answers
229 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
184 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
1answer
405 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 + ...
4
votes
1answer
193 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
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 ...
3
votes
3answers
98 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
83 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
3answers
490 views

$x+1/x$ an integer implies $x^n+1/x^n$ an integer

Suppose that $0\neq x\in\mathbb{R}$ and $x + \frac1x\in\mathbb{Z}$. Prove that, for all $n\ge1$, $x^n + \frac1{x^n}\in\mathbb{Z}$. I can't figure out and understand the question. Can you give me ...
3
votes
2answers
237 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
3answers
7k 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
3answers
344 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
194 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 ...
2
votes
2answers
146 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
1k 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
3answers
667 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
202 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
2
votes
2answers
309 views

Is my solution correct? Generating functions question: How many non-negative solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have?

so we began studying this subject, and I tried solving this question: How many non-negative and whole ($\in \Bbb Z$) solutions does the equation $x_1+x_2+x_3+x_4+x_5+x_6=12$ have? I would like to ...