Combinatorics Definition and 398 Threads

Hello! I’m teaching myself mathematics and physics, and I’m looking for a clear, rigorous book on combinatorics. The reason being is that past books I’ve read that included some combinatorics were difficult to understand (for example, my first encounter with the subject was in a precalculus...

Homework Statement A man needs to buy 12 cars. There are 4 kinds available. He can buy any number of cars of each kind, the condition being 12 cars in total. In how many ways can he buy the 12 cars? Homework EquationsThe Attempt at a Solution Hmmm as he can buy any number of each kind my...

Imagine we take a sheet of paper and along the bottom lay out ten equal spaces by marking off 11 equally placed points. We label this row 1. Directly above these points we mark off another 11 points to correspond to our first eleven points only this time we divide the ten spaces of this row into...

Hello, I am trying to solve a problem related to natural numbers. The solution is based on the pigeonhole principle, however I can't see the connection. The is the problem: Choose 12 two digit numbers. Divide each by 11 and write down the residue (i.e. do the modulu operation). Group the...

Homework Statement A state of a system of many noninteracting particles can be specified by listing which particle is in which of the accessible single particle states. In each microscopic state we can identify the number of particles in a given single particle state ##k##. This number is...

I have attached an image showing a (what I believe to be) simple problem involving arranging four blocks, each of different dimensions. Yes, the blocks fit together perfectly in the first arrangement shown in the diagram when there are no gaps. I'm convinced that the solution is likely easily...

Can anyone help me with the following scenario: A hopping circuit is painted on a school playground. It consists of 25 small circles, with the numbers 0 ( at the 12 o' clock place) to 24, arranged as a big circle. Each student jumps either 3 or 4 spaces clockwise(so a student can end up either...

Consider the one loop correction to a 2 -> 4 scattering process in phi4 theory.The only IPI/non snail contributions is that shown in the attachment. I have an automated package that will do all the feynman diagram generation for me and for this process it returns 15 diagrams, which means to say...

there's a proof provided, but i want to know the intuition as to why it is 2^k.

Homework Statement Hello, I have to solve a problem to calculate all the possible combinations in a dataset. I have candles and each one has 4 values: open, close, high and low. And I have a high number of candles (hundreds). I want to know all the possible scenarios that it's possible to...

Homework Statement A set ##P=\left\{ \ p1,p2,p3,p4 \right\}## is given. Determine the number of antisimmetric relations of this set so that ##p1## is in relation with ##p3##, ##p2## is in relation with ##p4## but ##p2## is not in relation with ##p1##. Homework Equations 3. The Attempt at a...

Homework Statement Using the common logic and known combinatorics properties solve the following problems: a) If you have 6 letters and 6 envelopes, each having it's corresponding envelope in how many ways can you place every letter in the wrong envelope? (1 letter goes into 1 envelope) b)You...

please help solving this question The letters of the word CONSTANTINOPLE are written on 14 cards, one on each card. The cards are shuffled and then arranged in a straight line: how many arrangements are there where no two vowels are next to each other?

Hi! I've been stuck with this problem: How many different n digit numbers are there that contain the numbers 3 and 5? I've approached it like this: There are 10^n different n digit numbers in total - variations made from the digits 0,...,9. There are 8^n of those that don't contain 3 and 5...

Homework Statement In how many ways can you choose 30 balls from an unlimited number of blue, red, green and white balls if you can choose any number of the different coloured balls? Homework EquationsThe Attempt at a Solution What I did is view the problem as choosing from a set of 30 of each...

Homework Statement There are 15 different apples and 10 different pears. How many ways are there for Jack to pick an apple or a pear and then for Jill to pick an apple and a pear? Homework EquationsThe Attempt at a Solution Let apples be A and pears P. Since Jack chooses either an apple or...

Homework Statement Given {1,2,...,n}, n is an even number. What are all the possible subsets that contain only even numbers? (Notice that ∅ is also defined as such a subset). Homework Equations 2n - all possibilities for group A with n objects The Attempt at a Solution I think the answer...

Homework Statement Given sample space U with n objects. A ⊂ U, and A has k objects. A ∩ B ≠∅ What are all the possibilities for B? Homework Equations 2n - All possibilities for set B with n objects The Attempt at a Solution I don't know where even to begin... The question itself confuses me.

If I have k positive integers, x1, x2, ..., xk and n(also an integer) where $$ x_1≤x_2≤x_3≤...≤x_k≤n $$ How can I get the total combinations? I am trying to find the distinct components of a symmetric tensor. But I stuck here.

Homework Statement If we want to use positive integers from 1 until 7 to form a ring in order. Since 1 and 7 are adjacent to each other in the ring. Due to their neighbouring position, 1 and 7 are also considered as neighbour numbers. Then if we want to pick 3 non-neighbouring numbers from this...

Homework Statement There is a book with 2 volumes. Each volume exists in 3 different languages. Each language has 2 identical copies(total of 12 books). In how many ways we can arrange them on a shelf, with no restrictions and order of the volumes is irrelevant? Homework EquationsThe Attempt...

Homework Statement Show that every subset with 6 elements of {1,2,3,4, ..., 9} contains 2 elements with sum 10. I solved this (solution below) but I want to do this easier using the pidgeon hole principle. Homework Equations Pidgeon hole principle Combinatorics The Attempt at a Solution...

Homework Statement The Jones family has 5 boys and 3 girls, and 2 of the girls are twins. In how many ways can they be seated in a row of 8 chairs if the twins insist on sitting together, and their other sister refuses to sit next to either of her sisters? Homework EquationsThe Attempt at a...

Doing my combinatorics homework, I just thought that I've made a mistake. When counting the number of ways to place two black and one white rooks on a chess board, I placed the black rooks on black squares and the white one- on a white square? So I chose C(32,1) for the first took. Is that...

Homework Statement In how many ways can we pick a group of 3 different numbers from the group ##1,2,3,...,500## such that one number is the average of the other two? (The order in which we pick the numbers does not matter.) Homework EquationsThe Attempt at a Solution I start by noting that in...

Homework Statement In how many ways can four identical red chips and two identical white chips be arranged in a circle? Homework EquationsThe Attempt at a Solution First, I calculated the number of different arrangements when the the chips are just in a line. This is ##\displaystyle {6 \choose...

I am faced with a problem in combinatorics while trying to set up a pool. Instead of explaining my real problem, I prefer to give you a simplified example: Say I am given a population of N persons of varying height ##h_i##. The height of each person ##i## in the population is known to me. Now I...

Hello! When studying binominal expansion: ## (a+b)^n = \sum_{k=0}^{n}{{n \choose k}a^{n-k}b^k} ## in high school, we proved this formula with combinatorics considering that "you can choose either a or b each time you multiply with a binom". Probably, this is not a real mathematical proof at...

Homework Statement There are 6 stale donuts in a set of 24. What is the probability of: a) there being no stale donuts in a sample of 10? b) there being 3 stale donuts in a sample of 10? c) What is the chance of a stale doughnut being found? Homework Equations N \, permutations = N! The...

Hi all, Say you have 4 apples, 3 strawberries and 6 carrots... a) If 4 items are to be selected, how many combinations are there? b) How many combinations will have no carrots? c) How many combinations will have at least 1 apple? d) Create the probability distribution table for strawberries...

Homework Statement This is a child thread I'm creating from a previous topic: https://www.physicsforums.com/threads/combinatorics-problem.871661/#post-5473920 In that thread, I was helped to come up with the expression for the number of arrangements of R distinct types of objects given the...

How many 10-digit numbers are there such that the product of its digits is equal to 2^{27}?

Homework Statement 8 friends are playing a tennis game together. How many different doubles games of tennis can they play? Homework Equations Combinations The Attempt at a Solution Well, I solved this problem by saying: we choose a group 4 people from 8 to play, so order is not important...

Homework Statement I have: 4 Blue pens 16 Green pens 7 Red pens 11 Yellow pens If I lay out all the pens in a single row, how many different arrangements does this system have? Homework Equations $$_nC_r = \frac{n!}{r!(n-r)!}$$ The Attempt at a Solution Procedure: Basically the number of...

Homework Statement 4 cards are dealt from a 52-card deck. How many hands contain 2 distinct pairs? Homework Equations This is an expression I come up with 13C1x4C2x12C1x4C2. The Attempt at a Solution This is how I approach it. From the 13 ranks, I choose 1. In this rank, I choose 2 cards from...

