最大の三角形を探す（4）

数学 プログラミング

次の図のように考えるとうまくいきます。

赤い部分が長いほうから見て最長の同じ長さの棒があるところで、この長さをkとします。長さが、100, 60, 40, 20, 20, 20, 10, 5, 5とすればkは20です。なぜこうするとよいのかというと、同じ長さの棒があると、そこで必ず三角形になってしまうからです。例えば、5、5とあったら、次が1でも三角形になります。
さて、赤い部分の場合の数は、青い部分は決まっているとすると、

dCb
d ≡ b + a

黄色い部分は、1からk-1を任意で選べるので、

(k - 1)c

kとdを決めたときの場合の数Ak,dは、

Ak,d = dC2(k-1)d-2 + … + dCd-1(k-1)1 + dCd
= kd - (dCd(k-1)d + dCd-1(k-1)d-1)
= kd - (k + d - 1)(k - 1)d-1

と簡単に求まります。
青い部分ですが、

Dp,q,r,s

を長い順にp,qと並んでいて、rがpより長い棒の個数、sを何回目にはじめて三角形になったか（まだ三角形になっていなかったら0とする）、としたときの場合の数とします。Dは比較的簡単に求まるので、各Dに対してAを対応させると全体の場合の数が求まります。

N = 100
M = 10

def add(dic, key, value):
    if key in dic:
        dic[key] += value
    else:
        dic[key] = value

D = [ { } for k in xrange(M - 1) ]
for p in xrange(1, N + 1):
    for q in xrange(1, p):
        D[0][(p,q,0)] = M * (M - 1)
for r in xrange(M - 2):
    for (p, q, s), value in D[r].iteritems():
        for t in xrange(1, q):
            s1 = s if s > 0 or p >= q + t else r + 1
            add(D[r+1], (q, t, s1), value * (M - r - 2))

A = [ [ 0 ] * (M + 1) for k in xrange(N + 1) ]
for k in xrange(1, N + 1):
    for d in (d for d in xrange(M + 1) if d != 1):
        A[k][d] = k ** d - (k + d - 1) * (k - 1) ** (d - 1) if d > 1 else 1

E = [ 0 ] * M
E[1] = sum(A[k][M] for k in xrange(1, N + 1))   # a = 0

# a = 1
for p in xrange(2, N + 1):
    for k in xrange(1, p):
        s1 = 1 if p < k * 2 else 2
        E[s1] += A[k][M-1] * M

for r in (r for r in xrange(M - 1) if r != M - 3):
    for (p, q, s), F in D[r].iteritems():
        if r + 2 == M:
            s1 = r + 1 if s == 0 else s
            E[s1] += F
        else:
            for k in xrange(1, q):
                if s == 0:
                    if p < q + k:
                        s1 = r + 1
                    elif q < k * 2:
                        s1 = r + 2
                    else:
                        s1 = r + 3
                else:
                    s1 = s
                E[s1] += A[k][M-r-2] * F

print E
print sum(s * E[s] for s in xrange(M)) / float(N ** M)

[0, 99609374562749955000L, 367746024475174330L, 21810340254822750L, 96
6656608644240L, 87560140026240L, 11205710843040L, 2216656108800L, 1057
878057600L, 375526368000L]
1.00414696653

棒の長さの最大が100、棒の数が10のときの期待値は、1.004くらいです。