Questions on discrete mathematics generally: "the study of mathematical structures that are fundamentally discrete rather than continuous"
2
votes
1answer
98 views
Please help me verify the following set equation from The Essence of Discrete Mathematics by Neville Dean
LaTeX markup suggested format:
$\{y\in N_1 | y\le 4 \land (\exists x\in Z| x< 4 \land 6=yx\}$
Author's original post:
{y:∈ N1 | y ≤ 4 Ʌ (∃x:∈Z | x < 4 . 6=y*x)}
The first part of the equation ...
0
votes
1answer
175 views
Predicates and proposition.
Specify two predicates $P(x)$ and $Q(x)$ over the universe of positive integers such that the proposition $\exists x(P(x) \wedge Q(x))$ is false while the proposition $(\exists x(P(x))) \wedge ...
3
votes
1answer
674 views
Combinatorics - pigeonhole principle question
This is for self-study. This question is from Rosen's "Discrete Mathematics And Its Applications", 6th edition.
An arm wrestler is the champion for a period of 75 hours. (Here, by an hour, we mean a ...
1
vote
0answers
237 views
Sylvester's Theorem and Schur Theorem
I'll probably end up asking more programming questions on StackExchange forums than math questions, but I'll lead off with a math question.
In my Number Theory class this past semester, I worked on a ...
1
vote
2answers
111 views
Binomial distributions
If I'm tossing 4 pennies at once, and then recording how many heads there came out to be 32 times, is that a Binomial experiment?
0
votes
1answer
109 views
Opposite of a logical expression
What is the opposite of this expression?
$p \land ( q \lor r )$
Please suggest any theorem as a starting point.
2
votes
2answers
486 views
Subsets with equal sums
I have a problem to solve but I am in need of your help.
Subjects with equal sums:
Prove that for every set $A$ which consists of $10$ double digit natural numbers( numbers among $10, \ldots, 99$), ...
1
vote
1answer
57 views
Every $t$-coloring of $K_{2t+1}$ contains a monochromatic cycle
I need help in the following question:
I need to prove that in all possible coloring with $t$ colors of the complete graph $K$ with $2t+1$ vertices, there will always be a monochromatic cycle (its ...
4
votes
2answers
148 views
Does this generalisation of Latin squares have a name?
I am interested in looking at $n\times n$ tableaux (or matrices) in which (WLOG) each integer in $\{ 1, 2, \ldots, n \}$ occurs exactly $n$ times. This is a generalisation of a Latin (or even ...
3
votes
1answer
470 views
Counting the number of directed graphs with $N$ vertices and $E$ edges?
Does any body who has good back ground in graph theory tells me that how many possible directed graphs will be there with $N$ vertices and $E$ edges. I need all the possible combinations even even ...
2
votes
1answer
203 views
Pigeonhole principle to prove division
Here's a little question that we were shown in class:
Let $S = \{1,2,\ldots,200\}$ and let $A \subseteq S$ such that $|A| = 101$.
Prove that there are two elements of $A$ such that one is a ...
143
votes
1answer
6k views
How many fours are needed to represent numbers up to $N$?
The goal of the four fours puzzle is to represent each natural number using four copies of the digit $4$ and common mathematical symbols.
For example, $165=(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}) ...
1
vote
1answer
101 views
Formula for sub and super sequence length given 2 strings
I have done a coding exercise where the problem was to compute the maximal length of a common substring given two strings. Consider strings as finite sequences with elements in the English alphabet ...
0
votes
2answers
994 views
Bijective proof? Examples?
I'm having trouble with understanding bijective proofs. I searched a lot, but I could not find a simple and well-explained resource.
Can you give a simple example of a bijective proof with ...
13
votes
2answers
537 views
Is there a discrete version of de l'Hôpital's rule?
When considering asymptotics of runtime functions, you often have to find limits of quotients of discrete functions, e.g.
$\displaystyle\qquad \lim\limits_{n \to \infty} ...
4
votes
2answers
436 views
Some three consecutive numbers sum to at least $32$
Here's a question we got for homework:
We write down all the numbers from $1$ to $20$ in a circle. Prove that there is a sequence of $3$ numbers whose sum is at least $32$.
I assume we need the ...
3
votes
3answers
117 views
to find number of divisor of $p^m$ times $q^n$ when $p$ and $q$ are primes
Am taking a intro discrete math course..it covers some number theory content
Euclidean algorithm,modular arithmetic, Euler's phi function, that's all
How can I solve a question like this:
If $p$ and ...
1
vote
2answers
137 views
Euclid algorithm greatest common divisor
In Knuth's book "The Art Of Computer Programming Vol.1" there is a description about Euclid's algorithm to find the greatest common divisor of m and n.
And there is a phrase. $m = qn+r$. If $r = ...
3
votes
0answers
192 views
What is the expression for putting $n$ indistinguishable balls into $k$ indistinguishable cells?
I'm looking for the expressions for the number of ways in which $n$ indistinguishable balls can be placed into $k$ indistinguishable cells, with
No cell being empty
Some cells being empty
I knew ...
2
votes
1answer
172 views
How to solve the following combinatorics problem?
There are $C$ kinds of colored balls, with $f_i$ being the frequency of each color $c_i$, such that $\Sigma_{i=1}^{C}f_i = n$, and $F= max(f_i)$.
Let $G(x)$ be the number of ways in which these $n$ ...
0
votes
1answer
392 views
Coin Toss Probablities and Outcomes
I'm having a hard time with this question, but I did the best that I could. I would appreciate any help to correctly solve it.
Suppose that a coin is tossed three times and the side
that ...
0
votes
1answer
849 views
Five people are to be seated around a circular table. How many seatings are possible? (Full Q inside)
I'm attempting this question, but I'm a little unsure about my answers. The full question is:
Five people are to be seated around a circular table. Two seatings are considered the same if one is a ...
1
vote
2answers
2k views
How many solutions are there to the equation $x + y + z + w = 17$?
How many solutions are there to the equation $x + y + z + w = 17$?
I don't know if I'm doing this right, but I guessed that the solution would be $\binom{20}{3}$, which equals $1140$. Am I doing ...
2
votes
2answers
159 views
Question about the Pigeonhole Principle
The question is:
Let $A = \{1,2,3,4,5,6,7,8\}$. If five integers are selected from $A$, must at least one pair of the integers have a sum of $9$?
The book explains the solution by dividing the ...
0
votes
1answer
149 views
Probablity: 2 Urns
I'm trying to find the solution for this problem:
There are 2 urns: urn 1 has 2 red balls and 1 blue ball and urn 2 has
1 red ball and 2 blue balls. You're supposed to randomly select one
urn ...
1
vote
1answer
107 views
points within discrete subgroups of the plane isometry group
So... last question that I have to do this semester... and of course it's one that I am completely wedged on.
I am supposed to show that for any discrete subgroup $G$ of the isometry group in the ...
2
votes
4answers
111 views
“Down-Closed”, “Down Ideal”, Something Else?
Let $X$ be an a set and let $\mathcal{C}$ be a collection of subsets of $X$ satisfying the following property:
If $A$ and $A^\prime$ are subsets of $X$ with $A \in \mathcal{C}$ and $A^\prime ...
2
votes
3answers
1k views
Number of non-isomorphic regular graphs with degree of 4 and 7 vertices?
I'm faced with a problem in my course where I have to calculate the total number of non-isomorphic graphs. The graph is regular with an degree 4 (meaning each vertice has four edges) and has exact 7 ...
2
votes
3answers
275 views
Is this a proper use of induction? ($(n^2+5)n$ is divisible by 6)
Just want to get input on my use of induction in this problem:
Question. Use mathematical induction to prove that $(n^2+5)n$ is divisible by $6$ for all integers $n \geqslant 1$.
Proof by ...
1
vote
0answers
38 views
How to solve this problem about discrete mathematics (Probability) [duplicate]
Possible Duplicate:
Number of ways of spelling Abracadabra in this grid
Determine the number of ways of spelling “mathematics” in the array below by following a path from top to bottom in ...
3
votes
1answer
137 views
crossing number question
Prove that there exists constant k such that, for all $5v < e$ there is a subgraph of the complete graph of $v$ vertics with crossing number less or equal than $ k e^3/v^2$.
Any hints for a way to ...
0
votes
1answer
296 views
Positive integers less than 1000 without repeated digits
How many integers from 1-999 do not have any repeated digits?
The answer is explained in this link, but why is the last set 9*9*8? Why not 9*9*9?
1
vote
1answer
433 views
Discrete Structures: Bit Strings
So my professor gave us an HW assignment which includes this question:
"How many bit strings consist of 1 through 5 bits. (Note 10 and 00010 are considered distinct even though they are both ...
6
votes
1answer
610 views
Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin
The number of ways to put $n$ unlabeled balls in $k$ distinct bins is
$$\binom{n+k-1}{k-1} .$$
Which makes sense to me, but what I can't figure out is how to modify this formula if each bucket has a ...
1
vote
1answer
53 views
What will be the mathematical formula to fetch the position of a letter from this string?
The above full string is a combined form of two different strings named string-1 and string-2. Both strings has equal length of 32 characters. There is two other parameters interval and size. ...
0
votes
3answers
155 views
Using induction to find a general pattern of $x,y$
Let $m$ be an even natural number. Find natural numbers $x$ and $y$ such that
$$ m=(x+y)^2+3x+y$$
Try a few cases to find pattern and then use induction to prove that the pattern works.
P.S I saw ...
1
vote
1answer
90 views
Is $\{a,c,e,g\}$ an equivalence class?
If the set $\{a,b,c,d,e,f,g\}$ is is partitioned into these three partitions:
$\{a, c, e, g\}$
$\{b, d\}$
$\{f\}$
and an equivalence relation is produced by these partitions, is $\{a,c,e,g\}$ an ...
3
votes
0answers
133 views
Expected value of the minimum of a random set of distances
You are given a rectangular $n_1\times n_2$ grid with one light bulb $b_i$ at every node. Each bulb is on or off with probability $p$ and $1-p$, respectively, and furthermore you know that exactly $m$ ...
2
votes
1answer
163 views
Expected value and Variance of a Random Variable
I understand Mean (Expected Value) and Variance of Random variables as outlined on this page. I can't seem to apply those concepts to this problem, however.
Say there's a class of 50 people answering ...
0
votes
2answers
297 views
How many strings are there of $4$ or fewer lower case letters that have the letter '$x$' in them?
These problems always fumble me up. Just looking to see if my answer is correct.
I found that:
$4$ letters: $(26^3) \times 4$,
$3$ letters: $(26^2) \times 3$,
$2$ letters: $(26) \times 2$,
$1$ ...
1
vote
2answers
160 views
Number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s
How do I find the number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s?
I think the title is self-explanatory.
E.g., if I have to represent $13$ as a sum of only ...
1
vote
1answer
205 views
Comparing the number of cuts and paths in graph
How would you prove that the number of cuts in a graph (where cut is a set of edges which split two vertices) cannot be smaller than the number of directed paths from one vertex to the other?
3
votes
2answers
144 views
Proof that the relation $5 \mid (a + 4b)$ is symmetric and transitive
Take the relation $R$ to be defined on the set of integers:
$$aRb \iff 5 \mid (a + 4b)$$
As part of a larger proof, I have to show that $R$ is both symmetric and transitive. I'm lost.
I see the ...
1
vote
1answer
529 views
Simple graphs (edges, nodes etc.)
Draw all possible graphs that can be constructed from the vertices $V_1=\{a,b,c\}$. Answer: Pic: I believe this is all of them (bottom three are all the same).
How many such graphs have no edges? ...
2
votes
1answer
171 views
Proof about trees
Show that in any tree there exists a node such that, if we remove this
node and the edges adjacent to it, we will obtain trees which have at
most n/2 nodes (the removed node is not counted ...
1
vote
3answers
301 views
Stirling Numbers of the Second Kind
I am trying to understand the derivation of the Stirling Numbers from a difference table.
From my book:
Let $h_n = n^p$.
The $0$-th diagonal of the difference table for $h_n$ has the form ...
2
votes
4answers
161 views
recursion need a closed form
Is there a closed formula to the problem $f(1)=1, f(2n)=f(n), f(2n+1)=f(2n)+1$. So far i have found a solution for $n$, which is the number of power of $2$'s needed to add up to the number starting ...
2
votes
1answer
163 views
Over an alphabet of $n$ symbols, how many are the strings of length $k$ without consecutive symbols repeated?
From combinatorics, it's known that over an alphabet of $n$ symbols there are $n^k$ different strings of length $k$, of which $\frac{n!}{(n-k)!}$ (assuming $k \le n$) are those without any repeated ...
-1
votes
2answers
276 views
Sets / Bijection / Countablity
Can you please help me with this question?
Is the set finite, countably infinite, or uncountable?
a. The set of all real-valued random variables on a finite sample space.
b. The set of ...
3
votes
3answers
595 views
Permutation and combination - Discrete Math
You have $15$ marbles and three jars labeled A, B, and C. How many ways can you put the marbles into the jars…
(a) If each marble is different? (My answer C(15,3) )
(b) If each marble is the same? ...
