XXIII OM - I - Zadanie 9

Ile liczb naturalnych mniejszych od $ 10^n $ ma zapis dziesiętny, którego cyfry tworzą ciąg niemalejący?

Rozwiązanie

Niech $ A $ będzie zbiorem liczb naturalnych mniejszych od $ 10^n $, mających zapis dziesiętny, którego cyfry tworzą ciąg niemalejący. Umówmy się w zapisie każdej z liczb zbioru $ A $ umieszczać tyle zer na początku, by łącznie zapis tej liczby miał $ n $ cyfr.

Niech $ B $ będzie zbiorem liczb naturalnych mniejszych od $ 10^{n+10} $ mających zapis dziesiętny (z zerami na początku), którego cyfry tworzą ciąg niemalejący i w którym występuje każda z dziesięciu cyfr.

Każdemu zapisowi liczby zbioru $ A $ przyporządkujmy zapis, w którym każda cyfra $ 0, 1, 2, \ldots, 9 $ występuje o jeden raz więcej i cyfry tworzą ciąg niemalejący. Przyporządkowanie to określa odwzorowanie $ f $ zbioru $ A $ w zbiór $ B $. Przy tym liczba $ x = \underbrace{00\ldots 0}_{n+1} 12\ldots 9 $ należąca do $ B $ nie odpowiada żadnej liczbie zbioru $ A $.

Odwzorowanie $ f \colon A \to B - \{x\} $ jest wzajemnie jednoznaczne; odwzorowanie do niego odwrotne polega na skreśleniu po jednej cyfrze każdego rodzaju w zapisie liczby zbioru $ B - \{x\} $. Zatem liczba elementów zbioru $ B $ jest o $ 1 $ większa od liczby elementów zbioru $ A $.

Zapis dowolnej liczby zbioru $ B $ składa się z $ n + 10 $ cyfr. Między kolejnymi cyframi jest więc $ n + 9 $ miejsc. Umówmy się w takim zapisie stawiać kreskę między cyframi, jeżeli są one różne. Kresek takich jest $ 9 $, ponieważ różnych cyfr jest $ 10 $ i każda z nich występuje w zapisie liczby zbioru $ B $.

Aby wyznaczyć liczbę elementów zbioru $ B $ zauważmy, że zapis liczby zbioru $ B $ jest jednoznacznie wyznaczony przez dowolne rozmieszczenie $ 9 $ kresek na $ n+9 $ miejscach. Zatem zbiór $ B $ ma $ \displaystyle \binom{n+9}{9} $ elementów, a zbiór $ A $ ma $ \displaystyle \binom{n+9}{9}-1 $ elementów.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź