Questions tagged [discrete-mathematics]

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

28 questions
Filter by
Sorted by
Tagged with
12k views

Counting binary trees

(I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.) Looking at Wikipedia page for Binary Trees, I've noticed this ...
138 views

567 views

How to check if a specific ILP problem can be solved in polynomial time or not?

How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?
4k views

Average height of a BST with n Nodes

I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My ...
60 views

Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]

I'm pracitcing exams towards finals, Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$. Prove : for every 2 ...
716 views

How to prove with induction [duplicate]

So far I have learned how to write proofs by induction and it went fine until I got this recursive problem, which I'm not quite sure how to begin and how to prove that with induction. ...
2k views

Calculating Binet's formula for Fibonacci numbers with arbitrary precision

Binet's formula for the nth Fibonacci numbers is remarkable because the equation "converts" via a few arithmetic operations an irrational number $\phi$ into an integer sequence. However, using finite ...
4k views

Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?

I've been reading Sedgewick's intro to algorithms book, and he says that the reverse postorder of a digraph's reverse is not the same as the postorder of the digraph, however in both cases it seems ...