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

Mathematical explanation for the Repertoire Method

There are a few questions already about this method, which has stumped me for a long while. The process is explained, for instance, here: Repertoire Method Clarification Required ( Concrete ...
8
votes
4answers
4k views

what are the applications of the isomorphic graphs?

While studying data structures i was told my instructor that even i am given 3 hour/30 days/3 years to find out whether two graphs are isomorphic or not, it is very very complex and even after ...
8
votes
1answer
77 views

How many rectangles are there on an $8 \times 8$ checkerboard?

How many rectangles are there on an $8 \times 8$ checkerboard? \begin{array}{|r|r|r|r|r|r|r|r|} \hline & & & & & & & \\ \hline & & & & &...
8
votes
5answers
217 views

Does $\{1,2,\ldots,3000\}$ contain a subset of $2000$ integers with no member twice another?

Does the set $X=\{1,2,\ldots,3000\}$ contain a subset $A$ of $2000$ integers in which no member of $A$ is twice another member of $A$? I started by putting $P=[1501,3000]$, but twice any integer in $...
8
votes
6answers
345 views

Can we always draw $n/3$ disjoint triangles from $n$ points in the plane in general position?

Suppose we are given $n$ points in the plane, where $n$ is a multiple of $3$ and no three of these points lie on a line. Is it possible to group all of these points into sets of three, so that if we ...
8
votes
4answers
334 views

Closed form for $\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$

How can I calculate the following sum involving binomial terms: $$\sum_{k=0}^{n} \binom{n}{k}\frac{(-1)^k}{(k+1)^2}$$ Where the value of n can get very big (thus calculating the binomial ...
8
votes
2answers
391 views

Given three integers in $\{0,\ldots,100\}$ which sum up to $100$. What is the probabilty that two of them are the same?

We pick $3$ numbers (one by one) from set $\{0,1,...,100\}$. What is probabilty that two numbers are the same if sum of those $3$ numbers is $100$? My solution: Which two are the same we can pick in $...
8
votes
2answers
12k views

Correct way to calculate numeric derivative in discrete time?

Given a set of discrete measurements in time $x_t, t \in \{0,\Delta t, 2\Delta t,\ldots,T-\Delta t,T\}$, what is the correct way to compute the discrete derivative $\dot x_t$. Is it more correct to ...
8
votes
3answers
6k views

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number

Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number I've looked at http://math.stackexchange.com/a/19998 It is known that $2^n-1$ can only be prime if $n$ is prime....
8
votes
5answers
4k views

If a plane is divided by $n$ lines, then it is possible to color the regions formed with only two colors.

I am self-studying Discrete Mathematics, and there is the following exercise. (in Portuguese) A plane is divided by many lines. Show that it is possible to color the regions formed with only two ...
8
votes
3answers
1k 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 ...
8
votes
1answer
12k views

What is the prerequisite knowledge for learning discrete math?

To become a better computer programmer I would like to take the time to learn discrete mathematics, but I am positive that I do not have the required existing knowledge to do so. So I would like to ...
8
votes
3answers
5k 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
2answers
518 views

Symbolic coordinates for a hyperbolic grid?

Rephrasing     (one year later)    (original question is below) Apparently the original question wasn't clear, or nobody knows an answer (or both). So I will try to rephrase it. Look at your ...
8
votes
2answers
163 views

Find Nth formula of recursive formula $a_n=a_{n-1}+n(n-1)a_{n-2}$

$$a_n=a_{n-1}+n(n-1)a_{n-2}$$ $$a_0=1, a_1=-\frac{1}{2}$$ Is it possible to find explicit formula for $a_n$ just by using $a_0$ and $a_1$? I know how to solve this problem if $a_n=Aa_{n-1}+Ba_{n-2}$ ...
8
votes
2answers
229 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
8
votes
1answer
13k views

Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
8
votes
2answers
234 views

I derived a new formula related to arithmetic sequences, I think!

First of all, I am a 12th grader so I don't know how to write research notes. So please forgive me if my writing is not so impressive! I don't know what to do to tell the world about whatever I found....
8
votes
3answers
168 views

Number of $n^2\times n^2$ permutation matrices with a 1 in each $n\times n$ subgrid

I found the following question in a paper I was trying to solve: The following figure shows a $3^2 \times 3^2$ grid divided into $3^2$ subgrids of size $3 \times 3$. This grid has $81$ cells, $9$ in ...
8
votes
2answers
409 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
8
votes
2answers
307 views

Solve a summation

Hi guys I have an exercise I don't know how to approach, would be cool if you could give me a tip or two! A sequence $a_{n}$ is defined by a dependency : $$ \sum_{i, j, k \geq 0}^{i+j+k = n } ...
8
votes
1answer
423 views

A finite sum involving the binomial coefficients and the harmonic numbers

Wikipedia has a proof of the identity $$ H_{n} =\sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k}$$ http://en.wikipedia.org/wiki/Harmonic_number#Calculation Curiously, there is also the identity $$...
8
votes
5answers
166 views

convert ceil to floor

Mathematically, why is this true? $$\left\lceil\frac{a}{b}\right\rceil= \left\lfloor\frac{a+b-1}{b}\right\rfloor$$ Assume $a$ and $b$ are positive integers. Is this also true if $a$ and $b$ are ...
8
votes
2answers
95 views

Probability that a clumsy boy eats $k$ out of 20 candies

A week or two (or maybe more) ago, the following question was posted and then deleted just as I was getting to the end of my solution. Unfortunately I have now forgotten what my solution was going to ...
8
votes
2answers
169 views

What is the subword complexity function of this infinite word?

Let $w_{0}$ denote the finite word $01$ in the free monoid $\{ 0, 1 \}^{\ast}$, and for $i \in \mathbb{N}$ define $w_{i}$ as the word obtained by adjoining the first $\left\lfloor \frac{\ell(w_{i-1})}{...
8
votes
2answers
230 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\}$. ...
8
votes
1answer
86 views

Share the beer fairly in a finite number of pours

A classical problem within measurements is that you have a $8\,\text{dl}$ mug of delicious expensive beer and need to share it evenly with your friend. However you only have two empty glasses of $5\,\...
8
votes
2answers
247 views

Counting number of distinct systems

This is an enumeration problem in conjunction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between $1$...
8
votes
1answer
166 views

$n \times n$ lattice graph with partial derivatives bounded by $1$ has $n$ equal values.

I once proved this question many years ago but now I have completely forgotten how I did it. I remember it being a fun problem and wouldn't mind seeing a proof again, with the likelihood of it being ...
8
votes
1answer
142 views

For how many $n \in \mathbb{N}$ is $\sqrt{n^2+2379}$ natural?

Here's my attempt at a solution: the expression $\sqrt{n^2+2379}$ is natural iff $$n^2 + 2379 = x^2, \quad \mbox{ for some } x \in \mathbb{N}.$$ Therefore $$(x+n)(x-n)=2379=3 \cdot 13 \cdot 61.$$ I ...
8
votes
1answer
219 views

Function mapping challange

For a given set $A=\{1, 2, 3, 4, \ldots, n\}$, find the number of non-constant mappings (associations ) $f$ from $A$ to $A$ such that $f(k) \leq f(k + 1)$ and $f(k) = f(f(k + 1))$. This is the ...
8
votes
1answer
579 views

Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$? That is, consider the following random process. At each of ...
8
votes
1answer
535 views

Into how many parts do $n$ ellipsoids divide $\mathbb{R}^{3}$?

What is the maximum number of regions into which $\mathbb{R}^{3}$ can be divided by $n$ ellipsoids? (Each ellipsoid has the same size). Let´s denote this number by $r_{n}$. Clearly $r_{1}=2$. But ...
8
votes
2answers
170 views

Given $N$, count $\{(m,n) \mid 0\leq m<N, 0\leq n<N, m\text{ and } n \text{ relatively prime}\}$

I'm confused at exercise 4.49 on page 149 from the book "Concrete Mathematics: A Foundation for Computer Science": Let $R(N)$ be the number of pairs of integers $(m,n)$ such that $0\leq m < N$, ...
7
votes
8answers
3k views

What is an example of function $f: \Bbb{N} \to \Bbb{Z}$ that is a bijection?

Could you give me an example of function $ f \colon \mathbb N \to \mathbb Z$ that is both one-to-one and onto? Does this work: $f(n) := n \times (-1)^n$? N starts with zero.
7
votes
6answers
3k views

Number of 6-digit passwords, starting with even or ending with odd digit

My problem is A password consists of six digits, each in $\{0,\ldots,9\}$ How many passwords start with an even digit or end with an odd digit? the answer is $750,000.$ I would like to know ...
7
votes
9answers
9k views

Prove by induction that $5^n - 1$ is divisible by $4$.

Prove by induction that $5^n - 1$ is divisible by $4$. How should I use induction in this problem. Do you have any hints for solving this problem? Thank you so much.
7
votes
9answers
748 views

How to prove $\left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor$?

everybody, how can I prove that, for natural $m$ and $n$, $$ \left \lceil \frac{n}{m} \right \rceil = \left \lfloor \frac{n+m-1}{m} \right \rfloor \; ? $$ Thanks a lot.
7
votes
3answers
7k views

What is a null set?

I am very confused with null sets. I get that a set which has no elements will be called a null set but I am not getting the examples given below. Please help me by explaining how $P,Q,R$ are all ...
7
votes
4answers
10k views

Prove the cuberoot of 2 is irrational

I need to prove the cube root is irrational. I followed the proof for the square root of $2$ but I ran into a problem I wasn't sure of. Here are my steps: By contradiction, say $ \sqrt[3]{2}$ is ...
7
votes
6answers
136 views

How am I supposed to know that $\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty } \binom{n+1}{n}x^n$?

I'm currently reading through the solution to a problem that involves finding generating functions. In some of the intermediary steps, it is written that $$\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty } \...
7
votes
3answers
16k 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?
7
votes
3answers
10k views

How many distinct ways to climb stairs in 1 or 2 steps at a time?

I came across an interesting puzzle: You are climbing a stair case. It takes $n$ steps to reach to the top. Each time you can either climb $1$ or $2$ steps. In how many distinct ways can you ...
7
votes
5answers
24k views

Antisymmetric Relations

Given a set $\{1,2,3,4\}$, how is the following relation $R$ antisymmetric? $$R = \{(1, 2), (2, 3), (3, 4)\}$$ Note: Antisymmetric is the idea that if $(a,b)$ is in $R$ and $(b,a)$ is in $R$, then $...
7
votes
3answers
4k views

Counting zero-digits between 1 and 1 million

I just remembered a problem I read years ago but never found an answer: Find how many 0-digits exist in natural numbers between 1 and 1 million. I am a programmer, so a quick brute-force would ...
7
votes
5answers
191 views

Show that if $g \circ f$ is injective, then so is $f$.

The Problem: Let $X, Y, Z$ be sets and $f: X \to Y, g:Y \to Z$ be functions. (a) Show that if $g \circ f$ is injective, then so is $f$. (b) If $g \circ f$ is surjective, must $g$ be surjective? ...
7
votes
5answers
650 views

How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$

I am self-studying Discrete Mathematics, and I have two exercises to solve. Find a formula for the following recurrence relation: (translated from Portuguese) a) $a_{1}=3,a_{2}=5, a_{n+1}=3a_{n}-2a_{...
7
votes
2answers
234 views

Combinatorial proof that $\frac{({10!})!}{{10!}^{9!}}$ is an integer

I need help to prove that the quantity of this division : $\dfrac{({10!})!}{{10!}^{9!}}$ is an integer number, using combinatorial proof
7
votes
4answers
284 views

Not understanding the concept of equivalence class

Let $U$ be a set defined: $U=\{(x,y)\in \Bbb R^2\mid x^2+y^2=1; xy\neq 0\}$, and let $R$ be relation defined: $(x_1,y_1)R(x_2,y_2) \iff (x_1 \cdot x_2>0∧y_1\cdot y_2>0)$. I was to prove it's ...
7
votes
3answers
1k views

Getting exactly one pair in a poker hand

I am not understanding this problem: In a deck of 52 cards, of 13 ranks, and 4 suits, how many different 5 card hand can we get such that, there is always exactly one pair. There is a similar ...