Articles of combinatorics

Minimum set of US coins to count each prime number less than 100

Say I wanted to be able to carry enough coins in my pocket such that at any time, I could count out exact change totaling any of the prime numbers less than 100. How would I determine the minimum set of coins I would need to carry? I don’t care about being able to count […]

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $ To obtain a closed form.

Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $? Does it have a closed form? It’s the last piece of a puzzle I need to solve a similar question Differentiate $P_{x_n}(z) = \prod_{i=1}^n\frac{1+z+z^2+…+z^{i-1}}{i}$ twice to calculate the variance of involutions. Taking the example $\sum_{i=1}^4 \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) = (\frac{2-1}{2} + \frac{3-1}{2} + \frac{4-1}{2})(\frac{1-1}{2}) + (\frac{1-1}{2} […]

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let’s consider the following two aspects: 1.) IEP transforms at least information to exact information Applying the Inclusion-Exclusion Principle to $n$ sets $A_1,\dots,A_n$ gives: \begin{align*} \left|\bigcup_{j=1}^{n}A_j\right|=\sum_{j=1}^{n}\left|A_j\right| -\sum_{1\leq i \leq j \leq n}\left|A_i\cap A_j\right|\pm\cdots+(-1)^{n-1}\left|\bigcap_{j=1}^{n}A_j\right|\tag{1} \end{align*} We observe that the LHS […]

Combinatorics question about english letters (with consonants and vowels)

The english alphabet contains $21$ consonants and $5$ vowels. How many strings of $6$ lowercase letters of the English alphabet contain a) exactly 1 vowel b) exactly 2 vowels c) at least one vowel d) at least two vowels

Solve a recursion using generating functions?

Given the recursive equation : $$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$ A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we’ll get : $$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$ Now subtracting both equations : $$F_n+F_{n-1}+⋯+F_0 – (F_{n-1}+F_{n-2}+⋯+F_0) = 3^n – 3^{n-1} $$ $$ F_n = 3^n – 3^{n-1}$$ But how can I do that […]

Finding the probability that red ball is among the $10$ balls

A box contains $20$ balls all of different colors including the red color. If we select $10$ balls randomly without replacement, what is the probability that the red ball will be among these $10$ balls? What I think is that: If we let $X$ to be the number of balls we select until we get […]

How prove this there exsit set $B$ such $card(B)>\dfrac{n}{3}$,

Question: Let $a_{i}\in N^{+}$, and the set $A=\{a_{1},a_{2},\cdots,a_{n}\}$, show that: There exists a set $B\subset A$, such that $card(B)>\dfrac{n}{3}$, and that for any $x,y\in B$, then $x+y\notin B$. This problem is from China Nankai university math competition today. How prove this? Thank you. Maybe this problem is an old problem, but I can’t find it. […]

How Many Ways to Make a Pair Given Five Poker Cards

I’m confused at the general method of solving this type of problem. The wikipedia page says that there are: ${13 \choose 1} {4 \choose 2} {12 \choose 3} {4 \choose 1}^{3}$ ways to select a pair when 5 cards are dealt. Can someone outline what each calculation means? For example, is $13 \choose 1$ the […]

Probability of having exactly 1 pair from drawing 5 cards

I have an exercise as follows: There is a collection of cards consisting of 52 cards (13 types and 4 colours each type). We draw 5 cards from the collection. Then what is the probability of having exactly 1 pair (pair means same colour or same type)? Thanks for any indication.

Combinatorics, equality, $n$-permutations with $k$ cycles

Let $b_r(n,k)$ denote the number of $n$-permuations with $k$ cycles in which all numbers: $1,…,r$ are in one cycle. Prove that for $n \ge r$, $\sum _{k=1} ^n b_r(n,k) x^k = (r-1)! \frac{x^{\overline{n}}}{(x+1)^{\overline{r-1}}}$. Here $x^{\overline{n}} = x(x+1)…(x+n-1)$ I’ve been thinking of using induction to prove it. But I don’t know which variable to choose – […]