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

Mathematical induction.

Use mathematical induction (and proof by division into cases) to show that any postage of at least 12 cents can be obtained using 3 cent and 7 cent stamps. I thought this was the simple kind of ...
0
votes
0answers
19 views

Writing regular expressions

So here's the problem: Let Σ = { a, b, c } . Write a regular expression for the set of all strings in Σ ∗ such that the sum of the number of a ’s and b ’s in the string is at most two. Thus the string ...
0
votes
1answer
34 views

Give some examples of strings in, and not in, these sets, where Σ = {a,b}

Here's the set: {w : for some u ∈ Σ*, www = uu} From what I understand, it's saying "w (which is a string) such that for some u (which is another string) is an element of the possible combinations ...
-1
votes
0answers
10 views

Linear Non-Homogeneous Recurrences - Guessing the particular solution

why does one need to multiply the particular solution of the function $4\cdot7^n$ with n, but this is not the case with $5 \cdot 2^n$. So what I'm asking is, why is the particular solution to $4 ...
1
vote
0answers
33 views

Rewriting regular expressions

For the following two regular expressions, how would I rewrite them as a simpler expression representing the same set? $b^* \cup a^* \cup (a \cup b)^*$ $\Big((a^*b^*)^*(b^* \cup a^*)^*\Big)^*$ I ...
0
votes
1answer
20 views

What is the image and preimage of the set values between 2 and 5?

Define f:$\Bbb R$ $\to$ $\Bbb R$ as a floor function: f(x) = $\lfloor x \rfloor$. What is $f^{-1}$ ({x| 2 < x < 5}? I figured out the image of the set values between 2 and 5. {2, 3, 4}. But I ...
1
vote
2answers
34 views

Looking for set of combinatorics problems

I'm preparing to Mathematics for Computer Science exam. What I learned from past edition of exams is fact of very often occurence of old problems. I mean more or less known problems, but possible to ...
0
votes
1answer
20 views

Number of partitions containing $k$ occurrences of a given number

Consider the ordered partitions of $N$ with size $m$ ($m \leq N$), that is, the set $\mathcal{P}_m^N$ of all vectors $\vec{n} \in \mathbb{N}^m$ such that $\sum_{i=1}^m n_i = N$. In how many of these ...
1
vote
2answers
46 views

Venn diagram of $A \cup B = B$

I have to draw 3 Venn diagrams. A $\cup$ B = B. B $\cap$ A = B. B - A = B. I understand how to shade all of these, but I do not understand what "= B" is in any of these. I've searched and can't find ...
1
vote
1answer
15 views

Define each set requested by listing the elements.

a) Give a set A with cardinality of 2. So I put A = {1,2}. easy enough b) Construct a set B so that both of the following statements are true: A $\in$ B and A $\subseteq$ B I was just gonna write B ...
0
votes
2answers
37 views

Is $\langle\mathbb Q^+, *\rangle$ a monoid?

Q: Given the set of positive rational numbers $\mathbb Q^+$, the operation is multiplication$~*$. Is $\left<\mathbb Q^+, *\right>$ a monoid? My answer is: $ \forall x, y, z \in \mathbb Q^+$, ...
1
vote
1answer
32 views

If $A = \{x\mid12 < x < 15\}$ and the universal set is the set of positive real numbers less than $15$, what is the complement of $A$?

I have to answer in set builder notation. I put $A^c = \{x\mid 0 \lt x \le 12\}$. I feel that was too easy. Am I missing something?
0
votes
0answers
28 views

Probability distributions associated with Markov chain

Let's say I have a Markov chain, with all the transition probabilities known, and there's a cost associated with each transition. The cost for transitioning from node $a$ to node $b$ is given by the ...
1
vote
3answers
80 views

Is $\{\}$ equal to $\{ \{\} \}$? [duplicate]

Is $\emptyset$ equal to $\{\emptyset\}$? I know an emptyset contains no elements. So I feel like they would be equal. Can someone explain how they wouldn't be?
0
votes
1answer
20 views

5-Card Poker Two-Pair Probability Calculation

Question: What is the probability that 5 cards dealt from a deck of 52 (without replacement) contain exactly two distinct pairs (meaning no full house)? Solution: ...
0
votes
0answers
33 views

Trial division formula [on hold]

I'm not very good with mathematic notation, I'm trying to describe a formula for trial division. Can anyone point me in the right direction or provide an answer? Also please do explain the notation ...
0
votes
0answers
10 views

How can I find out the Energy of this Energy signal?

