異なる半径のN個の円を一列に並べることができる方法の数

Question

質問：11単位で区切られた行のM点を指定します。異なる半径のN個の円を描くことができるように、N個の円を描くことができる方法の数を探します。但し、円の中心はそれらのMM点でなければならない。

例1：N = 3、M = 6、r1 = 1、r2 = 1、r3 = 1回答：24通り。

例2：N = 2、M = 5、r1 = 1、r2 = 2回答：6つの方法。

例3：N = 1、M = 10、r = 50。答え= 10通り。

この質問はオンラインで見つかりましたが、今まで解決できませんでした。これまでは、これまでどんな円でもn-rn-rからn-2rn-2rまでのスペースを取ることができました。しかし、他の問題の中で、半径33の円がn-4n-4番目の点を取るエッジケースの場合、どのように調整できますか？最後の点はそのままですが、半径1の円を置くことはできません。これに対する一般化された数学的解を見ることができる。

Answer 1

円の中心を非整数のx座標とy座標に置くことができれば、長さが短すぎるため不可能であるか、十分な長さがあり、無限に多くの翻訳が存在するため無限に多くなります。

結果を計算する必要があるので、（M、M）の座標は整数であると仮定します。

1つの円がある場合、解は円を法的に配置できる点の数です。

少なくとも2つの円がある場合は、直径の合計を計算する必要があります。それが、私たちが話している行の合計長さよりも大きくなる場合、解決策はありません。そうでない場合は、全長から直径の合計を差し引いてComplementerを得る必要があります。あなたはまた、N！サークルの順番を計算する順列。また、円の間にギャップを分散できるComplementer - 1の可能な場所があります。ギャップの長さは、G1、...、GN-1

我々は知っているG1 + ... + GN-1 =補数

G1の可能な分配の数...、Gnを-1はDです。したがって、式はb

N！ * D

残りの質問は次のとおりです。Dはどのように計算できますか？

ソリューション：

function distr(depth, maxDepth, amount) 
    if (depth = maxDepth) then 
     return 1 //we need to put the remaining elements on the last slot 
    end if 
    sum = 1 //if we put amount here, that is a trivial case 
    for i = amount - 1 to 0 do 
     sum = distr(depth + 1, maxDepth, amount - i) 
    end for 
    return sum 
end distr 

あなたがMAXDEPTH = N-1、深さ= 1で競合製品を呼び出す必要があり、AMOUT =補数