Explore BrainMass
Share

# Combinatorics

Combinatorics is a sub-discipline of Algebra which is concerned with the study of combination, enumeration and permutation of sets of elements. One of the main aspects of combinatorics is the study of combinatorial structures found in an algebraic context. It draws on principles from Group Theory and Representation Theory.

Representation Theory is the study of abstract algebraic structures. It aims to represent their elements in the form of linear transformations of vector spaces; in essence, representation makes an abstract mathematical concept more concrete. Thus, it can be seen that this particular theory is especially prominent in the study of Combinatorics – as it hints at the appearance of enumerative methods in the area of algebraic geometry.

Algebraic Combinatorial problems are not limited to the discipline of algebra, but rather they can extend into the realm of probability, geometry and topology. In fact, this study can go even further, as it has many applications in the fields of optimization, computer science and physics. Thus, understanding Combinatorics is crucial for the study of Algebra as well as other disciplines which examines combination, enumeration and permutation.

### Logic and counting problems

1. Each of the following people is either lying or telling the truth: Aisha: If Bian is telling the truth, then Chang is lying. Bian: If Chang is telling the truth, then so is Diego. Chang: If Diego is lying, then Aisha is lying too. Diego: Aisha is lying. Determine all possible combinations of which people ar

### Challenge problems in combinatorics theory

1) For this problem you have flags, which are distinct, and flagpoles, which are also distinct. The flags are placed on the flagpole in an order, so that if a red flag is on top of a blue flag, that's different than a blue flag being on top of a red flag. Assume the flagpoles are tall enough to hold all the flags. a. List

### Challenge problems based on combinatorics theory.

Solve the following challenge problems based on combinatorics theory - partitions and ordered and unordered arrangements. See the attached file for the formatted equations/notations. 1) Natural Number Partitions (do parts a and b): When we are counting surjective functions and both the n balls and the x boxes are indistinct

### Democrats and Republicans on Task Force

A certain city has experienced a relatively rapid increase in traffic congestion in recent times. The mayor has decided that it's time to do something about the problem and decides to form a task force to research the causes of the problem and come up with suggestions for dealing with it. The mayor first compiles a list of names

### Permutations self study

2) The National association of college and university business officers researched the change in university and college endowments from 2007 to 2008.The table below shows the findings of 203 colleges and universities with 2008 endowment levels above 300 million dollar . It indicates how many schools with an endowment level had t

### Gaussian Elimination Count

Please help with solving the following question regarding Gaussian eliminations to a system. The system [see the attachment for the matrix and equation] Where a_ij = 0 whenever i-j >= 2 Do an operation count of MD (Multiplications/Division) and AS (Addition/Subtraction) when using Gaussian elimination to solve the syst

### Generalized Computations and Permutations

How many strings with five or more characters can be formed from the letters in SEERESS?

### Upper bounds on states in the game of chess.

A step by step analysis is given for the following questions, 1. Find an upper bound for the number of possible states in the game of chess, assuming that draw-by-repetition is enforced if the same position is repeated three times. 2. Find an upper bound for the number of possible moves in a single turn in the game of ches

### Combinations and Different Ways for Statistical Measurement

I have attempted part of this practice exercise in the text, but I need help in understanding the rest of it. I thought maybe another perspective would enlighten me. Thanks! There are 7 women and 9 men on a faculty. a.) How many ways are there to select a committee of 5 members if at least 1 member must be a woman? b.) How

### Computations and permutations

How many bit strings of length 10 have a) exactly three 0s? b) more 0s than 1s? c) at least seven 1s? d) at least three 1s?

### Basic Permutation Example

Please help with the following combinatorics problems. Sarah, Jolly and Betty are female triplets. They and their 10 cousins are posing for a series of photographs. One pose involves all 13 children. How many ways can the 7 boys and 6 girls be arranged in one row under each of the following conditions? a) The boys and gir

### Combinations and Permutations Problem Set

Question 1: From a total of 15 people, three committees consisting of 3, 4, and 5 people, respectively, are to be chosen. b) How many such sets of committees are possible if there is no restriction on the number of committees on which a person may serve? Question 2: c) In how many ways can we select a set of five micro

### Positive Integer Counting

How many positive integers between 1000 and 9999 inclusive... a) are divisible by 9? b) are even? c) have distinct digits? d) are not divisible by 3? e) are divisible by 5 or 7? f) are not divisible by either 5 or 7? g) are divisible by 5 but not by 7? h) are divisible by 5 and 7?

### Fundamental Mathematics Sample Problems

May I please have step-by-step workings for all attached problems?

### Sets: Definitions and Examples

Explain and give examples for the following: - Equivalent sets vs. Equal sets - Cardinality of sets and how cardinality relates to the number of subsets of a set - Subset vs. Proper Subset - Complement of a set vs. Complement of a universal set.

