What is Combinatorics: Definition and 416 Discussions

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.

View More On Wikipedia.org
Recent contents Top users
  1. tellmesomething

    B Really simple mistake in this combinatorics problem?

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

    Combinatorics for number of distinct terms in multinomial expansion

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

    Show that ##^{n+1}C_r=^nC_r+^nC_{r-1}##

    ##^nC_r=\dfrac{n(n-1)(n-2)...(n-r+2)(n-r+1)}{1\cdot2\cdot3...\cdot(r-1)\cdot r}## ##^nC_{r-1}=\dfrac{n(n-1)(n-2)...(n-r+2)}{1\cdot2\cdot3...\cdot(r-1)}## ##^nC_r+^nC_{r-1}=\dfrac{[n(n-1)(n-2)...(n-r+2)](n-r+1+r)}{1\cdot2\cdot3...\cdot(r-1)\cdot...
  4. A

    Number of ways of arranging 7 characters in 7 spaces

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

    A Uncovering the Combinatorial Origins of Yang-Mills Theory?

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

    Combinations with identical and unidentical objects

    MY ATTEMPT: Case 1: No. of ways of selecting 0 letters-1 Case 2: No of ways of selecting 1 letter: From identical A's- 1 From D E F- 3C1= 3...
  7. S

    Prob/Stats Probability book for basic understanding

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

    Choose 6 pieces of candy from three flavors

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

    Drawing marked balls from an urn

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

    Basic combinatorics: How many ways can 4 boys and 4 girls sit in a row such that no 2 girls sit together?

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

    A railway carriage will accommodate 5 passengers on each side

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

    Let k∈N, Show that there is i∈N s.t (1−(1/k))^i − (1−(2/k))^i ≥ 1/4

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

    Find the total number of ways of coloring the eight regions

    The eight regions
  14. Entropix

    What is the Mixed Arrangements term and formula?

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

    Mastering Combinatorics: Exploring the Formula for Permutations

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

    What benefits can this site offer to increase knowledge and understanding?

    Hi all, It is nice to be a member in this site! Hope it will be beneficial and add to my knowledge and understanding.
  17. N

    B Combinatorics and Magic squares

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

    I Probability Spaces | What You Need to Know

  19. AndreasC

    I Problems involving combinatorics of lattice with certain symmetries

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

    Elements of Combinatorial Analysis

    ##P_m(r + 1, n)= n^{-r}\cdot E_m(r + 1, n), E_m(r + 1, n)= \binom{n}{m} A(r+1, n-m) = \binom{n}{m} \displaystyle\sum_{v=0}^{n-m}(-1)^v \binom{n-m}{v}(n-m-v)^r ## ##P_{m+1}(r, n) = \binom{n}{m} A(r, n-m-1) =\binom{n}{m+1} \displaystyle\sum_{v=0}^{n-m-1}(-1)^v \binom{n-m-1}{v}(n-m-1-v)^r...
  21. L

    MHB Combinatorics: Order in a line by 2 conditions

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

    I Why did I lose 60% on my proof of Generalized Vandermonde's Identity?

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

    MHB Combinatorics: Seats in a parliament

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

    MHB Combinatorics: Ordering a deck of cards

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

    Prob/Stats Books on Combinatorics, Permutations and Probability

    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...
  26. Mayan Fung

    B Distributing N indistinguishable balls into M piles

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

    Combinatorics: Seating Problem

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

    Combinatorics: calculating Oz Lotto odds for divisions

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

    Combinatorics: Counting quadrilaterals in triangle pattern

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

    Yr 10 Combinatorics -- Rearranging the letters of ABRACADABRA per this rule....

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

    Combinatorics and set cardinality

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

    Combinatorics question about the four-letter sequence "GRIT"

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

    I Analytical formula for the number of patterns by using combinations?

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

    Changing the Statement Combinatorial proofs & Contraposition

    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) ##...
  35. C

    Technique for proving Inclusion-Exclusion principle combinatorically

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

    Prob/Stats Top eBook for GRE Probability & Combinatorics Prep - Hi PF Community!

    Hi PF! Does anyone recommend a particular ebook for studying GRE-level questions in probability and combinatorics? I'd really appreciate it!
  37. Isaac0427

    I Weird Combinatorics Question

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

    B Generating Teams to Equally Distribute Papers for Evaluating

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

    Proving Spectrums: K6-$\lambda$I Matrix Trace

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

    Possible webpage title: Can You Solve the No Snap Order Puzzle with Pearls?

    This is my solution however I feel like the number is far too big can anyone see what I’ve done wrong
  41. H

    I What is the value of n in Reverse Combinatorics problem?

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

    Prove expression for N using inclusion-exclusion principle

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

    8 different items into 5 different boxes

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

    I Card Draw Probability with 2 copies of the same card

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

    A Binomial as a sum of tetranomials

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

    A Probability of finding a k-subset in a d-dimensional random

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

    MHB Some fundamental question in combinatorics

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

    Factoring Combinatorial Functions

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

    I A formula for the number of structures composed of n squares

    Hello, The problem I came up with deals with the structures that can be obtained by joining squares side to side or corner to corner. Specifically to this problem, structures, that are symmetrical to each other, are regarded the same. Ideally, I am looking for a formula that will tell how many...
  50. Combinatorics by Dr. L. S. Chandran (NPTEL):- Lecture 01: Pigeon hole principle - (Part 1)

    Combinatorics by Dr. L. S. Chandran (NPTEL):- Lecture 01: Pigeon hole principle - (Part 1)

    COPYRIGHT strictly reserved to Dr. L. S. Chandran and NPTEL, Govt of India. Duplication prohibited. Lectures: http://www.nptel.ac.in/courses/106108051/ Syllabus: http://www.nptel.ac.in/syllabus/syllabus.php?subjectId=106108051
    • Wrichik Basu
    • Media item
    • combinatorics nptel
    • Comments: 0
    • Category: Engineering
Back
Top