2020年8月30日 星期日

狀態配對乘法 (State-Pair Multiplication)

http://4rdp.blogspot.com/2020/08/state-pair-multiplication.html

你有沒有想過,乘法其實沒你所想的那麼簡單?

乘法除了算數字之外,還能解排列組合!?

討論問題之前,先看看一個直式乘法

       111111
x      111111
---------------
  12345654321

這個算式跟兩個骰子組合相關,標示出藍字應該更容易理解,

                 1  1  1  1  1  1
x                1  1  1  1  1  1
-----------------------------------
  1  2  3  4  5  6  5  4  3  2  1

 12 11 10  9  8  7  6  5  4  3  2

狀態配對乘法的結果,所代表的是可重複排列組合數量,例如藍字6為兩顆骰子數值總和,共有5種排列方式 (1,5),(2,4),(3,3),(4,2),(5,1)。因為位數不易觀察,以及拓展含零情形,將數值右邊多個零,
                    1  1  1  1  1  1  0
x                   1  1  1  1  1  1  0
-----------------------------------------
  1  2  3  4  5  6  5  4  3  2  1  0  0

 12 11 10  9  8  7  6  5  4  3  2  1  0



如果拓展成三顆骰子,就是 1111110 x 1111110 x 1111110

                                      1  1  1  1  1  1  0
x                                     1  1  1  1  1  1  0
----------------------------------------------------------
                    1  2  3  4  5  6  5  4  3  2  1  0  0
x                                     1  1  1  1  1  1  0
----------------------------------------------------------
                 1  2  3  4  5  6  5  4  3  2  1  0  0
              1  2  3  4  5  6  5  4  3  2  1  0  0
           1  2  3  4  5  6  5  4  3  2  1  0  0
        1  2  3  4  5  6  5  4  3  2  1  0  0
     1  2  3  4  5  6  5  4  3  2  1  0  0
  1  2  3  4  5  6  5  4  3  2  1  0  0
-----------------------------------------------------------
  1  3  6 10 15 21 25 27 27 25 21 15 10  6  3  1  0  0  0

 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0            

注意,每一位單獨乘法結果相加不進位,例如藍字5為三顆骰子數值總和,共有6種排列方式 (1,1,3),(1,3,1),(3,1,1),(1,2,2),(2,1,2),(2,2,1)。


倘若 A + B + C = 6,1 ≤ A ≤ 6,1 ≤ B ≤ 4≤ C ≤ 4,A, B, C ∈ N,請問有多少種排列組合?

那可以計算 1111110 x 11110 x 11111

                          1  1  1  1  1  1  0
x                               1  1  1  1  0
-----------------------------------------------
              1  2  3  4  4  4  3  2  1  0  0
x                               1  1  1  1  1
-----------------------------------------------
              1  2  3  4  4  4  3  2  1
           1  2  3  4  4  4  3  2  1
        1  2  3  4  4  4  3  2  1
     1  2  3  4  4  4  3  2  1
  1  2  3  4  4  4  3  2  1
-----------------------------------------------
  1  3  6 10 14 17 18 17 14 10  6  3  1  0  0

 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0 

藍字 6 為三個正整數值總和,共有14種排列方式 (5,1,0),(4,2,0),(4,1,1),(3,3,0),(3,2,1),(3,1,2),(2,4,0),(2,3,1),(2,2,2),(2,1,3),(1,4,1),(1,3,2),(1,2,3),(1,1,4)。


以上為 Andy 所創建的,我覺得這方法很棒,可以把骰子或是數值總和問題以簡易的方法解出,而且變通性很強,例如把骰子五塗掉,也可以計算,記得之前的一題 骰子機率,Andy 注意到機率分布是對稱,而想到 111111 x 111111 乘法結果也是左右對稱,一比對果真兩者是相關聯的,這也是求解 訓練數學感 263 ─ 骰子機率(二) 的好方法。說真的,組合配對問題跟直式乘法還真的蠻相配。最初他稱這乘法為陣列乘法,但是我覺得無法直接從名稱跟排列組合相映,建議命名為定量組合乘法,他對這名稱不甚滿意,認為無法從名稱細分出重覆與不重複的情形,所以最後討論命名為狀態配對乘法 (或 Andy SP 乘法),會這樣取名的原因,它還可以應用於多項式相乘,這對國中生多項式展開很實用。

例如 (3X² + 2X + 1) (X² + 2) = 3X + 2X³ + 7X² + 4X + 2

        3  2  1
x       1  0  2
-----------------
        6  4  2
  3  2  1
-----------------
  3  2  7  4  2

  4  3  2  1  0 

延伸閱讀

3 則留言:

  1. 請問這個可以用生成函數理解嗎

    回覆刪除
    回覆
    1. 個人認為想用生成函數來理解數列,應該是困難的,首先看 OEIS A047355,這數列是 0, 3, 7, 10, 14, 17, 21, 24, 28, 31, 35, 38, 42, 45, ...,它的生成函數 G.f.: x^2*(3 + 4*x)/((1 + x)*(1 - x)^2),這就是 N 顆骰子總和的中間值,而 OEIS A018901,數列為 1, 1, 6, 27, 146, 780, 4332, 24017, 135954, 767394, ...,這數列是 N 顆骰子組合出中間值的排列數量,因為數值變化過大難以求出生成函數。

      刪除