Combinatorics Definition and 421 Threads

Homework Statement How is the number of subsets of an n-element set related to the number of subsets of an (n-1) element set? Prove that you are correct. Homework Equations The Attempt at a Solution So, clearly the the number of subsets in an n element set is 2^{n}. So the number...

I am trying to find a way to calculate the number of positive integers less than n such that these numbers are not divisible by the prime numbers 2,3,5,7,11,13. If the problem were instead for prime numbers 2,3,5, then the solution is fairly simple. I used principle of inclusion and exclusion...

given a chain of n terms with each term either being x or y, how many arrangements are there such that you don't have any two terms being x next to each other. for example if n= 5 (x,y,y,y,x) ; (x,y,x,y,x) are acceptable while (y,x,x,y,x) is not acceptable. Generalize this result for...

Homework Statement Find the number of ways to place 8 toys amongst 4 children where 1 child gets at least two toys. Homework Equations (x^2/2! + x^3/3! + x^4/4! +...) = ex-1-x (1 + x + x^2/2! + x^3/3! +...)3 = e3x The Attempt at a Solution [(x^2/2! + x^3/3! + x^4/4! +...) =...

Homework Statement Show with generating functions that every positive integer can be written as a unique power of 2. Homework Equations The generating function for ar, the number of ways to write an integer r as a sum of distinct powers of 2 = g(x) = (1 + x)(1 + x^2)(1 + x^4)(1 +...

1. In how many ways can three aces and two kings be drawn? 2. There are 24 ways three aces can be drawn and there are 12 ways two kings can be drawn. 3. I tried 24x12=288 ways to get three aces and two kings.. people are telling me that it is wrong, but I am not understanding why

Homework Statement Find the coefficient of x^36 in (x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)^6 Homework Equations 1/(1-x) = 1 + x + x^2 +... (where +... indicates an infinite series). (1 - x^(m+1)/(1-x)) = 1+x+x^2+...+x^m (I'll call this identity 'TWEAK') The Attempt at a...

Homework Statement A national singing contest has 5 distinct entrants from each state. Use a generating function for modeling the number of ways to pick 20 semifinalists if: a) There is at most 1 person from each state b) There are at most 3 people from each state. Homework...

Homework Statement Each of ten employees brings one distinct present to an office party. Each present is given to a randomly selected employee by Santa, and any employee can get more than one present. What is the probability that at least two employees receive no presents? Homework...

Homework Statement a) How many arrangements of the letters in COMBINATORICS have no consecutive vowels? b) In how many of the arrangements in part (a) do the vowels appear in alphabetical order? Homework Equations C(n,k) P(n,k) The Attempt at a Solution a) First I divided up...

Homework Statement How many ways are there to arrange the letters of the word VISITING with no pairof consecutive I's? Homework Equations C(n,k) P(n,k) The Attempt at a Solution I am calculating the entire number of arrangements possible at P(8,5). I then want to find out the...

Homework Statement How many integers between 1000 and 10000 are there with distinct digits (no leading zeros) and at least one of 2 and 4 must appear? Homework Equations None The Attempt at a Solution I am discounting the case of 10,000 since that has repeating digits. Thus...

Homework Statement A rumor is spread randomly among a group of 10 people by successively having one person call someone, who calls someone and so on. A person can pass the rumor on to anyone except the individual who just called. What is the probability that if A starts the rumor, A...

Homework Statement How many ways are there to pick 2 different cards from a standard 52-card deck such that the first card is a spade and the second card is not a queen. Homework Equations P(n,k) C(n,k) The Attempt at a Solution Since the player must have one spade, there are 13...

Homework Statement Given nine different English books, seven different French books, and five different German books: How many ways are there to mak a row of three books in which exactly one language is missing? Homework Equations P(n,k) C(n,k) The Attempt at a Solution I...

Homework Statement There are eight applicants for a job, and three different judges who each rank the three applicants. Applicants are chosen if an donly if they appear in the top three in all three rankings. a) How many ways can the three judges produce their three rankings? b) What is...

Homework Statement There are eight applicants for the job of dog catcher and three different judges who each rank the applicants.Applicants are chosen if and only if they appear in the top three in all three rankings a) How many ways can the three judges produce their three rankings? b) What...

