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
2answers
29 views

Proving or disproving statements about operations with integers

I'm really stuck with this one and I'm thankful for any help. Consider the following operations on the set of integers: $\hspace{8em} a\star b := a^2 + b^2 \hspace{5em} a\diamond b := a+b+2ab$ ...
3
votes
3answers
123 views

In how many ways can $25$ identical pens be distributed to four students with restrictions?

Use combinatorics to count how many ways can 25 identical pens be distributed to four students so that each student gets at least three but no more than seven pens. What I have done so far is look ...
1
vote
1answer
21 views

Generating Function for a Recurrence: $a_k = 3a_{k−1} + 4$

Use generating functions to solve the recurrence relation $a_k = 3a_{k−1} + 4$ with the initial condition $a_0 = 1$. I have done my work until $(4-x)\sum_\limits0^\infty (n+1)x^n$ and got stuck ...
0
votes
0answers
20 views
0
votes
0answers
83 views

How to use the Set Builder Notation to express the composite relation $R^n$?

This is what I came up with $R^n=\{(x,z) ∈ R^n \mid \exists y\,((x,y) ∈ R^n ∧ (y,z) ∈ R^n)\}$ It's just that the $R^n$ bugs me a lot...Can someone explain? I have read the book and look through the ...
1
vote
2answers
43 views

Let $m$ and $n$ be positive integers. Show that $ \frac{(m+n)!}{(m+n)^{m+n}} < \frac{m! n!}{m^m n^n}$

Let $m$ and $n$ be positive integers. Show that $$\frac{(m+n)!}{(m+n)^{m + n}} < \frac{m! n!}{m^m n^n}.$$ I am not able to solve the problem. Is anyone is able to give me a hint?
1
vote
1answer
63 views

Using Property Rules to Simplify Set Expressions

I've been given a series of 20 set expressions which need to be simplified using property rules as part of an assignment. I have absolutely no idea what I'm doing. I've researched the subject online ...
1
vote
1answer
55 views

Counting Graph Isomorphism

