作者znmkhxrw (QQ)
看板Math
標題[代數] 找兩個離散函數的顯式
時間Fri Aug 18 01:03:25 2023
請教一下這個問題:
令N為自然數
令S:= N+(N-1)+...+1 = (N+1)*N/2
令i€{1,2,...,S}
我們把S拆成N, N-1, N-2,...,1共N組, 第一組有N個1加起來, 第N組有1個1加起來
即第k組有(N-k+1)個1加起來
因此對於任何i, 我們都能定義一組唯一的數對i=(a_i, b_i)
其中a_i是所在的第幾組, b_i是這一組的第幾個(照i遞增排列)
如下N=4的舉例:
S = 10
i€{1,2,...,10}
N=4: i=1 → (a_i,b_i) = (1,1)
=2 = (1,2)
=3 = (1,3)
=4 = (1,4)
N-1=3: i=5 → (a_i,b_i) = (2,1)
=6 = (2,2)
=7 = (2,3)
N-2=2: i=8 → (a_i,b_i) = (3,1)
=9 = (3,2)
N-3=1: i=10 → (a_i,b_i) = (4,1)
我想問對於任何的正整數N, i€{1,..,S}
a_i跟b_i有沒有顯式公式
(我知道電腦用loop逐次從N開始減, 還有剩就組數加1, 然後繼續減N-1
直到即將減的下一個導致負數的時就知道是在當前這組
但是我的需求是a_i與b_i的函數長相通式)
謝謝幫忙~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.137.78 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1692291807.A.7EE.html
1F：推 Vulpix : a_i = ceil( N+0.5 - sqrt( (N+0.5)^2 - 2i ) )08/18 10:21
2F：→ Vulpix : b_i = i - a_i( a_i - 1 )/208/18 10:22
哇V大這怎麼找的啊 這長相難怪我用線性的式都式不出來XDDD 好猛
3F：推 Vulpix : 就解不等式啊:)08/18 18:13
4F：→ Vulpix : 你想想看 a_{k(k+1)/2} 是多少。08/19 01:23
5F：→ Vulpix : 寫錯了，是 a_{k(2N-k+1)/2}。08/19 01:24
b_i = i - a_i( a_i - 1 )/2
這個代入例子怪怪的? i=9時, a_i=3, b_i=2
但是 b_i = 2
i - a_i( a_i - 1 )/2 = 9 - 3*2/2 = 6
不相等
我是得到 i=(2N-a_i+2)*(a_i-1)/2 + b_i這個等式然後想不到怎麼得到a_i或是b_i
剛剛由你說"不等式"以及看到ceil, 我寫出了:
(2N-k+2)*(k-1)/2 < i <= (2N-k+2)*(k-1)/2+N-k+1, 其中k就是a_i
該不會V大你姐的不等式就是這個吧...?
左邊跟右邊都是k的二次多項式P_L(k), P_R(k), 凹口向下
因此解P_L(k)=i的兩根為r_1<=r_2(假設為實根), 因此k<r1或是k>r2
同理解P_R(k)=i的兩根為r_3<=r_4(假設為實根), 因此r3<=k<=r4
是解這些東西嗎...@@?
※ 編輯: znmkhxrw (123.241.88.179 臺灣), 08/19/2023 03:19:41
6F：推 Vulpix : 所以是 b_i = i - a_i(2N-a_i+1)/2，前面寫錯了。08/19 08:34
7F：→ Vulpix : b_i = i - (a_i-1)(2N-a_i+2)/2，前面又寫錯了。08/19 08:47
8F：→ Vulpix : 那個……小的 r 應該都是負的。08/19 08:48
了解~我再硬爆出來看看, 謝謝V大~
※ 編輯: znmkhxrw (123.241.88.179 臺灣), 08/24/2023 16:12:39