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.
61,144 questions
0
votes
1
answer
34
views
Number of different values $(\sqrt{a}+\sqrt{b})/c$ can take, where $a,b,c$ are single digit integers
I would appreciate assistance with the following:
"If the following is a simplified expression:
$$\frac{\sqrt{a}+\sqrt{b}}{c}\quad (\star)$$
Such that $a,b$ and $c$ are single digit integers, how ...
- 5,697
0
votes
0
answers
45
views
Attempt to construct every tuple and show that there are $\epsilon_0$ of them
I'm interested in describing the sizes/orders/measure/whatever of tuples using transfinite numbers. For example, you might let $\omega$ represent the set of all natural numbers, while letting $\omega^...
- 160
0
votes
1
answer
74
views
Combinatoric solution to an Oxford interview question about replacing terms in a sequence
An Oxford interview question from a previous year goes like this:
"Starting with the sequence $1,2,\dots,n$, replace two arbitrary terms $x$ and $y$ with $x+y+xy$. Repeat this process until there ...
- 39.9k
-2
votes
0
answers
59
views
In how many parts can a plane be divided by $n$ lines? [duplicate]
I was trying to solve this question from Problem Solving Strategies by Engel. I was able to proof it by recursion, but my doubt is how do I prove it combinatorically, like its said that $n \choose 2$ ...
3
votes
1
answer
142
views
Iranian combinatorics olympiad 2024 problem 3
We say that a sequence $x_1, x_2,\ldots, x_n$ is increasing if $x_i ≤ x_{i+1}$ for all $1 ≤ i < n$. How many ways are there to fill an 8 x 8 table with numbers 1, 2, 3, and 4 such that:
• The ...
- 31
1
vote
0
answers
93
views
How many colours do we need to colour the points in $\mathbb{Z}^{n}$?
This question comes from two problems I've met.
The first problem is: $n$ is a given positive integer, $A$ is a set of $n$ integers, find the minimal $m$, such that for any $A$, it's possible to ...
- 151
-2
votes
0
answers
29
views
Do the Progressive Division Mechanism (PDM) and Common Square Method (CSM) yield results consistent with classical combinatorial counting?
In many grid-based counting problems, combinatorial formulas (e.g., choosing lines, rows, or columns) provide elegant global solutions.
However, these formulas can sometimes feel disconnected from the ...
-3
votes
0
answers
33
views
Verification Request: Step-by-Step Grid Counting Methods (PDM & CSM) [closed]
In many grid-based counting problems, combinatorial formulas (e.g., choosing lines, rows, or columns) provide elegant global solutions. However, these formulas can sometimes feel disconnected from the ...
- 1
2
votes
0
answers
45
views
Coupled Oscillators or "Springs and Masses" (question about sum of binomial coefficients and a reference request)
Suppose $n$ identical masses (each with mass $m$) lie on a friction-less surface and are connected by springs (each with spring constant $k$ and equilibrium length $a$). Let the positions of the ...
- 337
0
votes
1
answer
53
views
grouping ordered partitions of an integer
Consider the number of ways to ordered partition an integer $x > 4$ into $x-4$ ones and $2$ twos. In each of these partitions, we want to split them into at least two groups such that the sum of ...
- 71
-1
votes
0
answers
34
views
How to solve this problem? I just write the proposition from the 4 premise and don't know the solution that followed in style of logic [closed]
Using propositional logic to solve the following problem:
A teacher wants to arrange a teaching schedule for Monday morning. This schedule must satisfy the following four conditions:
Mathematics ...
1
vote
0
answers
66
views
How many possible combinations of a $3\times3$ grid with $5$ red tiles and $4$ blue tiles are there? [closed]
The question is pretty much all in the title.
I have 5 red tiles (R), 4 blue tiles (B), and I need to place them in a $3\times3$ grid. I know this can be done by hand but because I want to make sure I ...
- 19
5
votes
0
answers
68
views
Fixed-points-number distribution for strategically chosen permutation
Let $N \in \mathbb{N}$. We successively construct permutations $$A=(A_1, \dots, A_N), B = (B_1, \dots, B_N) \quad \in \text{Sym}(\{1, \dots, N\}).$$
At each time step $ 1 \leq n \leq N$,
We know $\{...
- 715
6
votes
2
answers
201
views
a very large chess event
Suppose we organize a very large chess event with $1000$ players. Each player plays exactly one game against every other player. Let the notation $a \rightarrow b$ mean that player $a$ beat player $b$....
- 71
5
votes
0
answers
137
views
Does Birkhoff-von Neumann's Theorem easily imply Hall's Marriage Theorem or equivalent?
The following is a collection of combinatorics theorems commonly refereed as "equivalent" due to one being easily derived from another.
Theorem (Hall).
A finite bipartite graph $G = (A\...
- 6,991