😊出会いの泉😊

横線の立体交差はアリでしたか？

たとえば、
①左から１本目の縦線と３本目の縦線とのあいだに横線を１個つなげる、ただし、２本目の縦線とこの横線とは立体交差にする。

②横線どうしで立体交差をする。

特に立体交差のコメントは無かったので、通常のあみだの横線の引き方で考えるものだと思います。

https://manabitimes.jp/math/1157
によると
縦線5本、横線8本でのあみだくじの行き先の確率は
P5=
[3/4 1/4 0 0 0]

[1/4 1/2 1/4 0 0]

[ 0 1/4 1/2 1/4 0]

[ 0 0 1/4 1/2 1/4]

[ 0 0 0 1/4 3/4]
から

P5^8=
[12155/32768 19449/65536 12393/65536 1581/16384 765/16384]

[19449/65536 8627/32768 3345/16384 9129/65536 1581/16384]

[12393/65536 3345/16384 6995/32768 3345/16384 12393/65536]

[ 1581/16384 9129/65536 3345/16384 8627/32768 19449/65536]

[ 765/16384 1581/16384 12393/65536 19449/65536 12155/32768]

これを小数へ直し
=
[ 0.37094116 0.29676819 0.18910217 0.096496582 0.046691895]

[ 0.29676819 0.26327515 0.20416260 0.13929749 0.096496582]

[ 0.18910217 0.20416260 0.21347046 0.20416260 0.18910217]

[0.096496582 0.13929749 0.20416260 0.26327515 0.29676819]

[0.046691895 0.096496582 0.18910217 0.29676819 0.37094116]

となるんではないかと思うんであるが・・・？

そのサイトでは横線の引き方がm^n通りと言っていますので、確率分布が違うのではないでしょうか。
例えば
│□□│□□│□□│
├──┤□□│□□│
│□□│□□├──┤
│□□├──┤□□│
│□□│□□│□□│
と
│□□│□□│□□│
│□□│□□├──┤
├──┤□□│□□│
│□□├──┤□□│
│□□│□□│□□│
を別のものと考えているのでは？

# 全部きちんと読んだわけではありませんので、
# もしとんちんかんなことを言っていたらご容赦下さい。

ツイッター検索で調べたら
チコちゃんの番組であみだくじについて解説した先生が岩手大学の理工学部の山中克久教授であるとわかりました。
OEIS のサイトでこの先生の名前で検索したらヒットしました。
https://oeis.org/A006245
A006245 の参考文献に以下があげられていました。

ひとつめ
Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno and Kunihiro Wasa, Ladder-Lottery Realization, 30th Canadian Conference on Computational Geometry (CCCG 2018) Winnipeg.

ふたつめ
K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara and K. Nakada, Efficient enumeration of all ladder lotteries and its application, Theoretical Computer Science, Vol. 411, pp. 1714-1722, 2010.

なお
ladder lotteries とはアミダクジのことです。

9841通りの計算は
Σ[i=0～8]Σ[j=0～8-i](i+j)Cj×9C(i+j+1)=9841
という式で出せました。
iは2本目の縦線と3本目の縦線の間に描く横線の数、
jは3本目の縦線と4本目の縦線の間に描く横線の数、
(i+j)Cjは「2本目の縦線と3本目の縦線の間の横線」と
「3本目の縦線と4本目の縦線の間の横線」の位置関係の場合の数、
9C(i+j+1)は残りの8-i-j本の横線を「1本目の縦線と2本目の縦線の間」と
「4本目の縦線と5本目の縦線の間」に配置する場合の数です。

らすかるさん。凄いです。

この数値をはじき出す数式を見つけるなんてビックリです。
分析させて頂きました。
[i,j] [binomial(i+j,j)"*"binomial(9,8-(i+j))] [2つの積]
0,0 1*9 9
0,1 1*36 36
0,2 1*84 84
0,3 1*126 126
0,4 1*126 126
0,5 1*84 84
0,6 1*36 36
0,7 1*9 9
0,8 1*1 1
1,0 1*36 36
1,1 2*84 168
1,2 3*126 378
1,3 4*126 504
1,4 5*84 420
1,5 6*36 216
1,6 7*9 63
1,7 8*1 8
2,0 1*84 84
2,1 3*126 378
2,2 6*126 756
2,3 10*84 840
2,4 15*36 540
2,5 21*9 189
2,6 28*1 28
3,0 1*126 126
3,1 4*126 504
3,2 10*84 840
3,3 20*36 720
3,4 35*9 315
3,5 56*1 56
4,0 1*126 126
4,1 5*84 420
4,2 15*36 540
4,3 35*9 315
4,4 70*1 70
5,0 1*84 84
5,1 6*36 216
5,2 21*9 189
5,3 56*1 56
6,0 1*36 36
6,1 7*9 63
6,2 28*1 28
7,0 1*9 9
7,1 8*1 8
8,0 1*1 1

合計 9841

そこで
i,j=0,2 で　1*84=84
の解釈が
縦線2,3番目には0本,3,4番目には2本引かれているので
1,2と4,5間には合計6本の縦線がある。
そこで
1,2番間　;4,5番間
6 ;0
5 ;1
4 ;2
3 ;3
2 ;4
1 ;5
0 ;6
本の線がある場合に別れる。
ところで2,3番間にはi=0より上記の左の本数は何の制限もなく引くことが出来る。
一方j=2より既に3,4番間には2本の横棒が引かれている。
そこで上記の右の本数の横棒を引く位置はそれぞれ重複組合せから
3H0=1
3H1=3
3H2=6
3H3=10
3H4=15
3H5=21
3H6=28
これの合計が84となる。
なんとこれが一発で9C6=9C3=9*8*7/(3*2*1)=3*4*7=84なわけですね。

