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

Why does $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$

I was looking at a solution to the problem and it says that $A = X-B$ is equivalent to $A \cup B = X$ and $A \cap B = \emptyset$. I am wondering why this is true? Any help would be highly ...
0
votes
0answers
12 views

Merge two sets, list and tree

We are given two sets $S_1$ and $S_2$. We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree. I have to write a pseudocode, that ...
0
votes
1answer
20 views

Learning question: to find whether a function is injective

Let $F: z \to z$ such that: $f(n)= \lfloor(1-6n)/3\rfloor$ To find injectivity i did: suppose $f(n_1) = f(n_2)$ therefore $\lfloor(1-6n_1)/3\rfloor$ = $\lfloor(1-6n_2)/3\rfloor$ therefore ...
0
votes
1answer
21 views

Question about some properties of combinatorial structures

Consider $\mathcal A$ as the set of perfect matchings in the complete bipartite graph $K_{n,n}$ and let $i$ be an edge of $K_{n,n}$. Let $$ B_i=\{a\in \mathcal A: \hbox{matching }a\hbox{ has edge ...
0
votes
1answer
18 views

Approximating a binomial coefficient using Stirling's formula

I am working on a problem of modelling a rubber molecule as a one-dimensional chain consisting of $N=N_{+}+N_{-}$ links, where $N_{+}$ points in the positive $x$-direction a distance $a$ and $N_{-}$ ...
0
votes
3answers
22 views

Determining the list elements of $U = \{(A,B)\in \mathcal P(X) ×\mathcal P(X)\mid A=(X−B)\}$

Define $X = \{1,2,3,\ldots,n\}$, for some positive integer $n$. The set $U$, is defined as: $U =\{(A,B)\in \mathcal P(X) ×\mathcal P (X)\mid A=(X−B)\}$. If $n=3$, show the elements of $U$. I ...
0
votes
1answer
25 views

Circular permutations problem with putting objects into circle

How many options do I have if I want to put red boxes and black boxes into circle so that no two black boxes are next to each other? I have 12 red boxes and 4 black boxes. Also all two red and black ...
0
votes
0answers
17 views

How to compare two strings and give the result in percentage according to how many letters are matched? [on hold]

Suppose I have two strings: "centre" and "formatted" How to compare two strings and give the result in percentage according to how many letters are matched? here e and t is matched..(Note if ...
0
votes
1answer
31 views

All solutions of the recurrence relation

Find all solutions of the recurrence relation $$ a_n = 2a_{n-1}+15a_{n-2}-36a_{n-3}+2^n $$ Hint: Find both the homogeneous and particular solutions. You can leave the homogeneous solution with ...
0
votes
0answers
10 views

Problem in understanding the proof of master theorem case

I am going through the proof of master method or master theroem. This is the formula that is been given by the author for the Total Work =Cn^d*(∑(a/b^d)^j) where value of J=0 to logbn as per the ...
0
votes
1answer
47 views

Use mathematical induction to prove that any integer n>=2 is either a prime or a product of primes.

Use strong mathematical induction to prove that any integer $n\ge2$ is either a prime or a product of primes. I know the steps of weak mathematical induction... basis step= $p(n)$ for $n=1$ or any ...
2
votes
1answer
49 views

Prove that the sum of harmonic series 1..n can be expressed as (n+1)H_n -n

Prove by induction that the sum of harmonic series Hn from 1 to n where n is a natural number is as follows. $$ H_n = \sum\limits_{i=1}^n 1/i $$ Prove: $$ \sum\limits_{i=1}^nH_i = (n+1)H_n -n $$ ...
-1
votes
0answers
30 views

Combinatorics Review; Discrete Math

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
2
votes
1answer
20 views

Counting Review; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
0
votes
1answer
18 views

Counting Problem; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
1
vote
0answers
9 views

Solving DFT of this array

I am told to solve the DFT of the following array (5,5,5,5) However, according to the answer sheet, it is suppose to be (5,0,0,0). I tried working it out by hand, and F(0) was correct. But my ...
0
votes
1answer
19 views

Explicit (General) formula for recursive definition.

I am given $a_n=3a_{n-1}+4^n$, $n=1,2,3,....$ and $a_0=1$. First four terms: $$ \begin{align} a_1&=3.1+4^1=3+4=7\\ a_2&=3.7 + 4^2 = 21 + 16 = 37 \\ a_3&=3.37 + 4^3 = 111 + 64 = 175\\ ...
0
votes
1answer
31 views

Counting Question; Discrete Structure

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
1
vote
1answer
22 views

Please explain counting; Discrete Structures

I have forgotten a lot of the counting portion of my discrete structures course and need some explanations how to count, maybe some general strategies on counting. Some example questions I need ...
5
votes
2answers
372 views

Vertical bar sign in Discrete mathematics

I am little bit confused about the sign " | ". Some people call it the division sign and some call it "such that". In computer programming, it's known as pipe. ...
2
votes
3answers
6k views

How many distinct functions can be defined from set A to B

In my discrete mathematics class our notes say that between set A (having 6 elements) and set b (having 8 elements), there are 8^6 distinct functions that can be formed, in other words: |b|^|a| ...
1
vote
2answers
31 views

A second order problem on recurrence relation equals 3^n

I had this Recurrence Relation problem: $a_{n+2} + a_{n+1} - 12a_n = 0$ And I solved in a form like this $a_n = A(r_1)^n + B(r_2)^n$ $r^{n+2} + r^{n+1} - 12r^n = 0$ ...
0
votes
4answers
41 views

proof for a problem in propositional logic

I cant find a proof for given problem: $$p \to ( q \to p) ≡ \lnot p \to ( p \to q ) $$ Please give proof to prove above statement.
0
votes
1answer
48 views

Explicit formula for Nth string of Gray Code.

From Wolfram MathWorld, we have: "A Gray code is an encoding of numbers so that adjacent numbers have a single digit differing by 1. The term Gray code is often used to refer to a "reflected" code, ...
2
votes
2answers
79 views

If $a+1/a$ is an integer, then so is $a^t+1/a^t$ for $t\in\mathbb N$

I need to show if $a$ is in $\mathbb{R}$ but not equal to $0$, and $a+\dfrac{1}{a}$ is integer, $a^t+\dfrac{1}{a^t}$ is also an integer for all $t\in\mathbb N$. Can you provide me some hints please?
1
vote
1answer
28 views

Concrete Mathematics Josephus Problem: How to prove 1.17 & 1.18

On the last page of the Josephus problem where things get really general, we're shown the pretty slick radix changing recurrence & solution 1.17 & 1.18 f(j) = aj, for 1 <= j <= d; ...
0
votes
3answers
26 views

Does a system om congruence equations have solutions?

I have a system of congruence equations $$ \begin{cases} x \equiv 17 \pmod{15} \\ x \equiv 14 \pmod{33} \end{cases} $$ I need to investigate the system and see if they've got any solutions. I know ...
1
vote
2answers
254 views

Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0

I am preparing for my finals for discrete mathematics and I came across this exercise in textbook. Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not ...
-2
votes
2answers
60 views

Combinatorics homework problem [on hold]

In how many ways can $23$ different books be given to $5$ students so that $2$ of the students will have $4$ books each and the other $3$ will have $5$ books each?
0
votes
0answers
9 views

Define the Fuzzy set

Can any one explain what is the difference between ordinary set and fuzzy set. Give me some examples of fuzzy sets
0
votes
2answers
385 views

Writing a boolean formula and logic circuit that computes mux

Let $mux(p_{11}, p_{10}, p_{01}, p_{00}, x_1, x_0) = P_{x1x0}$ (with all variables bits). Write a boolean formula, and then draw a circuit, that computes mux. For ...
3
votes
0answers
30 views

Solution of inhomogenous ODE (4th order)

Hello stackexchangers, I have an inhomogenous ODE in 4th order. This ODE is the constitutive law to describe a material by using the "Wiechert model" (p. 15) which is given by $p_0\sigma + ...
3
votes
1answer
88 views

property of a graph

I was working out on a problem. Came out with a result that $C_n$ is self centered graph, its complement is also self centered, infact 2-self-centered. Worked out on other few graphs which are self ...
1
vote
0answers
19 views

NIMO 16.8 Expected Value + Probability

Let $p=2^{16}+1$ be a prime. A sequence of $2^{16}$ positive integers $\{a_n\}$ is monotonically bounded if $1\leq a_i\leq i$ for all $1\leq i\leq 2^{16}$. We say that a term $a_k$ in the sequence ...
0
votes
5answers
1k views

Proving any product of four consecutive integers is one less than a perfect square

Prove or disprove that : Any product of four consecutive integers is one less than a perfect square. OK so I start with $n(n+1)(n+2)(n+3)$ which can be rewritten $n(n+3)(n+1)(n+2)$ After multiplying ...
0
votes
1answer
36 views

Is the relation on integers, defined by $(a,b)\in R\iff a=5q+b$, a function? [on hold]

Let $A=B=\mathbb N$. Relation $R$ is: $(a,b)\in R$ iff for some $q \in \mathbb Z$ we have $a=5q+b$ Given a relation, show that it's a function. To Show: $\forall a \in A \ \exists b \in B$ such ...
0
votes
2answers
33 views

How do I solve simultaneous congruence modulo equations

How do I find one value of $x$ in these equations? $$ \begin{cases} x \equiv 3 \pmod{5}\\ x \equiv 4 \pmod{7} \end{cases} $$
1
vote
1answer
25 views

big-Oh prove or disprove 2^n is in big-Oh(3^n)

the definiton of Big-Oh says $\exists c\in$R+,$\exists B\in$ N,$\forall n\in$N, $n \geq B$$\implies$$2^n \leq c\times 3^n$. I believe $2^n \in O(3^n)$, but how to prove it? can anyone help. This this ...
-1
votes
0answers
69 views

discrete math cryptography [on hold]

An affine cipher is encryption using a simple mathematical function. Consider the affine cipher $c = ax+b \pmod{26}$ where $x$ is the plaintext, the function applied to each letter of the plaintext ...
0
votes
0answers
20 views

Multinomial theorem: find the coefficient of $x^3 y^4$ in $(x+2y+3)^{10}$

I have trouble solving this problem: Find the coefficient of $x^3y^4$ in $(x+2y+3)^{10}$ The reason for that I struggle with this problem, is because it has an higher order (10) the $x^3y^4$. ...
2
votes
1answer
24 views

Use induction to prove summation

Use induction on $n\in\Bbb N$ to prove that $$\sum_{k=1}^n\frac{k}{2^k}=2-\frac{n+2}{2^n}\;.$$ I have got as far as to the induction step where I have: $$S(n+1)= 2-\frac{n+3}{2^{n+1}}$$ and this ...
-2
votes
2answers
15 views

Proving a Relation that is a Function by Division Algorithm [duplicate]

Let A=B=$\mathbb{N}$ R is: (a,b)$\in$R iff for some q$\in$Integers a=5q+b WHERE 0$\leq$b<5 Given a relation, show that it's a function. To Show: 1) $\forall$a$\in$A$\exists$b$\in$B((a,b)$\in$R) ...
2
votes
0answers
35 views
+150

Minimal “basis” in $n$ dimensional unit cube

Let's $$ B^n=\{\bar\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)|\alpha_i\in \{0,1\}\};~~~~n=1,2,\ldots $$ and let's $$ C\subseteq B^n, $$ $$ S(C)=\{\bar\alpha\oplus\bar\beta\ | \bar\alpha,\bar\beta\in ...
0
votes
3answers
39 views

Modulo: Calculating without calculator??

Calculate the modulo operations given below (without the usage of a calculator): $101 \times 98 \mod 17 =$ $7^5 \mod 15 =$ $12^8 \mod 7 =$ $3524 \mod 63 =$ $−3524 \mod 63 =$ Ok with calculator ...
0
votes
1answer
27 views

Some proof about greatest common divisor

Prove that (a) gcd(a, b) = gcd (a, b – a) (b) Let r be the remainder if we divide b by a. Then gcd(a, b) = gcd(a, r). I solved part a like: Assume a=pcommonpa b=pcommonpb gcd (a,b) = pcommon ...
1
vote
2answers
2k views

Maximal and Minimal Elements

In my textbook, the give an example for finding maximal and minimal elements on a set. The set is $(\{2,4,5,10,12,20,25\},|)$. To find the maximal and minimal elements of the set, the draw a Hasse ...
1
vote
1answer
31 views

Question about problem 53 in Problem Solving and Selected Topics in Number Theory

I solved problem 53 in Problem-solving and selected topics in Number Theory. The problem was: Find the sum of all positive integers that are less than 10,000 and whose square divided by 17 leaves ...
1
vote
2answers
33 views
0
votes
1answer
54 views

Prove that every integer from 1 to p – 1 occurs exactly once among these residues.

Let $p$ be a prime and $1 \leq a \leq p-1$. Consider the numbers $a, 2a, 3a, \cdots, (p-1)a$. Divide each of them by $p$, to get residues $r_1,r_2, \cdots,r_{p-1}$. Prove that every integer from $1$ ...
0
votes
0answers
25 views

Dynamic programming for optimal maximum and optimal minimum

We have a sequence of $a_i$ and a choosing rule that is take the first number $x_t\ge a_t$. The definition is = $$ min\{ t|t \in \{ 1,2,\cdots,n\}\,\,,\,\, x_t\ge a_t\}$$ The sequence $a_i$ is ...