IMO 1987 · Problem 1
Let \(p_n(k)\) be the number of permutations of the set \(\{1,\ldots,n\}\), \(n\geq 1\), which have exactly \(k\) fixed points. Prove that \[ \sum_{k=0}^{n} k\cdot p_n(k)=n!. \]
(Remark: A permutation \(f\) of a set \(S\) is a one-to-one mapping of \(S\) onto itself. An element \(i\) in \(S\) is called a fixed point of the permutation \(f\) if \(f(i)=i\).)
Official text of the problem. Official problem paper (PDF)
Solution
We count in two ways the pairs \((f,i)\), where \(f\) is a permutation of \(\{1,\ldots,n\}\) and \(i\) is a fixed point of \(f\).
A permutation with exactly \(k\) fixed points occurs in exactly \(k\) such pairs. Since there are \(p_n(k)\) such permutations, the total number of pairs is \[ \sum_{k=0}^{n} k\,p_n(k). \]
Alternatively, choose \(i\) first, in \(n\) ways. A permutation fixing \(i\) restricts to a permutation of the remaining \(n-1\) elements. Conversely, every permutation of those remaining elements extends uniquely to a permutation fixing \(i\). Thus there are exactly \((n-1)!\) choices for \(f\), giving \[ n(n-1)!=n! \] pairs. This also holds for \(n=1\), since the empty set has exactly one permutation and \(0!=1\).
Equating the two counts proves \[ \boxed{\sum_{k=0}^{n} k\,p_n(k)=n!}. \]
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1987 · Aufgabe 1
Sei \(p_n(k)\) die Anzahl der Permutationen der Menge \(\{1,\ldots,n\}\), \(n\geq 1\), die genau \(k\) Fixpunkte haben. Man beweise, dass \[ \sum_{k=0}^{n} k\cdot p_n(k)=n!. \]
(Bemerkung: Eine Permutation \(f\) einer Menge \(S\) ist eine bijektive Abbildung von \(S\) auf sich selbst. Ein Element \(i\) von \(S\) heißt Fixpunkt der Permutation \(f\), wenn \(f(i)=i\).)
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Lösung
Wir zählen auf zwei Arten die Paare \((f,i)\), wobei \(f\) eine Permutation von \(\{1,\ldots,n\}\) und \(i\) ein Fixpunkt von \(f\) ist.
Eine Permutation mit genau \(k\) Fixpunkten kommt in genau \(k\) solchen Paaren vor. Da es \(p_n(k)\) solche Permutationen gibt, beträgt die Gesamtzahl der Paare \[ \sum_{k=0}^{n} k\,p_n(k). \]
Alternativ wählen wir zuerst \(i\), wofür es \(n\) Möglichkeiten gibt. Die Einschränkung einer Permutation, die \(i\) festlässt, auf die übrigen \(n-1\) Elemente ist eine Permutation dieser Elemente. Umgekehrt lässt sich jede Permutation dieser übrigen Elemente eindeutig zu einer Permutation erweitern, die \(i\) festlässt. Somit gibt es genau \((n-1)!\) Möglichkeiten für \(f\), was \[ n(n-1)!=n! \] Paare ergibt. Dies gilt auch für \(n=1\), da die leere Menge genau eine Permutation besitzt und \(0!=1\) gilt.
Durch Gleichsetzen der beiden Anzahlen erhalten wir \[ \boxed{\sum_{k=0}^{n} k\,p_n(k)=n!}. \]
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1987 · Soru 1
\(n\geq 1\) olmak üzere, \(p_n(k)\), \(\{1,\ldots,n\}\) kümesinin tam olarak \(k\) sabit noktası olan permütasyonlarının sayısı olsun. Aşağıdaki eşitliği kanıtlayınız: \[ \sum_{k=0}^{n} k\cdot p_n(k)=n!. \]
(Açıklama: Bir \(S\) kümesinin bir \(f\) permütasyonu, \(S\)'den kendisine bire bir ve örten bir dönüşümdür. \(S\)'nin bir \(i\) elemanı, \(f(i)=i\) ise \(f\) permütasyonunun sabit noktası olarak adlandırılır.)
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Çözüm
\(f\), \(\{1,\ldots,n\}\) kümesinin bir permütasyonu ve \(i\), \(f\)'nin bir sabit noktası olmak üzere, \((f,i)\) ikililerini iki farklı yoldan sayalım.
Tam olarak \(k\) sabit noktası olan bir permütasyon, bu tür ikililerin tam olarak \(k\) tanesinde yer alır. Böyle \(p_n(k)\) permütasyon olduğundan, ikililerin toplam sayısı \[ \sum_{k=0}^{n} k\,p_n(k). \]
Diğer yoldan saymak için önce \(i\)'yi \(n\) farklı şekilde seçelim. \(i\)'yi sabit bırakan bir permütasyonun kalan \(n-1\) elemana kısıtlanması, bu elemanların bir permütasyonudur. Tersine, kalan elemanların her permütasyonu, \(i\)'yi sabit bırakan bir permütasyona tek bir şekilde genişletilir. Dolayısıyla \(f\) için tam olarak \((n-1)!\) seçenek vardır ve bu da \[ n(n-1)!=n! \] ikili verir. Boş kümenin tam olarak bir permütasyonu olduğundan ve \(0!=1\) olduğundan, bu sonuç \(n=1\) için de geçerlidir.
İki sayımın sonuçlarını eşitleyerek \[ \boxed{\sum_{k=0}^{n} k\,p_n(k)=n!} \] eşitliğini kanıtlamış oluruz.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1987 · Problema 1
Sea \(p_n(k)\) el número de permutaciones del conjunto \(\{1,\ldots,n\}\), \(n\geq 1\), que tienen exactamente \(k\) puntos fijos. Demostrar que \[ \sum_{k=0}^{n} k\cdot p_n(k)=n!. \]
(Observación: Una permutación \(f\) de un conjunto \(S\) es una aplicación biyectiva de \(S\) sobre sí mismo. Un elemento \(i\) de \(S\) se llama punto fijo de la permutación \(f\) si \(f(i)=i\).)
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Solución
Contamos de dos maneras los pares \((f,i)\), donde \(f\) es una permutación de \(\{1,\ldots,n\}\) e \(i\) es un punto fijo de \(f\).
Una permutación con exactamente \(k\) puntos fijos aparece en exactamente \(k\) de estos pares. Como hay \(p_n(k)\) permutaciones de este tipo, el número total de pares es \[ \sum_{k=0}^{n} k\,p_n(k). \]
Por otra parte, elegimos primero \(i\), lo que puede hacerse de \(n\) maneras. La restricción de una permutación que fija \(i\) a los \(n-1\) elementos restantes es una permutación de estos. Recíprocamente, toda permutación de esos elementos restantes se extiende de manera única a una permutación que fija \(i\). Por tanto, hay exactamente \((n-1)!\) posibilidades para \(f\), lo que da \[ n(n-1)!=n! \] pares. Esto también es válido para \(n=1\), pues el conjunto vacío tiene exactamente una permutación y \(0!=1\).
Al igualar ambos recuentos se obtiene \[ \boxed{\sum_{k=0}^{n} k\,p_n(k)=n!}. \]
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1987 · 问题 1
设 \(p_n(k)\) 表示集合 \(\{1,\ldots,n\}\)（\(n\geq 1\)）的恰有 \(k\) 个不动点的排列的个数。证明 \[ \sum_{k=0}^{n} k\cdot p_n(k)=n!. \]
（注：集合 \(S\) 的一个排列 \(f\) 是从 \(S\) 到自身的一一映射。若 \(S\) 中的元素 \(i\) 满足 \(f(i)=i\)，则称 \(i\) 为排列 \(f\) 的一个不动点。）
题目译自官方英文原文。 官方试卷 (PDF)
解答
我们用两种方法计算有序对 \((f,i)\) 的个数，其中 \(f\) 是 \(\{1,\ldots,n\}\) 的一个排列，\(i\) 是 \(f\) 的一个不动点。
一个恰有 \(k\) 个不动点的排列恰好出现在 \(k\) 个这样的有序对中。由于这样的排列共有 \(p_n(k)\) 个，有序对的总数为 \[ \sum_{k=0}^{n} k\,p_n(k). \]
另一方面，先选择 \(i\)，共有 \(n\) 种选法。一个固定 \(i\) 的排列限制在其余 \(n-1\) 个元素上，就得到这些元素的一个排列。反过来，其余这些元素的每一个排列都能唯一地扩充为一个固定 \(i\) 的排列。因此，\(f\) 恰有 \((n-1)!\) 种选法，从而有序对共有 \[ n(n-1)!=n! \] 个。这对 \(n=1\) 也成立，因为空集恰有一个排列，且 \(0!=1\)。
令两种方法所得的计数相等，即得 \[ \boxed{\sum_{k=0}^{n} k\,p_n(k)=n!}. \]
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1987 · Задача 1
Пусть \(p_n(k)\) — число перестановок множества \(\{1,\ldots,n\}\), \(n\geq 1\), имеющих ровно \(k\) неподвижных точек. Докажите, что \[ \sum_{k=0}^{n} k\cdot p_n(k)=n!. \]
(Замечание: Перестановкой \(f\) множества \(S\) называется взаимно однозначное отображение \(S\) на себя. Элемент \(i\) множества \(S\) называется неподвижной точкой перестановки \(f\), если \(f(i)=i\).)
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Решение
Подсчитаем двумя способами пары \((f,i)\), где \(f\) — перестановка множества \(\{1,\ldots,n\}\), а \(i\) — неподвижная точка \(f\).
Перестановка, имеющая ровно \(k\) неподвижных точек, входит ровно в \(k\) таких пар. Поскольку таких перестановок \(p_n(k)\), общее число пар равно \[ \sum_{k=0}^{n} k\,p_n(k). \]
С другой стороны, сначала выберем \(i\), что можно сделать \(n\) способами. Ограничение перестановки, оставляющей \(i\) на месте, на остальные \(n-1\) элементов является перестановкой этих элементов. Обратно, любая перестановка этих остальных элементов единственным образом продолжается до перестановки, оставляющей \(i\) на месте. Таким образом, имеется ровно \((n-1)!\) вариантов выбора \(f\), что даёт \[ n(n-1)!=n! \] пар. Это верно и при \(n=1\), поскольку пустое множество имеет ровно одну перестановку и \(0!=1\).
Приравнивая результаты двух подсчётов, получаем \[ \boxed{\sum_{k=0}^{n} k\,p_n(k)=n!}. \]
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1987 · المسألة 1
ليكن \(p_n(k)\) عدد تبديلات المجموعة \(\{1,\ldots,n\}\)، حيث \(n\geq 1\)، التي لها بالضبط \(k\) نقاط ثابتة. أثبت أن \[ \sum_{k=0}^{n} k\cdot p_n(k)=n!. \]
(ملاحظة: تبديل \(f\) لمجموعة \(S\) هو تطبيق تقابلي من \(S\) إلى نفسها. ويُسمّى العنصر \(i\) من \(S\) نقطة ثابتة للتبديل \(f\) إذا كان \(f(i)=i\).)
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الحل
نعدّ بطريقتين الأزواج \((f,i)\)، حيث \(f\) تبديل للمجموعة \(\{1,\ldots,n\}\) و\(i\) نقطة ثابتة له.
كل تبديل له بالضبط \(k\) نقاط ثابتة يظهر في \(k\) أزواج من هذا النوع بالضبط. وبما أن عدد هذه التبديلات هو \(p_n(k)\)، فإن العدد الكلي للأزواج هو \[ \sum_{k=0}^{n} k\,p_n(k). \]
وبطريقة أخرى، نختار \(i\) أولًا، وذلك بـ\(n\) طرق. تقييد أي تبديل يثبت \(i\) على العناصر \(n-1\) المتبقية هو تبديل لهذه العناصر. وبالعكس، يمتد كل تبديل لتلك العناصر المتبقية على نحو وحيد إلى تبديل يثبت \(i\). ومن ثم يوجد بالضبط \((n-1)!\) اختيارًا لـ\(f\)، فنحصل على \[ n(n-1)!=n! \] زوجًا. ويصح ذلك أيضًا عندما \(n=1\)، إذ إن للمجموعة الخالية تبديلًا واحدًا بالضبط، و\(0!=1\).
وبمساواة العددين نثبت أن \[ \boxed{\sum_{k=0}^{n} k\,p_n(k)=n!}. \]
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).