同じく
i,j=0,3 で1*126=126は
1,2番間　;4,5番間
5 ;0
4 ;1
3 ;2
2 ;3
1 ;4
0 ;5
上記の右の本数の横棒を引く位置はそれぞれ重複組合せから
4H0=1
4H1=4
4H2=10
4H3=20
4H4=35
4H5=56
この合計が126
同じく一発で9C5=9C4=9*8*7*6/(4*3*2*1)=126

こんな仕組みで計算されているんですね～

5本の縦線にn本の横線を引く場合、(3^(n+1)-1)/2 通りですか？

＞５本の縦線にn本の横線を引く場合、(3^(n+1)-1)/2 通りですか？

こんな明快な式になるとは？

ひょっとして最も左の縦線と最も右の縦線とを同一視して合計４本の縦線とみなすことによって全ての縦線について対称とするテクニックを使うということなのでしょうか？

((4-1)^(n+1)-1)/2

-1　のファクターの意味が取れませんが…… orz

(3^(n+1)-1)/2 通りの場合
n=3なら40となるが
別で調査すれば確かに40通りとなりますね。
例の
(i,j)=
(0,0)-->4
(0,1)-->6
(0,2)-->4
(0,3)-->1
(1,0)-->6
(1,1)-->8
(1,2)-->3
(2,0)-->4
(2,1)-->3
(3,0)-->1
で計40通り

何か縦線m本,横線n本のあみだくじでの一般式が作れそうですね。

一般式を作ろうと思っているが、縦線が奇数と偶数では構造が変わる様に
感じたので縦線が4本で横線がn本である場合のあみだくじの種類を調べてみたら、
n=1-->3
n=2-->8
n=3-->21
n=4-->55
n=5-->144
n=6-->377
ここまで調べて、この数字はなんか見たことあるぞ！
で検索するとフィボナッチ数列fibo(n)での
fibo(2*n+2)の部分が対応している。

なお
この各合計数は次の組合せ関数nCr(=binomial(n,r))を使うと
gp > T(n,k)=binomial(n+k,2*k-1);
gp > for(n=1,10,S=[];for(k=1,n+1,S=concat(S,[T(n,k)]));print(n"=>"S";"vecsum(S)))
1=>[2, 1];3
2=>[3, 4, 1];8
3=>[4, 10, 6, 1];21
4=>[5, 20, 21, 8, 1];55
5=>[6, 35, 56, 36, 10, 1];144
6=>[7, 56, 126, 120, 55, 12, 1];377
7=>[8, 84, 252, 330, 220, 78, 14, 1];987
8=>[9, 120, 462, 792, 715, 364, 105, 16, 1];2584
9=>[10, 165, 792, 1716, 2002, 1365, 560, 136, 18, 1];6765
10=>[11, 220, 1287, 3432, 5005, 4368, 2380, 816, 171, 20, 1];17711
で求めていることになっている。
しかし縦線が6本の場合は未調査なのでまだ何とも言えないですが･･･

縦線が m 本である場合、
「1 から m-1 までの数を重複を許して n 個並べる、ただし直前の数より 2 つ以上小さくなってはいけない」
の並べ方の総数と一致します。
なので、

縦線3本
[1,1] * [[1,1],[1,1]]^(n-1) * t[1,1] = 2^n


縦線4本
[1,1,1] * [[1,1,0],[1,1,1],[1,1,1]]^(n-1) * t[1,1,1] = 1/√5 * ( ((3+√5)/2)^(n+1) - ((3-√5)/2)^(n+1) )

縦線5本
[1,1,1,1] * [[1,1,0,0],[1,1,1,0],[1,1,1,1],[1,1,1,1]]^(n-1) * t [1,1,1,1] = (3^(n+1)-1)/2

と出せます。
縦線6本は固有値が綺麗に出ないので難しそう。

６本の縦線がある場合について横線がn本の場合の構成数について調べてみました。
n=1-->5
n=2-->11
n=3-->40
n=4-->145
n=5-->525
n=6-->1900
n=7-->6875
n=8-->24875

ここまででOEISのお世話になるとn=1を除いてA136775がヒットした。そこには
Number of multiplex juggling sequences of length n, base state <1,1> and hand capacity 2.
という分けがわからい説明が付けられていた。