I am self studying graph theory and was wondering: is there a simple way to count/compute the number of subgraphs G that are isomorphic to another graph (say, G')? For instance, if G = the complete ...
1
vote
3answers
58 views

$(n-1)^{(n-1)}>n^{(n-2)}$ - Chebyshev inequality

Let $f(n)=(n-1)^{(n-1)}$ and $ g(n)=n^{(n-2)}$. Show that $f>g$ for all $n >2$. I think I have to use the Binomial theorem and Chebyshev inequality to solve the problem. Is anyone is able ...
1
vote
1answer
23 views

Palindrome arrangement problem

How many five-letter palindromes are there (using ordinary 26 letter alphabet)? I was thinking it was either using permutation with first three leters or using 26 cubed. Thanks
1
vote
1answer
100 views

Identities about Bell numbers

The $n$-th Bell number equals the number of set partitions of $\{1,2,\dots,n\}$. We set $B_0 := 1$. Prove the following identities: $$B_n = \sum_{k=0}^{n}S_{n,k} \qquad and \qquad B_{n+1} = ...
1
vote
3answers
72 views

Show that for any $a\in\mathbb{Z}$, $3 \mid(a^3 - a)$

Show that for any $a\in\mathbb{Z}$, $3 \mid (a^3 - a)$ my solution is : if $a$ is a multiple of $3$ then $a^3-a$ is a multiple of $3$; if $\gcd(a,3)=1$ then by FLT $a^2\equiv 1 \pmod3$, hence $a^3-a ...
0
votes
1answer
45 views

Seating six people at a round table, permutation question

How many ways are there of seating six people at a round table so that two specific people sit together? I think it is a permuation question but not 100% sure. Thanks
0
votes
0answers
20 views

How can I find out the sum of these two particular sets of natural numbers?

With the function $g : A\times B \to \mathbb N$ defined by $g(a,b)=a+b$, how could I determine the subset $C \subseteq \mathbb N$ that is the image of $g$ if I knew the way $A$ and $B$ are ...
2
votes
1answer
29 views

What does it mean when a number 'y' is pseudoprime to base 'x'

I am self learner so I don't really understand about pseudoprime to base 'x' for example) 91 is a pseudoprime to base 3 then is 91 also a pseudoprime to base 2? thank you please explain. ...
0
votes
1answer
23 views

Prove that the two sets are identical.

Consider the function $g(n):N\rightarrow R^+$ and two sets defined as follows: $o(g(n)) = ${$f(n):N\rightarrow R^+|\forall c \in R^+$ $\exists n_0\in N$ $\forall n\geq n_0: f(n)<c \centerdot ...
1
vote
0answers
49 views

Probability of getting a subset

During a discussion with my colleague we've raised a question that can be simplified to the probability of getting a specific subset. Suppose we have two types of components and one type is treated as ...
2
votes
1answer
119 views

Solution to a recurrence relation

Set $F_k(x) := \sum_{n\geq k} S(n,k)x^n$. Prove that $$F_1(x) = \frac{x}{1-x}, \space \space \space F_2(x) = \frac{x^2}{(1-x)(1-2x)} $$ Furthermore, show that the function $F_k(x)$ satisfy the ...
0
votes
2answers
47 views

Find all integer solutions to this congruence

This is what I got but I am not sure if it is correct. \begin{align} & 5x \equiv 3 \pmod 3 \\ & 3 \times 5x \equiv 3\times 3 \pmod 3 \\ & x \equiv 15x \equiv 6 \pmod 3 \\ & x \equiv 0 ...
0
votes
1answer
61 views

Cyclic representation of permutations and Stirling numbers

I have been studying combinatorics lately, and I came across this cyclic representation of permutations and Stirling numbers. I understood some stuff, but other stuff are still unclear to me. For ...
1
vote
1answer
22 views

Justifying $\sum_{k=1}^{n}k\cdot 2^k=2^{n+1}(n-1)+2$ using difference and shift operators

$$\sum_{k=1}^n k\cdot 2^k = 2^{n+1}(n-1)+2$$ How can I justify that using difference and shift operators?
0
votes
2answers
110 views

Number of injective and surjective mappings $f : A \rightarrow B$ for two sets?

Let $A, B$ be two finite sets with $|A| = n$ and $|B| = k$. How many injective mappings $f : A \rightarrow B$ are there? Furthermore, show that the number of surjective mappings $f: A \rightarrow ...
3
votes
5answers
111 views

Prove the identity $x^n = \sum^{n}_{k=0}S_{n,k}(x)_k$

Prove the following identity: $$x^n = \sum^{n}_{k=0}S_{n,k}(x)_k \space \space \space\space\space\space\space\space\space\space\space\space\space (n \geq 0)$$. We are talking clearly about ...
2
votes
2answers
109 views

Proving recurrence relation on the cardinal of the derangements

Let $$f_n = |\{\pi \in S_n \space | \space \forall 1 \leq i \leq n : \pi(i) \neq i \}|$$ Prove that $f_1 = 0, f_2 = 1$, and $f_n = (n-1)(f_{n-1} + f_{n-2})$. Furthermore, prove that this ...
1
vote
2answers
96 views

Counting the number of words made of $2n$ letters

Compute the number of words made of $2n$ letters taken from the alphabet $\{a_1, a_2,\ldots,a_n\}$ such that each letters occurs exactly twice and no two consecutive letters are equal. I started ...
0
votes
0answers
20 views

Discrete Logarithm of 1 (mod p)

Strangely there is no question about this anywhere on the internet or this site, SO I assume it is settled then... Suppose I am given a modulus with prime index p, defined in the usual way. Just as ...
0
votes
1answer
35 views

Correctly quoting a Hamilton Circuit

This might come across as a slightly petty question. Apologies for this, I am only asking as I have an exam on Graph Theory soon and want to make sure I do things correctly. The definition of a ...
2
votes
0answers
117 views

Bounding the global intersection of a family of sets

Suppose that we have a decision tree of height $r + 1$ that describes how to increment an $n$-bit integer in the range $[0, 2^n -1]$. That is, the internal nodes are labelled with a bit position that ...
0
votes
1answer
47 views

Pythogorean Triples

How can I prove the statement that in a Pythagorean Triple if c is even then so are both a and b. I know someone asked this question previously but those solutions don't make sense so can someone tell ...
4
votes
4answers
188 views

What is the probability of getting exactly 3 two's OR three's when a die is rolled 8 times?

What is the probability of getting exactly $3$ two's OR three's when a die is rolled $8$ times? I know that $P(E) = |E| / |S|$. I believe that $|S| = 36$, since there are $36$ different ...
1
vote
2answers
441 views

Prove Perfect square of the form 4k or 4k+1 [closed]

So i want to prove that every perfect square is of the form 4k or 4k+1, can someone tell me how to do this. Really need help with this
0
votes
1answer
28 views

How to compute an adjacency matrix?

I'm doing graph theory in my discrete math class, and I'm not understanding the concept. I've read online it has something to do with number of edges for undirected and number of arrows for directed, ...
0
votes
2answers
130 views

Discrete Mathematics Logic Based

For our maths assignment it is heavily Logic based, with some of the questions being quite confusing, such as the one below. My lecturer has asked the following: In the 1730’s, the “Grande Loge” of ...
0
votes
0answers
23 views

Solve an equation of factorials (Gamma fumction)

I am trying to solve following equation: $F(z)=\frac{(z!)(n-z)}{(n!)}$. Where n is a constant. I know it is equivalent to $F(z)=\frac{\Gamma(z+1)\Gamma(n-z+1)}{\Gamma(n)}$. How can I find the two ...
-1
votes
1answer
78 views

Pigeonhole principle formula using Propositonal Logic

According to the Pigeonhole Principle, if we try to place $n+1$ pigeons in $n$ pigeonholes, then at least one pigeonhole must have two or more pigeons. For $i \in \{1, 2, \dots, n+1\}$ and $j \in \{1, ...
1
vote
1answer
27 views

finding contrapositive of logical statement

I am familiar with the contraposition definition of if P then Q and if Q then P, as well as real world examples such as "if all cats are animals" then "if something is a cat, it is an animal" . ...
3
votes
1answer
173 views

How many ways can you get a bag of $12$ donuts if a shop sells $30$ kinds of donuts?

A donut shop sells $30$ kinds of donuts, and there are at least $12$ donuts of each kind. How many ways can you: Get a bag of $12$ donuts? Get a bag of $12$ donuts if you want at least $3$ glazed ...
1
vote
1answer
31 views

Hamilton cycles for bipartite graphs

I know that a hamilton cycle exists for a bipartite graph $K_{m,n}$ if and only if $m=n$ But my question is why is it not possible to have a bipartite graph if $m=n=1$ I mean we would go from $x$ to ...
1
vote
1answer
30 views

Prove that there is a red triangle or a blue triangle that is is a sub-graph

If the edges of $K_6$ are coloured blue or red, prove that there is a red triangle or a blue triangle that is a sub-graph. Well I am having a hard time proving this, I try to prove it by ...
2
votes
1answer
43 views

Largest possible number of vertices in this graph

let $G=(V,E)$ be a connected graph, with $|E| = 19$ and $deg(v) \geq 4$ for all vertices $v$ in $V$ What is the largest possible value of $|V|$ ? Well I know that the sum of the degree is ...
1
vote
1answer
42 views

How to use pigeonhole principle to demonstrate lower bound in this problem is $\frac{k(n+1)}{2}$?

Background This is not a homework problem, but I am reading through a discrete mathematics book since I am trying to formalize my background in computer science. I came across the following. ...
0
votes
3answers
79 views

solving iff logical statements

Given that Processor A reports that Processor B is not working and Processor C is working. Processor B reports that Processor A is working if and only if Processor B is working. Processor C reports ...
0
votes
2answers
27 views

Is my process of proving inequalities using Mathematical Induction correct?

$$ 2^n<(n+1)! \quad \text{for all integers} \quad n \ge 2$$ Base Case: $$ 2^2< (2+1)! = 4< 6 $$ Correct Assumption: $$ P(k): 2^k<(k+1)!$$ $$P(k+1)= 2^{k+1}<(k+2)!$$ Now we start ...
0
votes
3answers
45 views

translating logical quantifiers

Let a = “A is working,” b = “B is working,” and c = “C is working.” Write the three status reports in terms of a, b, and c, using the symbols of formal logic. Processor A reports that Processor B is ...
1
vote
1answer
41 views

Formula for periodic sequence with increasing period

The first values of the sequence are: $\lt1, 0, 1, 1, 0, 0, -1, -1, -1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, ...
0
votes
1answer
106 views

For all real numbers x, if x −⌊ x ⌋≥ 1/2 then ⌊2x ⌋= 2⌊x ⌋+ 1.

I had this problem as a homework assignment and had to write a proof for it. I've tried some approaches but keep getting stuck. This is what I have so far: Suppose that x is any particular but ...
1
vote
2answers
83 views

Proving a Set Theory identity [closed]

Please guys help me prove some Identities. I need to prove that: $$B=C \Longleftrightarrow (A \cup B = A \cup C) \land (A \cap B = A \cap C)$$ and also that $$(A \cap B)\cup C = A\cap(B\cup C) ...
0
votes
1answer
56 views

How to find the recursive definition of this function and prove by induction.

For question $2a$.) i so far put down: The recursive definition of $$S(n+1) = S(n) + \left[\left(\frac{1}{2^n}\right) - 1\right]$$ $2b$.) Induction hypothesis, $n\ge0$, $S(n) = 1 - ...
0
votes
1answer
69 views

How many bit strings of length 6 either begin with two 0's or end with three 1's

How many bit strings of length 6 either begin with two 0's or end with three 1's I have this so far: Starting: 0 0 X X X X so: $2^4$ combinations Ending: ...
0
votes
0answers
18 views

Nonhomogenous Recurrence Relations | p(n) for given f(n)

I've been reviewing questions for an upcoming test and I got to a question an+1 - an = 3n2 - n In the textbook I use, given f(n) = 3n2 it says to use p(n) = d2n2 + d1n + d0 and if f(n) = n to use ...