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.

59,052 questions
Filter by
Sorted by
Tagged with
61 views

• 2,214
29 views

Maxflow-mincut implies Menger (vertices)

I was studying graph theory when a question came to my mind. I am trying to understand a proof of the Menger's theorem (vertex version) using the maxflow-mincut (capacity on vertices). I think I miss ...
1 vote
31 views

Prove $\sum_{j=0}^{n} q^{j^{2}}\binom{n}{j}_{q^{2}}$ generates the self-conjugate partitions with part at most $n$.

Prove $\sum_{j=0}^{n} q^{j^{2}}\binom{n}{j}_{q^{2}}$ generates the self-conjugate partitions with part at most $n$, and that it equals $(1+q)(1+q^{3})\cdot\cdot\cdot(1+q^{2n-1})$. For the first part, ...
• 607
1 vote
30 views

Prove the q-Vandermonde identity $\binom{m+n}{k}_{q} = \sum_{j} \binom{m}{k-j}_{q}\binom{n}{j}q^{(n-j)(k-j)}$ using q-commuting variables

I have seen a few questions on here surrounding the q-Vandermonde identity but in a different form. I've yet to find a proof that uses q-commuting variables. Does anybody have any suggestions on how ...
• 607
49 views

Maximum coins with one Counterfeit coin among them that can be determined in 3 weighings given that the coin can be heavier or lighter

What is the largest number of coins from which one can detect a counterfeit in three weighings with a pan balance, if it is known in advance only that the counterfeit coin differs in weight from the ...
• 39
18 views

Combinatorics: How to use the tree dissymmetry theorem to find singularities?

Denote by $T(z)$ the exponential generating function of the class $\mathcal{T}$ of labelled (unrooted) trees in which all vertices have degree $1$ or $3$. Use the tree dissymmetry theorem (see below) ...
• 4,200
1 vote
42 views

Zarankiewicz’s conjecture

The Turán's brick factory problem asks for the minimum number of crossings in a drawing of a complete bipartite graph. A few years later, Zarankiewicz published a formula that provided a solution to ...
• 525
24 views

78 views

Formula for most likely total number of steps in a probability simulation with n coins? [closed]

Suppose there are a total of n coins that can flip either heads or tails and n is even. The bias of these coins can change with each step. Initially there an equal number of coins showing heads and ...