ただしこの数値はらすかるさんが構成されているプログラムを参考にさせてもらい
F(n)=for(i=0,n,for(j=0,n-i,for(k=0,n-i-j,\
print(i","j","k"=>"binomial(i+j,j)"*"binomial(j+k,k)"*"binomial(n-1,n-(i+j+k))"=>"\
binomial(i+j,j)*binomial(j+k,k)*binomial(n-1,n-(i+j+k))))))
で
2,3番目の間にある横線の数をi
3,4番目の間にある横線の数をj
4,5番目の間にある横線の数をk本
として
その横線の取り方がbinomial(i+j,j)*binomial(j+k,k)で起こせて
残りの本数n-(i+j+k)を1,2番目と5,6番目の間に取れる場合の可能性がbinomial(n-1,n-(i+j+k))と
してやることで上手く働くことを観察してみた。
これをすべて掛け合わせることで、(i,j,k)に対するパターン数が求まっていくので、すべての総和から
n>=2での数値を求めて行きました。
n=6で1900となる経過が下の表です。(F(6)からの表示)
(i,j,k)
0,0,0= 1*1*0= 0
0,0,1= 1*1*1= 1
0,0,2= 1*1*5= 5
0,0,3= 1*1*10= 10
0,0,4= 1*1*10= 10
0,0,5= 1*1*5= 5
0,0,6= 1*1*1= 1
0,1,0= 1*1*1= 1
0,1,1= 1*2*5= 10
0,1,2= 1*3*10= 30
0,1,3= 1*4*10= 40
0,1,4= 1*5*5= 25
0,1,5= 1*6*1= 6
0,2,0= 1*1*5= 5
0,2,1= 1*3*10= 30
0,2,2= 1*6*10= 60
0,2,3= 1*10*5= 50
0,2,4= 1*15*1= 15
0,3,0= 1*1*10= 10
0,3,1= 1*4*10= 40
0,3,2= 1*10*5= 50
0,3,3= 1*20*1= 20
0,4,0= 1*1*10= 10
0,4,1= 1*5*5= 25
0,4,2= 1*15*1= 15
0,5,0= 1*1*5= 5
0,5,1= 1*6*1= 6
0,6,0= 1*1*1= 1
1,0,0= 1*1*1= 1
1,0,1= 1*1*5= 5
1,0,2= 1*1*10= 10
1,0,3= 1*1*10= 10
1,0,4= 1*1*5= 5
1,0,5= 1*1*1= 1
1,1,0= 2*1*5= 10
1,1,1= 2*2*10= 40
1,1,2= 2*3*10= 60
1,1,3= 2*4*5= 40
1,1,4= 2*5*1= 10
1,2,0= 3*1*10= 30
1,2,1= 3*3*10= 90
1,2,2= 3*6*5= 90
1,2,3= 3*10*1= 30
1,3,0= 4*1*10= 40
1,3,1= 4*4*5= 80
1,3,2= 4*10*1= 40
1,4,0= 5*1*5= 25
1,4,1= 5*5*1= 25
1,5,0= 6*1*1= 6
2,0,0= 1*1*5= 5
2,0,1= 1*1*10= 10
2,0,2= 1*1*10= 10
2,0,3= 1*1*5= 5
2,0,4= 1*1*1= 1
2,1,0= 3*1*10= 30
2,1,1= 3*2*10= 60
2,1,2= 3*3*5= 45
2,1,3= 3*4*1= 12
2,2,0= 6*1*10= 60
2,2,1= 6*3*5= 90
2,2,2= 6*6*1= 36
2,3,0= 10*1*5= 50
2,3,1= 10*4*1= 40
2,4,0= 15*1*1= 15
3,0,0= 1*1*10= 10
3,0,1= 1*1*10= 10
3,0,2= 1*1*5= 5
3,0,3= 1*1*1= 1
3,1,0= 4*1*10= 40
3,1,1= 4*2*5= 40
3,1,2= 4*3*1= 12
3,2,0= 10*1*5= 50
3,2,1= 10*3*1= 30
3,3,0= 20*1*1= 20
4,0,0= 1*1*10= 10
4,0,1= 1*1*5= 5
4,0,2= 1*1*1= 1
4,1,0= 5*1*5= 25
4,1,1= 5*2*1= 10
4,2,0= 15*1*1= 15
5,0,0= 1*1*5= 5
5,0,1= 1*1*1= 1
5,1,0= 6*1*1= 6
6,0,0= 1*1*1= 1

　合計 1900

はてこれは一つの式で作れるのか？

> 残りの本数n-(i+j+k)を1,2番目と5,6番目の間に取れる場合の可能性がbinomial(n-1,n-(i+j+k))
これは
binomial(n+1-j,n-(i+j+k))
にしないといけないと思います(中央に使ったj本は残り本数に影響しますが配置に影響しません)。
よってn=1,2,3,…に対する構成数は
5,19,66,221,728,2380,7753,25213,81927,…
のようになります。
（n=2を手作業で数えてみると、19で正しいことがわかると思います。）
そしてこの数列はA005021にあり、漸化式が
a[1]=5, a[2]=19, a[3]=66, a[n+3]=5a[n+2]-6a[n+1]+a[n]
と書かれていますので、これを解いて一般項は
a[n]=up^n+vq^n+wr^n
ただし
u={-(4√91)sin(arcsin(127√91/2366)/3)+7}/21
v={-(4√91)cos(arccos(-127√91/2366)/3)+7}/21
w={(4√91)cos(arccos(127√91/2366)/3)+7}/21
p={-(2√7)cos(arccos(-√7/14)/3)+5}/3
q={-(2√7)sin(arcsin(√7/14)/3)+5}/3
r={(2√7)cos(arccos(√7/14)/3)+5}/3
とわかります。
# u,v,wは49x^3-49x^2-105x+1=0の3解、p,q,rはx^3-5x^2+6x-1=0の3解です。

らすかるさんからの指摘を受けて改めて(数個のパターンでいいと勝手に思ってしまう悪い癖)
６本の縦線がある場合について横線がn本の場合の構成数について調べてみました。
n=1-->5
n=2-->19
n=3-->66
n=4-->221
n=5-->728
n=6-->2380
n=7-->7753
n=8-->25213

ここまででOEISのお世話になるとA005021がヒットした。

らすかるさんとn=3で違ったので
(i,j,k)
0,0,0= 1*1*4= 4
0,0,1= 1*1*6= 6
0,0,2= 1*1*4= 4
0,0,3= 1*1*1= 1
0,1,0= 1*1*3= 3
0,1,1= 1*2*3= 6
0,1,2= 1*3*1= 3
0,2,0= 1*1*2= 2
0,2,1= 1*3*1= 3
0,3,0= 1*1*1= 1
1,0,0= 1*1*6= 6
1,0,1= 1*1*4= 4
1,0,2= 1*1*1= 1
1,1,0= 2*1*3= 6
1,1,1= 2*2*1= 4
1,2,0= 3*1*1= 3
2,0,0= 1*1*4= 4
2,0,1= 1*1*1= 1
2,1,0= 3*1*1= 3
3,0,0= 1*1*1= 1

合計; 66
でチェックしてみたのですが、どうしても67にはなれないのですが・・・?
（あら！修正されたんですね。安心しました。）
A005021のコメントはRandom walksとなっているのでとても驚いています。

文章読解力に乏しい私にはちょっと理解できないのですが、
とりあえず「全然」は何かの変換ミスですか？

文章力が無い文章で混乱させまして申し訳ありません。
9を幾つかずつのグループに分ける方法は
[9],[8,1],[7,2],[6,3],[5,4],[7,1,1],･･･････,[1,1,1,1,1,1,1,1,1]
など全部で30通りのパターンが存在し、このグループに9人を振り分けるには
それぞれに対する振り分け方が計算される。(合計数はベル数Bell(9)=21147通りとなる。)

