Articles of combinatorics

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 […]

Number of ways to put N items into K bins with at least 1 per bin?

Possible Duplicate: Unique ways to keep N balls into K Boxes? Number of ways to put N items into K bins with at least 1 per bin? I know that normally you can do N + K + 1 choose K – 1 or something like that, but that allows for bins where nothing is […]

How many ways are there to color vertexes of a $n\times n$ square that in every $1\times 1$ squares we should have $2$ blue and $2$ red vertexes?

How many ways are there to color vertexes of a $n\times n$ square that in every $1\times 1$ squares we should have $2$ blue and $2$ red vertexes? My attempt:I had found an answer but it is not in the book because for the first corner we can choose two vertexes to color blue which […]

Combinatorics: Color a wall such that not two neighbored slots have the same color

We have a wall with $7$ slots. We can color the wall either with blue or red. How many combinations do we have to color the wall if two red slots cannot be neighbors? I thought, in a very intuitive way, to try all the different cases. For example if color $0$ slots of red, […]