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

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$?

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$ , I don't have an idea for solve the question. My attempt : $\frac{T(n)}{\sqrt {n}}^2 =99T(\sqrt {n})+100 $ and $\ s(k)= ...
0
votes
1answer
452 views

Size K subset sum problem?

I am trying to solve the following problem - I have a set of $n$ elements consisting of objects say from $O_1$ to $O_n$ ($\{O1_,O_2,O_3,........,O_n$}). Each of those elements are mapped to an integer ...
2
votes
5answers
52 views

Showing that $\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$ for all $n\geq 1$

Show that $$\frac{1}{2^n +1} + \frac{1}{2^n +2} + \cdots + \frac{1}{2^{n+1}}\geq \frac{1}{2}$$ for all $n\geq 1$ I need this in order to complete my proof that $1 + \frac{n}{2} \leq H_{2^n}$, but ...
3
votes
1answer
1k views

Recurrence relation question

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. a) Find a recurrence relation for ...
-4
votes
0answers
19 views

How many 8 bit strings with exactly one 1? [on hold]

Can you help me? How many 8 bit strings with exactly one 1? Can I ask for the solution? Thank you.
-3
votes
0answers
17 views
1
vote
1answer
58 views

Can we prove that set of irrational numbers is a set using Zermelo-Fraenkel axioms?

To remove paradoxes of naive set theory, We started with the axioms of Zermelo-Fraenkel and developed a set theory. Where we are building sets starting from a empty set. How to construct set of ...
1
vote
1answer
29 views

What is a transfer function?

If: $N$ is a set of nodes in a program dependence graph, which is a graph with two type of edge $L$ is a lattice of security levels What does the following mean: "For every $x\in N$, a so-called ...
0
votes
0answers
16 views

Clarification of conditional propositions [duplicate]

I am studying first order logic and we have been introduced to conditional propositions.$(p \Rightarrow q)\;$ The truth table for $p \Rightarrow q$ is this: ...
4
votes
3answers
530 views

Expected Value of Local Maxima and Local Minima

