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

Get days on basis of Sum of values of

Lets suppose i have list of days : Sun - 1 Mon - 2 Tue - 4 Wed - 8 Thu - 16 Fri - 32 Sat - 64 Now user can select one or more then one from checklist .My database just storing the sum of days ...
1
vote
1answer
33 views

What kind of set system is defined to have this property?

Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property: For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$. I wonder ...
1
vote
2answers
70 views

Proof Verification for Homework

If $n$ is odd, then $n^2$ is odd. $1$) $n = 2k + 1$ (Definition of an odd number) $2$) $n^2 = (2k+1)^2 = (2k+1)(2k+1) = 4k^2 + 4k + 1$ (Distributive Property) $3$) $4k^2 + 4k + 1 = 2(2k^2 + 2k) + ...
1
vote
1answer
49 views

Finite family of subtori in the torus $(S^{1})^{n}$

Working on a problem on matroids, I've already ask a question about some subtori. Here's the link to a previous problem: Topological subspace in $(S^{1})^{n}$ Anyway, here's another problem related ...
1
vote
1answer
59 views

Topological subspace in $(S^{1})^{n}$

Studying the set of solutions of a particular linear system associated to a matroid, I notice that is it possibile to determine the topology of the quotient and identify it as a subtorus of ...
1
vote
1answer
36 views

Algebra subgroup question

Let $G$ be a group, and let $H$ be a subgroup of $G$. Define $$C_G(H) := \lbrace g \in G \mid h \in H :gh=hg \rbrace.$$ (The set $C_G(G)$ is called the centralizer of $H$ in $G$.) Show that $C_G(H)$ ...
1
vote
1answer
58 views

Let $a_1=1$, $a_2=3$ , and for $n \ge 2$ let $a_n=a_{n-1}+a_{n-2}$. Show that $a_n < \left(\frac{7}{4}\right)^n$ for all natural numbers.

Let $a_1=1$, $a_2=3$ , and for $n \ge 2$ let $a_n=a_{n-1}+a_{n-2}$. Show that $a_n < \left(\frac{7}{4}\right)^n$ for all natural numbers. I assume I'm supposed to use induction. base step is easy. ...
1
vote
1answer
60 views

Easy Z-Transform doesn't match in Wolfram/Matlab

I have this function: $$g(k)=2*(\frac14)^{k-1}+(\frac18)^k$$ I calculate the Z-transform in this way, applying the delay property: $Z[x(k-1)]=z^{-1}X(z)$ $$G(z)=\frac{8}{4z-1}+\frac{8z}{8z-1}$$ ...
1
vote
1answer
56 views

if $f(n)=\Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f+g)(n)=\Theta(n^4)$ where we define $(f+g)(n)=f(n)+g(n)$ ∀$n$.

if $f(n)=\Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f+g)(n)=Θ(n^4)$ where we define $(f+g)(n)=f(n)+g(n)$ $∀ n$. Is the above true or false. I would say its false but honestly its a guess and i ...
1
vote
1answer
45 views

question application product

can any one help me in this questions The perimeter of a square is equal to four times the length of a side of the square. Find the perimeter of a square whose side $s$ measures $2.7$ meters? thank ...
1
vote
1answer
81 views

A naive example of discrete Fourier transformation

We know a discrete Fourier transformation with discrete $n$ and continuous $x_1,x_2$: $$ \sum_{n\in\mathbb{Z}} e^{-in(x_1-x_2)\frac{2\pi}{L}}=L\delta(x_1-x_2) $$ with Dirac delta function $\delta$. ...
1
vote
1answer
166 views

Integrating a discrete 3D surface, in spherical coordinates

I have an matrix which contains height information for a sheet suspended in air. Like a checkerboard, each value in the matrix represents a sampled height. Here's the hard parts: the data in the ...
1
vote
1answer
87 views

How do we determine the duration of a fundamental frequency using the DFT (or FFT)?

I'm still in the process of learning the details of the DFT (and FFT) and I've just made a test .wav file in Audacity by joining 3 one-second sine waves together. .wav file 1 = 440 Hz, sample rate ...
1
vote
4answers
58 views

Help with groups

let $G$ be a finite group with $e$ Identity element and let $a$ and $b$ belong to $g$ prove that if: $\gcd(o(a),o(b)) =1$ then $\langle a \rangle \cap \langle b \rangle = \{ e \}$. if someone can ...
1
vote
2answers
295 views

Hamilton Paths in n-Wheel Graph

According to wolfram, $n$-wheel graphs have $4(n-1)(n-2)$ Hamilton paths in them. $n$-wheel graph = http://mathworld.wolfram.com/WheelGraph.html http://mathworld.wolfram.com/HamiltonianPath.html ...
1
vote
1answer
234 views