この時、同じ数が起こる6組のグループの分け方が存在している。
(10人でも同数となる組合せも勿論発生はするのですが、多くて4組でしたので、
比較的少ない人数で重なる組合せが6個も発生する9人を問題に選びました。
なお16人なら8組が重なるがパターンが多すぎる。)

適当に候補を考えたら見つかりました。
[4,3,2]=[3,2,2,2]を見つければ終わりですね。
同じ数がないもの一つだけをバラしても場合の数が変わりませんので、
[4,3,2]=[1,1,1,1,3,2]=[4,1,1,1,2]=[4,3,1,1]
[3,2,2,2]=[1,1,1,2,2,2]
で6通りです。

(追記)
16人の場合は上記の[4,3,2]=[3,2,2,2]に7人グループを付け加えるだけでいいですね。
[4,3,2]=[3,2,2,2]から[7,4,3,2]=[7,3,2,2,2]が成り立つことは明らかで
[7,4,3,2]=[1,1,1,1,1,1,1,4,3,2]=[7,1,1,1,1,3,2]=[7,4,1,1,1,2]=[7,4,3,1,1]
[7,3,2,2,2]=[1,1,1,1,1,1,1,3,2,2,2]=[7,1,1,1,2,2,2]
なので8通りになります。

理解されるとたちまち解決されますね。
それもこちらが思ってない発想で、コンピュータに頼ることなく
あっけなく正解が出てきます。
私は何とかn人の分割方法とその組み割り数を対応させれるプログラムを作ろうと
約2時間もかけて（プロからみたら笑われると思います。)やっと完成でき
これで色々実験していた時、同数になるものが結構発生してくるものだと感じた。
中でも9人の分割方法では多数の同数を持つ分割方法が存在していることが面白かった。
これより多いものを探していくとやっと１６人の分割方法（全部で231通りもある。)
で結果をエクセルに貼り付けソートする作業を通してやっと8組が存在していることを
認識できました。
こんな手間をかけないらすかるさんの思考方法には只々頭は使いようだ！と感心するばかりです。

「n=9で最大6組、n=16で最大8組」について
他のnではどうなるのか気になったのでプログラムを作って調べてみました。
n=1～34に対する最大組数の数列は
1,2,2,2,3,4,4,3,6,4,7,6,6,9,11,8,11,9,11,14,14,19,21,18,23,24,27,30,29,31,33,34,36,40
となりましたが、さすがにこんな変な数列はOEISに載っていませんね。
新規に載せようと思っても説明が複雑になりますので、英語が苦手な私には残念ながら不可能です。
結果を見てみると、n=9とn=16だから手作業で求められましたが、n=15やn=17では厳しそうです。
# n=34でやめたのは、n≧35ではn!が符号なし128ビット変数に収まらなくなって
# プログラムの変更が必要になるためであり、実行時間的な問題ではありません。

結構15人が多くの組合わせが一致したんですね。
改めて探したら6306300で皆一致しました。
[2, 3, 4, 6]
[3, 3, 4, 5]
[1, 1, 3, 4, 6]
[2, 2, 2, 3, 6]
[1, 1, 1, 2, 4, 6]
[1, 1, 1, 1, 2, 3, 6]
[1, 1, 1, 1, 3, 3, 5]
[1, 1, 1, 2, 2, 2, 6]
[1, 1, 1, 1, 1, 3, 3, 4]
[1, 1, 1, 1, 1, 1, 2, 3, 4]
[1, 1, 1, 1, 1, 1, 2, 2, 2, 3]

調査された中で2番目に多かったn=33人での分割での36通りが皆一斉に揃うものが見たかったので挑戦してみました。
すべて30051520145226019440000のパターン数で一致しました。
目だけで点検しているので他の部分を見落としているかも・・・
1; [3, 3, 4, 4, 5, 6, 8]
2; [1, 2, 2, 4, 4, 5, 6, 9]
3; [2, 2, 2, 3, 4, 6, 6, 8]
4; [2, 2, 2, 4, 4, 6, 6, 7]
5; [2, 2, 3, 3, 4, 4, 5, 10]
6; [1, 1, 2, 2, 3, 4, 4, 6, 10]
7; [1, 2, 2, 2, 2, 4, 5, 6, 9]
8; [2, 2, 2, 2, 3, 3, 4, 5, 10]
9; [2, 2, 2, 2, 3, 3, 5, 5, 9]
10; [1, 1, 1, 1, 2, 3, 4, 6, 6, 8]
11; [1, 1, 1, 1, 2, 4, 4, 6, 6, 7]
12; [1, 1, 1, 1, 4, 4, 4, 5, 5, 7]
13; [1, 1, 1, 2, 2, 2, 4, 6, 6, 8]
14; [1, 1, 2, 2, 2, 2, 3, 4, 6, 10]
15; [2, 2, 2, 2, 2, 2, 3, 4, 5, 9]
16; [1, 1, 1, 1, 1, 3, 3, 4, 4, 6, 8]
17; [1, 1, 1, 1, 1, 3, 4, 4, 4, 5, 8]
18; [1, 1, 1, 1, 2, 2, 2, 3, 6, 6, 8]
19; [1, 1, 1, 1, 2, 2, 2, 4, 5, 5, 9]
20; [1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 10]
21; [1, 1, 1, 1, 1, 1, 2, 3, 4, 4, 6, 8]
22; [1, 1, 1, 1, 1, 1, 3, 3, 4, 4, 5, 8]
23; [1, 1, 1, 1, 1, 2, 2, 2, 4, 4, 5, 9]
24; [1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 10]
25; [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 5, 10]
26; [1, 1, 1, 2, 2, 2, 2, 2, 2, 4, 5, 9]
27; [1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 10]
28; [1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 5, 9]
29; [1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 4, 4, 5, 6]
30; [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4, 4, 6, 6]
31; [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 4, 9]
32; [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 6, 6]
33; [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5]
34; [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 5, 5]
35; [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 5]
36; [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 4, 5]

