Combinatorics Definition and 421 Threads

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...

Homework Statement if there are k spots for n balls, what are the number of possible arrangements? each spot can hold n number of balls and each ball is indistinguishable from one another. Homework Equations $$\frac{n+k-1}{k!(n-1)!}$$ The Attempt at a Solution I just wanted to know if this...

Homework Statement I hope someone can help me as it is urgent... We randomly assign 40 people (20 girls and 20 boys) into 20 double rooms (we can assume that all room assignments are equally likely). What’s the probability that there will be no mixed sex rooms? Homework EquationsThe Attempt at...

I need to know this subject for my uni access exam, which will include one combinatorics problem. It's very silly because it's not studied in the course at all, you are instead given random problems and are supposed to magically know them and work them out in the most painful ways. I just don't...

Dear Physics Forum friends, I am a college junior who is currently conducting the undergraduate research in the theoretical computer science. I wrote this post to seek you recommendation on the books that separately treat the graph theory and combinatotics, both in theory and applications. I...

Homework Statement and attempt at a solution[/B] If 5 gifts are to be given among 8 children: a) if the gifts are identical (indistinguishable) and no child can receive more than 1 gift, there are 8P5 ways b) if the gifts are non-identical (distinguishable) there are 5!(8P5) ways In a), the...

Use inclusion-exclusion to find the number of ways to arrange the six numbers 1, 2, 3, 4, 5, 6 such that either 1 is immediately followed by 2, or 3 is immediately followed by 4, or 5 is immediately followed by 6. I believe that this can be solved using unions. By setting the sets to be the...

Homework Statement If you have a 52card deck and split it evenly to 4 people (a,b,c,d) then what is the probability that persons a and b have 7 spades and person c has 3 spades. Homework Equations P(A) = |A|/|S| The Attempt at a Solution I divided up the decks 4 ways. So Persons a and b...

Homework Statement In a 52 card deck, if you draw 5 cards find the probability of drawing exactly one ace. Homework Equations (n k) = n!/k!(n-k)! P(A) = |A|/|S| The Attempt at a Solution So I took the logic of a different example we had that stated it like this - If we have 5 options but...

Homework Statement If three number are chosen randomly from the set ##{1,3,3^2,...3^n}## without replacement, then the probability that they form an increasing geometric progression is? (a) 3/2n if n is odd (b) 3/2n if n is even (c)3n/2(n² -1) if n is even...

Homework Statement An ice cream shop has a special on banana splits, and Xing is taking advantage of it. He’s astounded at all the options he has in constructing his banana split: · He must choose three different flavors of ice cream to place in the asymmetric bowl the banana split is served...

I want to get better at this topic and I have trouble finding good questions apart from past year exam questions. I am currently an A- Level student, so can someone recommend me a good book full of challenging questions at my level? To give you some idea of the types of questions in the exam...

Homework Statement In the coordinate plane let ##A_i=(i,1)## for ##l\leq i\leq15##, and let ##A_i=(i-15,4)## for ##16\leq i \leq 30##. Find the number of all isosceles triangles, where all three vertices belong to the set ##\{A_1,A_2, \cdots,A_{30}\}## Homework Equations Knowing the number of...

Homework Statement Find the number of ways to distribute 55 identical coins among three people, so that everyone gets an odd number of coins. Homework Equations Stars and Bars Formula [/B]The Attempt at a Solution (n+r-1,n-1) Ways to place r indistinguishable objects into n distinguishable...

Hello! On this Fall Semester, I will be taking the Linear Algebra with Proofs (Friedberg), Analysis I (Rudin-PMA) or Abstract Algebra I (Dummit/Foote), and Combinatorics (Brualdi). Since I can take only one from Analysis I or AAI on Fall, I am trying to figure out if the introductory...

While reading about combinatorial mathematics, I came across the Stirling transform. https://en.wikipedia.org/wiki/Stirling_transform So then, if I want to find the Stirling transform of, for instance, ##(k-1)!##, I have to compute this (using the explicit formula of the Stirling number of the...

