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

How many binary relations can be defined on a set of $5$ elements?

Let $X$ be a set with $5$ elements. How many binary relations on $X$ are either reflexive or symmetric or both? show work. you need not simplify the answer.
0
votes
0answers
4 views

What is the orthogonal rank of Grötzsch graph?

How to represent the Grötzsch graph as an orthogonal graph? Grötzsch graph: https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph
1
vote
1answer
11 views

unsure about variables in Bayes' Theorem question

I would just like to double check that I have completed this question correctly. I am new to Baye's theorem and find the variables a bit confusing, particularly what a general rule is for determining ...
0
votes
0answers
28 views

NP-Complete: Prove this Problem is in NP (specific)

I'm trying to prove that this problem is in NP: Given $n$ dices, there are at least $m$ ways of rolling a given value $y$. Theoretically I need to argue that there is an efficient verifier for ...
6
votes
6answers
78 views

Series of inverse function

$A(s) = \sum_{k>0}a_ks^k$ and $A(s)+A(s)^3=s$. I want calculate $a_5$. What ways to do it most efficiently?
-3
votes
1answer
22 views

alumini weekend discrete math question [on hold]

On Alumni Weekend, 5 classmates, Yin, Yang, Yash, Yazid, and Miss Eliza Tudor, are back at the College. In how many ways can pictures of them be taken if they want to appear in every possible order ...
0
votes
1answer
19 views

In how many ways can $12$ balls be distributed to $4$ distinguishable bags if the balls are distinguishable and each bag gets at least 3 balls?

In how many ways can $12$ balls be distributed to $4$ distinguishable bags if the balls are distinguishable and each bag gets at least 3 balls? If each bag gets 3 balls then there are 0 balls left. ...
0
votes
1answer
17 views

A dance party is happening on a world with 3 genders: snails, pre-snails and post-snails. There are 8 aliens of each gender at the party.

A dance party is happening on a world with 3 genders: snails, pre-snails and post-snails. There are 8 aliens of each gender at the party. How many ways can the aliens be divided up into triples to ...
0
votes
0answers
10 views

discrete mathematics combinatoric questions [duplicate]

A store sells 8 kinds of candy. How many ways can you pick out 15 candies total to throw unordered into a bag and take home. i think the answer is C(22,7) but I am not sure.
-1
votes
0answers
20 views

In how many ways can $4$ indistinguishable catfish and $4$ indistinguishable dogfish be distributed to $5$ children?

What happens if we split the difference and try to count the number of ways to distribute among the $5$ children $4$ indistinguishable catfish and $4$ indistinguishable dogfish? One can tell a dogfish ...
-3
votes
0answers
17 views

Pascals triangle and its applications. [on hold]

Are there, besides Newtons binomial expression for (a+b)exp(n), practical uses for the numbers in the triangle (and I don´t mean the properties that are formed by the numbers themselves)?
2
votes
1answer
93 views

Derive a Recurrence

Could really use some help with this. For an integer $m \geq 1$ and $n \geq 1$, consider $m$ horizontal lines and $n$ non-horizontal lines, such that no two of the non-horizontal lines are parallel ...
0
votes
0answers
19 views

3D rotation Problem [on hold]

Pic1 Pic2 Can anyone explain to me how to rotate in the first pic and second pic? I understand it's trying to do transformation and i understand about the purpose of it and no problem in calculation ...
0
votes
1answer
26 views

double sum simplification

I'm looking for a simplification to the following expression $$ \sum_{j=0}^m\sum_{l=0}^m \binom{m}{j} \binom{m}{l} h(j+l) $$ where $h$ is a given function. I looked for a formula of the product of ...
1
vote
1answer
32 views

Vandermonde's Convolution special case.

I am not able to show this case of Vandermonde's Convolution without using induction. Can someone help me? $$ \binom{n}{m} = \sum_{k=0}^{m} \binom{n-p}{m-k} \binom{p}{k}. $$ I thank now.
3
votes
2answers
476 views

How would I show this bijection and also calculate its inverse of the function?

I want to show that $f(x)$ is bijective and calculate it's inverse. Let $$f : \mathbf{R} \to \mathbf{R} $$ be defined by $f (x) = \frac{3x}{5} + 7$ I understand that a bijection must be ...
-1
votes
0answers
18 views

Number of ways to write $n \in \Bbb N$ as a sum of $k$ positive integers? [on hold]

For example: The number of ways to write $6$ as a sum of $6$ positive integers is $1$ which is $1+1+1+1+1+1$. And the number of ways to write $10$ as a sum of $2$ positive integers is $5$. I need the ...
0
votes
0answers
12 views

Writing Co-ordinates as a power of a Generator

