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,196 questions
0
votes
1
answer
39
views
What is the probability that a bus will skip the first stop?
Suppose that there are $k$ stops and $n$ passengers on the bus, including yourself. You are going to get off at the second stop and want to know what the probability is that nobody on the bus needs to ...
- 3,403
1
vote
0
answers
56
views
Possible arrangements for any n number of distinct cubes
This problem has been bouncing around in my head for years, and I can't seem to make progress. I'll give the rules.
Cubes are all uniform in size with an edge length of 1 unit.
Cubes are located ...
- 11
3
votes
0
answers
102
views
Number of integer solutions to $\sum_{i=1}^{10} x_i = 100$ with $2 \le x_i \le 21$
I am trying to solve a combinatorial problem involving finding the number of integer solutions to the following equation:
$$ x_1 + x_2 + \dots + x_{10} = 100 $$
Subject to the constraints:
$$ 2 \le ...
0
votes
0
answers
43
views
Digital Roots in Pascal's Triangle
I know that in Pascal's Triangle there are wonderful patterns (Sierpinski's Triangle one example) that result from highlighting the multiples of a certain prime number, for example only highlighting ...
- 1
0
votes
0
answers
27
views
Finding an exact closed (non-recursive) form formula for the probabilities in a game of Risk
Yesterday I enjoyed some rounds of RISK: Global Domination with a friend from university. It is a long-running in-joke that “True Random” is the cause of winning and losing certain battles.
Our ...
- 2,584
4
votes
0
answers
50
views
Optimal signaling to recover an element’s position in a k-set
Given integers $n$ and $k$, Alice is given $k$ numbers $1 \le a_1 < a_2 < \cdots < a_k \le n$. She then writes down a message $x\ (1 \le x \le m)$. Bob is given the message $x$ and one ...
- 595
-3
votes
0
answers
63
views
Is it valid to compare solving vs checking NP problems using average time per logical step?
I’ve been exploring a measurement approach for NP and NP-complete problems based on average time per logical step.
I define:
...
2
votes
1
answer
46
views
Upper bound on the intersection of two radius-$r$ Hamming balls in binary constant-weight codes when codewords are at Hamming distance 2
Let $\mathcal{B}(n,w)$ be the set of all binary vectors of length $n$ and constant weight $w$, i.e.,
$\mathcal{B}(n,w) = \{ x \in \{0,1\}^n : \mathrm{wt}(x) = w \}$.
The Hamming ball of radius $r$ (in ...
- 21
3
votes
0
answers
90
views
Cases $n=7,8$ of a conjecture on semigroups
[Crossposted at mathoverflow and AoPS].
I would like to prove cases $n=7,8$ of this conjecture (general question asked here): given any commutative semigroup $S$ of order $n \ge 1$, there exist $a, b \...
- 2,405
2
votes
1
answer
65
views
Using Polya and Cycle Index
I have a D6 hexagon with edges connecting vertices 1,3,5 and 2,4,6. I'm supposed to find the number of different, proper colorings for the shape with 4 colors. I'm considering the symmetries and ...
- 23
2
votes
0
answers
52
views
Size of family of pairs of edges overlapping at exactly 1 vertex in a non two colorable hypergraph
Show that every n-uniform non 2 colorable hypergraph $H$ contains atleast $\frac{n}{2} {2n-1 \choose n-1}$ unordered pairs of edges each overalapping at exactly 1 vertex. I came across this problem in ...
0
votes
0
answers
84
views
approximation formula like Stirling’s for factorial for the number of Dispositions
My name is Alessandro Falconi and I write from Calcata, Italy.
Question:
Is there any approximation formule like Stirling’s for factorial for
the number of Combination:
$$\frac{N!}{K!(N-K)!}$$
for $N=...
7
votes
3
answers
257
views
Minimum size of a sequence summing to $2013$ that guarantees a consecutive subset sum of $31$ (still wanted rigorous proof)
I am trying to solve the following problem on integer sequences and subset sums from a 2023 Shanghai high school entrance exam:
Let $A = (a_1, a_2, \dots, a_n)$ be a sequence of positive integers ...
0
votes
1
answer
126
views
Given that $a_n \sim \operatorname{Unif}[0,n]$, calculate $\mathbb{P}(a_1 < \cdots < a_5)$
Let $a_n \sim \operatorname{Unif}[0,n]$ be a sequence independent uniform random variables. The goal of the problem is to find the probability that the first 5 of these random variables turn out to be ...
- 672
4
votes
1
answer
275
views
Winnability of an urn-ball game with restricted two-urn moves
My question is about a certain combinatorial game. The game works as follows. We have $n$ urns, each of which contains $m$ balls, where $m$ and $n$ are positive and satisfy $m < n$. A move consists ...
- 728