Recently I came across this question: Given a random permutation of integers 1, 2, 3, …, n with a discrete, uniform distribution, find the expected number of local maxima. (A number is a local maxima ...
-6
votes
0answers
26 views
1
vote
2answers
49 views

Runs of white balls in sampling without replacement

There are $m$ white balls and $n$ black balls in a box. Balls are randomly drawn from the box with no return. Denote $X_1$ : number of white balls that been drawn before the first black. For $2 \leq i ...
2
votes
2answers
59 views

Order of statements in implication

The question is from Exercise 13 of part 1.4 in Rosen's "Discrete Mathematics and Its Applications" (5th edition): "let $M(x,y)$ be "$x$ has sent y an e-mail message", where the universe of discourse ...
-4
votes
2answers
51 views

rearranging the digits of 7524693 [on hold]

In the number 7524693, how many digits will be as far away from the beginning of the number if arranged in ascending order as they are in the number?
-1
votes
1answer
48 views

Bijective correspondence between $X$ and $X \cup \{a\}$ for an infinite set $X$ [on hold]

Let $X$ be an infinite set, and $a\notin X$. I need to prove that $|X \cup \{a\}| = |X|$. Preferably using bijective correspondence or Schröder–Bernstein theorem. Thank you.
1
vote
4answers
47 views

Discrete Maths Set Theory: Prove that $\left|(X^Y)^ Z\right|=\left|X ^{Y \times Z}\right|$.

I need to prove that $(X^Y)^ Z$ and $X ^{Y \times Z}$ are in bijective correspondence. Can anyone please help? EDIT: Chuks's version said: prove that $(X\times Y)\times Z\sim X\times(Y\times Z)$. ...
2
votes
2answers
78 views

Fill $8$ boxes with $60$ items

I have $8$ boxes and $60$ items: how many ways can I fill the boxes so that The order of the items in each box does not matter It does not matter which boxes are filled with which items. In other ...
0
votes
1answer
81 views

Permutation question in discrete mathematics. At least 1 out 3 members (P) from a total of 10 members

Im doing a question out of Discrete and Combinatorial mathematics by Grimaldi (4th Edition). I'm stuck on one of the questions and am trying to find an alternative way of doing it, that is not in the ...
0
votes
0answers
15 views

DFT of subdomain of periodic domain

$f(t_i,x_j)$ is a solution of stochastic differential equation on grid. $j=[0,N+1]$, $i=[0,\infty]$ and boundary conditions are periodic: $f(t_i,x_0) = f(t_i,x_N)$ and $f(t_i,x_{N+1}) = f(t_i,x_1)$ ...
1
vote
1answer
15 views

Recurrence Relations for Sequence Counting Hamming Weights

Define $a(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=0, ||x||=k\}|$ and $b(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=1, ||x||=k\}|$ where $||\cdot||$ denotes the Hamming weight of $x$ (i.e. number of non-zero ...
3
votes
2answers
61 views

Finding how many bits of length n there are

So we are starting on the section of combinatorics in my discrete math class and our instructor gave us a simple problem to see if we understood what we learned that day. The problem consists of three ...
-1
votes
1answer
68 views

What is the inverse function of gcd? [on hold]

Let $a,x,c \in\mathbb{Z}$. If $\gcd(a,x)=c$ where $a, c$ are constants and $x$ is a variable, then what values can $x$ take and how to find those values ?
4
votes
3answers
47 views

Discrete math - Set theory - Symmetric difference: Proof for a given number.

I can't find anything on this topic elsewhere. I'd like to know what keywords/sites I should be using to find what I'm looking for if this is to elementry of a question. (been using discrete math, set ...
-4
votes
2answers
41 views

License Plate problem [on hold]

A license plate contains 7 characters (order matters). Each character may either be an upper-case letter A–Z or a number 0–9. How many license plates. . . (a) contain the string ABC? (b) have at ...
-1
votes
1answer
106 views

Injections, Surjections, Bijections [on hold]

So i was given a question that asks me to determine whether the function is injective, bijective, or surjective. If you answer bijective than determine the functions inverse, domain, and target space. ...
1
vote
5answers
58 views

Proving that that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$

How might I prove that ${(R \setminus S)\setminus T} \subseteq R \setminus (S \setminus T)$? I am not sure the best place to start other than assuming $x\in(R \setminus S)\setminus T$ and trying to ...
0
votes
0answers
22 views

Asymptotical stability of a discrete dynamical system

There is a linear time invariant discrete system, \begin{align} x_{k+1}&=\tilde{A}x_k, \end{align} where $\tilde{A}$ is a block matrix represented by \begin{align} \tilde{A}= ...
2
votes
2answers
248 views

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side?

In how many ways can eight people, denoted $A,B,C,D,E,F,G,H$ be seated about a square table that seats two people on each side? My approach: Since each side of the table seats two people, there are ...
0
votes
1answer
76 views

Find the number of flags of different types using induction

A flagpole is $n$ feet tall. On this pole we display flags of the following types: red flags that are $1$ foot tall, blue flags that are $2$ feet tall, and green flags that are $2$ feet ...
0
votes
2answers
1k views

What is the purpose of implication in discrete mathematics?

I would be obliged if you can show me an example of a truth table for implication where there is a also a real life aspect to it. (i.e., where would someone use the scenario to make F->F = T and also ...
3
votes
4answers
117 views

Proving that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even.

Here is the proof: Let $a,b \in \mathbb{Z}$. Prove that if $a+b$ and $ab$ are of the same parity, then $a$ and $b$ are even. When working these problems, I do try to set them up logically. My ...
0
votes
0answers
21 views

Repertoire method in solving recurrence [duplicate]

I don't know, how should I start solving this: $$a_1 = 2 \\ a_n = 2a_{n-1} +7$$ using the repertoire method. Could anyone give me an algorithm or explain, how to use this method in this case?
3
votes
1answer
469 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
0
votes
3answers
29 views

Proving $a=b \bmod 19$ is an equivalence relation

My question is: $a \equiv b \bmod {19} \iff aRb$ (prove that $R$ is an equivalence relation) Before that, I already know that equivalence relation is when $R$ is reflexive, symmetric and ...
-1
votes
0answers
70 views

Determine whether it is injective, surjective, bijective or neither injective nor surjective [closed]

The question i was given asked (a) Determine whether it is injective, surjective, bijective or neither injective nor surjective. (b) If you answered "bijective" in part (a) determine the ...
1
vote
1answer
51 views

Inviting 4 friends out of 8 for a week such that each friend visits at least once

Dave is inviting 4 friends out of 8 for a week how many possibilities there are such that each friend visit at least once. Let's number the friends for brevity, 1 to 8. This is like asking how ...
40
votes
8answers
41k views

What is the best book for studying discrete mathematics?

As a programmer, mathematics is important basic knowledge to study some topics, especially Algorithms. Many websites, and my fellows suggest me to study Discrete Mathematics before going to ...
0
votes
0answers
29 views

Application of Havel- Hakami Theorem [closed]

Definition :Given a sequence $d_1 \geq d_2 \geq \cdots \geq d_n$ called graphical if it is degree of a possible graph. need a proof of the question below. Question : The above sequence is graphical ...
0
votes
1answer
25 views

defining a sequence of numbers L n≥1, and prove something about it

So i was given this question just to try for practice to test our knowledge and i'm really confused on how to go about this question. How should i go about this question, i'm confused with the greek ...
-4
votes
0answers
46 views

prove that for any 2n≥2 and any \a ​1 ​​ ,…,a ​n ​​ ∈N, we have the following: [closed]

So the question I was given goes like this we will introduce a mystery function,P:N→N. We don't know a formula for P (and we won't be able to determine one!) but we do know that P satisfies the ...
2
votes
3answers
74 views

Proving $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$ using strong induction

The question says $10\cdot n=0$ for all $n\in\mathbb{Z}$ with $n\geq 0$. Here is my proof by strong induction: Base case: $10\cdot0=0$. Let $k\geq 0$, and suppose that for any $m\leq k$ we have ...
1
vote
3answers
204 views

Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$ a) Find $a_2,a_3,a_4,a_5$ b) Find a closed form-formula for $a_n$ I found the value to be ...
3
votes
3answers
4k views