なおn=34人の最高値が40なんですがどう探してもこの39しか見つからなくて・・・
1; [1, 3, 4, 4, 4, 5, 6, 7]
2; [2, 3, 3, 3, 4, 5, 6, 8]
3; [3, 3, 3, 4, 4, 5, 5, 7]
4; [1, 1, 2, 3, 3, 4, 5, 6, 9]
5; [1, 1, 3, 3, 3, 4, 5, 6, 8]
6; [1, 2, 2, 2, 3, 4, 5, 6, 9]
7; [1, 2, 3, 3, 3, 3, 5, 6, 8]
8; [2, 2, 2, 3, 3, 3, 5, 6, 8]
9; [2, 3, 3, 3, 3, 3, 4, 5, 8]
10; [1, 1, 1, 2, 2, 3, 4, 5, 6, 9]
11; [1, 1, 1, 2, 3, 3, 4, 5, 5, 9]
12; [1, 1, 1, 3, 3, 3, 4, 5, 5, 8]
13; [1, 1, 2, 2, 2, 3, 3, 5, 6, 9]
14; [1, 1, 2, 2, 3, 3, 3, 4, 5, 10]
15; [1, 1, 2, 2, 3, 3, 3, 5, 5, 9]
16; [1, 1, 3, 3, 3, 3, 3, 4, 5, 8]
17; [1, 2, 2, 3, 3, 3, 3, 3, 6, 8]
18; [2, 2, 2, 3, 3, 3, 3, 3, 5, 8]
19; [1, 1, 1, 1, 2, 3, 3, 3, 5, 6, 8]
20; [1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 10]
21; [1, 1, 1, 2, 2, 2, 3, 3, 5, 5, 9]
22; [1, 2, 2, 2, 2, 2, 3, 3, 3, 5, 9]
23; [2, 2, 2, 2, 2, 2, 3, 3, 3, 6, 7]
24; [1, 1, 1, 1, 1, 2, 3, 3, 3, 4, 6, 8]
25; [1, 1, 1, 1, 2, 3, 3, 3, 3, 3, 5, 8]
26; [2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 7]
27; [1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 4, 5, 8]
28; [1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 6, 8]
29; [1, 1, 1, 1, 1, 2, 3, 3, 3, 3, 3, 4, 8]
30; [1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 4, 4, 5, 5]
31; [1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 8]
32; [1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 8]
33; [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 4, 5, 6]
34; [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 6]
35; [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 3, 3, 4, 5]
36; [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 7]
37; [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 5]
38; [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 6]
39; [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3]

1362335579916912881280000通りになるものは39個しかありません。
40個あるのは 14596452641966923728000通りになるものです。

先を計算してもあまり意味はないのですが、n=34までというのはどうも
中途半端で気になったので、n=100まで計算しました。
n=1～10: 1, 2, 2, 2, 3, 4, 4, 3, 6, 4
n=11～20: 7, 6, 6, 9, 11, 8, 11, 9, 11, 14
n=21～30: 14, 19, 21, 18, 23, 24, 27, 30, 29, 31
n=31～40: 33, 34, 36, 40, 49, 51, 58, 54, 56, 75
n=41～50: 73, 78, 79, 105, 108, 97, 115, 134, 155, 158
n=51～60: 162, 173, 197, 209, 214, 224, 247, 306, 331, 339
n=61～70: 330, 408, 434, 452, 490, 501, 564, 562, 618, 643
n=71～80: 670, 734, 816, 816, 888, 951, 1060, 1130, 1178, 1195
n=81～90: 1360, 1353, 1464, 1549, 1780, 1885, 1955, 2096, 2257, 2338
n=91～100: 2512, 2751, 3062, 3146, 3301, 3733, 3744, 4250, 4428, 4996
n=100の計算は2時間近くかかっています。

[6, 4, 3, 1]で12を重複を許して支払おうとするときに、16通りになりますね。偶然？

1000,[500,100,50,10],100のようなケースでは
500と100と50をいくつずつ使っても必ず残りが10で割り切れますので
（つまり最小以外の数(500,100,50)がすべての最小の数(10)で割り切れる）
if target / coin <= usable
で問題が起こりませんが、
12,[6,4,3,2],6のように最小の2で割り切れない数があると
targetが2で割り切れない場合でも
@cnt += 1
が実行されてしまうと思います。
つまり、3が奇数個使われて最後にtargetが奇数になる
6+3+2
4+4+3
4+3+2+2
3+2+2+2+2
3+3+3+2
の5個（すべて1不足）が余計に数えられてしまっているのでしょう。
「if target / coin <= usable」
を
「if targetがcoinで割り切れ、かつtarget / coin <= usable」
に修正すれば正しく動くと思います。
（Rubyの文法を知りませんので言葉で書きました）

らすかるさんの仰る通りなのでしたか。

((x^6)^2+(x^6)+1)*((x^4)^3+(x^4)^2+(x^4)^1+1)*((x^3)^4+(x^3)^3+(x^3)^2+(x^3)^1+1)*((x^2)^6+(x^2)^5+(x^2)^4+(x^2)^3+(x^2)^2+(x^2)^1+1)

を展開して x^11 の項の係数が 5 だとチラと頭をよぎったのですが
《targetが奇数》となることをプログラムから読み取れませんでした。残念な私。

０＜ａ≦ｂ≦ｃ≦ｄ　として、
（ａ，ｂ，ｃ，ｄ）＝（１，２，８，９）、（１，６，７，８）、（２，３，４，１１）、（３，４，５，１０）

