Articles of combinatorics

How to find the number of distinct combinations of a non distinct set of elements?

I’m trying to figure out a way to find the number of factors a number has based on its prime factorization without working out all the combinations. If the number breaks down into $n$ distinct prime factors I know it’s max number of combinations is $2^n$, with $\frac{n!}{(n-r)!r!}$ being the number of combinations when selecting […]

TicTacToe State Space Choose Calculation

I understand there are numerous questions around the internet about the state space of tic-tac-toe but I have a feeling they’ve usually got it wrong. Alternatively, perhaps it is I who have it wrong. Which is what leads me to my question. Common Over Estimates: Over Estimate One: First some common answers to the number […]

Closing a subcategory under finite colimits by transfinite induction

Let $\mathcal{C}$ be a locally small category with all finite colimits, and let $\mathcal{A}$ be a small full subcategory. I wish to prove the following: Proposition. There exists a full subcategory $\mathcal{B}$ of $\mathcal{C}$ satisfying these conditions: $\mathcal{A} \subseteq \mathcal{B} \subseteq \mathcal{C}$ Finite colimits exist in $\mathcal{B}$ and are the same as in $\mathcal{C}$. Every […]

Odd binomial sum equality has only trivial solution?

Suppose $$\sum_{k\ {\rm odd}}^n {n \choose k} 2^{(k-1)/2} = \sum_{k\ {\rm odd}}^m {m \choose k} 2^{(k-1)/2} 3^{(m-k)/2}.$$ Does $m=n=1$? Clearly $m \leq n$, and for every $n$ there is at most one $m$.

Finding the minimum number of chains of a given poset (partially ordered set)

I’m trying to understand posets better but for the life of me I can’t seem to grasp what is required of a chain. So I am given a poset (P([4]), ⊆), and I am trying to find the minimum number of chains that cover the poset and then list out the chains as a set […]

Given K balls and N buckets what is the expected number of occupied buckets

Given K balls and N buckets how do you calculate the expected number of buckets with at least 1 ball. Each ball is put in a bucket chosen at random with a uniform probability distribution. Assume also K $\leq$ N.

In how many different ways can boys and girls sit a desks such that at each desk only one girl and one boy sits?

There are $n$ boys, $n$ girls and $n$ desks. In how many different ways can boys and girls sit a desks such that at each desk only one girl and one boy sits? I have a solution, but I have a little doubt that it is incomplete. So my solution is as follows: My worked […]

How can I calculate closed form of a sum?

As we know the closed form of $$ {1 \over k} {n \choose k – 1} \sum_{j = 0}^{n + 1 – k}\left(-1\right)^{\, j} {n + 1 – k \choose j}B_{j} = \bbox[10px,border:2px solid #00A000]{{n! \over k!}\, \left[\, z^{n + 1 – k}\,\,\,\right] {z \exp\left(z\right) \over 1 – \exp\left(-z\right)}} $$ where $B_{n}$ the Bernoulli sequence […]

How many ways to get at least one pair in a seven card hand?

This was the question and answer I saw: How many different seven-card hands are there that contain two or more cards of the same rank? Solution: There are C(52,7) total hands. To subtract the ones that don’t have pairs, we observe that such hands have cards of 7 different ranks, and there are C(13,7) ways […]

Minimum Sum that cannot be obtained from the 1…n with some missing numbers

Given positive integers from $1$ to $N$ where $N$ can go upto $10^9$. Some $K$ integers from these given integers are missing. $K$ can be at max $10^5$ elements. I need to find the minimum sum that can’t be formed from remaining $N-K$ elements in an efficient way. Example; say we have $N=5$ it means […]