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
2answers
18 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
15 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
20 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
315 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
47 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
32 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
36 views
4
votes
0answers
51 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
54 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
46 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
19 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
693 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
34 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
24 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\}$? [on hold]

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 [on hold]

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 [on hold]

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

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

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 ...
2
votes
0answers
54 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 ...
-3
votes
2answers
36 views

What is the matrix and directed graph corresponding to the relation $\{(1, 1), (2, 2), (3, 3), (4, 4), (4, 3), (4, 1), (3, 2), (3, 1)\}$?

Let $R$ be a relation on set $A = \{1, 2, 3, 4\}$ defined by $$R = \{(1, 1), (2, 2), (3, 3), (4, 4), (4, 3), (4, 1), (3, 2), (3, 1)\}.$$ Find the matrix and directed graph of relation $R$.
0
votes
1answer
30 views

Euler-Fermat with exponents

How to solve $6^{(3^{17})}$ mod 11 with Euler-Fermat? Note: If not possible with Euler-Fermat than with Chinese Remainder Theorem I know that that they are coprime and I computed $\varphi(11)$, so ...
0
votes
2answers
26 views

Student card handing Inclusion–exclusion principle

I got the following question and would very much appreciate any help with understanding it solution. "5 Student cards are handed to 5 students so that each student gets 1 student card, what is the ...
-3
votes
0answers
35 views

Show that $\log_ax \in \operatorname{\Theta}(\log_bx)$ [closed]

Suppose $a$ and $b$ are greater than $1$ and that $f(x) = \log_ax$ and $g(x) = \log_bx$. Prove $f \in \operatorname{\Theta}(g)$. Edit: I fail to see how this is off-topic. This is the entire ...
1
vote
1answer
59 views

Big O Notation basics

Having some problems with big O notation question... getting confused on how to figure this out. I'm working on a problem (exam coming up so doing extra ones) where it asks us to arrange the ...
3
votes
2answers
80 views

Probability with changing number of marbles

Given a bag containing 20 marbles of 5 different colors in this configuration: 8x Blue 6x Red 3x Green 2x White 1x Black How would you determine the probability of picking a marble of a specific ...
-2
votes
0answers
21 views

Prove that for any polyhedron [closed]

Prove that for any polyhedron there are two faces with the same number of vertices.
0
votes
1answer
24 views

What is the subset D of the domain

What is a subset $D$ of the domain of $f$ such that $f\rvert_D$ is simultaneously one-to-one and onto the range of $f$? The function $f: \mathbb{R} \to \mathbb{R}$ is given as $$ f(x) = ...
0
votes
1answer
11 views

What is the range of the function

let f:R->R What is the range of the function f I think it is(-infinity to infinity). But i am confused because p/q is in their lowest term. Can Someone please help me, Thanks in advance
1
vote
1answer
27 views

Lower bound for the size of a maximal matching in a general graph

Let $G=(V,E)$ be a graph, let $M\subseteq E(G)$ be a maximal matching, and let $M^\star\subseteq E(G)$ be a maximum matching. Prove that $|M|\ge |M^\star|/2$. Any hints on how to prove this?