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
7 views

How to drive the membership function in fuzzy clustering nean

I am learning about Fuzzy c-means (FCM) which is a method of clustering which allows one piece of data to belong to two or more clusters. This method (developed by Dunn in 1973 ) is frequently used in ...
0
votes
0answers
9 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
24 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
67 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
93 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
675 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
28 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
28 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
42 views

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

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
32 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
2answers
19 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
13 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
23 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?
-1
votes
1answer
19 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
24 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
23 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
39 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 ...
1
vote
0answers
39 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
25 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
32 views

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

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

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
26 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
votes
0answers
21 views

Divisibility apples. [on hold]

The basket is n apples. If you remove from the basket after 2 ( 3,4,5,6 respectively ) apples, like the end is in basket 1 ( 2,3,4,5 respectively ) apple . If you remove from the basket after 7 ...
1
vote
1answer
54 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
29 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 ...
0
votes
0answers
12 views

a Maximum of Discrete Function 3

I have asked a question about a maximum of discrete function yesterday at a Maximum of Discrete Function and a Maximum of Discrete Function 2. I want to generalize the question. Let $X=\{(x_1,\ldots ...
1
vote
3answers
23 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
60 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
33 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 ...
-3
votes
0answers
30 views

Write a recurrence relation [on hold]

Write a recurrence relation for the value of a binomial coefficient, and explain why it makes sense. I was getting: Using a Pascal's triangle looking at row 5 that (x + y)5 = 1 x5 + 5 x4y + 10 x3y2 + ...
0
votes
0answers
23 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
45 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 ...
-3
votes
2answers
64 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
19 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\}$. ...