Found problems: 17
Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.[i](IMO Problem 1)[/i]
[b][i]Original formulation [/i][/b]
Let $S$ be a set of $n$ elements. We denote the number of all permutations of $S$ that have exactly $k$ fixed points by $p_n(k).$ Prove:
(a) $\sum_{k=0}^{n} kp_n(k)=n! \ ;$
(b) $\sum_{k=0}^{n} (k-1)^2 p_n(k) =n! $
[i]Proposed by Germany, FR[/i]
$n$ men and one woman are in the meeting room with $n+1$ chairs, each of them having their own seat. Show that the following two number of cases are equal.
(1) Number of cases to choose one man to get out of the room, and make the left $n-1$ men to sit to each other's chair.
(2) Number of cases to make $n+1$ people to sit to each other's chair.
Let $n \ge 2$ be an integer. There are $n$ beads numbered $1, 2, \ldots, n$. Two necklaces made out of some of these beads are considered the same if we can get one by rotating the other (with no flipping allowed). For example, with $n \ge 5$, the necklace with four beads $1, 5, 3, 2$ in the clockwise order is same as the one with $5, 3, 2, 1$ in the clockwise order, but is different from the one with $1, 2, 3, 5$ in the clockwise order.
We denote by $D_0(n)$ (respectively $D_1(n)$) the number of ways in which we can use all the beads to make an even number (resp. an odd number) of necklaces each of length at least $3$. Prove that $n - 1$ divides $D_1(n) - D_0(n)$.
Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.
Prove the following inequality.
\[\frac{e-1}{n+1}\leqq\int^e_1(\log x)^n dx\leqq\frac{(n+1)e+1}{(n+1)(n+2)}\ (n=1,2,\cdot\cdot\cdot) \]
1994 Kyoto University entrance exam/Science
Let $d_n$ denote the number of derangements of the integers $1, 2, \ldots n$ so that no integer $i$ is in the $i^{th}$ position. It is possible to write a recurrence relation $d_{n}=f(n)d_{n-1}+g(n)d_{n-2}$; what is $f(n)+g(n)$?
How many one-to-one functions $f : \{1, 2, \cdots, 9\} \rightarrow \{1, 2, \cdots, 9\}$ satisfy (i) and (ii)?
(i) $f(1)>f(2)$, $f(9)<9$.
(ii) For each $i=3, 4, \cdots, 8$, if $f(1), \cdots, f(i-1)$ are smaller than $f(i)$, then $f(i+1)$ is also smaller than $f(i)$.
Let $n \ge 2$ be an integer. There are $n$ beads numbered $1, 2, \ldots, n$. Two necklaces made out of some of these beads are considered the same if we can get one by rotating the other (with no flipping allowed). For example, with $n \ge 5$, the necklace with four beads $1, 5, 3, 2$ in the clockwise order is same as the one with $5, 3, 2, 1$ in the clockwise order, but is different from the one with $1, 2, 3, 5$ in the clockwise order.
We denote by $D_0(n)$ (respectively $D_1(n)$) the number of ways in which we can use all the beads to make an even number (resp. an odd number) of necklaces each of length at least $3$. Prove that $n - 1$ divides $D_1(n) - D_0(n)$.
Let $Q(x)$ be a polynomial with integer coefficients. Prove that there exists a polynomial $P(x)$ with integer coefficients such that for every integer $n\ge\deg{Q}$,
\[\sum_{i=0}^{n}\frac{!i P(i)}{i!(n-i)!} = Q(n),\]where $!i$ denotes the number of derangements (permutations with no fixed points) of $1,2,\ldots,i$.
[i]Calvin Deng.[/i]
Find the number of even permutations of $ \{1,2,\ldots,n\}$ with no fixed points.
How many ways to fill the board $ 4\times 4$ by nonnegative integers, such that sum of the numbers of each row and each column is 3?
Consider a cube with a fly standing at each of its vertices. When a whistle blows, each fly moves to a vertex in the same face as the previous one but diagonally opposite to it. After the whistle blows, in how many ways can the flies change position so that there is no vertex with 2 or more flies?
The spectators are seated in a row with no empty places. Each is in a seat which does not match the spectator's ticket. An usher can order two spectators in adjacent seats to trade places unless one of them is already seated correctly. Is it true that from any initial arrangement, the spectators can be brought to their correct seats?
Let $Q(x)$ be a polynomial with integer coefficients. Prove that there exists a polynomial $P(x)$ with integer coefficients such that for every integer $n\ge\deg{Q}$,
\[\sum_{i=0}^{n}\frac{!i P(i)}{i!(n-i)!} = Q(n),\]where $!i$ denotes the number of derangements (permutations with no fixed points) of $1,2,\ldots,i$.
[i]Calvin Deng.[/i]
Let $p$ be a permutation of the set $S_n = \{1, 2, \dots, n\}$. An element $j \in S_n$ is called a fixed point of $p$ if $p(j) = j$. Let $f_n$ be the number of permutations having no fixed points, and $g_n$ be the number with exactly one fixed point. Show that $|f_n - g_n| = 1$.
Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.[i](IMO Problem 1)[/i]
[b][i]Original formulation [/i][/b]
Let $S$ be a set of $n$ elements. We denote the number of all permutations of $S$ that have exactly $k$ fixed points by $p_n(k).$ Prove:
(a) $\sum_{k=0}^{n} kp_n(k)=n! \ ;$
(b) $\sum_{k=0}^{n} (k-1)^2 p_n(k) =n! $
[i]Proposed by Germany, FR[/i]
Four boys and four girls each bring one gift to a Christmas gift exchange. On a sheet of paper, each boy randomly writes down the name of one girl, and each girl randomly writes down the name of one boy. At the same time, each person passes their gift to the person whose name is written on their sheet. Determine the probability that [i]both[/i] of these events occur:
[list]
[*] (i) Each person receives exactly one gift;
[*] (ii) No two people exchanged presents with each other (i.e., if $A$ gave his gift to $B$, then $B$ did not give her gift to $A$).[/list]