I'm studying probability and am currently stuck on this question: Let's say we have n distinct dice, each of which is fair and 6-sided. If all of these dice are rolled, what is the probability that there is at least one pair that sums up to 7? I interpreted the above as being equivalent to the...

Homework Statement Give combinatorial proofs of the identities below. Use the following structure for each proof. First, define an appropriate set S. Next, show that the left side of the equation counts the number of elements in S. Then show that, from another perspective, the right side of the...

Homework Statement This problem is from MIT OpenCourseWare- a diagram is attached to clarify certain definitions. I'd like to check my answers. The degree sequence of a simple graph is the weakly decreasing sequence of degrees of its vertices. For example, the degree sequence for the 5-vertex...

There is a table tennis tournament consisted of 8 participants that is guided by the following rules: 1. Each player plays with every other player for exactly one party 2. If in the i-round there was a party between A and B and a party between C and D, and A and C play In i+1, then in i+1...

Hi, I am trying to find a completely rigorous book on combinatorics. For example, one that states the sum and product counting principles in terms of set theory and proves them, treats permutations as a bijection from a set onto itself, etc. Many don't even explain the reasoning behind those...

The problem statement: How many five-letter strings of capital letters have a letter repeated twice in a row? For example, include ABCCA and AAABC and ABBCC but not ABCAD. The attempt at a solution: First, let's break down how we would perform the selection of a string that meets the...

Homework Statement ##A=\{1,2,3,4,5\}##, ##B=\{0,1,2,3,4,5\}##. Find the number of one-one functions ##f:A\rightarrow B## such that ##f(i)\neq i## and ##f(1)\neq 0\text{ or } 1##. Homework Equations Number of derangements of n things =...

*sigh* As the title says, they are the bane of my existence... I'd really appreciate it if you guys could help me with these bloody things. 1. Prove that 3C0 + 3C1 + 3C2 + 3C3 = 23 Generalize the formula for any value of r and n such that 0<=r<=n. 2. Prove that n-1Cr + n-1Cr-1 = nCr 3. i) How...

Hello! I stumbled across a question in mathematics which left me confused. Apparently there is a character in a computer game that has 10 different actions. Which action he makes is determined by which combination of buttons that you press. You should press three buttons and gets to choose...

There are 9 doors in a house.Each door needs a password to open.Passwords can be of at least 4 digits and 10 at most . In how many ways password can be used to open at least one door .

Homework Statement In a grid O(0,0) A(7,8) find the number of paths that 1. pass through (3,4) 2. don't pass through (3,4) 3. pass through M(2,3) AND N(4,6) 4. DON'T pass pass through M(2,3) and N(4,6) 5. pass through ONLY ONE of M(2,3) and N(4,6) 6. pass through AT LEAST ONE of M(2,3) and...

Homework Statement Prove that \sum\limits_{k=0}^l{n \choose k}{m \choose l-k} = {n+m \choose k}Homework Equations Binomial theorem The Attempt at a Solution [/B] We know that (1+x)^n(1+x)^m = (1+x)^{n+m} which, by the binomial theorem, is equivalent to: {\sum\limits_{k=0}^n{n \choose...

Hi all, There is a known formula for the number of solutions to ## x_1+x_2+...+x_k =n ## when ##x_1,x_2,...x_n ##are non-negative Integers. Question: Are there known formulas for the sum ##x_1+x_2+...+x_k =n ## when ## x_1, x_2,..,x_k ## are positive or negative Integers in a bounded...

Homework Statement Three children, each accompanied by a guardian, seek admission in a school. The principal wants to interview all the 6 persons one after the other subject to the condition that no child is interviewed before its guardian. In how many ways can this be done ? Homework...

Homework Statement The chance that an event A will happen is always equal to 0,3. We stop the experiment once event A occurs What is the probability that : a) we have to attempt the even at least 4 times b)we then do the event a fourth time I am asking this because the professor did not tell...