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
1answer
27 views

How do the dependent sets of a matroid characterize the matroid?

Wikipedia says: The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid. So I ...
1
vote
0answers
32 views

Name for variations of elements from several sets

Consider the set $S=\{1,2,3\}$. As is well known, $(1,1), (1,2), (1,3), (2,1), (2,3), \ldots, (3,3)$ are the variations with repetition of elements of $S$ taken two at a time. We can similarly ...
1
vote
1answer
230 views

Rules of inference: The Rules of Disjunctive Syllogism and Double Negation

I have a question about the use of Double Negation in relation to this problem I found in my textbook examples. Problem: $\;¬(r \land t) \lor u$ $\;r \land t$ Therefore, $u$. In my textbook it ...
0
votes
1answer
41 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
0
votes
3answers
118 views

Find the problem with this proof.

The following attempts to prove that if $n^2$ is even, then $n$ is even. Suppose $n^2$ is even. Then $n^2$ = 2$k$ for some integer $k$. Let $n$ = 2$m$ for some integer $m$. This shows that $n$ is ...
1
vote
3answers
51 views

Using set theory to count the possible paths on an XY plane

I'm taking an introductory discrete math course, and we're studying set theory. It's going okay, but I read an example problem which gave me some difficulty. I've included a screenshot of the problem. ...
1
vote
1answer
97 views

Transition probabilities in a finite state machine

