# Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

485 questions
Filter by
Sorted by
Tagged with
17 views

### Is there any upper bound for the number of ways we can partition a multiset, where each part/segment in the partition has distinct elements?

A question is asked in the below link, which asks for the number of cases we can partition a multiset, where each part/segment in the partition has distinct elements. https://math.stackexchange.com/...
• 1
23 views

### Prove there is a way to partition vertices of a simple graph into two groups so that degree of each vertex will be even in it's group induced subgraph

One of our groups can be empty Hint : we should use induction Question designer also suggested to choose one vertex first then supplement its neighbourhoods induced subgraph and then delete selected ...
32 views

### How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [duplicate]

We define the set S as {(s1, f1), (s2, f2), ..., (si, fi)}, where each si is the frequency that it is repeated in the multiset T. How many ways can we partition the multiset T into different ...
• 1
1 vote
30 views

• 19
21 views

### What Basic (pre-discrete maths course) areas to focus on - and what resources would be recommended?

To cut a long story short, I'm a mature CS student with fairly rusty maths skills, going into my second last year of my degree. I had studied maths to the sort of decent-ish high school level you'd ...
65 views

### Walk from vertex u to vertex v on complete graph, formula for number of walks of length k

Complete graph with n vertices. Walk from vertex u to vertex v of length k. I don't understand how the number of walks between the two of length k is $n^{k-1}$ I've tried this formula on an example ...
52 views

### equivalency of some facts in $O$ notation

I misunderstanding about some logarithm property in algorithm course: is it correct that we say following three term is equivalent? $O(\log a + \log b)$ $O(\log (ab))$ $O(\log (a+b))$
30 views

### Finding Sum(F(i)) where F(i) = min(⌈ Ai / B1 ⌉ * C1, ⌈ Ai / B2 ⌉ * C2, ⌈ Ai / B3 ⌉ * C3, .... ,⌈ Ai / Bm ⌉ * Cm)

Given three arrays A, B, and C of size n, m, and m respectively (1-based indexed). A function F(i) is defined as - F(i) = minimum_of(⌈ Ai / B1 ⌉ * C1 , ⌈ Ai / B2 ⌉ * C2 , ⌈ Ai / B3 ⌉ * C3 , .... , ⌈ ...
43 views

### The relationship between types of registers / feedback functions and de Bruijn sequences, and how these feedback functions are created

I have been learning about de Bruijn sequences recently, and have a decent sense what they are. There seem to be 3 or 4 primary methods for generating de Bruijn sequences: Feedback functions/...
• 1,943
1 vote
23 views

### How do you generate lots of binary de Bruijn sequences (somewhat small, such as less than 100 bits)?

I have been learning about de Bruijn sequences recently. I looked at this C library on Greedy algorithms, and took what I learned to make this JavaScript version, which tries to make as many de Bruijn ...
• 1,943
1 vote
51 views

### What is a de Bruijn sequence exactly?

I just discovered the term "de Bruijn sequence", but don't quite follow what it means exactly (or how de Bruijn is pronounced :), "brown" I guess). There are two good resources I ...
• 1,943
73 views

### Mathematical Induction vs Strong Induction

In Rosen's book Discrete Mathematics and Its Applications, 8th Edition it is mentioned that: You may be surprised that mathematical induction and strong induction are equivalent. That is, each can ...
• 337
21 views

### Can you recommend some materials on Turing Machine?

I need exercises with answers to practice building Turing machines. Books, online resources etc. Can anyone recommend something?
1 vote
81 views

### 3-colouring with a bounded amount of colors

The topic of 3-colouring is often talked about, but what happens if we limit the amount of times we can use one color? Take a graph $G=(V,E)$ with $k$ being the number of vertices, is it possible for ...
• 49
35 views

115 views

### Analytic combinatorics and less-precise running times

Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the ...
• 287
59 views

Statement Consider the following modified node structure for the linked list: struct Node { int value; Node* next; Node* random; } The ...
1k views

### Can we solve a "very" exponential recurrence?

Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ? Thanks!
• 29
1 vote
146 views

### Θ, O and Ω, and how they relate to each other as subsets

I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track. I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
1 vote
124 views

### bellman ford and one surprizing fact

I ran into a very surprising local contest problem. after finishing bellman ford algorithm, if we continue to updating distance and distance of one vertex v being updated, then v is on negative cycle....
33 views

### How to generate supersets from a finite number of subsets efficiently

Let $F$ be a set, for instance $\{a,b,c,d,e \}$. Suppose I have a set of subsets of cardinality two obtained from $F$: { a,b },$\{b,c\},${a,d} I want to create every possible set of cardinality ...
• 111
43 views

### How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?

Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one Eg. ...
• 168
129 views

1 vote
24 views

### Is $\{\emptyset,a,\epsilon\}$ an algebraic structure with respect to $+$?

Let $R = \{\emptyset,a,\epsilon\}$ (the elements here are regular expressions) and let $+$ be the or operation, which can be applied over the regular expressions of $R$. Is $(R,+)$ some kind of an ...
1 vote
Suppose that matrix A is a symmetric positive definite matrix over the integers, i.e., $A \in Z^{n\times n}$, if B is a matrix over the real numbers, it is not difficult to find B such that \$A = B \...