Using arithmetic progression sum to show an algorithm is both $\Theta(n^2)$ and $O(n^2)$

Exercise 4 in http://discrete.gr/complexity/ askes to give an arithmetic progression sum to show that the following algorithm is both $O(n^2)$ and $\Theta(n^2)$. ...
1
vote
1answer
31 views

Generating functions for $n*2^n$ & the seq a0+a1+a2+…

1) What is the generating function of $a_n = n2^n, n\geq0$? My answer: $f(x) = \sum a_nx^n = \sum n2^nx^n = \sum n(2x)^n$, but I have no idea where to go from here. 2) Let the sequence $s_n = a_0 + ...
1
vote
1answer
70 views

Show that a subset of the $2 \times 2$ matrices is an infinite cyclic group

Let $M$ Denote the set of 2x2-matrices of the form $$A=\pmatrix{1&m\\0&1}$$ where the entries are integers. Show that $M$, with respect to matrix multiplicaation, is an infinite cyclic ...
1
vote
1answer
39 views

Hanging pictures in the rooms

How many ways to hang 13 different pictures in 7 numbered rooms are there so that there is at least 1 picture in each room? So I tried to look at this from, say, each picture's perspective. So ...
1
vote
1answer
294 views

Dijkstra's Algorithm- Two equal weights, one leads to a shorter path. What to do?

I am confused about this situation that happened to me as I was trying to solve a shortest path problem using Dijkstra's Algorithm. '$s$' is the starting point and '$t$' is finish. When I reach to ...
1
vote
1answer
31 views

Risk Faced With Insurance

I'm studying a simple models of insurance. Suppose that a machine breaks down with probability $p$, and suppose that an insurance company collects enough in premiums to pay for $k$ breakdowns. What ...
1
vote
4answers
862 views

Discrete Mathematics books for Computer Science Self-study

I am an experienced software developer, want to refresh discrete math back in uni. I am looking for a book that is easy to read, contains more examples, and exercises and solutions for self study ...
1
vote
1answer
82 views

Number of arrangements of marbles into boxes

Problem: $n$ different marbles shall be placed in $N$ similar boxes in the following way: $b_1$ boxes should contain $1$ marble each, $b_2$ boxes $2$ marbles each, $b_3$ boxes 3 marbles each and ...
1
vote
1answer
63 views

Basic combinatorics question, can you help me?

Before I start let me thank anyone that contributes to helping me with an answer for this. Ok - on to the question. Assume you have 10 jelly beans, 5 yellow and 5 red. What is the total amount of ...
1
vote
1answer
58 views

Equivalence Relation ~

let S = {1,2,3,4} Explain why each of the below are not equivalence relation. { (1,1), (1,2), (2,1), (2,2), (3,3) } { (1,1), (1,2), (2,3), (1,3), (2,2), (3,3), (4,4) } { (1,1), (2,2), (3,3), ...
1
vote
1answer
51 views

Recurrence Relation for binary sequences

How can I find the recurrence relation with a) no block of 2 consecutive 0's and b)no block of 3 consecutive 0's. Please help me understand this material, detailed explanation will be much ...
1
vote
1answer
51 views

Recurrence Relation Poker Chips

I am assuming that the recurrence relation for a) would be $a_n = a_{n-1} + a_{n-2}+ a_{n-3}$. Correct me if I'm wrong. And I have no idea to what the answer for B is. I would really appreciate it ...
1
vote
2answers
451 views

What does the inverted V represent in math

I know that A V B represents Logical disjunction which means A OR B and the result of it is false only when both A and B are false . But I still didn't understand what an inverted V means as shown in ...
1
vote
3answers
75 views

Prove that $A\subseteq B\Longleftrightarrow A\cap B = A$

In set theory logic mathematics. How would i do the proof for: $A\subseteq B\Longleftrightarrow A\cap B = A$
1
vote
1answer
37 views

Number of relations from A to B with specific domain

I have two sets $A = \{1,2,3,4\}$, $B = \{5,6,7,8,9\}$ I need to find the number of relations from $A$ to $B$ which includes $\{1,2,3\}$ in the domain. It says to use the Inclusion–exclusion ...
1
vote
1answer
53 views

Proving breath first traversal on graphs [duplicate]

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
1
vote
1answer
43 views

Discrete On Recurrence Sets [duplicate]

Find a recurrence relation for the number of ways to select a subset (any size, including the empty set) from the set {1,2,3, … ,n} that does not contain a pair of consecutive numbers? Would this ...
1
vote
1answer
42 views

Discrete Math On inductions

Show that the sequence defined by the formula a_n = n+3, satisfies the recurrence relation a_n = 2a_n-1 - a_n-2 ,for all n ≥ 2. I know this is a induction problem and I think I have to set n= n+1 ...
1
vote
1answer
45 views

