Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [combinatorics]

For questions about the study of finite or countable discrete structures, especially how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

Combinatorics is the study of finite or countable discrete structures — especially enumerative combinatorics: how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. This tag can be used for questions about permutations, combinations, partially ordered sets, bijection proofs, and generating functions.

Questions about:

These tags may be used alone or together with .

To learn more about enumerative combinatorics, see Wikipedia.

58658 questions
95
votes
2 answers

$6!\cdot 7!=10!$. Is there a natural bijection between $S_6\times S_7$ and $S_{10}$?

Aside from $1!\cdot n!=n!$ and $(n!-1)!\cdot n! = (n!)!$, the only product of factorials known is $6!\cdot 7!=10!$. One might naturally associate these numbers with the permutations on $6, 7,$ and $10$ objects, respectively, and hope that this…
RavenclawPrefect
  • 17,299
52
votes
4 answers

A zero sum subset of a sum-full set

I had seen this problem a long time back and wasn't able to solve it. For some reason I was reminded of it and thought it might be interesting to the visitors here. Apparently, this problem is from a mathematics magazine of some university in the…
Aryabhata
  • 82,206
45
votes
14 answers

Why is the number of ways of choosing $0$ items from $n$ items $1$?

It seems easy to grasp that number of ways of choosing $n$ items from $n$ items is 1. But I am unable to understand why is it 1 for choosing 0 items.
subba
  • 585
42
votes
16 answers

Why do you add +1 in counting test questions?

Here's an example question from the SAT question of the day: On the last day of a one-week sale, customers numbered 149 through 201 were waited on. How many customers were waited on that day? Possible answers: 51, 52, 53, 152, 153. The correct…
ian5v
  • 531
  • 1
  • 4
  • 8
42
votes
2 answers

Numbers on blackboard

All numbers $1$ to $155$ are written on a blackboard, one time each. We randomly choose two numbers and delete them, by replacing one of them with their product plus their sum. We repeat the process until there is only one number left. What is the…
Yousha Tagor
  • 391
40
votes
5 answers

Six real numbers so that product of any five is the sixth one

One needs to choose six real numbers $x_1,x_2,\cdots,x_6$ such that the product of any five of them is equal to other number. The number of such choices is A) $3$ B) $33$ C) $63$ D) $93$ I believe this is not so hard problem but I got no clue to…
ChakSayantan
  • 1,069
36
votes
11 answers

How many ways can seven people sit around a circular table?

How many ways seven people can sit around a circular table? For first, I thought it was $7!$ (the number of ways of sitting in seven chairs), but the answer is $(7-1)!$. I don't understand how sitting around a circular table and sitting in seven…
omidh
  • 876
34
votes
5 answers

Number of ways of distributing $n$ identical objects among $r$ groups

I came across this formula in a list: The number of ways of distributing $n$ identical objects among $r$ groups such that each group can have $0$ or more $(\le n)$ objects I know that standard way of doing this is to solve the problem of…
user118102114
  • 585
32
votes
7 answers

Prove that $\frac{100!}{50!\cdot2^{50}} \in \Bbb{Z}$

I'm trying to prove that : $$\frac{100!}{50!\cdot2^{50}}$$ is an integer . For the moment I did the following : $$\frac{100!}{50!\cdot2^{50}} = \frac{51 \cdot 52 \cdots 99 \cdot 100}{2^{50}}$$ But it still doesn't quite work out . Hints anyone ?…
JAN
  • 2,379
32
votes
5 answers

Iteratively replacing $3$ chocolates in a box of $10$

In the fridge there is a box containing 10 expensive high quality Belgian chocolates, which my mum keeps for visitors. Every day, when mum leaves home for work, I secretly pick 3 chocolates at random, I eat them and replace them with ordinary cheap…
Sal.Cognato
  • 1,527
31
votes
3 answers

How to prove that the number $1!+2!+3!+...+n!$ is never square?

How to prove that the number $1!+2!+3!+...+n! \ \forall n \geq 4$ is never square? I was told to count permutations but I cannot figure out what we are permuting.... Thanks!
Adam L.
  • 569
30
votes
2 answers

a problem from 1977 all Soviet Union Mathematical Olympiad

Seven dwarfs are sitting at a round table. Each has a cup, and some cups contain milk. Each dwarf in turn pours all his milk into the other six cups, dividing it equally among them. After the seventh dwarf has done this, they find that each cup…
yiyi
  • 7,352
29
votes
11 answers

How many positive integers $< 1{,}000{,}000$ contain the digit $2$?

How many positive integers less than $1{,}000{,}000$ have the digit $2$ in them? I could determine it by summing it in terms of the number of decimal places, i.e. between $999{,}999$ and $100{,}000$, etc. Then to determine the number of numbers…
math1234567
  • 1,736
28
votes
3 answers

Counting matchings, the modern way

A hundred years ago, if you had $k$ men and $k$ women and wanted to marry them all off in pairs, it was easy to see that there are exactly $k!$ ways to do that. Today, however, societal standards have evolved, and many countries now recognize…
hmakholm left over Monica
  • 286,031
27
votes
5 answers

Is it possible to put $+$ or $-$ signs in such a way that $\pm 1 \pm 2 \pm \cdots \pm 100 = 101$?

I'm reading a book about combinatorics. Even though the book is about combinatorics there is a problem in the book that I can think of no solutions to it except by using number theory. Problem: Is it possible to put $+$ or $-$ signs in such a way…
user66733
  • 7,379
1
2 3
…
99 100