So here is the problem: Now what seems logical to me is first choose 1 of the 10 non-performing and then choose 4 from the remaining 139 chips. What is wrong with my logic here? I don't get the answer the book gets (130,721,752), and instead get 148, 916, 260.

Homework Statement A dance class consists of 22 students, of which 10 are women and 12 are men. If 5 men and 5 women are to be chosen and then paired off, how many results are possible? Homework Equations The Attempt at a Solution We can say that for the first couple, there are a...

suppose that I want to walk from the corner of a block to the corner of another block (I depart from the corner of coordinates (0,0) and want to get to the corner with coordinates (X,Y), with X and Y being whole numbers. ); and I want to do so by walking N block sides (I can walk over the same...

I am a senior student double majoring in computer science and mathematics with the intention of getting a p.h.d in theoretical computer science(either computational complexity or applied discrete mathematics). for the upcoming winter semester I can take 1 math course. The ones that are related...

Homework Statement There are 7 parties competing in the elections. One party has obtained 3 mandates, and the rest 6 have received one mandate each. a) How many different coalitions with at least 5 mandates can be formed? b) Assume that the parties are being called to join each other in a...

Homework Statement I have K birds to put into M cages. How many ways can I do this(no limit on the amount of birds in a cage - there can be empty cages)? Unfortunately I haven't had a combinatorics course (and my friends who have apparently have forgotten all of it...) so I'm a little...

Homework Statement How many permutations of the letters a, b, c, d, e, f, g have either two or three letters between a and b? b _ _ a is also very much possible.Homework Equations nPr= n!/(n - r)!, where n >= rThe Attempt at a Solution For this question there can be 4 cases which are as...

Homework Statement You have 3 types of postcards. There are 5 of each type. How many ways can you send the 15 postcards to 15 friends, if each friend receives 1. The Attempt at a Solution I thought it would merely be 15!/(3*5!)