0＜a≦b≦c≦d として
(a,b,c,d)=(1,1,2,12),(1,2,8,9),(1,6,7,8),(2,3,4,11),(2,4,7,9),(3,4,5,10),(4,6,7,7),(5,5,6,8)

整数の制限が付いてないので他にも
(14/5,33/5,47/5,16/5)
(33/13,79/13,112/13,74/13)
(56/25,137/25,193/25,186/25)
(41/21,103/21,48/7,26/3)
(48/23,119/23,238/23,79/23)
(109/57,275/57,550/57,104/19)
(12/7,31/7,62/7,7)
(52/33,137/33,359/33,38/11)
(115/79,309/79,812/79,410/79)
(6/5,17/5,56/5,17/5)
(31/17,127/17,158/17,36/17)
(53/31,221/31,274/31,132/31)
(39/25,167/25,206/25,148/25)
(101/71,445/71,718/71,180/71)
(4/3,6,29/3,13/3)
(21/19,101/19,202/19,52/19)
(16/13,103/13,119/13,18/13)
(107/91,701/91,808/91,42/13)
(50/51,353/51,168/17,95/51)
(31/37,303/37,334/37,32/37)
(119/27,64/9,238/27,41/27)
(55/13,89/13,110/13,48/13)
(155/39,84/13,310/39,211/39)
(137/37,224/37,361/37,78/37)
(103/29,169/29,272/29,114/29)
(153/49,254/49,508/49,17/7)
(271/81,623/81,718/81,28/27)
(153/47,353/47,406/47,136/47)
(101/35,237/35,338/35,8/5)
(149/57,458/57,168/19,37/57)
(224/43,313/43,359/43,18/43)
(169/33,709/99,812/99,226/99)
(254/55,357/55,508/55,61/55)
(505/119,921/119,1010/119,4/17)
(17/3,22/3,8,1/3)
･････････････
他に
(3,5,11,131)
(3,5,29,113)
(3,5,41,101)
(3,5,53,89)
(3,5,59,83)
･････････
(11,19,47,73)
(11,19,53,67)
(11,19,59,61)
(11,23,37,79)
(11,23,43,73)
･････････
(19,29,31,71)
(19,29,41,61)
(19,29,43,59)
(19,31,41,59)
(19,31,47,53)
(19,37,41,53)
(19,41,43,47)
(23,29,31,67)
(23,29,37,61)
(23,31,37,59)
(23,31,43,53)
(23,37,43,47)
(29,31,37,53)
(29,31,43,47)
(29,37,41,43)
･･････････
ただし数値に√記号を付けて下さい。
更にiを虚数単位とし
(-10+i,-9+5*i,-5+7*i,10+9*i)
(-10+3*i,-9+4*i,2+5*i,8+7*i)
(-10+6*i,-8+7*i,-6+10*i,16+11*i)
(-9+2*i,-8+4*i,-5+6*i,10+8*i)
(-8+i,-6+2*i,-4+3*i,8+4*i)
(-8+3*i,-6+5*i,-5+6*i,12+7*i)
･･･････････
などなど無数にありそう。

面白くない回答ですが、
実数範囲の一般解はp,q,rを任意の正の実数として
(a,b,c,d)=(±√{150/(1+p+q+r)},±√{150p/(1+p+q+r)},±√{150q/(1+p+q+r)},±√{150r/(1+p+q+r)})
複素数範囲の一般解はp,q,rを任意の複素数（ただしpqr≠0かつp^2+q^2+r^2≠150）として
(a,b,c,d)=(p,q,r,±√(150-p^2-q^2-r^2))

上手く纏められますね～。

最大数に着目して
７＾２＋７＾２＋６＾２＋４＾２
８＾２＋６＾２＋５＾２＋５＾２
９＾２＋７＾２＋４＾２＋２＾２
１０＾２＋５＾２＋４＾２＋３＾２
１１＾２＋４＾２＋３＾２＋２＾２
１２＾２＋２＾２＋１＾２＋１＾２
１３＾２＋（３i）^2+（３i）+i^2
14^2+(6i)^2+(3i)^2+i^2
複素数には大小関係はありませんが。
そもそも、２（１，２，３，４）＋（４，１，２，ー３）＝（６，５，８，５）と２（１，２，３，４）＋（２，３，－４，１）＝（４，７，２，９）
２乗和が１５０になりました。１，２，３，４を並べ替えと、符号を適当につけると、４乗和も等しくできますが、６乗和はむつかしいみたいです。
（a,b,c,d)の２，４，６乗和まで、等しいのが見つかると
（-a,-b,-c,-d,a,b,c,d)が、８個の累乗和が見つかる作戦です。

2(1,2,3,4)+(a,b,c,d)
但し、a,b,c,d は、順序関係なく1,2,3,4符号をつけたものです。
2(1,2,3,4)+(-4,-1,2,-3)=(-2,3,8,5)
2(1,2,3,4)+(-2,3,-4,-1)=(0,7,2,7)
の二組は、二乗和、四乗和が、等しくなります。
上の形式で、二乗和、四乗和、六乗和まで、等しくなる
二組は、存在するでしょうか？

何とか手作業で見つけました。
(236/7777)^2+(37/707)^2+(8/77)^2+(97976/1111)^2=7777
a^2+b^2+c^2+d^2=7777^3となるa,b,c,dの組み合わせで
7777で割って約分したときに全部分母が異なるものを探しました。

手作業で見つけました。
これが凄いですね。
確かに分母が[77,707,1111,7777]で分子を上記の数値で分数を作っておくと
7777がつくれる。
私も何とかコンピュータの力をお借りして
分母が[3,15,25,75]で固定して置いて、分子を色々動かしてみると
(100/3)^2+(454/15)^2+(974/25)^2+(4879/75)^2
(100/3)^2+(461/15)^2+(994/25)^2+(4826/75)^2
(100/3)^2+(464/15)^2+(967/25)^2+(4868/75)^2
(100/3)^2+(496/15)^2+(997/25)^2+(4738/75)^2
(100/3)^2+(508/15)^2+(913/25)^2+(4852/75)^2
･････････････････････
と周辺にいくつも条件を満たす集団が発見できました。

