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

Recursion and Counting

If $2$ numbers $n$ and $m$ are given, how can be found out the number of numbers with zero between and including $m$ and $n$ ($m \leq n$)?. For example, if $m=10$, $n=100$ the numbers with zeroes are ...
2
votes
0answers
10 views

Looking for a generalised or non-iterative maths equation for the process of slicing up a range value

Suppose I have a integer range $[0,n]$ and an integer $x$ within that range. Suppose I can generate an integer $y$ though this iterative process: $x$ is converted to Base 2 For each bit from most ...
1
vote
2answers
132 views

Discrete Mathematics Riddle, square grid problem

I've been trying to solve this problem in my book to no avail: I am even stuck on part a... to find a closed form of this I started with size 2x2 square, counted the number of paths, then used a ...
0
votes
1answer
93 views

Proving $\sum^n(1/i^2)\le2$ by induction

I am having difficulty proving this from a practice problem in my book with no solutions: For part a, I set up the inductive hypothesis then I am stuck with the Riemann sum of 1/k^2 + 1/(k+1)^2 ...
0
votes
1answer
27 views

Calculating number of students who don't study any language

According to a survey of 100 students, there are 40 students studying English, 30 studying French, and 25 studying Spanish. Inaddition, 8 students are studying English and French, 6 are ...
0
votes
1answer
36 views

Distributing Apples and oranges. confused about solution

How many ways are there to distribute 4 identical oranges and 6 distinct apples into 5 distinct boxes I know you find number of ways for apples which is 5^6. The solution tells me that the ways for ...
1
vote
1answer
73 views

Applying the master theorem

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why: 1) $T(n) = $T($n/3)$ 2) $T(n)= $ $5T$($2n/5$) + $n$ 3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$ ...
0
votes
0answers
48 views

Predicate with Non-Number Domain

I am having difficulties defining a predicate, given the following domain and requirement: Let x and y be two parameters whose domains Dx and Dy, respectively, are the set ...
0
votes
1answer
34 views

Probability - Random viarbles

A notepad manufacturer requires that 90% of the production is of sufficient quality. To check this, 12 computers are chosen at random every day and tested thoroughly. The day's production is deemed ...
-1
votes
1answer
31 views

does an explicit formula for GCD exist?

i was trying to put GCD(a,b) into the form of f(a,b) = a +5b. i know the euclidean algorithm finds the GCD, so I was trying to put that concept into a recursive formula but its getting way too ...
1
vote
3answers
86 views

If $x^2$ is divisible by $4$ then $x$ is even?

I am studying discrete mathematics as course and I have to prove this "If $x^2$ is divisible by $4$ then $x$ is even". I am wondering how to prove it using the contrapositive of this ...
0
votes
2answers
49 views

recurrence problem for number of words

Let $w_n$ be the number of words (strings) of length $n$ that can be made using the digits {0,1,2,3} with an odd number of twos. Find a recurrence relation for $w_n$ and solve the recurrence. The ...
1
vote
1answer
29 views

Strange Absorption Behavior in Discrete Math

I'm studying for my discrete math exam and I'm looking over the professors' examples. I have a question about one of them and I was hoping someone could help me out. Here is the example: ...
1
vote
1answer
48 views

How does one find/list equivalence classes?

Can someone explain how I would find/list the equivalence classes (And number of equivalence classes) of these two examples? Example 1: A is the set of all possible strings of 3 or 4 letters in ...
1
vote
1answer
43 views

Probability involing percentages (Bernoulli?)

Assume that about 56% of population belong to group type of O. A) What is the probability that it will need to take a blood test from exactly three individuals in order to find a person with O-type ...
1
vote
2answers
44 views

How to formalize proofs

I'm struggling a bit with my discrete maths course and I was wondering if anyone could help me with my assignment. The question I'm working on is, Prove that if a and b are positive integers, then ...
0
votes
1answer
58 views

How would I draw the diagram for this relation?

The question I am trying to solve is below. I have proven it is an order but am unsure how to draw the diagram for it. Can someone point me in the right direction? Let A = {1, 2, 3, 4}, and let R be ...
0
votes
1answer
33 views

How to prove this equivalence relation?

How would one go about proving this is an equivalence relation? I have no idea where to start. $\cal R$ is the relation on $\Bbb Z \times \Bbb Z$, such that $((a, b),(c, d)) \in \cal R$ if and only ...
1
vote
2answers
77 views

