Articles of combinatorics

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

Problem with concepts of circular permutation.

I am having problem in understanding this concept: Circular permutation : The definition in my book goes like that ‘ Arrangements of things in a circle or a ring are called circular permutations. The fundamental difference between linear and that of circular permutation is that in the former, there are always two separate ends but […]

The number of permutations with descents at specified positions $1 \leq a_1 < a_2 < \cdots < a_m \leq n-1$

(a) We say that a permutation $\sigma$ of $[n]$ has a descent at position $i$ if $\sigma(i) > \sigma(i+1)$. Let $a_1,\dotsc,a_m$ be integers, with $1 \leq a_1 \lt \dotso \lt a_m \leq n-1$. Use inclusion-exclusion to show that the number of permutations of $\{ 1, 2, \ldots, n \}$ with descents at positions $a_1, \dotsc, […]