同じく分母を[3,21,35,105]固定したら
(140/3)^2+(1301/21)^2+(1464/35)^2+(356/105)^2
(140/3)^2+(1306/21)^2+(1418/35)^2+(997/105)^2
(140/3)^2+(1318/21)^2+(1417/35)^2+(482/105)^2
(140/3)^2+(1325/21)^2+(1404/35)^2+(316/105)^2
(140/3)^2+(1363/21)^2+(1276/35)^2+(796/105)^2
･････････････････

[7,15,21,105]の分母では
(404/7)^2+(653/15)^2+(898/21)^2+(2822/105)^2
(404/7)^2+(692/15)^2+(844/21)^2+(2783/105)^2
(405/7)^2+(676/15)^2+(866/21)^2+(2774/105)^2
(405/7)^2+(716/15)^2+(806/21)^2+(2734/105)^2
(409/7)^2+(692/15)^2+(832/21)^2+(2708/105)^2
･･････････････
が浮かび上がってきます。

整数だけに限定すると有限個でおさまるところ
有理数へ探索を拡張すると世界が全く異なってくる感覚になります。
しかも探す苦労は一筋縄ではいかなくなる。
任意の整数Nを4つの有理数の平方和で作るアルゴリズムは有りや無しや？

「最も簡単な式」すなわち分子分母に登場する自然数の最大値が最も小さいものは
(173/2)^2+(161/10)^2+(155/26)^2+(1/130)^2=7777
（最大値173）
でした。最大値が173になる式は全部で5つあり、
173を除いた数の最大値（この式では161）が最も小さくなるのがこの式です。
（172以下の自然数では7777は作れないということになります。）

最大値が173になる式は全部で5つあり、

(173/2)^2+(161/10)^2+(155/26)^2+(1/130)^2
(173/2)^2+(167/10)^2+(103/26)^2+(53/130)^2
(173/2)^2+(169/10)^2+(77/26)^2+(79/130)^2
(173/2)^2+(171/10)^2+(33/26)^2+(111/130)^2
以外何があるのですか？

あと一つは
(173/2)^2+(167/10)^2+(133/34)^2+(127/170)^2
です。

(173/2)^2+(167/10)^2+(133/34)^2+(127/170)^2
を探し出すためには他にも前3つの最小公倍数が173を越えない組合せ(1541通り)
が山ほど考えられるので、それから見つけ出すって凄くないですか？

(173/3)^2+(173/4)^2+(173/5)^2+(173/6)^2＜7777から
一つ目の分母は2に固定できますので、探索する組み合わせは減らせると思います。
同様に
(173/2)^2+(173/17)^2+(173/18)^2+(173/19)^2＜7777から
二つ目の分母は3～16（一つ目の分子が小さければさらに絞られます）に限られるなど、
常に「この値（以上）にした場合に合計が7777になる可能性がなければパス」という
処理を入れて短縮すれば、実行時間が結構短くなるのではないかと思います。
※一つ目の「2のみ」もそういう固定値にしているわけではなく、
「3にした場合に残りが最大として7777に達するか」を計算しています。
(補足)
上記のチェックは巨大整数演算や分数演算では多分遅いので、
最大値をdoubleで計算して7776.9より小さければパス、としています。

同じ記事の話題なので、同一スレッドにぶら下がります。

△ABC を、A を中心に時計周りに 90° 回転させてから外周が長方形になるよう補助線を引くと、
長方形から 3 つの直角三角形（うち 2 つは合同）を切り落として直角二等辺三角形が残る図ができます。
よって θ-90° = 45° より θ=135°

という解答が一番お手軽ですかね。

直角三角形 2 つで、直角を挟む 2 辺の長さが
12+5=17, 12-5=7
17+7=24=12*2, 17-7=10=5*2
みたいな関係のときにはまずこの図を作ることを考えるようにしています。

問題から、少し外れますが

２つの「直角三角形同士」が、この「向き」で接していた時
辺の長さが、分かっていなくても
必ず
∠θ＝∠Ｂ＋∠Ｄ　が成り立つ・・・と
ちょとした公式（大げさ？）の出来上がりになるかな？

中学入試問題にちょうどいい
θが１３５°の時、∠Ｂと∠Ｄの和は何度ですか？
（直感で、すぐに分かってしまうと思うけど）

ひょっとして
10円玉までで
158通りでしょうか？

((x^50)^2+(x^50)+1)*((x^10)^10+(x^10)^9+(x^10)^8+(x^10)^7+(x^10)^6+(x^10)^5+(x^10)^4+(x^10)^3+(x^10)^2+(x^10)^1+1)*((x^5)^20+(x^5)^19+(x^5)^18+(x^5)^17+(x^5)^16+(x^5)^15+(x^5)^14+(x^5)^13+(x^5)^12+(x^5)^11+(x^5)^10+(x^5)^9+(x^5)^8+(x^5)^7+(x^5)^6+(x^5)^5+(x^5)^4+(x^5)^3+(x^5)^2+(x^5)^1+1)*((x)^100+(x)^95+(x)^90+(x)^85+(x)^80+(x)^75+(x)^70+(x)^65+(x)^60+(x)^55+(x)^50+(x)^45+(x)^40+(x)^35+(x)^30+(x)^25+(x)^20+(x)^15+(x)^10+(x)^5+1)

を展開してx^100 の項の係数をみました。

本当は次の式を展開したかったのですが、オンライン展開サービスが受け付けてくれませんでした。