How many distinct ways to climb stairs in 1 or 2 steps at a time?

I came across an interesting puzzle: You are climbing a stair case. It takes $n$ steps to reach to the top. Each time you can either climb $1$ or $2$ steps. In how many distinct ways can you ...
0
votes
0answers
26 views

Is there a theory for cellular automata propagating signals in straight lines?

Is there a theory explaining how a cellular automata can propagate signals in straight lines? For example, this video shows how some "signals" travel down at a diagonal, even though they are composed ...
3
votes
2answers
41 views

number of triangles determined by a rectangular grid

Suppose we are given an $m\times n$ rectangular grid of lattice points, such as $S=\{(k,l): 0\le k\le n-1,\; 0\le l\le m-1, \;k,l\in\mathbb{Z}\}$, and we want to determine the number of ...
-2
votes
1answer
22 views

Determine the number of strings that can be formed by ordering the letters given. [closed]

How many strings can be formed by ordering the letters SALESPERSONS if the four S's are consecutive?
0
votes
1answer
47 views

consider a graph of a gameboard

Consider a graph of a game board. Rounds in the game result in a token moved from a game board location to a game board location, possibly returning to the same one. Let the game board location at the ...
0
votes
0answers
29 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
0
votes
1answer
44 views

Compose $(1243)$ and $(5)$

Checking my work. In either direction: $(1243)[1] = 2$ and $(5)[2] = 2$, so far we have $(1, 2,\ldots$ $(1243)[2] = 4$ and $(5)[4] = 4$, so far we have $(1, 2, 4,\ldots$ $(1243)[4] = 3$ and ...
1
vote
1answer
100 views

Minimization of a combinatorial function

The following gamma function depends on the overall sum of $x_n,x_j,x_k$ $$\gamma(X)=\sum_{x_n+x_j+x_k=X}\left [ \left ( \prod_{i=1}^{s}(x_{ni}-1)!C_i^{x_{ni}} \right )\times ...