Showing that ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S (∃y ∈ E Q(x, y)) → R(x)

Q(x, y) := “Student x did exercise y in the book” R(x) := “Student x gets an A in the class” So my goal is to show that the following equivalency holds: ∀x ∈ S ∀y ∈ E ( Q(x, y) → R(x) ) ≡ ∀x ∈ S ...
1
vote
1answer
46 views

distributing r distinct objects into n-distinct boxes when repetition is allowed

Suppose there are 5 students and we are trying to create 3 distinct commissions which every student must be in at least one commission and every commission must have at least 2 members. what is the ...
0
votes
2answers
72 views

What is the number of nonnegative solutions of a linear equation?

What is the number of solutions of a linear equation? for example look at this equation: $X_1+X_2+...+X_n=r$ The number of solutions is the following formula, because the way of choosing $r$ objects ...
-2
votes
1answer
127 views

Expected value of $\sin^2(0.01n)$ for discrete $n$

Is it possible to calculate the expected value of $\sin^2(0.01n)$, with $n$ taking non-negative integer values? Normally, when we wish to find the expected value of the sine function, we integrate ...
0
votes
1answer
28 views

What rule of logic is this?

I was reading a proof on proving associative law for XOR operator and came across these steps. = (AB'C'+A'BC')+(A'+B)(A+B')C = (AB'C'+A'BC')+(A'(A+B')+B(A+B'))C = (AB'C'+A'BC')+(A'B' + AB)C I ...
2
votes
1answer
242 views

If $\gcd(\gcd(a, b),\gcd(a, c))=1$, then $\gcd(a, bc) = \gcd(a, b) \cdot \gcd(a, c)$

Let $a, b$ and $c$ be integers. Prove that if $\gcd(a, b)$ and $\gcd(a, c)$ are coprime, then $\gcd(a, bc)$ = $\gcd(a, b) · \gcd(a, c)$ I am stumped in this problem. Can anybody clarify me what ...
-1
votes
2answers
37 views

prove the equivalence of the following statements: 2x-1 is irrational; x/3 is irrational

I am stumped. I really have no idea how to solve this problem. Can someone please help me through this? THE TWO EQUATIONS ARE SEPERATE
2
votes
1answer
175 views

Gossip problem proof by induction

Question Suppose there are $n$ people in a group, each aware of a scandal no one else in the group knows about. These people communicate by telephone; when two people in the group talk, they ...
1
vote
1answer
64 views

How to generate a single instance of multichoose (stars and bars)

So we know that if I have $k$ balls and $n$ buckets, I have $\binom{n+k-1}{k}$ unique ways to allocate the balls. Let's say $n=4$ and $k=2$ then I have $\binom{5}{2}=10$ ways. All possible allocations ...
6
votes
2answers
141 views

Graph and in-Degree and Drawing

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
1
vote
1answer
76 views

How many integers could be in such a way that any digits is not bigger than the left digits?

How many 4-digits integers could be in such a way that any digits is not bigger than it's left digits? I Try it with simulation, i get 714. anyone could describe a formula for me? My try:
1
vote
2answers
49 views

Getting the cumulative distribution function for Sqrt(X) from the cumulative distribution function for X

I've a data set X which consists of randomly generated numbers. My aim is to plot the cumulative distribution function for square root of X without generating data set for square root of X. I'm using ...
0
votes
1answer
9 views

Discrete algebra and exponents (See body text)

Let $a,b\in\mathbb{Z}^+$. If $a \equiv b\bmod 49$, and $\gcd(a,49) = 1$. How can I find any positive integer $n > 1$, so that $b^n\equiv a\bmod 49$? I'm completely stumped by this. I've been ...
1
vote
4answers
268 views

Closed Form for Factorial Sum

I came across this question in some extracurricular problem sets my professor gave me: what is the closed form notation for the following sum: $$S_n = 1\cdot1!+2\cdot2!+ ...+n \cdot n!$$ I tried ...
-1
votes
1answer
59 views

Decorate Tables

You have $r$ red, $g$ green and $b$ blue balloons. To decorate a single table for the banquet you need exactly three balloons. Three balloons attached to some table shouldn't have the same color. What ...
1
vote
0answers
17 views

Topology of the intersection of toric arrangement

Hope someone will help me in the solution of the following question. I'm working on some topological problem involving the topology of the intersection of some characters of the torus. I want ot find ...
3
votes
0answers
134 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...
1
vote
1answer
100 views

Proof for the number of perfect matchings in complete graph.

I'm working on a question: Let $P_n$ be the number of perfect matchings in $K_{2n}$. Prove by mathematical induction that for each integer $n\geq1$, $P_n$ is the product of odd integers from $1$ to ...
1
vote
1answer
56 views

License plate combination

California's license plate is made up for a number, followed by 3 letters, and 3 more numbers. If you cannot have the word BOB then how many license plate can be made in total? I'm guessing it's ...
1
vote
3answers
61 views

show that every rational number has one and only one multiplicative inverse

I am stumped and have no idea on how I prove this. I don't know what else to say. I am beyond lost.
5
votes
1answer
83 views

How many natural numbers less than 1,000,000,000 are multiples of 5 or 7?

I used the Inclusion-Exclusion Principle and I got $200,000,000$ (multiples of $5$ less than $10^9$, obtained by $10^9 / 5$) + $124,857,142$ ( multiples of $7$ less than $10^9$, obtained by $10^9 / 7$ ...
1
vote
1answer
232 views

How to solve this knights and knaves problem using CNF?

There are 5 natives A-E, each is either a knight or knave. Let a be the statement “A is a knight” and ¬a be “A is a knave”. Same format for the other four natives. Let T be “tautology” and F be ...
0
votes
1answer
150 views

Trouble understanding case analysis (proof by cases)

I've got a discrete math test coming up, and I've been studying religiously for the past week. Proof styles still frighten me though, I find it hard to wrap my head around them. Right now I am ...
0
votes
2answers
37 views

combinatorics: even numbers

There are given 6 numbers: 1,2,4,6,7,8. I need to find out how many 5 number combinations are there ($A_6^5$=720) and how many of those combinations are even numbers. The numbers can't recur. The book ...
0
votes
2answers
34 views

Determining if statement is even or odd.

When referencing the following page (http://geneseo.edu/~heap/courses/239/activity3.pdf) which uses the definition of... an integer $n$ is even if there exists an integer $k$ such that $n = 2k$ If ...
0
votes
0answers
32 views

Hyperplane arrangements and matroids

I'm studying some topics related to hyperplane arrangements and matroids. I've some problem in finding some practical example. Here's my question: Let $\mathbb{K}$ be a field (suppose of ...
1
vote
3answers
87 views

Discrete mathematics proof that I have been stuck on

So I have been working on these proofs for a while and finished 13 of 14 of them but I was never able to figure this one out so I thought I would ask for help on how it would be done:S Here is the ...
3
votes
1answer
48 views

Solving recurrence -varying coefficient

How can one find a closed form for the following recurrence? $$r_n=a\cdot r_{n-1}+b\cdot (n-1)\cdot r_{n-2}\tag 1$$ (where $a,b,A_0,A_1$ are constants and $r_0=A_0,r_1=A_1$) If the $(n-1)$ was not ...
0
votes
1answer
30 views

abstract machine, what language does M accecpt?

What language does M accept? 1: {a}3 ∪ {b}3 ∪ {λ} 2: {a}3 ∪ {b}3 3: {a, b}3 ∪ {λ} 4: {a, b}3 ∪ {λ} I'm not completely sure just yet which one would work. I would appreciate it if ...
1
vote
3answers
133 views

Hard Mathematical Induction [duplicate]

I have a mathematical induction question and I know what I need to do just not how to do it. The question is: Prove the equality of: $$(1 + 2 + . . . + n)^2 = 1^3 + 2^3 . . . + n^3$$ Base ...
0
votes
0answers
32 views

Bounding a discrete function

If there is a discrete-time function $u(t)$, where $u(T)=u(0)+\sum_{t=0}^T G(u(t))$, is it possible to prove that $u(t)$ remains bounded for a specific class of $G$ functions? Such as $G\in L^1$ or ...
2
votes
1answer
44 views

Solving a recurrence with a term $T(\frac n 2 + 2)$

I'm stuck trying to solve the following recurrence: $$\begin{align*} T(n) &= 4T(\frac n 2 + 2) + n : n > 8\\ T(n) &= 1 : n \leq 8 \end{align*}$$ In particular, I'm not sure how to deal ...