Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc.
The full scope of combinatorics is not universally agreed upon. According to H.J. Ryser, a definition of the subject is difficult because it crosses so many mathematical subdivisions. Insofar as an area can be described by the types of problems it addresses, combinatorics is involved with:
the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,
the existence of such structures that satisfy certain given criteria,
the construction of these structures, perhaps in many ways, and
optimization: finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion.Leon Mirsky has said: "combinatorics is a range of linked studies which have something in common and yet diverge widely in their objectives, their methods, and the degree of coherence they have attained." One way to define combinatorics is, perhaps, to describe its subdivisions with their problems and techniques. This is the approach that is used below. However, there are also purely historical reasons for including or not including some topics under the combinatorics umbrella. Although primarily concerned with finite systems, some combinatorial questions and techniques can be extended to an infinite (specifically, countable) but discrete setting.
Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is graph theory, which by itself has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms.
A mathematician who studies combinatorics is called a combinatorialist.
Note, it's not assumed anywhere that ##X_1,\ldots,X_n## are independent.
My solution to (a) is simply ##1/n!##, since we've got ##n!## possible orderings, and one of the orderings is the ordered one, so ##1/n!##. However, I am not sure this is correct, since I don't understand why the...
There are two questions I need some help with. They both involve a ‘honeycomb strip’ (which is just a hexagonal tessellation of two rows), ‘worker bees’ (which take up two hexagons), and larvae (which take up one hexagon).
How can we count the number of ways there are for worker bees and larvae...
Right, so i came across this problem
My approach was uninteresting and not clever at all. I started making cases i had to make about 14 of them and while it didnt take long,i think it would have been very tedious for a bigger number say 16 players. But it was logical and i got my answer.
Smart...
Expanding the multinomial, the general term is 8!/i!j!k! * x^(3j+4k) for all i + j + k = 8.
The number of terms would be the number of distinct powers of x, the number of distinct outputs of 3j+4k with the specified constraints for i, j and k.
I attempted to make cases. 3j+4k where j+k <= 8...
The rightmost position has 3 possibilities: ##x,y,z##
The remaining two letters are to be arranged in 6 spaces: ##\frac{6!}{4!}##
Now the 3 can be placed in ##\frac{4!}{3!}##
Total no of ways =$$3×\frac{6!}{3!}=12×30$$
$$OR$$
Since ##x,y,z## are three different boxes/variables, we can use the...
For many years now, the theorist Nima Arkani-Hamed has lent his prestige and energy to a research program that aims to transform our understanding of quantum field theory, by using symmetries in the sums of Feynman diagrams to uncover perspectives on the theory not based in ordinary space-time...
I want to learn topics related to combinatorics, probability theory, discrete and continuous random variables, joint pdf and cdf, limit theorems and point estimation, confidence intervals and hypothesis testing.
Any recommendations for books to learn those topics? High school level or...
I saw this question from here: https://www.cs.sfu.ca/~ggbaker/zju/math/perm-comb-more.html (under Combinations with Repetitions).
I thought the answer would be obvious: ##3\cdot3\cdot3\cdot3\cdot3\cdot3=729##
But the course notes give the answer as ##28##, and it says this is obvious because...
part (a) was straightforward ##\mathcal{P} = \frac{20}{200} = 0.1##. Instead of directly trying to find the probability of the 20th drawn ball being marked I decided to start with finding the probability of the second ball drawn being marked and then after figuring that out moving to the cases...
I tried this for a long time but im not getting there, not even close. So far I tried finding out the total number of ways you could sit these boys and girls if there were no restriction, that came out to be 40320.
Then I found the number of ways you could have with two girls sitting next to...
The straightforward way to solve this question:
1. Two passengers decline to face the engine: ##^5C_2 \cdot 2! = 20##
2. One passenger cannot travel backwards: ##^5C_1 \cdot 1! =5##
3. The remaining seven passengers can sit in any order in the remaining seven seats: ## 7! ##
Multiply 1,2,3...
let ##k \in\mathbb{N},## Show that there is ##i\in\mathbb{N} ##s.t ##\ \left(1-\frac{1}{k}\right)^{i}-\left(1-\frac{2}{k}\right)^{i}\geq \frac{1}{4} ##
I tried to use Bernoulli's inequality and related inequality for the left and right expression but i the expression smaller than 1/4 for any i...
My studies relate with construction engineering and environment improvements and I have a passion about combinatorics and exact sciences. I'm always in touch with the novel things that pop out in science related media. I don't like when people start make politics upon science findings.
I'm the...
My combinatorics professor has a MA, PhD from Princeton University. On our test, she asked
I handwrote, but transcribed in Latex, my answer below.
How can I improve this? What else should I've written? Professor awarded me merely 50%. She wrote
Hi there. Happy new year.
I am interested in magic squares. I am particularly interested in how to fill a square of order n in a symmetrical and logical way by analyzing the possible ways to achieve a given sum of numbers.
My question is about combinatorics analyses.
For example for a square...
I was reading about numerical methods in statistical physics, and some examples got me thinking about what seems to be combinatorics, an area of math I hardly understand at all beyond the very basics. In particular, I was thinking about how one would go about directly summing the partition...
Hi all,
I need some help with this one:There are 3 shapes of pasta: 1,2,3.
In a box there are 3 packages of pasta of shape 1, with different weights: 300 gr, 400 gr, 500gr.
In addition, there are 5 packages of paste of shape 2, with weights: 300gr, 350gr, 400gr, 500gr, 600gr,
and 4 packages...
My tests are submitted and marked anonymously. I got a 2/5 on the following, but the grader wrote no feedback besides that more detail was required. What details could I have added? How could I perfect my proof?
Beneath is my proof graded 2/5.
Hello,
Another combinatorical question I scratch my head with.
In a parliament of a country there are 400 seats that should be divided between 3 parties.
What is the number of possibilities of division if we want that no party will have more than 200 seats ? Each party must have at least one...
Dear all,
I am trying to calculate this one, I can't think of a way to calculate it..
A standard deck of cards is given with 13 cards of 4 shapes ( Clubs , Diamonds , Hearts , Spades ).
What is the number of possibilities to order the cards in the deck such that a king won't be on top of an...
Hello!
I am looking for textbooks to relearn Combinatorics, Permutations Combinations and Probability and also Matrix algebra( decomposition, etc). I had done these many years ago and the course/books provided to me at that time weren't that great. So I want to relearn this with a more...
If there are N distinguishable boxes and M indistinguishable balls, the answer is easy as it is equivalent to the combinations of arranging N 0s and (M-1) 1s in a queue.
$$\binom{M+N-1}{N}$$
However, if the boxes are themselves indistinguishable (which I name them "piles" instead), how should...
Hi,
I found this problem online and I wanted to see whether my solution was going along the correct lines or not?
Question: There are 7 people going to eat lunch at a table with 10 seats, arranged in two rows of 5 (2 x 5 arrangement). 5 people are wearing a red shirt, and the other 2 are...
In Oz Lotto, balls are numbered 1 to 45. Nine are selected, seven of which are winning numbers and two being supplementary numbers. Players select seven numbers.
The odds of winning can be found here: https://www.lottoland.com.au/magazine/oz-lotto-everything-there-is-to-know.html
I tried...
Hi,
I was watching a Youtube on combinatorics (here) and a problem was posed at the end of the video about counting the number of quadrilaterals.
Question:
How many quadrilaterals are present in the following pattern?
Attempt:
The video started with the simpler problem of finding the number...
Hi everyone
Can anyone help with this combinatorics problem? I have the answers, but don't understand how the answer was derived.
Here's my attempt and reasoning.
Step 1: Determine all possible combinations
Since A, B and R have multiple letters, the number of possible combinations is given...
QUESTION:
If A is a finite set, its cardinality, o(A), is the number of elements in A. Compute
(a) o(A) when A is the set consisting of all five-digit integers, each digit of which is 1, 2, or 3.
(b) o(B), where B = {x ∈ A : each of 1,2 and 3 is among the digits of x} and A...
Question: "A total of 9! = 362880 different nine-letter ‘‘words’’ can be produced by rearranging the letters in FULBRIGHT. Of these, how many contain the four-letter sequence GRIT?"
Solution: There are six ways of getting the word "GRIT" with five letters left over giving 6 x 5! = 720...
A 4×3 matrix which has all elements empty, now I select any two consecutive elements until all elements are selected. I assign an index number (1 to 12) to the matrix element, in one row there are only 1,2,3 elements and 3 & 4 are not consecutive.
for example, if I select index 1 & 2 of the...
I have a question regarding to combinatorial proofs and predicate logic. It seems to me that in some combinatorial proofs there is a use of contraposition ( although not explicitly stated in the books where I've read so far ), for example If we to prove that ## C(n,k) = C(n,n-k) ##...
This is a popular combinatorial proof for the Inclusion-Exclusion principle but I was wondering what kind of proof technique they use?
Initially I thought - since we have cardinalities on both sides of the equality , I thought we'd have to show a bijection exists between the set on the left...
This is an interesting combinatorics problem that I thought of. Oddly, I think I know of an application of said problem to physics, but I could not find any problem like it online (the closest I got was the Knapsack problem, which is just about optimization). My initial instinct was to look for...
I have ##N## papers to be evaluated, ##40 \le N \le 56##. I have 9 people named A - I that need to be put in teams of 3 to evaluate the papers individually, i.e. 3 evaluations per paper. There are ##\begin{pmatrix}9 \\3\end{pmatrix} =84## triplets that can be formed. Thus there are more...
This is my solution so far however I’m not sure where to go from here I think it’s something to do with the trace of the matrix but. This is the full solution but I did row reduction on the matrix K6- $lambda$I
Not homework, just working odd numbered problems in the book.
Sue has 24 each of n different colored beads. If 20 beads are selected (with repetition allowed) what is the value of n if there are 230,230 possible combinations. I view this as a problem of number of integer solutions to a linear...
Well ##\cup_{i} E_i## is just the event that at least one color is not used, so its probability is given by ##1- (1/N)^N##. Now if I is a subset of {1,...,N} where ##\left | I \right | = l## then ##Pr(\cap_{i\in I} E_i) = (1-l/N)^N## (I'm guessing this is where I'm making a mistake?). So then we...
My teacher solved this using inclusion-exclusion formulas to count the number of surjections from a set of 8 elemets (containing items) to a set of 5 elements (containing boxes). However, I thought of a different solution. But I have a hunch it's wrong.
What I thought is to first make sure every...
I understand that the odds of drawing one of the unique cards in the first 7 is expressed as
29c6 / 30c7
where NcK is "N choose K" or Binomial[N,K] in Mathematica.
Am I correct in using the following to answer my original question?
Let q be the first card of interest and q' be the second...
Hello there,
I'm working on a kinetic theory of mixing between two species - b and w.
Now, if I want to calculate the number of different species B bs and W ws can form, I can use a simple combination:
(W+B)!/(W!B!)
Now, in reality in my system, ws and bs form dimers - ww, bb, wb and bw...
For a somwehat simple version of the problem, imagine a group of ten people (n=10), for which we observe two binary attributes (d= 2). One of the attributes tells us if any given person wears glasses (d_1) the other if any given person wears a hat (d_2). We know that in total 5 people wear hats...
Hey.
We started to study all this subject of combinatorics integrated with the subject of functions.
1. I don't actually understand how to integrate between combinatorics and function, those functions which represent our possibilities and etc...
And why at all we need to represent our...
Homework Statement
Define {x \choose n}=\frac{x(x-1)(x-2)...(x-n+1)}{n!} for positive integer n. For what values of positive integers n and m is g(x)={{{x+1} \choose n} \choose {m}}-{{{x} \choose n} \choose {m}} a factor of f(x)={{{x+1} \choose n} \choose {m}}?
Homework Equations
The idea...