Discrete math Definition and 214 Threads

Discrete Mathematics is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications. It was established in 1971 and is published by North-Holland Publishing Company. It publishes both short notes, full length contributions, as well as survey articles. In addition, the journal publishes a number of special issues each year dedicated to a particular topic. Although originally it published articles in French and German, it now allows only English language articles. The editor-in-chief is Douglas West (University of Illinois, Urbana).

View More On Wikipedia.org
Recent contents Top users
  1. Shackleford

    Can Rational and Irrational Numbers Multiply to Yield an Irrational Product?

    The book works out the case with x and y irrational and xy rational. They used the nonconstructive existence proof method with x = sqrt(2) and y = sqrt(2). If that's rational, then you're finished. If it's irrational, then you can simply raise it to the power of sqrt(2) to get 2. I'm not sure...
  2. Shackleford

    Discrete Math: Is R Necessary for Q?

    "For the router to support the new address space it is necessary that the latest software release be installed." I said Q: The latest software released be installed R: The router to support the new address space. I interpreted this as Q is necessary for R, therefore R => Q. The professor has...
  3. N

    Confused on how to do a simple discrete math problem

    Homework Statement Use the equivalence p\rightarrow(r \rightarrow s) \equiv p\wedge r\rightarrow s to rewrite the following problem before the proof. Homework Equations [p\rightarrow (q\rightarrow r)]\wedge (p\rightarrow q) \tautologicallyimplies (p\rightarrow r) The Attempt at a...
  4. D

    What is an indirect proof for the theorem: If n^2+1 is odd, then n is even?

    Here's the problem. Theorem: If n^2+1 is odd, then n is even. Give indirect proof.
  5. D

    Schools Going to CS grad school for Algebra or Number theory problems in Discrete Math

    I am currently a CS undergrad. my university offers no courses in Abstract algebra or Number theory or Topology or Analysis. recently I have got interested in Number theory in Discrete math course. moreover I was and still am interested in algebra too. but the problem is, can I apply to CS grad...
  6. H

    How can induction be used to prove a sum of cubes formula?

    Hi guys, Long time lurker of this forum, but first time poster. Discrete Math is going to be the end of me; I'm just not understanding how to solve problems and write the proofs. Any help would be greatly appreciated. Thanks in advance. The Problem: Let nεZ≥1. Show that...
  7. F

    Discrete Math: Functions with Powers

    Did this as a homework problem, got it wrong obviously. Not too sure how to solve it otherwise Homework Statement Let f be a function from A to A. Prove that for all m,n ε N, f^m*f^n = f^(m+N) Homework Equations The Attempt at a Solution f^(m+1) f^(n+1) = f(f^m) * f(f^n) =...
  8. S

    Discrete Math: Self-referential formula

    Homework Statement Figure out a self-referential formula for the number of handshakes required for a group of n aliens to introduce themselves by hand-calculating a few small values and coming up with a solution. Homework Equations We are given: Let H(n) be the number of handshakes...
  9. S

    Discrete Math: Proof by contradiction

    Homework Statement Using contradiction, prove that for every four positive real numbers c, d, e and f, at least one of c, d, e, f is greater than or equal to the average of c, d, e, f. Homework Equations I don't believe that there are any relevant equations for this problem. I do know that...
  10. D

    Discrete math - Infinite sets having the same cardinality.

    From a pdf textbook: Example (infinite sets having the same cardinality). Let f : (0, 1) → (1,∞) be defined by f(x) = 1/x. Then f is a 1-1 correspondence. (Exercise: prove it.) Therefore, |(0, 1)| = |(1,∞)|. Exercise. Show that |(0,∞)| = |(1,∞)| = |(0, 1)|. Use this result and the fact that (0,∞)...
  11. A

    Discrete Math- Irrational numbers, proof or counterexample

    Homework Statement Determine if the statement is true or false. Prove those that are true and give a counterexample for those that are false. If r is any rational number and if s is any irrational number, then r/s is irrational. Homework Equations A rational number is equal to the...
  12. A

    Discrete Math irrational and rational numbers proof

    Homework Statement Prove by contradiction. Your proof should be based only on properties of the integers, simple algebra, and the definition of rational and irrational. If a and b are rational numbers, b does not equal 0, and r is an irrational number, then a+br is irrational. Homework...
  13. C

    Help with a proof in my discrete math summer class

    Homework Statement Let A be the set of all integers x such that x is = k2 for some integer k Let B be the set of all integers x such that the square root of x, SQRT(x), is an integer Give a formal proof that A = B. Remember you must prove two things: (1) if x is in A, then x is in B, AND...
  14. C

    How Many Positive Divisors for 2^n and 30? | Discrete Math Question

    Homework Statement How many positive divisors does each of the following have? 2^n where n is a positive integer. and 30 The Attempt at a Solution for 30 i get 2 , 5 , 3 , 10 but my book says 2 ,3 ,5 I don't understand why 10 isn't a divisor. and for 2^n I am trying...
  15. A

    Discrete math - proof of divisibility question

    1. For any integer n, prove that 3 divides n^3 -n The Attempt at a Solution I'm stuck. I understand that means that n^3 -n mod 3 =0. or I can n^3 -n can be expressed as 3x. But I don't know how to prove it. Where do i go from here. Thanks
  16. P

    How Can I Correctly Apply Induction to Solve My Discrete Math Homework?

    Homework Statement Homework Equations I need to prove this by using induction. I need help with the induction step. The Attempt at a Solution. Basis step: let n=0; 2^0 = 2^(0+1) - 1 -----> 1=1
  17. X

    Understanding Relations, GCD, and LCM in Discrete Math

    Homework Statement Define the relation a I b ( a divides b) between integers a and b and then define the greatest common divisor, gcd ( a,b), and the lowest common multiple, lcm ( a,b) Is there any number for m for which you have n I m ( n divides by m) for every n. I just found this...
  18. Lolligirl

    Discrete Math: Proving Injectivity/Surjectivity of g°f

    1. Show by example that it is possible for g°f(x) to be surjective while f(x) is not I am confused by the general pattern of injectivity (one-to-one) and surjectivity (onto). I know the following by looking through my book: If f and g are surjective, then g°f is surjective. If f is...
  19. E

    Solve the Congruence (Discrete Math)

    Homework Statement Solve the congruence 2x≡7 (mod 17) Homework Equations None. The Attempt at a Solution I think my main problem with this is I am still confused on what modulo actually means. But I'll save that for some other time. So here is what I have done so far. I...
  20. V

    Discrete Math: Is "Next Year Interest Rates Will Rise" a Statement?

    Homework Statement Is the following a statement: "Next year interest rates will rise" Homework Equations Sort of obvious, but a statement is defined as something which is true or false. The Attempt at a Solution I'm guessing that it is a statement, even if it isn't known whether it...
  21. P

    Discrete Math: Binary Relations

    Homework Statement A = {0, 1, 2, 3, 4 ,5} Let R be a binary relation on set A such that: R = {(0,1), (1,0), (1,3), (2,2), 2,1), 2,5), (4,4)} a. Make a Directed Graph for the relation R on A b. What must be added to R to make it reflexive/symmetric?
  22. I

    How can you prove this discrete math induction statement?

    Homework Statement Homework Equations base case: n=1 The Attempt at a Solution im not sure where to start because the examples that my professor showed us did not have a n(n-1) (n+1) but rather (p+1)P=1+1)(2(p+1)+1) im just very lost in this example
  23. C

    How Can You Prove the Triangle Inequality Using Case Analysis in Discrete Math?

    Discrete Math -- Proof methods Homework Statement Prove |x-y| ≤ |x| + |y| for all real numbers x and y (where |x| represents the absolute value of x, which equals x if x≥0 and equals -x if x<0). prove by cases Homework Equations The Attempt at a Solution
  24. Z

    Proving Existence of a Survivor in a Discrete Math Problem | Odd n Case

    Homework Statement Suppose n > 1 people are positioned in a feld, so that each has a unique nearest neighbour. Suppose further that each person has a ball that is thrown at the nearest neighbour. A survivor is a person that is not hit by a ball. Prove that if n is odd, then there is at least...
  25. C

    Discrete Math: Subsets and Venn Diagrams Explanation

    Homework Statement Let their be a set A, and let B be the set: {A, {A}} (the set containing the elements A and the set that contains element A) As you know, A is an element of B and {A} is also an element of B. Also, {A} is a subset of B and {{A}} is also a subset of B. However...
  26. F

    MATLAB Discrete Math vs MATLab for Physics: Which is Better?

    Which one is a better course to take? I feel like MATLab is simple enough I can learn on my own if I ever need it. How useful is discrete math in physics? Should I take that now or stick to MATLab?
  27. M

    I got a C in discrete math My life is over

    I think I've screwed up my future. I am in my third year, double major in physics and math (math major more to supplement my understanding of physics), and this semester was just horrid. I made the mistake of moving off campus, working two jobs, and in the time I had to study, could not focus...
  28. C

    Discrete Math: Number Segments and Common Parts | Homework Problem

    Homework Statement The statement that S is a number segment means that there are numbers a and b and S is the set to which x belongs only in case x is a number between a and b.Problem 1) If each S1 and S2 is a number segment and there is a number common to S1 and S2 then is the common part a...
  29. S

    Discrete math - links to biology?

    Discrete math -- links to biology? Hey, I'm in a math and biology program in college and I've recently become more and more into the discrete side of math. I was wondering if anybody knew of any areas of research that integrate discrete mathematics and biology, as there doesn't seem to be...
  30. G

    Discrete Math Problem : Mathematical Induction

    Homework Statement Prove that H1 +H2 +...+Hn = (n +1)(Hn-n)? Homework Equations Hn denotes the nth harmonic number. The nth harmonic number is the sum of 1+1/2+...1/n, which is n / n +1. I'm not really sure if Hn = (1/ n) . Prove by Mathematical Induction Hn denotes the...
  31. G

    Mathenatucak Induction Problems in discrete math

    Homework Statement Prove that 3 divides n3 + 2n whenever n is a positive integer. Homework Equations The Attempt at a Solution Basis Step : P(1) : [13 + 2(1) ] /3 [1+2] /3 [3]/3 1 Since 3/3 =1, P(1) is true Inductive Step: [ k3 + 2k...
  32. S

    Proving a Discrete math problem

    Another one of my homework asks is this true or false and prove it: For all sets A, B, and C if A U C is a subset of B U C then A is a subset of B Please help!
  33. S

    Discrete Math Problem: Proving Subset Relationships in Sets A, B, and C

    One of my homework problems says is this true or false and prove your answer: For all sets A, B, C if A n C is a subset of B n C then A is a subset of B. I believe the answer is true but i have no idea please help!
  34. M

    Help Max Get Started on a Discrete Math Proof for Sum of Consecutive Integers

    I'm completely stumped on how to begin a discrete math proof, and I'm looking for a little advice on what might be a good way to approach this. In a previous problem I did a proof by contradiction to show that at least one of the real numbers a1, a2, ... an is greater than or equal to the...
  35. W

    Discrete Math - equivalence laws

    I need to show that P<->Q is logically equivalent to ( P ^ Q ) v ( ~P ^ ~Q) So far I have P <-> Q is equivalent to ( ~P v Q ) ^ ( ~Q v P ) by a example I have no idea where to go from here
  36. C

    Proper Subsets in Discrete Math

    Discrete Math "Proper Subsets" Hey everyone, I am confused on part of this. Any input would be much appreciated! X has ten members. How many members does ~P(X) have? (~P is the set of all subsets) How many proper subsets does X have? Well the number of members of ~P is 2^10 or 1024...
  37. H

    Discrete math problem: R.P. Grimaldi text

    Homework Statement Okay so I'm trying to teach myself the first three chapters if Grimaldi before I take a discrete math course in January. I'll probably be posting a few problems. The question is as follows: In how many ways can we select n objects from a collection of size 2n that...
  38. X

    Discrete Math - question about sets

    1. Homework Statement Use set builder notation to give a description of each of these sets. a) { 0,3,6,9,12 } b) { -3, -2, -1,0, 1, 2, 3 } c) { m,n,o,p } 3. The Attempt at a Solution X={x l x is an odd possitive multiplier of 3 less than 12 } X is supposed...
  39. D

    Pure Mathematics vs. Applied Math vs. Discrete Math

    "Pure" Mathematics vs. Applied Math vs. Discrete Math I'm approaching the point where I'm going to have to decide which four-year university I'm going to finish my Bachelor's degree at. I'm pretty much restricted to colleges in Georgia, and I am primarily looking at Georgia State and Georgia...
  40. M

    How is Discrete Math Used in Physics?

    Anybody know of any uses of discrete math in physics? I learned proof by induction in discrete math. Is that used to prove anything in physics? Any other examples that you can think of?
  41. James889

    Discrete math, defining an operator

    Hi, I have some troubles with this question. Define an operator * on R by x*y = 2xy -x -y +1 a) is * commutative? b) is * associative? I can easily see that * is commutative, but how do i test for associativity? The rule states that (x*y)*z = x*(y*z) But what is z ?
  42. J

    Discrete Math: Distributing 11 Cookies to 50 Children - Efficient Solution?

    Homework Statement If I want to know how many ways there are to distribute 11 chocolate chip cookies to 50 children, is there any way to do this without brute force? Homework Equations The Attempt at a Solution
  43. B

    Finding Pairs of Integers with GCD 14 and LCM 168 | Discrete Math Homework

    Homework Statement Find all pairs of integers a, b such that their GCD and LCM are 14 and 168 respectively. Homework Equations a x b = gcd(a,b) x lcm(a,b) (useful?) The Attempt at a Solution confused...
  44. B

    What is the Remainder of Dividing 2(562009)-3?

    Homework Statement Find the remainder of dividing 2(562009)-3. Homework Equations Let m be a positive integer. If a\equivb (mod m) and c\equivd (mod m), then a + c \equiv b + d (mod m) and ac\equivbd (mod m). The Attempt at a Solution Using ac\equivbd (mod m): (2 mod...
  45. K

    Why Are Discrete Math and Statistics Approaches Giving Different Probabilities?

    In statistics I learned how to do this problem one way, & in discrete mathematics I learned how to do it another way, but the answers don't jive. So I'm wondering if I'm doing something wrong. Below is the question. A bakery produces six different kinds of pastry. If the different kinds of...
  46. T

    Some Discrete Math Help, Im Exhausted

    Homework Statement Suppose that we play the following game. You are given a pile of N matches. You break the pile into two smaller piles of m and n matches. Then you form the product 2mn and remember it. Next, you take one of the piles and break it into two smaller piles (if possible), say of...
  47. T

    Can you prove or disprove (mn)!=m!n! for positive integers m and n?

    If m and n are positive integers, (mn)!=m!n! Prove or disprove. its so obviously true i can't prove it. anyone help? -also- Prove: The square root of a prime integer is an irrational number. any help?
  48. D

    Is x Necessarily Rational If It Satisfies (ax+b)/(cx+d)=1?

    Suppose a,b,c,d are integers and a DOES NOT equal c. Suppose that x is a real number that satisfies the equation: (ax+b)/(cx+d)=1 Must x be rational? If so, express x as a ratio of two integers. I have no idea how to begin this problem.
  49. S

    The Expectation of X and the Expectation of X squared (discrete math)

    Homework Statement prove or disprove that E[X^2] = E(X)^2 Homework Equations E[X] = \sumxi*pr(xi) The Attempt at a Solution I really don't know where to start, I believe that it is not true, so I should try to disprove it, and the easiest way to do that would be by...
  50. S

    Card Hand probabilities: Discrete Math

    Homework Statement In the following you are given a 5-card hand from a 52 card deck. a) given that you have at least one ace, what is the probability you have at least 2 aces? b) given that you have the ace of diamonds, what is the probability that you have another ace? c) given that you...
Back
Top