Homework Statement A code consists of at-most two identical letters followed by at-most four identical digits. The code must have atleast one letter and one digit. How many distinct codes can be generated using letters A-Z and digits 1-9. Homework EquationsThe Attempt at a Solution //One...

Dear Physics Forum advisers, My recent study on number theory and cryptography got me really interested in the fields of combinatorics and graph theory. I am really interested in learning about them independently now since I will not be able to take the combinatorics course until next year...

Homework Statement My book repeatedly uses the phrase "contains one of each complementary pair of sets" and I am wondering what do they mean by that exactly? Homework Equations None The Attempt at a Solution For example, when it proves that an intersecting family of subsets of...

Homework Statement A Steiner Triple System, denoted by ##STS(v),## is a pair ##(S,T)## consisting of a set ##S## with ##v## elements, and a set ##T## consisting of triples of ##S## such that every pair of elements of ##S## appear together in a unique triple of ##T##. Homework Equations None...

Homework Statement Show that any finite graph contains two vertices lying on the same number of edges. Homework Equations None The Attempt at a Solution I am confused how my book proved this. Let G be a graph with n vertices ##v_1, ..., v_n.## Place ##v_i## in a pigeonhole labelled...

Homework Statement To make sure I don't get booted right off the bat, I should emphasize that this is not a homework assignment. I'm a lawyer working on a brief, and I'm trying to respond to an allegation that has dragged combinatorics into the case. In a complaint filed in court, you are...

Homework Statement If the 2-subsets of a 9-set are colored red and blue, there is either a red 3-set or a blue 4-set. Homework Equations None The Attempt at a Solution My book first proved for 10 points, the proof given is: Consider first for 10 points. Consider the nine edges joining one...

Hi there, my question is the following: What are your chances of winning the following lottery? You choose a set of 10 distinct numbers from the set S = {1, . . . , 50}, and the person running the lottery selects 6 (distinct) numbers at random, also from the set S. If all six selected numbers...

Homework Statement set {A} : 26 elements <--- let's call this number n set {B}: 24 elements <--- let's call this number m goal: i want to know the number of possible combinations i will have if i start by replacing one element in {A} with an element in {B}, then i want to know the number of...

Hi all, I've come across an interesting problem that I'm unsure how to solve. Let say we have N numbers {1, 2, ... N}. Each number in this list is mapped to one number in {1,..,M} where M < N. What are the possible ways I can list the first set, such that the numbers of the second set which...

Hello, I am a student interested in pure mathematics, and am considering giving this book a try. I was wondering what you all think if this book as I have it in my possession. Is it good? If not, is there any very rigorous (I can handle Rudin Analysis rigor) discrete textbook, like one that...

Homework Statement There are 5 errors, and 3 people are proofreading the text. P(1. person finds an error) = 0,5 P(2. person finds an error) = 0,6 P(3. person finds an error) = 0,7 There are 5 errors, and whenever a person comes across one, they have the above probability of seeing it...

Homework Statement How many ways can you select 10 jellybeans from colors Red, Blue, Green so that at most you only have 4 Green jellybeans? Homework Equations ... 3. The Attempt at a Solution [/B] # of ways = # of ways to pick 1 Green + # of ways to pick 2 Green + #of ways to pick 3...

Consider the following segment where i,j,k,n and counter are integer variables and the value of n (a positive integer) is set prior to this segment. counter := 0 for i := 1 to n do for j :=1 1 to i do for k :=1 to j do counter := counter + 1 I am so lost as to what this program is...

Hi folks, can you guys share your experience and tips for understanding this subject? I find the sheer amount of problems and their novelty very difficult to reconcile. I mean I understand the definitions and theorems well and can usually apply them in straight forward cases, but the many...

6 people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly 6 chairs. So each person has exactly two neighboring chairs, one on the left and the other on the right. The host decides to shuffle the sitting arrangements. A...

