Articles of combinatorics

Proving the existence of disjoint subsets

Let $A$ be a set of cardinality $n$ and let $A_1,…,A_{n+1}$ be subsets of $A$. Prove that there are disjoint nonempty $I,J\subset\{1,…,n+1\}$ satisfying $$\bigcup_{i\in I}A_i=\bigcup_{j\in J}A_j.$$ I’ve been stuck on this problem for awhile – not quite sure how to start. Thus far in the course we’ve been studying vector spaces, subspaces, bases, etc. Edit: […]

How to distribute $k$ prizes in $p$ student with each student would receive $(k-1)$ prizes at most?

A teacher decided to encourage the kids by distributing prizes to them. Each of the prizes was different from the other. The total number of prize was $k$, and total number of kids was $p$. To encourage the kids, the number of prizes was more than the number of kids. But, the teacher imposed a […]

find the number of five digit combinations from the set ${1,2,3,4,5}$ where some digits occur at least three times

So to solve this, I started with the total and subtract where some digit occurs only once or twice. Total = $5^5$ Digits are only used once $= 5! = 120$ Digits occur twice: I’m starting to think this is where the inclusion exclusion comes into play because as lulu pointed out, AABCD can occur […]

Find the total number of partitions of $12$ having unequal positive parts.

$P(k, n) = P(k – 1, n – 1) + P(k – n, n)$ Let $P^\star(k,n)$ denote the number of partitions of $k$ having exactly $n$ positive parts, all of which are unequal. For example, $P(8, 3)$ implies $8$ can be partitioned as $8 = 2 + 2 + 4,$ but $P^\star(8,3)$ does not. $P^\star(k, […]

How many distinct football teams of 11 players can be formed with 33 men?

Can anyone help me with this problem, I can’t figure out how to solve it… How many distinct football teams can be formed with 33 men? Thanks!

Finding Binomial expansion of a radical

I am having trouble finding the correct binomial expansion for $\dfrac{1}{\sqrt{1-4x}}$: Simplifying the radical I get: $(1-4x)^{-\frac{1}{2}}$ Now I want to find ${n\choose k} = {\frac{-1}{2}\choose k}$ \begin{align} {\frac{-1}{2}\choose k} &= \dfrac{\frac{-1}{2}(\frac{-1}{2}-1)(\frac{-1}{2}-2)\ldots(\frac{-1}{2}-k+1)}{k!} \\ &= (-1)^k\dfrac{\frac{1}{2}(\frac{1}{2}+1)(\frac{1}{2}+2)\ldots(\frac{1}{2}+k-1)}{k!} \\ &=(-1)^k{\frac{1}{2}+k-1\choose k} \end{align} Now, applying Newton’s Generalized Binomial Theorem I get: \begin{equation}\sum\limits_{k=0}^\infty(-1)^k{\frac{1}{2}+k-1\choose k}(4x)^k \end{equation} Is this correct? it seems […]

How many elements of order 4 does $S_6$ have?

I am trying to count the number of elements of order 4 in $S_6,$ but my answer is not matching the one in the back of the book. Here’s my attempt: Such elements are either of the form $(6543)(21)$ or $(6543).$ For the first type, we have $6!/(4\cdot2\cdot2)$ possibilities, where the second divisor $2$ arises […]

Rooks Attacking Every Square on a Chess Board

8 rooks are randomly placed on different squares of a chessboard. A rook is said to attack all of the squares in its row and its column. Compute the probability that every square is occupied or attacked by at least 1 rook. The first step I took was to state that there are $64C8$ ways […]

Probability of predicting, then throwing, a particular multiset for 5 dice.

My friend shared with me a story that after losing to his SO at Yahtzee, before they put the game away he just randomly predicted he would roll four 5’s and a 1. He then got that roll and freaked out. I wanted to calculate exactly how likely that was but my combinatorics knowledge isn’t […]

Prove $\sum_{j=0}^n \left(-\frac{1}{2}\right)^j \binom{n}{j}\binom{n+j}{j}\binom{j}{k} = 0$ when $n+k$ is odd

An integral led me to a power series with these coefficients: $$a_k = \sum_{j=k}^n \left(-\frac{1}{2}\right)^j \binom{n}{j}\binom{n+j}{j}\binom{j}{k}$$ I strongly suspect that the series should have $a_k = 0$ when $n+k$ is odd, and I’ve verified it for $k,n\leq 10$. I’m looking for a direct proof of this. Does anyone have a suggestion?