Assume I have a finite state machine and a bunch of tokens. Transitions happen every time a token is inserted. Transitions are based on the token (i.e. at state S, inserting a blue token would give a ...
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 ...
0
votes
1answer
30 views

Discrete Math sets and equality.

I have a question about sets and subsets. Consider the universe $\mathbb{Z}$ comprising of all integers and with the following sets: $A=\{2m+1\}$ $B=\{2n-3\}$, where $m$ and $n$ are elements of ...
-1
votes
1answer
38 views

Trouble determining planarity of graph

I am practicing for an exam and I can not wrap my head around this exercise. I am supposed to show if the given graph is planar by drawing it or show the subgraph that is homeopathic to K 3,3 or K5. ...
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
50 views

Determining if a graph is planar and if so draw or disprove with Kuratowski's Theorem

This is a practice exercise for in my text that even my professor was having trouble explaining to me. The instructions are in the title. Here is an image of the graph: I believe this graph is not ...
3
votes
2answers
76 views

What am I doing wrong with this derivative? (Calculus)

I've been doing derivatives with the formula: Definition of a Derivative: for every $x$ plugin $(x+h)$, then subtract original from the equation. This means for $x^2$, I get: $$\frac{(x+h)^2 - ...
0
votes
1answer
50 views

Master Theorem , Polynomial, recurrences

Going through Master's theorem for recurrences but I am seriously confused as what it means when we say that function f(n) is polynomially greater than function g(n) (Case 3) and how can one check ...
0
votes
2answers
65 views

Discrete Math and Sets and subsets question

Let Universe be {1,2,3,4,5,6} If A = {1,2,3,4} then |A| = 4, and from this we can see that A is an element of U(universe), but can someone explain to me why {A} is NOT an element of U? I'snt the ...
0
votes
0answers
53 views

Combination Problem on Create Groups !!!

I'm getting stuck on this combination problem I ran into on a previous final exam: How many ways can 3 different Scientific Groups be formed using 5 students such that each student is at ...
0
votes
1answer
78 views

Polynomial producing only primes

The polynomial: $$a_n x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$$ Coefficients ai are natural numbers, the claim is once you substitute the positive integers 1,2,3,... for $x$ the values of the ...
0
votes
1answer
91 views

How many cards of a single suit must be present in any set of n cards?

In a standard deck with 52 cards, 4 suits with 13 cards per suit. I feel like I may be looking at this question wrong from the angle of probabilities. How do I answer this?
0
votes
3answers
724 views

Celebrity problem, discrete math

so for my problem I have A guest at a party is a celebrity if this person is known by every other guest, but knows none of them. There is at most one celebrity at a party, for if there were two, ...
1
vote
2answers
143 views

Prove that a complement graph of a tree is either connected or it's a union of an isolated vertex and a full graph

I managed to prove the second part - that a tree that is one vertex with n-1 degree and all the rest are connected to it - the complement graph of such tree is an isolated vertex and the rest of the ...
0
votes
1answer
69 views

Prove $1^3+2^3+\ldots +n^3= \left( \frac{n(n+1)}{2} \right)^2$

Ok, so I have $$P(n) = 1^3+2^3+3^3 + n^3= \left( \frac{n(n+1)}{2} \right)^2 $$ assuming $n = k $ $P(k) = 1^3+2^3+3^3+ \cdots + k^3= (k(k+1)/2)^2$ < inductive hypothesis $P(k) = 1^3+2^3+3^3+ ...
1
vote
0answers
30 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
0
votes
3answers
94 views

How many factors does $10^n$ have?

I am trying to workout a pattern, I am not sure if there's any: If $n = 1$, $10^n$ has $4$ factors. If $n = 2$, $10^n$ has $9$ factors. $\ldots$ If $n = 5$, $10^n$ has $49$ factors. For n = $\{1, ...
4
votes
3answers
56 views

Find all integer solution

Find all integer solutions such that $$a+1|2a^2+9$$ Solution. I could solve this by writing $$\frac{2a^2+9}{a+1}=2a-2+\frac{11}{a+1}.$$ So, the only integer solution for the last equation are $a=10, ...
0
votes
1answer
47 views

function, strange formula from Discrete mathematics

I have task: Let $f(x)=\frac{x}{1-2x^2}$. Appoint $[x^n]f(x)$. It's from example exam from Discrete mathematics. In task there isn't anymore information. I don't know what means $[x^n]f(x)$. Anybody ...
2
votes
0answers
37 views

what does “modular” mean?

I find some similarity of the concept "modular set functions" to the cardinality function. But I don't see the cardinality function is also called "modular" or something else. I wonder what "modular" ...
3
votes
1answer
69 views

Problem involving recurrence equation

I have a problem involving two recurrence equations and I can't find an algebraic solution for it. I can however use Excel to determine its solution by generating their terms and check when their ...
3
votes
0answers
38 views

what is the significance of Eigen values of autocorrelation matrix?

I am trying to find auto correlation matrix of an image to get Harris corners.Paper I am referring suggest that if eigen values of auto correlation matrix are large the point will be corner point.so ...
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 ...
0
votes
1answer
50 views

Unusual conditional probability problem

I came across this task in an exam a few days ago: There are 4 men. The first man receives a signal (a "YES" or a "NO"), and tells it to the second man, the second to the third and the third to the ...
1
vote
0answers
17 views

about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...
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
2answers
61 views

Is this a valid proof?

Q: Prove that $m^2 = n^2$ iff (if and only if) $m = n$ or $m = -n$ I began by assuming that the condition m = n or m = -n could be restated as |m| = |n|. Next, I rewrote that as $\sqrt{m^2} = ...
14
votes
2answers
374 views

Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
0
votes
1answer
49 views

Is $f(n) + O(f(n)) = \theta(f(n))$?

I've been asked to show whether this is always, never or sometimes true. I think I understand that in this situation, $O(f(n))$ can be treated as a macro for some function $g(n)$. So if the equation ...
0
votes
2answers
69 views

How many different ways are there to put $9$ coins in $9$ boxes if…

the coins are all identical and exactly six boxes are empty. My first thought was that it should be ${9\choose6} {{3+9-1}\choose9} $, first choosing the $6$ empty boxes and then distributing the ...
3
votes
3answers
66 views

Proof by induction that $\sum_{i=1}^{n} \frac{2^i}{i} \leq n!+1$ for $n\ge 3$

Prove that $\forall n, n\geq 3$, $$ \sum_{i=1}^{n} \frac{2^i}{i} \leq n!+1 $$ By induction, I have that: For $n=3$: $\displaystyle\sum_{i=1}^{3} \frac{2^i}{i} = 20/3 \leq 3!+1=7$ Suppose that ...
0
votes
0answers
49 views

How do we prove that, if $\mathcal{P}(A) \sim \mathcal{P}(B)$, then $A \sim B$? [duplicate]

The converse--if $\ A \sim B$ then $ \mathcal{P}(A) \sim \mathcal{P}(B)$--is very easy to prove. I can't see an immediate, simple proof for the converse case. It seems like a potentially good strategy ...
0
votes
2answers
51 views

Find the values of $r_1, r_2, r_3$ in the recurrence relation $a_n = r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $

Consider the recurrence relation $a_n = > r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $ for $n \ge 3$. The roots of the characteristic polynomial are $x = -1$ of multiplicity 2, $x= 3$ of ...
1
vote
1answer
37 views

A relationship among multiple periodic arrays

There are N periodic arrays ai[n] with period Ti, respectively, where i=1, 2, … , N. Each array has a property that a[n]=1 when n=k*T where k is integer, otherwise a[n]=0. Then a new array is created ...
2
votes
1answer
79 views

Convex Hull of discrete points

If i was to give an $n \times n$ grid with each grid point having probability $p$ of being selected, would it be difficult to calculate distributions of various measures regarding the convex hull of ...
0
votes
0answers
40 views

Formula for this game

There are two players A and B. Given K,L a player A can pick 1, or K or L coins($1<K<L$) from the M coins then player B can pick 1 or K or L coins from the remaining coins, and the ...
1
vote
2answers
106 views

How can I solve this problem without having to do it by hand?

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement without forcing me to do it ...
3
votes
1answer
119 views

Graphs without nontrivial automorphism

I'm trying to solve two problems about graph automorphisms. I want to construct a bipartite graph without a nontrivial automorphism. I want to find the smallest possible number of nodes for a graph ...
4
votes
2answers
162 views

Count Number of Sequences

The question is: Given a sequence of positive integers A={1,2,3,...,N}. Count the number of sequences you can get after making K swaps between adjacent element on it for a given N ? My approach: My ...
0
votes
2answers
56 views

Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0 $ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...
0
votes
1answer
76 views

How can I solve this problem without doing it by hand? [duplicate]

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement without forcing me to do it ...
1
vote
1answer
75 views

Inclusion–exclusion principle (about intersections)

As an outcome of this question what does the Inclusion–exclusion principle means in disjoint? is {1,4}$\cap${1,2}=$\emptyset$?
1
vote
2answers
94 views

Is there any way to solve this problem without having to do it by hand? [duplicate]

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement. Is there any way to group ...
2
votes
1answer
124 views

A generalized combinatorial identity for a sum of products of binomial coefficients

I have the following question. For given natural numbers $n$ and $d$, let $a_1,a_2,..., a_r$ be fixed integers such that $a_1+\cdots+a_r=d$. Let $A=\{(i_1,..,i_r)~|~0\le i_j\le n~ \text{and}~ ...