< Mentor Note -- thread moved to HH from the technical math forums, so no HH Template is shown > N people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly N chairs. So each person has exactly two neighboring chairs, one on...

We have to distribute m distinguishable toys, k identical candy bars to 12 children in the following ways: a. How many ways can we distribute toys if each child can get any number of toys? b. How many ways can we distribute candy if each child can get any number of candy bars? c. How many ways...

Proofs in most mathematical topics refer theorems with impressive names and use technical terminology. Proofs of combinatorial results often say something like "imagine we have n numbered balls ...". . ( If we wanted to give the proof a prehistoric sound , we could say "imagine we have n...

Homework Statement Eight cards are selected with replacement from a standard pack of 52 playing cards, with 12 picture cards, 20 odd cards, and 20 even cards. (a) How many different sequences of eight cards are possible? (b) How many of the sequences in part (a) will contain three picture...

Homework Statement Let p be a prime, k be positive integer, and m ∈ {1, 2, 3, ..., pk-1}. Without using Lucas' theorem, prove that p divides \binom{p^k}{m}. Homework Equations The definition of the binomial coefficients: \binom{a}{b} = \frac{a!}{b! (a-b)!} The Attempt at a Solution I've...

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1. One of my friend told me that he can determine the number of ways with inclusion-exclusion principle and found the result 195 for given N=10 and the positive...

Hey guys, I'd love to get the formula to answer the following question: I have 50 colorless balls and 100 different paints. All balls have to be painted. Note that the balls' order is not important and repetition is allowed (means I can paint up to 50 balls in any single color if I want). With...

Homework Statement In how many ways can m men and n women be arranged such that no two women are besides each other? (m > n)Homework EquationsThe Attempt at a Solution The given answer is m! x P(m + 1, n). I understood how the answer should be a multiple of m!. I also understood that there...

Homework Statement 1)How many bitstring of length 11 contain three more 0's than 1's? 2)How many string of 5 lowercase letters from the Latin alphabet contain: a) the letter c? b) the letters c and d? c) the letters c and d in consecutive positions with c preceding d and all letters distinct...

Hi, there are two problems I can't really solve yet they don't seem that difficult. The two of them seem pretty related to me, I think there's something I'm not getting I'll detail my attempts at solving but any help especially with the steps to the solution would be really appreciated as I have...

Hi, just a simple combinatorics problem I can't figure out how to do! We want to place n books, of which m are broken, on a bookshelf so that there are at least 2 consecutive broken books. The broken books are indissociable from one another and so are the good book, how many ways can we do...

So look at what I've done: {n+1 \choose k} = \frac {(n+1)!} {(n+1-k)! \cdot k!} = \frac {(n+1)\cdot n!}{(n-(k-1))!\cdot k \cdot (k-1)!} = \frac {(n+1)}{k} \cdot \frac { n!}{(n-(k-1))!\cdot (k-1)!} = \frac {(n+1)}{k} \cdot {n \choose k-1} oops I accidentally posted this before I...

Hi, this is the problem: Delegates from 10 countries, including Russia, France, England, and the United States, are to be seated in a row. How many different seating arrangements are possible if the French and English delegates are to be seated next to each other and the Russian and U.S...

Hello community. I'd like to know about good books dealing with combinatorics that you might recommend. I'm a math major who has neglected this area for some time now and essentially I feel like I don't know how to count. Advice is welcome!

Homework Statement How many 4-digit odd numbers are there? (Without repetition) Homework Equations The Attempt at a Solution I thought in the following way: For the last digit, we have 5 possibilities(1,3,5,7,9). For the last second we are left with 9 possibilities, 8 for the next...

Homework Statement How many ways can 5 different letters be posted in 3 boxes, if any number of letters can be posted in all of the three post boxes? Homework Equations Order of the letters being put into the box doesn't matter, only which letter or letters ends up in which box. A box...