### Permutations and Combinations-Single Row, Multiple Row Problems

I am studying perms and combs on my own for a course which i want to take in the future. I have come across 2 questions, to which I need a solution. I would also need the reasoning applied to the solution for future application. Here are the 2 questions. Question 1. How many ways can 18 different vehicles be arranged in a c

### Operations/Proofs with Sets

Please show these proofs in great detail with all steps explained as they will serve as a template for future proofs. 1. Suppose A, B, and C are sets with A?B?C = 0. Prove or disprove: |AUBUC|= |A|+|B|+|C|. 2. Suppose A, B, and C are sets. Prove or disprove: AUB= A?B if and only if A=B.

### Combinations: Selecting members of committee

A club has 28 members, and 6 members must be selected to make a committee. a) Of the 28 members, 15 are men and the rest are women. How many ways can the 6 member committee can be selected if there are to be 4 men and 2 women on the committee? b) How many different ways can the committee be selected if one person must be the

### Discrete Math Counting

How many permutations of the letters ABCDEFGH contain a. the string ED? b. the string CDE? c. the strings BA and FGH? d. the strings AB, DE and GH? e. the strings CAB and BED? f. the strings BCA and ABF? How many ways are there for eight men and five women to stand in a line so that no two women stand next to each other

### Dealing cards, counting bagels, permutations of a string

How many ways are there to deal hands of seven cards to each of five players from a standard deck of 52 cards? A bagel show has onion, poppy seed, egg, salty, pumpernickel, sesame seed, raisin, and plain bagels. How many ways are there to choose: a) six bagels? b) a dozen bagels? c) two dozen bagels? d) a dozen bagels wi

### Permutations in Probability

There are 10 workers and 2 administrators in a company meeting room. Two people will be selected at random without replacement. The chance that the second person is a worker is: a. none of these b. 15/66 c. 5/6 d. 5/33 e. 10/11

### Truth Tables of Seven Teachers and Three Children

1) How would you disprove this statement? [P and Q] => [P and R] 2) How many multiples of 4 are there in {n; 37< n <1001} ? 3) Seven teachers and three children are to stand in line for a photo session. a) How many arrangements are there? b) How many arrangements are there if only any 4 teachers and no children are in th

### Discrete math lists: MP3 player playlist, photos, rooks

I want to create two play lists on my MP3 player from my collection of 500 songs. One playlist is titled "Exercise" for listening in the gym and the other is titled "Relaxing" for leisure time at home. I want 20 different songs on each of these lists. In how many ways can I load songs onto my MP3 player if I allow a song to

### Basics of Counting

The name of a variable in the C programming language is a string that can contain uppercase letters, lowercase letters, digits, or underscores. Further, the first character in the string must be a letter, either uppercase or lowercase, or an underscore. If the name of a variable is determined by its first eight characters, how m

### Distinguishable Permutations of Letters in a Word

Find the number of distinguishable permutations of the letters in each word a. initial b. little c. decreed.

### Cryptography in RSA

1. Prove that the RSA Cryptosystem is insecure against a chosen ciphertext attack: Given a ciphertext y, describe how to choose a ciphertext y(hat)≠y such that the knowledge of the plaintext x(hat)=d_k (y(hat)) allows you to compute x=d_k (y). Hint: First prove that in the RSA Cryptosystem ,e_k (x_1 ) e_k (x_2 )modn=e_k

### Permutations and Combinations Results

For each of the following, express your results in two ways: 1st, using the nPr or nCr notation, whichever is appropriate; 2nd, giving the numerical value: a) The number of permutations of 8 objects taken 3 at a time b) The number of combinations of 7 objects taken 5 at a time

### find total number of combination

My favorite Moroccan restaurant offers the following menu: Cold appetizer (no choice): spicy carrots, khobiza, and zalouk Appetizer (select one): spicy chicken wings, charmoula chicken drumsticks, maaquda, shrimp maaquda, or lamb borek Entree (select two): free range chicken, baked kefta, or shekshouka Dessert (no choice):

### Cardinality, countability

2-12 through 2-14. Exercise 2-12. Consider the integers in the arrangement 0, 1, -1, 2, -2, 3, -3, ... Let n E N. Which integer occupies the 2n position? The 2n+ 1 position? Prove that I and N can be put into one-to-one correspondence. From Exercise 2-12, I has N0 integers. As we have seen, adding one new members to a cou

### Counting the number of different teams

A group of high school students is preparing to compete with groups from other schools on a TV show in which questions about various academic subjects are asked of the contestants. There are seven boys and five girls in the group. Every time this school is represented on the show, a team of three students participates. How many