I am trying to solve the problems in my text book. but I reached an impasse in 'discrete-signal' chapter. $x[nT]=(-0.5)^nu[nT]$, $ $ $ $ $T=0.01s$ ...
-1
votes
0answers
28 views

Understanding the set structure of probability theory [on hold]

Since events have their own probabilities and outcomes have their own probabilities. Why don't we just consider only one of events or outcomes directly? What's the motivation to have this set-point ...
-1
votes
1answer
23 views

What are good techniques for creating a DFA state diagram given a set of accepted/rejected strings?

I am in a Discrete Structures class and my teacher is pretty big on proving his intellect to the class and getting an average of about 60% for his test questions. Right now we are working with ...
-1
votes
1answer
35 views

Need help on understanding a theorem on subsets

An example in my textbook for Discrete Mathematics states, that, Let A be a set, and B = {A, {A}} Then A is a included in B, and so is {A} also an element of B. (Understood) Also it states, {A} is a ...
1
vote
2answers
57 views

Is there an application form $\emptyset\to\emptyset$.

What is the cardinal of $\mathcal F(\emptyset,\emptyset)$ where $\mathcal F(X,Y)$ is the set of the function from $X\to Y$ ? I would say $0$ because a function can't associated nothing at nothing, but ...
2
votes
0answers
23 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
-1
votes
1answer
72 views

define two functions whose compositions are equal to identity

Let B be the set $B = \{1,2,....n\}$ where n is a positive integer. Let C be the set of all bitstrings of length n and let Z be the set of all functions from B to $\{0,1\}$. How do I find the two ...
14
votes
13answers
3k views

Show that from a group of seven people whose (integer) ages add up to 332 one can select three people with the total age at least 142. [on hold]

I need help with this problem, and I was thinking in this way: $$ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} = 332 $$ and I need to find three of these which sum is at least 142. But I ...
2
votes
2answers
83 views

If $\gcd(ab,c)=d$ and $c|ab$ then $c=d$

For all positive integers $a$, $b$, $c$ and $d$, if $\gcd(ab, c) = d$ and $c | ab$, then $c = d$. Need help proving this question, I know that $abx + cy = d$ for integers $x,y$ and that $c|ab$ can be ...
1
vote
1answer
34 views

Raising an adjacency matrix to a power: Why does it work?

An adjacency matrix $M$ represents the number of ways to travel between pairs of points in a network in exactly one move. $M^k$ represents the number of ways to travel between pairs of points in a ...
3
votes
4answers
61 views

Intuitive explanation for p ∨ q → r ≡ ( p → r) ∧ (q → r)

Although, it is possible to prove the above equivalence using truth tables, I don't know how to prove it without using truth tables.Can someone explain it in plain english?
3
votes
1answer
33 views

How many numbers between 1 and 10000, inclusive, are multiples of 12 or 20?

I calculated the multiples of 12 and multiples of 20, 833 and 500 respectively. Now I calculated the multiples of 12 * 20 = 240,and as a result have 41. The solution would be 833 + 500-41 = 1292 ...
-5
votes
0answers
24 views

How does an image an preimage come about from inequality? [on hold]

How does an image or a preimage come about from inequality like this: f(x)={1 < x < 4}
0
votes
1answer
26 views

uniform distribution vs normal distribution for discount use case [on hold]

Problem statement: Reward a customer with lucky draw coupon of X% discount in between 1% to 100% Assume that slabs are pre-defined ( all are theoretical) 1% discount : 90% customers 10% ...
0
votes
1answer
28 views

Union of subspace

Q. Say U and W are subspaces of a a finite dimensional vector space V (over the field of real numbers). Let S be the set-theoretical union of U and W. Which of the following statements is true: a) ...
-3
votes
1answer
36 views

Can someone check my answers on group permutation and answer part (g) [on hold]

it would be great if someone could check my answers for Question 5 and answer part (g) Thanks you very much! Question 5: ...
-5
votes
0answers
39 views

Non repeatable combinations [on hold]

There are 10 girls and 15 boys in class. They're preparing zumba dance for the final show. The teacher decided that boys are doing better and only boys will play 3 zumba dances. Every each of them ...
2
votes
2answers
54 views

How to determine a kind of distance between two permutations?

Let's define a distance between two permutation of length $N$: it is the minimum steps to change one to be another. "A step of change" means that exchanging any two elements' location. For example, ...
-1
votes
0answers
33 views

Find the extreme points of the below polyhedral sets

