Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

1
vote
1answer
58 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
49 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
35 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
49 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
62 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+ ...
0
votes
0answers
20 views

A supper club rotation scedule

I have a couples supper club with 28 couples. We will meet 6 months as groups of about 4 couples at 7 different host homes each month. I need a way to schedule these each month so we have as little ...
1
vote
0answers
20 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
73 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, ...
3
votes
3answers
35 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
37 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
25 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" ...
0
votes
0answers
16 views

The empirically-obvious statement about minimization of Boolean functions

The statement: $\forall f,g: \{0;1\}^n \to \{0;1\} \; (n > 0),$ if $$|f^{-1}(1)| > |g^{-1}(1)|$$ then $f$ has the (non-strictly-)simpler minimization than $g$. $\text{ }$ As mentioned, the ...
3
votes
1answer
56 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 ...
2
votes
0answers
17 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
40 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
38 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
13 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
47 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 ...
0
votes
2answers
46 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
269 views

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

Post-Bounty Edit: Still no answer; will gladly accept if someone can provide a reference. Earlier Edit: It appears that the answer is "yes," either by an already existent publication or by ...
0
votes
0answers
20 views

Algebra homomorphisims question

Define $$\alpha:H \rightarrow HK/K\\ h \rightarrow kh$$ Show that this is a homomorphisim and show that ker$(\alpha)$=$H \cap K$ I know what it means for two groups to be a homomorphisim ...
0
votes
1answer
28 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
30 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 ...
0
votes
0answers
29 views

Two definitions of matroid

From Wikipedia, a finite matroid $M$ is a pair $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$ either with the following properties: The empty set is in $F$. if $X \in ...
3
votes
2answers
67 views

Prove $A = (A \setminus B) \cup (A \cap B)$

Prove $A = (A \setminus B) \cup (A \cap B)$ Logically, this is clearly true. I can explain why: start with $A$, remove all elements in $B$ and then add in any elements in both $A$ and $B$, which ...
0
votes
0answers
7 views

Rank feasible subset of a greedoid

From Wikipedia, given a greedoid $(E,F)$, with ground set $E$ and the class $F$ of feasible sets, A subset $X$ of $E$ is rank feasible if the largest intersection of $X$ with any feasible set has ...
3
votes
3answers
59 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
21 views

Max Function Notation [duplicate]

I've been asked whether the following is always, never or sometimes true: $f(n) + g(n) = \theta(\max(f(n), g(n)))$ I understand the definition of theta notation, but I'm not sure how to read the ...
0
votes
0answers
40 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
27 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
29 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 ...
1
vote
0answers
23 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
27 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
82 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 ...
2
votes
1answer
47 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
99 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 ...
1
vote
2answers
34 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
68 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
30 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
66 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 ...
0
votes
0answers
42 views

Combination Problem on Contest [duplicate]

I get stuck in one combination problem that mentioned in computer informatics Olympiad on two days ago. You have just 1,2,3 Euro coins, and how many ways you buy a 20 Euro ice-cream, if the seller ...
2
votes
1answer
75 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}~ ...
1
vote
1answer
28 views

Source coding and Entropy

Hell people, I have a small question I came by , but I am not quite sure about the right approach to it. Suppose that we have a source that transmits 5 symbols. We have two cases. When all ...
0
votes
3answers
45 views

Calculate the number of functions $f:A \rightarrow B$ satisfying the condition $f(1) \le f(2)…\le f(n)$

Let $n$ be a positive integer and Denote by $X$ the set of all functions $f$ from the set $A=\{1,2,...n\}$ to the set $B=\{1,2,3 \} $. Calculate the number of functions $f:A \rightarrow B$ ...
0
votes
1answer
87 views

Coin in City Problem [closed]

Please consider this problem. in one city common coin is 1dollar ,2dollar and 3dollar coin. how many way of paying the The price for an 20dollar candy which the seller has no money and number of ...
0
votes
3answers
29 views

DNA Sequence Distinct Way

we know The genetic code is based on the four nucleotides adenine (A), cytosine (C), guanine (G), and thymine (T). These are connected in long strings to form DNA molecule. with three A, one C, two G ...
1
vote
0answers
15 views

Existence of a particular transformation

I've a set of data points $S = \{ x | x\in [0,1]\}$ (i.e. real values from the unit interval). In some cases I've big clusters in the data and I want to spread the values in between the unit interval ...
1
vote
2answers
22 views

Relations on a set, check my answers?

I've been struggling with identifying relations on a set, and was hoping someone could check my answers and make sure I'm on the right track. Let A = {1,2,3,4} and R be a relation on the set A ...
2
votes
0answers
26 views

Identification of (Centers of) Cycles in a Discrete Time Dynamical System

I am studying dynamics on nonlinear Discrete Time Dynamical System of the form $$ \vec{X}_{t+1} = D(\vec{X}_t), $$ where D is some nonlinear function. I was looking for a (relatively) quick ...
2
votes
0answers
30 views

Inequality in matroid theory

Working on a proof in matroid theory I found there is a smooth map from an open set of $(\mathbb{C}^{\ast})^{(d−1)(n−d−1)}$ to a disjoint union of tori $(S^{1})^{\binom{n}{d}-n}.$ As a direct ...