((A*x^50)^2+(A*x^50)+1)*((B*x^10)^10+(B*x^10)^9+(B*x^10)^8+(B*x^10)^7+(B*x^10)^6+(B*x^10)^5+(B*x^10)^4+(B*x^10)^3+(B*x^10)^2+(B*x^10)^1+1)*((C*x^5)^20+(C*x^5)^19+(C*x^5)^18+(C*x^5)^17+(C*x^5)^16+(C*x^5)^15+(C*x^5)^14+(C*x^5)^13+(C*x^5)^12+(C*x^5)^11+(C*x^5)^10+(C*x^5)^9+(C*x^5)^8+(C*x^5)^7+(C*x^5)^6+(C*x^5)^5+(C*x^5)^4+(C*x^5)^3+(C*x^5)^2+(C*x^5)^1+1)*((D*x)^100+(D*x)^95+(D*x)^90+(D*x)^85+(D*x)^80+(D*x)^75+(D*x)^70+(D*x)^65+(D*x)^60+(D*x)^55+(D*x)^50+(D*x)^45+(D*x)^40+(D*x)^35+(D*x)^30+(D*x)^25+(D*x)^20+(D*x)^15+(D*x)^10+(D*x)^5+1)

10円＝1ギルドとして
100ギルドの商品を
1ギルド、5ギルド、10ギルド、50ギルドの硬貨で支払いたいと考えます。

このとき、1ギルド硬貨の枚数は明らかに5の倍数なのでそうした縛りをつけます。
(D*x) は1ギルド硬貨のシンボルです。この項の肩にのっかる指数は、1ギルド硬貨で支払う価格を表します。上の式では0ギルドから100ギルドまで5ギルド単位の全ての可能性を列挙しています。

(C*x^5)は５ギルド硬貨のシンボルです。0枚から20枚まで、肩の指数でもって１枚づつの刻みで列挙します。

同様に(B*x^10)及びに(A*x^50)は、それぞれ、10ギルド硬貨、50ギルド硬貨のシンボルです。式での意味はここまでの扱いに準拠します。

さきほどの式は、それぞれの硬貨の枚数の上限およびに刻みに制限を付与した上で、支払える金額の全てのパターンを自動的に(展開をしてくれるサイトを利用してですが)求めるものです。
xの指数が100のものの全てのバリエーションが求めるものなのですが、、
まじめに展開できれば、100ギルドの支払い方が各係数をみることでわかるはずです。

展開してくれるサイトがみつからなかったので、AからDまでに1を代入して、バリエーションの組み合わせの数のみ求めることとしました。

一つ目
10円硬貨で10n円を表す方法は1通り
　→ 50n円を表す方法も1通り
10円硬貨と50円硬貨で50n円を表す方法は、Σ[k=0～n]1=n+1通り
　→ 100n円を表す方法は2n+1通り
10円硬貨と50円硬貨と100円硬貨で100n円を表す方法は、Σ[k=0～n]2k+1=(n+1)^2通り
　→ 500n円を表す方法は(5n+1)^2通り
10円硬貨と50円硬貨と100円硬貨と500円硬貨で500n円を表す方法は、
　Σ[k=0～n](5k+1)^2=(n+1)(50n^2+55n+6)/6通り
よって1000円を表す方法はn=2を代入して3×316÷6=158通り

二つ目
5円硬貨で5n円を表す方法は1通り
　→ 10n円を表す方法も1通り
5円硬貨と10円硬貨で10n円を表す方法は、Σ[k=0～n]1=n+1通り
　→ 50n円を表す方法は5n+1通り
5円硬貨と10円硬貨と50円硬貨で50n円を表す方法は、
　Σ[k=0～n]5k+1=(n+1)(5n+2)/2通り
　→ 100n円を表す方法は(2n+1){5(2n)+2}/2=(2n+1)(5n+1)通り
5円硬貨と10円硬貨と50円硬貨と100円硬貨で100n円を表す方法は、
　Σ[k=0～n](2k+1)(5k+1)=(n+1)(20n^2+31n+6)/6通り
　→ 500n円を表す方法は(5n+1){20(5n)^2+31(5n)+6}/6=(5n+1)(500n^2+155n+6)/6通り
5円硬貨と10円硬貨と50円硬貨と100円硬貨と500円硬貨で500n円を表す方法は
　Σ[k=0～n](5k+1)(500k^2+155k+6)/6=(n+1)(625n^3+1050n^2+305n+6)/6通り
よって1000円を表す方法はn=2を代入して3×9816÷6=4908通り

三つ目
1円硬貨でn円を表す方法は1通り
　→ 5n円を表す方法も1通り
1円硬貨と5円硬貨で5n円を表す方法は、Σ[k=0～n]1=n+1通り
　→ 10n円を表す方法は2n+1通り
1円硬貨と5円硬貨と10円硬貨で10n円を表す方法は、Σ[k=0～n]2k+1=(n+1)^2通り
　→ 50n円を表す方法は(5n+1)^2通り
1円硬貨と5円硬貨と10円硬貨と50円硬貨で50n円を表す方法は、
　Σ[k=0～n](5k+1)^2=(n+1)(50n^2+55n+6)/6通り
　→ 100n円を表す方法は(2n+1){50(2n)^2+55(2n)+6}/6=(2n+1)(100n^2+55n+3)/3通り
1円硬貨と5円硬貨と10円硬貨と50円硬貨と100円硬貨で100n円を表す方法は、
　Σ[k=0～n](2k+1)(100k^2+55k+3)/3=(n+1)(100n^3+240n^2+131n+6)/6通り
　→ 500n円を表す方法は(5n+1){100(5n)^3+240(5n)^2+131(5n)+6}/6
　　　= (5n+1)(12500n^3+6000n^2+655n+6)/6通り
1円硬貨と5円硬貨と10円硬貨と50円硬貨と100円硬貨と500円硬貨で500n円を表す方法は
　Σ[k=0～n](5k+1)(12500k^3+6000k^2+655k+6)/6
　　= (n+1)(12500n^4+29375n^3+15800n^2-195n+6)/6通り
よって1000円を表す方法はn=2を代入して3×497816÷6=248908通り