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
2answers
25 views

compositions of n with k even summands and compositions of n-k with k odd summands [closed]

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
30 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
43 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
336 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 ...
1
vote
2answers
40 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
35 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
52 views

I need to prove the following property of the binomial coefficient…please Help!

$$\binom rk = \frac rk \binom{r-1}{k-1}$$ Any help is immensely appreciated! I am absolutely confused by this problem and have no real idea of how to solve it, my professor mentioned that the answer ...
3
votes
0answers
65 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}$? [on hold]

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
67 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
19 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
49 views

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

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
25 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 ...
2
votes
0answers
28 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
35 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
72 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.
5
votes
3answers
724 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
38 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
50 views

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

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
42 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
32 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
35 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
39 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
32 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
21 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
15 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 ...
0
votes
1answer
29 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
vote
2answers
43 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
109 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
28 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
32 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
29 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 ...
1
vote
1answer
64 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
86 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 ...
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
12 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
36 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?
1
vote
1answer
58 views

Bit strings of even length that start with 1

We have to give the recursive definition of the set of bit strings of even length that start with 1 We were shown an example that showed the set of all bit strings with no more than a single 1 can be ...
0
votes
1answer
30 views

discrete math: n pennies among k children with each child having atleast 2 pennies

This problem is posed in Lovasz's Discrete math book chapter 3 and I understand the correct answer which is $$ \binom{n-k-1}{k-1} $$ However, why is my approach not right ? Here it goes. We have n ...
1
vote
3answers
27 views

Determine whether the following argument is valid

Premises: $p → r, q → r$, and $q ∨ ¬r$ Argument: $¬p$ I understand the answer but am having problems understanding how to construct this statement ie $(p → r)∧(q → r)∧(q∨ ¬r)$ where does the argument ...
1
vote
1answer
65 views

prove that $p(n) := n^2 + n + c$ is not prime

The question is in MIT Mathematics for CS assignments but unfortunately there is no solutions. -> I do understand that it is false if we use $n = c$ or $n = c-1$ but cannot formally write it as ...
1
vote
3answers
34 views

Discrete metric means all sets are countable?

I was working on a proof of "Show that if $A \subseteq \Re^2$ is discrete, then A is a countable set." and I thought about using the discrete metric ($d(x,y)=\delta_{xy}$) on the set as an example ...
0
votes
0answers
42 views

Comparison of books that teach proof techniques

I have to take discrete math and want to learn proof techniques both to get ahead in it as well as open up the possibility of understanding higher math. I've seen several books recommended such as How ...
1
vote
1answer
54 views

What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?

What is the combinatorial proof for the formula of Stirling numbers of the second kind ? i.e. S(n,k) where n is the number of objects and k is the number of parts $${n\brace ...
-1
votes
2answers
79 views

$n! \le n^n$, $\forall$ $n \ge 1$. [closed]

Prove that $n! \le n^n$, $\forall$ $n \ge 1$. It is so difficult, please help me solve it. Thank you.
0
votes
0answers
21 views

How is floor(x) + j/A between x and y, and how the proof is related to the well-ordering property?

I am having trouble with a proof by well-ordering property exercise. Use the well-ordering principle to show that if x and y are real numbers with $x \lt y$, then there is a rational number r with $x ...
2
votes
1answer
30 views

a Maximum of Discrete Function 2

I have asked a question about a maximum of discrete function yesterday at a Maximum of Discrete Function. I want to generalize the question. Let $X=\{(x_1,\ldots ,x_n)\mid x_i=\pm 1,1\leq i\leq n\}$. ...
0
votes
1answer
53 views

Is the game fair or unfair?

In a box there are 20 balls, 10 are red and 10 black. An automaton draw randomly successively the 20 balls. The player wins if at any time during the drawing of 20 balls more black than red balls are ...
0
votes
1answer
13 views

Giving change - what denominations guarantees an optimal greedy algorithm?

I was thinking about how giving change is a greedy algorithm for the optimal result, where the optimal result is getting the lowest amount of bills and coins possible. The algorithm I am referring to ...