In the group formed by the points $(x, y)$ with $x^2 + y^2 = 1$ with coordinates in F31, show that $g = (2, 11)$ is a generator of the group and write $(20, 29)$ as a power of $g$. Am I right in ...
0
votes
1answer
11 views

Reducing a Boolean function

I have the following boolean function: f(x,y,z) = xyz + xyz' + xy'z + x'yz + xy'z' I could reduce it to the following: f(x,y,z) = xy + xy'z + x'yz + xy'z Im not sure what to do next, i know it can ...
0
votes
0answers
31 views

Why are is partitions counting technique wrong?

I recently heard about partitions. I tried to count them using the following technique: 1) Ways to write $5$ as a sum of five positive integers: $$1+1+1+1+1$$ 2) Number of ways to write $5$ a sum of ...
2
votes
3answers
49 views

Establish by mathematical induction that a set having $n$ elements has $2^n$ subsets.

I know the steps to an induction proof. The first step is to establish that $n=1$ is true. Then the second step is to assume that if we replaced $n$ by $k$, $2^k$ is true. For the third step, assuming ...
3
votes
3answers
57 views

How many $5$-digit numbers (including leading $0$'s) are there with no digit appearing exactly $2$ times?

How many $5$-digit numbers (including leading $0$'s) are there with no digit appearing exactly $2$ times? The solution is supposed to be derived using Inclusion-Exclusion. Here is my attempt at a ...
3
votes
2answers
43 views

Combination of elements in a ring and selecting non adjacents

Ok, suppose we have a clock, with the usual design of numbers ordered from 1 to 12 (so 1 and 12 are adjacents). The question is what is the number of possible combinations of four non adjacent ...
1
vote
2answers
56 views

Is $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ a tautology?

Is this proposition a tautology? $((p\rightarrow q) \land \neg p) \rightarrow \neg q$ Knowing that $\alpha \rightarrow \beta$ is equivalent to $\neg \alpha \lor \beta$, I have come up with ...
1
vote
1answer
23 views

Minimal 4-regular planer graph

I'm asked to draw a minimal 4-regular planer graph and to give number of its verteces and edges. I tried Octahedral graph (see picture) with 6 verteces and 12 edges, but it doesn't work. I'm not sure ...
0
votes
1answer
21 views

Proof for association law?

I am new in logic and I getting a little bit confused with maths. Can I do something like this following the Associative Law? $$(p ∨ ¬r) ∨ (r ∨ ¬p) ≡ (p ∨ ¬p) ∨ (r ∨ ¬r)$$ Thank you in advance for ...
0
votes
1answer
36 views

Using a truth table to prove or disprove $¬(P\vee (Q\wedge R))=(¬P)\wedge (¬Q\vee ¬R)$ and $¬(P\wedge (Q\vee R))=¬P\vee (¬Q\vee ¬R)$

This question was taken from the MIT OCW Math for Computer Science course. Use a truth table to prove or disprove the following statements: a) $¬(P\vee (Q\wedge R))=(¬P)\wedge (¬Q\vee ¬R)$ b) ...
0
votes
2answers
25 views

help on simplifying boolean algebra

I need t show the the terms on the left simplify to the ones on the right $$(X+Y).(X'+Z)= X.Z+X'.Y$$ My attempt: I went with $$XX'+XZ+YX'+YZ= 0 +XZ+YX'+YZ$$ But I'm stumped beyond ...
3
votes
1answer
2k views

Find an inverse of $a$ modulo $m$ for each of these pairs of relatively prime integers

How would I find the inverse of a given number $a$ modulo $m$, given that $\gcd(a,m)=1$? a) $a = 2$, $m = 17$ $17 = 2 \cdot 8 + 1$ $2 = 1 \cdot 2 + 0$ $1 = 17 - 8 \cdot 2$ <-How do I know ...
0
votes
0answers
28 views

Multivariable recurrence: Solving $c(n,k) = c(n-1,k) + c(n-1,k-1) = \binom{n}{k}$ by algebraic methods.

Let $(c_{n,k})_{n,k=0}^{\infty}$ be defined by $c(0,0)=1$, $\:\:c(0,k)=0 \:\: \forall \: k > 0$ $$c(n,k) = c(n-1,k) + c(n-1,k-1) \:\:\: \forall \: n \geq 1$$ I can show that the ...
5
votes
3answers
40 views

Game is winnable if and only if $n \neq k$

Integers $n$ and $k$ are given, with $n \ge k \ge 2$. You play the following game against an evil wizard. The wizard has $2n$ cards; for each $i = 1, \ldots, n$, there are two cards labelled $i$. ...
2
votes
1answer
389 views

What is the difference between a forest and a spanning forest?

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree). If a graph is ...
2
votes
2answers
29 views

