Explore BrainMass

Discrete Structures

Big O notation

I) Show that x^3 is O(x^4) but x^4 is not O(x^3) ii)Show that xlnx is O(x^2) but x^2 is not O(xlnx) iii)Show that a^x O(b^x) but b^x is not O(a^x) if 0 < a < b (0 = zero) iv)Show that 1^k + 2^k+...+n^k is O(n^(k+1)) for every positive integer k

Formula - Several Problems

(See attached file for full problem description with proper symbols) --- 2. Let f(x) = x2 +1 and g(x) = {x+1, x> =3; x-1, x<3 so both f and g map R into Find the formula for a. (f+g)(x) b. (f .g)(x) c. (f o g)(x) d. (g o f)(x) 3. Let A = {a,b,c,d} and B = {1,2,3} and let f : A &#61664; B be a function . Let g : Z

Discrete structures located

We worked on the attached problems today in class I am now trying to work through them again for understanding and I am not getting very far. My skills in discrete mathematics are not such that I can work through these on my own effectively. 3. Seven points are located in a plane. List the possible numbers of lines determi

Discrete Structures : Sequences, Subsequences and Remainders

1. How do I prove that in a group of n people there are two people with the same number of acquaintances within the group? 2. Prove that given a sequence of twelve integers, a1, a2, ...,a12, there is a subsequence aj, aj+1, ..., ak where 12 divides &#8721;kn= aa n. 3. A scrape of paper is found in an old desk that read:


When a pair of dice is rolled, the total will range from 2 (1,1) to 12 (6,6). It is a fact that some numbers will occur more frequently than others as the dice are rolled over and over. Why will some numbers come up more frequently than others? Each die has six sides numbered from 1 to 6. How many possible ways can a numb

Suppose that only 25% of all drivers...

48. Suppose that only 25% of all drivers come to a complete stop at an intersection having flashing red lights in all directions when no other cars are visible... (see attachment for complete question)


On the first day of math class, 20 people are present in the room. To become acquainted with one another, each person shakes hands just once with everyone else. How many handshakes take place?

Multinomial experiment, Expected Frequency

1. True or False. In a multinomial experiment, all outcomes of each trial can have several categories. 2. In finding Expected Frequency you multiply what divided by what?

Discrete Structures : Congruences

Construct addition and multiplication tables for arithmetic modulo 11. For example, 7 + 8 mod 11 is 4 and 7*8 mod 11 is 1 so the entry in row 7, column 8 would be 4 for the addition table and 1 for the multiplication table. Use your tables to solve each of the following congruences: a. 3x+2&#8801;8 (mod11) b. 3x-5&#8801;2 (m

experiment that consists of determining the type of job

16. Consider an experiment that consists of determining the type of job?either blue-collar or white-collar?and the political affiliation?Republican, Democratic, or Independent?of the 15 members of an adult soccer team. How many outcomes are (a) in the sample space; (b) in the event that at least one of the team members is a b

Application of Stirling's Formula

An often used application of Stirling's approximation is an asymptotic formula for the binomial coefficient. One can prove that for k = o(n exp3/4), (n "choose" k) ~ c(ne/k)^(k) for some appropriate constant c. Can you find the c? Can you say why this only works when k is much smaller than n exp3/4?

Double Eulerian Tour

Use words to describe the solution process. No programming. 4. Suppose G is a graph. We define a double Eulerian tour as a walk that crosses each edge of G twice in different directions and that starts and ends at the same vertex. Show that every connected graph has a double Eulerian tour.

Discrete Structures : Coloring

Let G be a properly colored graph and let us suppose that one of the colours used is red. The set of all red-coloured vertices have a special property. What is it? Graph colouring can be thought of as partitioning V(G) into subsets with this special property. (See attachment for full background)


Let G be a complete graph on n vertices. Please calculate how many spanning and induced subgroups G has... (see attachment)

Big-Oh: Context Free Grammars

Following is a big-oh relationship. Give witnesses n0 and c that can be used to prove the relationship. Choose your witnesses to be minimal, in the sense that n0 - 1 and c are not witnesses, and if d < c, then n0 and d are not witnesses. n¹º is O(3ⁿ)

Absolute Deviation with a Given Equation

Estimate the absolute deviation for the following calculation. List the result y and the absolute deviation. Round your answer so that it contains only significant digits. Y= 251(+/-1)*((860(+/-2))/(1.673(+/-0.006))= 129.025.70(+/-xxxxxx)

Subsequences Characteristic Lines

In a line of people you are looking for a subsequence of 4 (not necessarily consecutive = neighboring) people with increasing height. How many people should be in the line so that you can be sure to find this subsequence?

Trees and Rooted Binary Trees

A. If T is a rooted binary tree of height 5, then T has at most 25 leaves. b. If T is a tree with 50 vertices, the largest degree that any vertex can have is 49.

Tree Traversal.

Find the: 1. preorder transversal 2. inorder transversal 3. postorder transversal Of the tree attached in the Word document.

Dimensions for Percent Increase

We have some skylights and they measure 1.2m by 0.8m Suppose both dimensions increase by 20%. What's the percent increase in the amount of light admitted? You have a newspaper the dimensions are 35cm by 38cm they reduce the pages by 10%. There are 48 Pages in the newspaper, daily circulation of 135,000. Comp

Recursive relationship problem

Consider the recursive relationship for combinations: C(n,r) = C(n-1,r) + C(n-1,r-1) Prove this relationship algebraically using the mathematical definition of a combination, as well as that of the factorial function. Provide a logical explanation for this relationship (Hint: consider n objects as consisting of n-1 ex

Relations for Symmetric Transitive Closures

S = {0, 1, 2, 4, 6} Test the binary relations on S for reflexivity, symmetry ,antisymmetry, and transitivity. Also find the reflexive, symmetric and transitive closure of each relations. A) P = {(0,0), (1,1), (2,2), (4,4), (6,6), (0,1), (1,2), (2,4), (4,6) } B) P {(0,1), (1,0), (2,4), (4,2), (4,6), (6,4)} C) P ((0