Re: [中學] 基礎計數

[cuteSquirrel (可愛的小松鼠)]

※ 引述《Swartz (I_Am_Swatz)》之銘言：
: 從1寫到9999
: 自然數中，5一共寫了多少次?
========================================

生成關係與遞迴解


令數列A_n = n位數字，書寫5的總次數。


初始條件:

A_1 = 一位數字，書寫5的總次數。

顯然，一位數字的情況下，只有5滿足條件，書寫5的總次數為1

A_1 = 1

-----------------------------------------

遞推的生成關係(由下而上推演):


當A_n-1 和 n-1位數字已知的時候，

我們可以在最左邊填上新的最高位，新的最高位表示符號為 "口"，

讓原本n-1位的數字成為n位數字

n位數字的表達式可以寫成: 口 串接 原本的n-1位數字


原本n-1位的數字 在 擴充完之後，原本5的書寫次數仍然存在，

而且原有的5的書寫次數恰好就是 A_n-1 。

擴充之後，相當於拷貝10份原有n-1位數字的5的書寫次數。


另一方面，當最高位 "口" 填上5的時候，又額外多書寫了5。

多了幾次5的書寫次數呢?

多了 10^(n-1)個5。

因為，最高位"口"填上5 固定之後，後面可以串接原本的n-1位數字

從 5 00...0 到 5 99...9 都是合法數字。
   ^           ^
   |           |
最高位       最高位


從生成規則可以知道，

n位數字 5的書寫次數

= A_n

= 10*原本n-1位數字 5的書寫次數 + 擴充最高位之後所多出來的5的書寫次數

= 10*A_n-1 + 10^(n-1)

= 5的書寫次數的遞迴關係數

其中，初始條件就是一開始提到的A_1 = 1


那麼，剩下的工作就回到離散數學，解出遞迴關係一般式的步驟

依序解出 齊次解 和 特解，

可得

    通則:  A_n = n * 10^(n-1), for every n >= 1.

初始條件:  A_1 = 1

========================================

原本題目所求是 四位數字，所以n=4 代入 A_n的通則

可得

A_4

= 4 * 10^3 = 4000

四位數字，5的書寫次數為4000次。




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.206.247 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1710504406.A.DD1.html
※ 編輯: cuteSquirrel (114.37.206.247 臺灣), 03/15/2024 20:45:12
→ Justin890820: 借串問一下 最近在看burnside’s lemma
→ Justin890820: 有辦法轉換成代數問題用orbit個數算嗎？
→ Justin890820: 因為課本上的習題 數骰子塗色方式 感覺都能用排列
→ Justin890820: 組合來解
→ Justin890820: 所以在想是不是排列組合問題都能轉換成代數的group
→ Justin890820:  action來解
推 LPH66       : burnside 主要是用在要數「操作下的同類項」個數
→ LPH66       : 一般的計數問題不一定會有這樣的同類項集出現
推 Justin890820: 了解 謝謝
→ cuteSquirrel: 謝謝