Can$A \cap (B' \cap C')$ be $(A \cap B') \cap (A \cap C')$?

If I use the above statement, provided that it is right, in a question, would I have to prove it as well?
2
votes
0answers
36 views

$(k^2)! \cdot \prod_{j = 0}^{k = 1} {{j!}\over{(j + k)!}}$ integer for $k \in \mathbb{N}$

How do I see that for any positive integer $k$,$$(k^2)! \cdot \prod_{j = 0}^{k = 1} {{j!}\over{(j + k)!}}$$is an integer?
1
vote
1answer
17 views

How can I analyse signal with discrete wavelet transform?

With CWT it's clear enough. We have function of two variables which are scale and translation. But what about DWT? Here is Matlab code: ...
0
votes
0answers
17 views

Can you identify this stochastic process?

So I run into this problem the other day and I cannot even think of the keywords I need to use to look it up. For the discrete random variable $X$ we have: $P_{\Delta X(t)} = F\big(X(t-1), ...
-1
votes
1answer
37 views

How do I find all n values for which the equation $\phi (n) = 8$ holds? [duplicate]

I've heard all kinds of different ways to solve this problem, yet haven't been able to apply them specifically to the number 8 (Worked fine for 6 for example). I'd love to see a well-explained ...
0
votes
1answer
15 views

Proving Recurrence Relation By Forward Substitution

I'm having trouble understanding the inductive proof of the following recurrence relation by forward substitution. I get that were plugging in the value for our induction step into the relation but I ...
0
votes
2answers
24 views

I'm trying to find a homogeneous equation for the following: [on hold]

$$f(n) = 2f(n-1) + n$$ I don't know how to handle the $n$ by itself, any thoughts?
1
vote
2answers
33 views

Find the sum using

The question is as follows: Find the sum: $1\cdot2 + 2\cdot3 + ... + (n-1)n$ What I have tried so far: We can write $(n-1)n$ as $\frac{(n+1)!}{(n-1)!}$ which we can also write as ...
0
votes
0answers
14 views

Holes on Map - Constraint Satisfaction Problem

Hello all I have been working on a constraint satisfaction problem and I am a little bit lost on where I am going with it. Basically I have a map that is 4x4 and 6 holes are on the map that are ...
1
vote
1answer
24 views

What is the probability Amy wins a lottery prize for correctly choosing 5, not six, numbers…

Here is the full question: What is the probability that Amy wins a lottery prize for correctly choosing 5, not six, numbers out of six integers chosen at random from the integers between 1 and 40 ...
1
vote
1answer
28 views

Counting bridge hands argument

The question is as follows: What is wrong with the following argument, which purports to show that $4C(39,13)$ bridge hands contain three or fewer suits? "There are $C(39,13)$ that contain only ...
26
votes
6answers
375 views

You have to estimate $\binom{63}{19}$ in $2$ minutes to save your life.

This is from the lecture notes in this course of discrete mathematics I am following. The professor is writing about how fast binomial coefficients grow. "So, suppose you had 2 minutes to save your ...
0
votes
0answers
11 views

Number of nodes (or vertices) with degree at most average degree + some constant [on hold]

I'm struggling with a problem of graph theory. In any graph I'm trying to compute how many nodes have degree at most average degree + 1 (or some constant independent of the graph). Obviously there ...
0
votes
2answers
35 views

For all sets A, B, and C, does the equality hold

For all sets A, B, and C, does the following equality hold? $A-(B-C) = (A-B) - C$ $A\cap (\bar B\cup C) = (\bar B \cap A) \cap C$ by DeMorgan's From this, I am able to obtain $A=$ on the ...
0
votes
3answers
29 views

Prove the proposition: $z$ is even if and only if $w$, $x$, and $y$ are even.

Suppose that $w^2 + x^2 + y^2 = z^2$, where $w, x, y,$ and $z$ always denote positive integers. (Hint: It may be helpful to represent even integers as $2i$ and odd integers as $2j + 1$, where ...
0
votes
0answers
30 views

Find the best Big-O estimate

Find the best (i.e., lowest) big-O estimate for the following function: $f(n) = 1 + 3 + 5 + 7 + ...+ (2n-1)$ Since the sum would be $f(n)= \frac{1 + n(2n-1)}2$, that would leave $\frac {2n^2 -n ...
1
vote
0answers
14 views

Does it make sense to compare sets (polygons) with different dimensions?

In the context of integer programming, I am considering 3 different linear models for a given problem. The goal is to determine which formulation is the tightest, that is, the one that gives the least ...
1
vote
0answers
16 views

Is there a difference in decryption of a message if more than two primes are given?

So, I've been looking at RSA Encryption, and I came across Multiple-prime RSA. Is there a different way to go about decryption of a given message if there are more than two primes mentioned? Or does ...