Find the extreme points of the below polyhedral sets: (a)$$ P =\{(x_1,x_2,x_3)|x_1 +x_2 +x_3 ≤1,x_1,x_2,x_3 ≥0\}.$$ (b)$$ P = \{(x_1, x_2, x_3 x_4|x_1+ x_2+ 0.5 x_ ≤ 1, x_1 x_2,x_3,x_4≥ 0\}. $$ ...
3
votes
1answer
36 views

If $b \equiv 0 \pmod a$ and $c \equiv 0 \pmod b$, then $c \equiv 0 \pmod a$

The question is If $b \equiv 0 \pmod a$ and $c \equiv 0 \pmod b$, then $c \equiv 0 \pmod a$. My attempt is that $b \equiv 0 \pmod a$ can be written $a\mid b-0 = a\mid b$ and the same with $c \equiv 0 ...
1
vote
0answers
27 views

I need a Discrete Mathematics book that breaks down solutions to the Algebraic level to explain how they work. Which one does that? [on hold]

By breaking it down to the Algebraic level, that means they even explain what they're doing Algebraically. I need something where I'm not second-guessing how they did it, or clueless altogether. They ...
0
votes
1answer
26 views

Find number of nonnegative integer solutions to x+3y+3z=n, given n, using generating functions

For every $n,x,y,z\in \mathbb N$, where $x\ge{0}$ and $y,z \ge1$ Find the number of nonnegative integer solutions for $x+3y+3z = n$ I created a generating function for the problem: ...
0
votes
1answer
49 views

How many different words can be formed using the letters of the word “ PERMUTACION”?

Is there any guide to solve this? Edit: This is what I do. I used the permutations. Please check if I did the right thing? Since 11 words so i did 11Pr 1 letter 11p1 2 letter 11p2 11 3 letter ...
-2
votes
0answers
21 views

In a special deck of playing card, one which doesnt contain any Jack, Queen or King [closed]

Determine the probability of the following events: a. Drawing a space (one card) b. Drawing a black card (one card) c. Drawing of four hearts ( four card) d. Drawing of full house (five cards) e. ...
5
votes
4answers
136 views

Combinatorial Proof for Binomial Identity: $\sum_{k = 0}^n \binom{k}{p} = \binom{n+1}{p+1}$ [duplicate]

I am studying combinatorics and I came across the identity $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$$ I have read the algebraic proof and it does not appeal to me. Is there an elegant ...
0
votes
2answers
16 views

Define temperature by clustering with math operators

I can´t figure out how to cluster the temperature for the weather in 3 optimal cases: hot, mild, cold My data contains: air temperature(the average daily value), max air temperature(highest daily ...
14
votes
1answer
1k views

True or false: {{∅}} ⊂ {∅,{∅}}

Note: Actually there's no error in the book and the manual. I actually misread it. The answer is of a different question : True or False: {0} ⊂ {0} This question is from Discrete Math Book by Rosen. ...
-5
votes
2answers
49 views

Discrete mathematics: Question regarding “Pigeonhole principle”. [closed]

Each point in the plane is coloured either red or blue. Show that there are two points of the same colour which are exactly 1 cm apart.
10
votes
2answers
1k views

Pigeonhole principle: Five points on an orange

Five points are drawn on the surface of an orange. Prove that it is possible to cut the orange in half in such a way that at least four of the points are on the same hemisphere. (Any points lying ...
1
vote
3answers
62 views

How many ways can 6 cars ( 3 pink, 2 orange and 1 yellow) be parked in 6 parking slots in a row?

a. If the pink cars must be park together? - my answer is 4!3! or 144 b. If the orange cars must not be parked together? c. If you can't park the yellow on either end? d. If a pink car must be on ...
1
vote
3answers
33 views

solve non homogeneous recurrence relation with only '1' as root of its equation [closed]

I'm stuck in this relation: $f(n) = f(n-1) + 3n - 1$ I've tried to search everywhere if I could find this kind of example where there is only root and that is '1' but all in vain. And all the ...
1
vote
1answer
64 views

Example to show that $f(A-B)$ is not necessarily a subset of $f(A) - f(B)$

Suppose f : X→Y is a function and A,B ⊆ X. I am trying to come up with counterexample to show $f(A-B)$ is not always a subset of $f(A) - f(B)$ and this is what I have so far: $A = \{1,2,3\}$ $B = ...
-3
votes
1answer
23 views

Is statement “Bitwise Xor of y and y+1=z and y>z” true? [closed]

Can y be greater than z in the condition. Bitwise Xor of y and y+1=z and y>z
0
votes
0answers
27 views

XOR N and N+1 to get M [closed]

You are given a positive no M and it is required to find a no N, such that N xor N+1 = M N ^ N+1 = M find N How to find it i have tried it a lot... I just cant get any way to solve it except for the ...