Simplification of a boolean polynomial

I have to simplify the following Boolean polynomial using $x\land y$ = $xy$ and $x\lor y$ = x+y : $xy'+x(yz)'+z$ =$xy'+x(y'+z')+z$ =$xy'+xy'+xz'+z$ =$xy'+xz'+z$ My book gives the following ...
1
vote
1answer
47 views

Pairwise sums in an ordered list

The scenario: In a game with n players, each player has a in individual score and players are ranked accordingly (P1 is the player/score in 1st place, and Pn is last place). Ties are allowed. Next, ...
1
vote
2answers
31 views

set problem subsets of function

Let $f \colon A \to B$ be a function and let $p$ and $q$ be subsets of $A$. How can we prove by counterexample that $f(p) \cap f(q)$ is not a subset of $f(p \cap q)$? Could anyone show me how to ...
1
vote
1answer
60 views

Number Theory Related Question: 3x^10=10x^3(mod13)

Number theory related question. Give all answers to: $$3x^{10}\equiv 10x^3 \pmod{13}$$ $0$ is obvious but I can't see a good way to draw out $12$. I've got this so far: Rearrange to ...
1
vote
2answers
60 views

Different ways to distribute

If I have $5$ bananas, $3$ oranges, and $8$ apples, how many ways can I distribute these to $16$ friends, if each friend gets one fruit? Would it simply be $5*3*8=120$?
1
vote
1answer
72 views

Permutation + Combination

this is a question I had on my midterm, and I can't seem to be sure what the answer is and our professor did not post the solutions, therefore I cannot make sure I got it right (or wrong). How many ...
1
vote
3answers
580 views

Use mathematical induction to prove that $(3^n+7^n)-2$ is divisible by 8 for all non-negative integers.

Base step: $3^0 + 7^0 - 2 = 0$ and $8|0$ Suppose that $8|f(n)$, let's say $f(n)= (3^n+7^n)-2= 8k$ Then $f(n+1) = (3^{n+1}+7^{n+1})-2$ $(3*3^{n}+7*7^{n})-2$ This is the part I get stuck. Any help ...
1
vote
1answer
208 views

manhattan to euclidean metric

One may define a graph on a square lattice by taking the nodes of the lattice as graph vertices and the bonds of the lattice as edges. Suppose for simplicity that the nodes have integer $(x,y)$ ...
1
vote
1answer
26 views

calculate the number of different lottery columns

How many different lottery columns exist(of length $13$,with $1,2 \text{ or } X \text{ at each position}$) ? I have to use this theorem: Let $k$ a natural number and $E$ the set of all different ...
1
vote
3answers
26 views

Intersection of two sets that contain other sets as elements

How would the intersection of $A=\{a, b, e, \{a, b, c, d\}, \{d, e\}\}$ and $B=\{a, b, c, f, \{a, d\}, \{d, e\}\}$ be defined? I've searched quite a few books but no luck so far.
1
vote
1answer
90 views

Card probability

There are two 10-card decks, consisting of 5 red cards and 5 blue cards each. Both are shuffled separately. One card is then dealt from each deck and compared. This is repeated for all 10 pairs of ...
1
vote
1answer
323 views

commutative ring and unity elements proof

So this is a review problem in our book I came across and i really want to understand it but I am just not having any luck, I did some research and found a guide on solving it but that's not really ...
1
vote
1answer
53 views

Addition of Binomial Coefficients

$$\left[\binom n{k-1} + \binom nk\right] + \left[\binom nk + \binom n{k+1}\right] = \binom{n+1}k + \binom{n+1}{k+1}$$ Can anyone else explain to me, without using Pascal's triangle, how this ...
1
vote
2answers
418 views

Probability of rolling at least 2 sixes

Okay I do know the answer is $$ \frac{6^5 - 5^5}{6^5} $$ which gives you the probability of at least one six. But then how can you find the probability of at least "Two" sixes? I think this ...
1
vote
2answers
62 views

Permutations and Combinations

Show that $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - ...+(-1)^k * \binom{n}{k} = (-1)^k * \binom{n-1}{k}$. I know this has to do with permutations and combination problems, but I'm not sure how ...
1
vote
1answer
289 views

Give an example of a relation R on $A^2$ which is reflexive, symmetric, and not transitive

I am just looking for some clarification on this exercise: Let $A = \{a,b,c,d\}$. Give an example of a relation $R$ on $A^2$ which is reflexive, symmetric, and not transitive. I understand that if I ...
1
vote
2answers
96 views

Proving that a function from $N\times N$ to $N$ is bijective.

I am stuck on this problem: Define $f: N\times N \rightarrow N$ by $f(i,j)=\frac{(i+j-1)(i+j-2)}{2}+i$. How do you prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically ...