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
0answers
20 views

A Binomial Series In Closed Form

I am wondering if any knows how to compute a closed form for the following two series. $\sum_{m=1}^{n}\frac{(-1)^m}{m^2}\binom{2n}{n+m}$ $\sum_{m=1}^{n}\frac{(-1)^m}{m^4}\binom{2n}{n+m}$ ...
0
votes
0answers
16 views

For a real number x, define the fractional part of x as fp (x) := x − floor(x)

For a real number x, define the fractional part of x as fp (x) := x − floor(x). Prove that 0 ≤ fp (x) < 1. Here is my proof By the way of contradiction assume 0 > fp(x) >= 1. Suppose x is an ...
1
vote
1answer
20 views

How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg p \lor p) \lor (\neg q \lor q)$

I'm reviewing discrete math a second time (after it being over a decade since I took the course in college). How does one go from this step: $(\neg p \lor \neg q) \lor (p \lor q)$ to this one: $(\neg ...
1
vote
4answers
55 views

Proof that intervals of the form $[x, x+1)$ or $(x, x+1]$ must contain a integer.

Show that any real interval of the form $[x, x+1)$ or $(x, x+1]$ must contain a integer. Here is my proof (by contradiction) We start by saying, assume the interval of the form $[x, x+1)$ or $(x, ...
0
votes
2answers
34 views

Proving a Recursive Formula

I know there are some questions on this site about how to find a recursive formula, but I've already found the formula. I'm doing an assignment (http://mathstat.dal.ca/~svenjah/math2112/Assign6.pdf) ...
0
votes
1answer
28 views

How to convert 3 SAT Problem to a Graph using some kind of reduction ~? [on hold]

How to convert 3 SAT Problem to a Graph using some kind of reduction ~? Here is my example and I would like to transform it to a graph $( V_4 \lor V_2 \lor \lnot V_3) $ $\land (\lnot V_2 \lor V_1 ...
0
votes
1answer
55 views

Prove that two non-bald residents of NYC have exactly the same number of hairs.

In New York City there are two non-bald people who have the same number of hairs ( the human head can contain up to several hundred thousands with maximum of about 500,000) How can I prove the ...
0
votes
2answers
58 views

At least $500$ of the $25,000$ students in a school come from the same state

Imagine, in the school there are 25,000 students, at least one from each of 50 states. Than must be a group of 500 students coming from same state. I don't know what to count the 25,000 students or ...
0
votes
1answer
34 views

One to One Correspondence versus One to One Function

I'm doing some discrete math reading and I am confused by the question "if A and B are infinite sets, is it possible for there to be a 1-1 function from A to B and a 1-1 function from B to A without ...
3
votes
2answers
58 views

Closed form for solution of $t_{n+1}=t_n(t_n-2)$

As in the title I am interested in finding closed form for sequence satysfing $$t_{n+1}=t_n(t_n-2)$$ with $t_1=4$. I have tried many guesses, because I don't know if there is a metod to solve that, ...
1
vote
2answers
23 views

Proof that if a simple Graph contains at most two nodes with odd degree then it has a Euler walk

My proof would be start as the following : In general if there are two node at most, then one node used to start walking and the other to end. A) If we start from odd one, this means we have two ...
0
votes
2answers
19 views

compositions of n with k even summands and compositions of n-k with k odd summands

A composition of the number n with k summands is the representation n=a1+⋯+ak with integers ai≥1,1≤i≤k. The order of the summands is important. Show that: There are as many compositions of n ...
0
votes
2answers
24 views

Show that the sum of (outdeg(v)-indeg(v))=0

Let $G = (V,E,\Phi)$ a directed graph. Let $outdeg(v)=\#\{e \in E| source(e) = v\}$ and $indeg(v)=\#\{e \in E| sink(e) = v\}$. Show that $$\sum \limits_{v \in V}(outdeg(v)-indeg(v)) = 0$$ Can you ...
1
vote
3answers
40 views

Show that the coefficient of $x^i$ in $(1+x+\dots+x^i)^j$ is $\binom{i+j-1}{j-1}$

Show that $$\text{ The coefficient of } x^i \text{ in } (1+x+\dots+x^i)^j \text{ is } \binom{i+j-1}{j-1}$$ I know that we have: $\underbrace{(1+x+\dots+x^i) \cdots (1+x+\dots+x^i)}_{j\text{ times}}$ ...
5
votes
2answers
319 views

proof by contradiction puzzle

Consider the following game between two players: • There is an initially rectangular grid of cookies. • The cookie in the upper left corner is poisoned. • The players take turns. On a player’s ...
0
votes
1answer
48 views

Show that $c_n=\frac{n!}{4(n-4)!}$ [on hold]

Let $c_n, n\geq1$ be the number of pair $(\sigma,\tau)$ of permutations $\sigma , \tau \in S_n$ of Type $(1^{n-2},2)$ with the product $\sigma \tau$ of Type $(1^{n-4},2^2)$. Show that ...
1
vote
2answers
37 views

Prove that in a simple graph with $\geq 2$ nodes at least one node can be removed without disconnecting the graph

Prove that in any simple graph $G$ with number of nodes $\geq 2$ there is at least one node $v$ that can be removed with its all edges, and keep the graph connected? From my point of view I can say ...
0
votes
1answer
34 views

Confused by one-to-one question, I think it's order incorrectly

I have this question and it seems a tad redundant If $A$ and $B$ are infinite sets, is it possible for there to be a 1-1 function from $A$ to $B$ and a 1-1 function from $B$ to $A$ without there ...
-4
votes
2answers
39 views
4
votes
0answers
54 views

How do i find formula for the recurrence relation :$x_{n+1}= x^2_{n}-x^2_{n-1}$ with :$x_{-1}=0,x_{0}=\frac{3}{4}$?

How do i find formula for the recurrence relation according to the below initial conditions: $x_{n+1}= x^2_{n}-x^2_{n-1}$ with :=$x_{-1}=0,x_{0}=\frac{3}{4}$ ? Note:$n=0,1,2\cdots$ Thank you for ...
0
votes
0answers
61 views

Number of graphs with 5 vertices

Let $v_i$ where $i=1,2,3,4,5$ be vertices of a graph. Each vertex makes only one directed edge to any other vertex. For instance $v_1 \to v_2 \to v_3 \to v_4 \to v_5 \to v_1$ and $v_1 \to v_3 \to v_4 ...
0
votes
2answers
16 views

Invalid function or invalid domain

Let $ f : A \rightarrow B $ What happens if $\exists\ a\in A $ which doesn't map to any element in B ?
-2
votes
2answers
47 views

An injection from R × {0, 1} to R [on hold]

What would be an example of this An injection from R × {0, 1} to R i think it is all real numbers f(x) = x Can some one help me on this. Thanks in advance
1
vote
1answer
22 views

Proof by contradiction - Predicates and quantifiers

Consider statement, For all integers, b,c,d, if x is a rational number such that $x^2+bx+c=d$, than x is an integer. a) express above statment in the form, $Q_1 b,c,d\in U_1 ( Q_2 x\in ...
1
vote
0answers
20 views

Maximum number of edges in a subgraph of hypercube

Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. Prove that ...
1
vote
1answer
27 views

Lines in the plane from Concrete Mathematics. How many bounded regions are there?

I'm studying Concrete Mathematics by Donald Knuth. While doing the warmup questions, from the recurrence chapter, I stumbled upon an interesting problem. I have an intuition about the solution but I ...
0
votes
5answers
69 views

How can I prove that $4^{2012} \mod 8$ is $0$

Prove that $4^{2012} \mod 8 = 0$ I'm not really sure what rule I should use to prove this.
1
vote
0answers
99 views

Maths puzzle 1: smart play with sets

Let $$X=\{ a, b, c, d, e, f, {ab}, {ac}, {ad}, {ae}, {af}, {bc}, {bd}, {be}, {bf}, {cd}, {ce}, {cf}, {de}, {df}, {ef}, {abc}, {abd}, {abe}, {abf}, {acd}, {ace}, {acf}, {ade}, {adf}, {aef}, {bcd}, ...
5
votes
3answers
694 views

Number of 11-digit length number with all 10 digits and no consecutive same digits

Here is the question: In how many ways we can construct a 11-digit long string that contains all 10 digits without 2 consecutive same digits. Initially, I came up with $10!9$. I thought that there ...
0
votes
2answers
35 views

Solve it by using logical proposition

Show that given logical proposition is tautology $((A \implies C) \land (B \implies C) \land \lnot C) \implies \lnot (A \lor B) $ I can apply the implication rule first and got $\lnot((A \implies ...
-2
votes
1answer
31 views

What is the best answer from choices for 15:220 :: 100:? [on hold]

This question is from "DEO General Intelligence Exam" Held on 31 August 2008 by Staff selection commission of India. So, please help me solve this, which of the option best suits for this question. ...
-2
votes
1answer
46 views

How many elements are in the set $S^S$, where $S=\{a,b\}$? [on hold]

If set $S =\{a,b\}$, then how many elements will be in set $S^S$? Here $S^S$ is {Set S is Exponent of S}. Do we need to do cross product like $S*S$ when it says $(S^S)$. Please advise.
0
votes
2answers
39 views

Big-O Question 1

We have to find the least integer such that $f(x)$ is $O(x^n)$ for the given function. We also have to find the smallest corresponding witnesses $C$ and $K$. Here is what I have, let me know where I ...
0
votes
1answer
29 views

What are the composite functions

f : $\mathbb{R} \to \mathbb{R}$ $$g(x)=\begin{cases} \frac1n,&x\in\Bbb Q\text{ and }x=\frac{1}n\text{ in lowest terms}\\ \sqrt{2},&x=0\ \end{cases}$$ g(x) is the inverse of f(x) determine ...
0
votes
1answer
34 views

Is the function invertible?

$$f(x)=\begin{cases} \frac1q,&x\in\Bbb Q\text{ and }x=\frac{p}q\text{ in lowest terms}\\ 0,&x\notin\Bbb Q\;. \end{cases}$$ Is the function $f|_D$ invertible? If so, describe its inverse ...
0
votes
2answers
38 views

What is the domain of the function

I think the subset D is 1/n where n is an element of natural numbers. Can someone help me with this, thanks in advance
0
votes
3answers
27 views

Double modular exponent with Euler-Fermat

$$7^{3^{18}} \pmod{9}$$ Using this formula : $a^{\phi(m)} \equiv 1 \pmod m$ I got $7^6 \equiv 1 \pmod{9}$ and I can write $3^{18}$ as $3^6 \cdot 3^3$ And what are next steps? I got stuck here.
0
votes
0answers
19 views

RSA number sequence encryption

Encrypt the following number sequence $3,9,27$ with key $m=33$ and $r=7$ It's about RSA encryption. How should I encrypt this? Should I find the key $s$ (inverse key) and what then? $r \cdot s + ...
1
vote
1answer
30 views

Graph and tree computation

A graph is given with set of nodes $[x_1,x_2,x_3,\ldots,x_6]$ and with set of edges: $$\{[x_1,x_2], [x_1,x_3], [x_1,x_4], [x_1,x_5], [x_1,x_6], [x_2,x_3], [x_2,x_6], [x_3,x_4], [x_4,x_5], ...
0
votes
1answer
14 views

Solve the relation with congruence

On $\Bbb Z$ consider the relation $xRy \Leftrightarrow x-y \not\equiv 0 \mod 3$. Prove (with explanation), whether the relation reflexive, symmetric, antisymmetric transitive is and prove if they are ...
-1
votes
2answers
24 views

What is the adjacency matrix and number of paths of length $4$ between vertex $2$ and vertex $5$ in the null graph on $\{1,2,3,4,5\}$? [closed]

Given the following graph 1) Compute adjacency matrix 2) Compute the number of paths of length 4 from knot Nr.2 to knot Nr.5 Can anyone provide a solution how to do it?
0
votes
1answer
20 views

Bridge hands (13) Discrete Mathematics [closed]

How many bridge hands contain four cards of the three suits and one card of the fourth suit?
-4
votes
1answer
17 views

Compound interest in half yearly [on hold]

In what time will $64000 amount to $68921 at 5% per annum interest being compounded half yearly.
-4
votes
0answers
13 views

Discrete mathematics: propositional calculus [closed]

Please state and explain the duality law and De Morgan's theorem for propositional calculus
-4
votes
0answers
33 views

find a method for twin primes and with Golbach conjecture [closed]

There are infinitely many twin primes. Two primes (p, q) are called twin primes if their difference is 2. Let be the number of primes p such that p<= x and p + 2 is also a prime. a sample ...
0
votes
1answer
25 views

Show that $[(P→Q)∧P)]→Q$ is a tautology using rules of replacement

Show that $[(P→Q)∧P)]→Q$ is a tautology using rules of replacement I've done this so far, from $[(P→Q)∧P)]→Q$ to $[(~P∧Q)∧P)]→Q$ by Mat. Imp. to $[P∧(~P∧Q))]→Q$ by Commutation. After that ...
-1
votes
0answers
25 views

Quadratic recurrence inequality

I have the recurrence relation: $r_{k+1} \leq r_k^2+ (1/2)r_k \quad (k =1,2,\ldots)$, where each $r_k$ is non-negative and $r_1<1$. I have the following questions in this regard: A simple plot ...
1
vote
2answers
40 views

In how many ways I can write a number $n$ as sum of $4$ numbers?

The precise problem is in how many ways I can write a number $n$ as sum of $4$ numbers say $a,b,c,d$ where $a \leq b \leq c \leq d$. I know about Jacobi's $4$ square problem which is number of ways ...
4
votes
1answer
78 views

how to sum the floors of ratios n/k when prime factorization of n is known

According to @harald-hanche-olsen the sum of the floors of ratios of $n/k$ is approximately: $$n(\ln n-1-\ln2)<\sum_{k=2}^{n-1}\Bigl\lfloor \frac nk\Bigr\rfloor<n\ln n.$$ If the prime ...
0
votes
1answer
26 views

Relation $R = \{(1,2), (2,2), (2,3), (3,2)\}$ is defined on $A = \{1,2,3\}$. Draw the digraph for the relation $R^3$.

So I don't want an explicit answer, but I do need help getting it from $R^1 \rightarrow R^2 \rightarrow R^3$. Relation $R = \{(1,2), (2,2), (2,3), (3,2)\}$ is defined on $A = \{1,2,3\}$. Draw the ...