Homework Statement Use the Summation Identity to count the cubes of all integers sizes formed by an n by n by n assembly of cubes. Homework Equations Summation Identity: Sum [from i = 0 to n] (i choose k) = (n+1 choose k+1). Sum [from i = 0 to n] (i^3) = (n^2)(n+1)^2 / 4 = (sum[from...

In how many ways can 16 people be seated: A. In a row, if 4 of the 16 do not want to sit next to one another B. In a row, if 3 of the 16 must be seated next to one another C. In a circle, if 3 of the 16 must be seated next to one another D. In a circle, if 4 of the 16 do not want to...

Homework Statement Sum the series 1^2+2^2+\cdots|n^2 by observing that m^2=2* \dbinom{m}{2} + \dbinom{m}{1} and using the identity \dbinom{0}{k}+ \dbinom{1}{k} + \cdots+ \dbinom{m}{k}= \dbinom{m+1}{k+1}. Homework Equations The Attempt at a Solution I know that...

Homework Statement Prove that 1 - \dbinom{n}{1}\ + \dbinom{n}{2} \ - \dbinom{n}{3} \ + \cdots \ + (-1)^r \dbinom{n}{r} = (-1)^r \dbinom{n - 1}{r} by induction. Homework Equations The Attempt at a Solution Well, I know how to solve the normal binomial sums by using the...

Hi, I'm trying to figure out a variation of the problem where you determine the number of paths on a discrete grid from one point to another. For example, for the paths from (0,0) to (a,b), you can consider one path to be a rearrangement of a word with a x's and b y's, so the number of paths...

In my combinatorics book, it's discussing inclusion-exclusion, and it says that n!-(n-1)! = (n-1)!*(n-1)! Can someone help me understand the rules of factorials? Thanks!

Probably the only area of math that really confuses me. :frown: I'm trying to calculate some probabilities for Liar's Dice. Essentially, the probabilities that a certain number of faces will appear when five dice are rolled, with one being a wildcard. If I try a specific combinatoric approach...

I was reading Stanley's first volume on Enumerative Combinatorics, and I am seemingly stuck on a basic question regarding compositions. It may be that my algebra skills are rusty, but I just cannot get the correct formula for the number of compositions of n into even numbers of even valued...

Dear all, I am attending a taught postgrad programme starting next October. I can not decide whether to take the Algebraic Number Theory or the (additive/arithmetic) Combinatorics modules. My choice will determine my PhD route, so it is a choice of career rather than just a choice of...

Find the number of ways of placing two knights in a chessboard that they can threaten each other. I tried to solve it like this but it was wrong because the answer was not among the four options. I wrote the number of squares that that the knight can threaten on every square that we place...

6 unique experienced persons 2 unique inexperienced persons How many 3-person combinations if at most one in the group can be inexperienced? 6*5*4/3! + 6*5*2/2! is the answer. My answer was 6*5*4/3! + 6*5*2/3! Why does the book divide by a 2-permutation and not a 3-permutation for...

Homework Statement Two n-digit integers (leading zeros allowed) are considered equivalent if one is a rearrangement of the other. (For example, 12033, 20331, and 01332 are considered equivalent five-digit integers.) If the digits 1, 3, and 7 can appear at most once, how many nonequivalent...

Homework Statement Determine the number of permutations of {1,2,3,4,5,6,7} in which exactly four integers are in there natural positions. The Attempt at a Solution Would this be solved by using the Inclusion/Exclusion Principle and finding \left|S\right| - \sum \left|A_{1}\right|...

Homework Statement Prove that n5^n = \frac{5}{4} \sum_{k=0}^{n}k\begin{pmatrix}n\\k\end{pmatrix}4^k (Hint: First Expand (1+x^2)^n) The Attempt at a Solution So if I expand that I get (1+x^2)^n = (1+x^2)(1+x^2)...(1+x^2) n times so it equals \sum_{k=0}^n (1+x^2) Not sure where to...

Homework Statement How many integers between 1 and 2009, inclusive are (a) not divisible by 3,2, and 10 (b) not divisible by 3,2, or 10? Homework Equations The number of objects of the set S that have none of the properties is given by the alternating expression: \mid S \mid -\sum...

Homework Statement 6 children are sitting arounbd a round table, with each chair numbered from 1 to six. In how many ways can we rearange them so that no child sits across from the child who was across him before. Homework Equations The Attempt at a Solution Because the chairs...

Homework Statement My professor has 50 questions. In the beginning of the semester he makes 10 work sheets each with 5 questions. At the end of the semester, he makes 10 new worksheets from the same quetions, this tiem sorted by difficulty. Prove that there exists a subset of 10 question in...

1. (a) How many repeating three-digit numbers can be formed using the numbers {1, 2, 3}? (b) How many non-repeating three-digit numbers can be formed using the numbers {1, 2, 3}? My solutions: a. 3 x 3 x 3=27 b. 3 x 2 x 1 =6 2. (a) Construct a tree diagram for 4 tosses of a fair coin...

Hi, I'm trying to figure out a variation of the problem where you determine the number of paths on a discrete grid. For example, for the paths from (0,0) to (a,b), you can consider it to be a rearrangement of a word with a x's and b y's, so the number of paths is (a+b)! / a!b!. The...

Homework Statement Find the coefficient of x^{9} y^{10} in (3x^{3} - 4y^{2})^{8} Homework Equations The professor gave us a somewhat algebraic tactic or shortcut for solving these kinds of problems, mainly consisting of solving for each exponent. It can be somewhat tricky for me to explain...

Homework Statement You are given n identical As and n identical Bs. You are supposed to arrange them in a circle. How many unique arrangements are there? Homework Equations Use of combinatorics The Attempt at a Solution At first, I tried working out the answer if I arrange them in...

Homework Statement 1. Recall that Fn denotes the number of perfect coverings of a 2–by–n chessboard with dominoes. Use combinatorial reasoning to show that F2n = Sum [of k=0 to k=n] of (nCk) Fk for all integers n ≥ 0. Make sure to describeFk in the context of perfect coverings of a 2–by–2n...

Homework Statement in a poker game we want to calculate the Probability to get differnet combinations. in a card deck there are 52 cards from 4 different series. each series has 13 cards. we assume that each card get 5 random cards. What is the number of combinations to get the cards? (The...

how do I evaluate \sum_{k=0}^d \binom{n+d-k}{n} ?

Hi, I'm trying to figure out a variation of the problem where you determine the number of paths on a discrete grid. For example, for the paths from (0,0) to (a,b), you can consider it to be a rearrangement of a word with a x's and b y's, so the number of paths is (a+b)! / a!b!. The...