FC2ブログ

Welcome to my blog

[答740] 三角形の個数

ヤドカリ

ヤドカリ



[答740] 三角形の個数


 凸7角形の対角線14本のうちの3本でできる三角形は 189個あります。

 ( 図はそのうちの6個に色を塗ったものです )

 では、凸40角形の対角線は何本? また、そのうちの3本でできる三角形は何個?

 ただし、どの3本の対角線も凸40角形の頂点以外の1点で交わらないものとします。


[解答1]

 一般化して、n≧4 として 凸n角形で考えます。また、n<r のとき nr=0 とします。

 対角線は2つの頂点を結ぶ線分のうち辺以外のものだから、

 n2-n=n(n-1)/2-n=n(n-3)/2 本です。

 次に三角形の個数は、

 (0) 三角形の頂点が3個とも凸n角形の内部にある場合

  頂点のうち6個を選んで、3本の対角線で凸n角形の内部に三角形を作れるので、

  n6=n(n-1)(n-2)(n-3)(n-4)(n-5)/720 個です。

 (1) 三角形の頂点のうち1個だけが凸n角形の頂点である場合

  頂点のうち5個を選んで、☆形を作ると、5個ずつできるから、

  5・n5=n(n-1)(n-2)(n-3)(n-4)/24 個です。

 (2) 三角形の頂点のうち2個だけが凸n角形の頂点である場合

  頂点のうち4個を選んで、四角形と対角線を描くと、4個ずつできるから、

  4・n4=n(n-1)(n-2)(n-3)/6 個です。

  ただし、凸n角形の1辺と対角線2本でできる三角形を除外します。

  除外するのは n・n-22=n(n-2)(n-3)/2 個です。

  よって、n(n-1)(n-2)(n-3)/6-n(n-2)(n-3)/2=n(n-2)(n-3)(n-4)/6 個です。

 (3) 三角形の頂点が3個とも凸n角形の頂点である場合

  頂点のうち3個を結んで、三角形を作ると、

  n3=n(n-1)(n-2)/6 個です。

  ただし、凸n角形と1辺または2辺を共有する三角形を除外します。

  除外するのは n(n-4)+n=n(n-3) 個です。

  よって、n(n-1)(n-2)/6-n(n-3)=n(n-4)(n-5)/6 個です。

 (0)~(3) より 三角形の総数を計算すれば、途中の計算を省略しますが、

 n(n-4)(n+3)(n3+16n2-67n-10)/720 個になります。

 本問では n=40 なので、以下の通りです。

 対角線は 40(40-3)/2=740 本、

 三角形は 40(40-4)(40+3)(403+16・402-67・40-10)/720=7474260 個です。


[解答2]

 一般化して、n≧4 として 凸n角形で考えます。また、n<r のとき nr=0 とします。

 対角線は2つの頂点を結ぶ線分のうち辺以外のものだから、

 n2-n=n(n-1)/2-n=n(n-3)/2 本です。

 次に三角形の個数を求めるのに、頂点の1つから左回りに 1,2,……,n と番号をつけ、

 1 と他の点を結ぶ対角線を使う三角形を考えます。

 (0) 三角形の頂点が3個とも凸n角形の内部にある場合

  2 ~ n のうち5個の数を選んで 小さいほうから a,b,c,d,e とし、1 と c ,a と d ,b と e を結びます。

  同一の三角形を6回ずつ数えることになるから、n-15/6=(n-1)(n-2)(n-3)(n-4)(n-5)/720 個です。

 (1) 三角形の頂点のうち1個だけが凸n角形の頂点である場合

  2 ~ n のうち4個の数を選んで 小さいほうから a,b,c,d とし、1 と b ,d と a ,a と c を結びます。

  n-14=(n-1)(n-2)(n-3)(n-4)/24 個です。

 (2) 三角形の頂点のうち2個だけが凸n角形の頂点である場合

  2 ~ n-1 のうち3個の数を選んで 小さいほうから a,b,c とし、1 と b+1 ,b+1 と a ,a と c+1 を結びます。

  n-23=(n-2)(n-3)(n-4)/6 個です。

 (3) 三角形の頂点が3個とも凸n角形の頂点である場合

  3 ~ n-2 のうち2個の数を選んで 小さいほうから a,b とし、1 と a ,a と b+1 ,b+1 と 1 を結びます。

  同一の三角形を3回ずつ数えることになるから、n-42/3=(n-4)(n-5)/6 個です。

 1 ~ n の番号のつけ方が n 通りで (0)~(3) より 三角形の総数を計算すれば、

 途中の計算を省略しますが、n(n-4)(n+3)(n3+16n2-67n-10)/720 個になります。

 本問では n=40 なので、以下の通りです。

 対角線は 40(40-3)/2=740 本、

 三角形は 40(40-4)(40+3)(403+16・402-67・40-10)/720=7474260 個です。


[参考] たけちゃんさんのコメントからの考察

 凸n角形で、対角線に辺を含めた n(n-1)/2 本のうちの3本でできる三角形の個数は、

 n+36n+15n5 であることが

 オンライン整数列大辞典に載っているとのコメントをたけちゃんさんより頂きました。

 その理由を述べます。まず、頂点に番号 1,2,……,n と番号をつけておきます。

 (1) 1,2,……,n,A,B,C から 6 個を選ぶ方法は n+36 通りあります。

  番号3個と 記号A,B,C の3個を選んだ場合、
  頂点3個のうち 番号の小さい順に A,B,C として、△ABCを作ります。

  番号4個と 記号A,B,C のうち2個だけを選んだ場合、
  頂点4個のうち 番号の小さい順に A,B,C,D とし、
  線分AC,BD ともう1本の線分を次のようにして三角形を作ります。
  記号が A,B のときは 線分AB 、B,C のときは 線分BC 、C,A のときは 線分CD 。

  番号5個と 記号A,B,C のうち1個だけを選んだ場合、
  頂点5個のうち 番号の小さい順に A,B,C,D,E として、
  記号が A のときは ∠CAD と 線分EB ,記号が B のときは ∠DBE と 線分AC ,
  記号が C のときは ∠ECA と 線分BD で三角形を作ります。

  番号6個を選び、記号A,B,C のいずれも選ばなかった場合、
  頂点6個を 番号の小さい順に A,B,C,D,E,F として、
  線分AD,BE,CF で三角形を作ります。

 (2) 1,2,……,n,D から 5 個を選ぶ方法は n+15 通りあります。

  番号4個と 記号D を選んだ場合、
  頂点4個のうち 番号の小さい順に A,B,C,D とし、線分AC,BD,DA で三角形を作ります。

  番号5個を選び 記号D を選ばなかった場合、
  頂点5個のうち 番号の小さい順に A,B,C,D,E として、∠ADB と 線分CE で三角形を作ります。

 (3) 1,2,……,n から 5 個を選ぶ方法は n5 通りあります。

  頂点5個のうち 番号の小さい順に A,B,C,D,E として、∠BEC と 線分DA で三角形を作ります。

 (1)(2)(3)ですべての場合を重複なく網羅するので、n+36n+15n5 です。

 辺を含めない場合は、[解答1]のように、除外するのは、

 n(n-2)(n-3)/2+n(n-4)+n=n2(n-3)/2 ですので、途中の計算を省略しますが、

 n+36n+15n5-n2(n-3)/2=n(n-4)(n+3)(n3+16n2-67n-10)/720 になります。 


[追記]

 [参考]のように考えるのであれば、

 凸n角形で、対角線に辺を含めた n(n-1)/2 本のうちの3本でできる三角形の個数は、

 n+36n+26n6 のほうが良いと思います。

 [参考]と同様に、頂点に番号 1,2,……,n と番号をつけておきます。

 1,2,……,n,A,B,C または 1,2,……,n,D,E から 6 個を選びます。

 番号3個と記号3個を選んだ場合、
  頂点3個のうち 番号の小さい順に A,B,C として、△ABCを作ります。

 番号4個と 記号のうち2個だけを選んだ場合、
  頂点4個のうち 番号の小さい順に A,B,C,D とし、
  線分AC,BD ともう1本の線分を次のようにして三角形を作ります。
  記号が A,B のとき 線分AB 、B,C のとき 線分BC 、C,A のとき 線分CD 、D,E のとき 線分DA 。

 番号5個と 記号のうち1個だけを選んだ場合、
  頂点5個のうち 番号の小さい順に A,B,C,D,E として、
  記号が A のときは ∠CAD と 線分EB ,記号が B のときは ∠DBE と 線分AC ,
  記号が C のときは ∠ECA と 線分BD ,記号が D のときは ∠ADB と 線分CE ,
  記号が E のときは ∠BEC と 線分DA で三角形を作ります。

 番号6個を選び、記号を選ばなかった場合、
  頂点6個を 番号の小さい順に A,B,C,D,E,F として、
  線分AD,BE,CF で三角形を作ります。

 これで すべての場合を網羅し 番号6個を選ぶ場合が重複するので、n+36n+26n6 です。

 辺を含めない場合は、[解答1]のように、除外するのは、

 n(n-2)(n-3)/2+n(n-4)+n=n2(n-3)/2 ですので、途中の計算を省略しますが、

 n+36n+26n6-n2(n-3)/2=n(n-4)(n+3)(n3+16n2-67n-10)/720 になります。 

.

スポンサーサイト



Comments 20

There are no comments yet.
さっちゃんこ  
No title

おはようございます
真っ白な蔓バラが清楚で良いですネ
大きな花の薔薇も良いですがつる薔薇のように小さな花が一杯咲いてくれるのも良いですネ

ナイス☆彡

樹☆  
No title

おはようございます
可愛いノイバラ。。一重は豪華ではないのに
気品があってすてきです。ナイス

ニリンソウ  
No title

白のモッコウバラでしょうか、棘が無いように見えたので。野薔薇も咲いてきました。

ナイス

tsuyoshik1942  
No title

「解答」+「参考」早速読ませていただきました。
まだ読みきれていませんが、いずれにしろ大変ですね!

自分も最初は、同様な「区分け+数え上げ」を試みましたが、7角形でさえ「189個」が出てこず、あきらめました。
そこで、十進BASICに頼りました。ただ、そのプログラムにも、自信がもてませんでしたが、何はともあれ、「7角形の時、189」をはじき出したので、7474260を送信させていただきました。

当たっていてうれしかったです。その後も「数え上げ」の再試行、一般解の模索に挑戦しましたが、ゴールできませんでした。
ヤドカリさんのたけちゃんさんへのリコメを参考に、最後にようやく、一般解だけはつかめました。

たけちゃん  
No title

[参考]について,
一般項(n+3)C6+(n+1)C5+nC5 (*1)はオンライン整数列大辞典(OEIS) によるもの,
その意味付けはヤドカリさんの功績です.

私は,対角線に辺を含めたn(n-1)/2本のうち,三角形の辺をなす3本の
両端の頂点(のべ6個)のうち,異なるものの個数Nで分類して考えました.
[解答1],[解答2]を混ぜたような感じですが,以下のようです.

たけちゃん  
No title

N=3のとき,nC3通り.(n個の頂点から3個を選ぶ)
N=4のとき,4*nC4通り.
(n個の頂点から4個を選び,辺を1つ選んで対角線と合わせる)
N=5のとき,5*nC5通り.(n個の頂点から5個を選び,
頂点を1つ選んでそこから五角形の対角線を引いて,残り2頂点を結ぶ)
N=6のとき,nC6通り.
(n個の頂点から6個を選び,六角形ABCDEFならAD,BE,CFを結ぶ)
以上を合わせて,nC3+4*nC4+5*nC5+nC6通り. (*2)

(n+3)C6=nC3+3*nC4+3*nC5+nC6, (n+1)C5=nC4+nC5
(いずれも,パスカルの三角形で,
ある数を斜め上2つの和として表すことを繰り返せば確かめられます)
なので,(*1)と(*2)は一致します.

なお,[解答1],[解答2]の1行目「n<rのときnC2=0」は「nCr=0」と思われます.

uch*n*an  
No title

この問題は,最初,
対角線から3本を選び凸n角形の頂点に集まる場合と外で交わる場合を引けばいいだろう,
と考えたのですが,凸7角形の場合ですらややこしいことになり,はまってしまいました。
翌日仕切り直しをして[解答1]で答えを得ました。
その際に思い出したのですが,浮浪さんのところや算チャレで類題があったと思います。
もっとも,[解答2]の地道な考え方で考えようとしなかったことは猛省すべきですね。
なお,[参考]は巧妙で面白いですが,答えを求めるなら[解答1]の方向が簡単で,
nC3 + 4 * nC4 + 5 * nC5 + nC6
になります。この方が式の意味も明解だと思います。

uch*n*an  
No title

一見違って見えますが,nCr = (n-1)C(r-1) + (n-1)Cr,を使えば,
nC3 + 4 * nC4 + 5 * nC5 + nC6
= (((nC3 + nC4) + (nC4 + nC5)) + ((nC4 + nC5) + (nC5 + nC6))) + (nC4 + nC5) + nC5
= ((n+1)C4 + (n+1)C5) + ((n+1)C5 + (n+1)C6) + (n+1)C5 + nC5
= ((n+2)C5 + (n+2)C6) + (n+1)C5 + nC5
= (n+3)C6 + (n+1)C5 + nC5
と,容易に示すことができます。
むしろ,この最後の式の意味を解釈したものが[参考]といった方がいいのかも...?

uch*n*an  
No title

おっと,たけちゃんさんのコメントが既にありましたね。
>その意味付けはヤドカリさんの功績です.
ふむ,やはり,式の意味を解釈し直した,ということなんでしょうか。
いずれにせよ,たけちゃんさんではなく,ヤドカリさんのオリジナルなのかな?

スモークマン  
No title

グーテンターク ^^
たしかに類題を考えたことがあった記憶があったのですが…^^;
わからず…最終的に、3本の対角線で辺を含まない△のできないように40角形を分割する場合を740C3から引けばいいはずと思うも…これまたわからず…断念しちゃいました…^^;;…数列大辞典には載ってないということはオリジナルなカウントなんだと思われます☆…Orz~
熟読玩味ぃ~でっす ^^;v

ヤドカリ  
No title


写真の花はアズマイバラです。
これも浜寺公園で見ました。
関東南部に分布するそうです。
関東地方に多いのでアズマイバラです。
オオフジイバラ,ヤマテリハノイバラ
とも言われます。

ヤドカリ  
No title

さっちゃんこさん、早速のコメントとナイス!を有難うございます。
素朴な白い花がたくさん咲いている光景はいいですね。
人間によって品種改良を加えられていないのもいいものです。

ヤドカリ  
No title

樹ちゃん、早速のコメントとナイス!を有難うございます。
ノイバラの素朴な美しさもいいですね。
豪華でないところが可憐に感じます。

ヤドカリ  
No title

ニリンソウさん、早速のコメントを有難うございます。
上に書きましたように、アズマイバラという花です。
野薔薇は素朴ながらもたくさん咲くのがいいですね。

ヤドカリ  
No title

tsuyoshik1942さん、早速のコメントを有難うございます。
けっこう面倒な問題だったと思います。
対角線が内部で交わる場合と頂点で交わる場合があり、
プログラミングも工夫を要したことと思います。

ヤドカリ  
No title

たけちゃんさん、コメントとコピペのミスの指摘を有難うございます。
[参考]については、誤解のないように書き直しました。
大辞典に載っていることなので、自分の功績のようには思っていませんでした。
Cの性質を使っての説明は簡単ですが、折角ですので、意味付けをしました。
[追記]を加えましたが、[参考]のように考えるのであれば、
こちらの方が自然かなと思います。

ヤドカリ  
No title

uch*n*anさん、コメントを有難うございます。
> やはり,式の意味を解釈し直した,ということなんでしょうか。
たけちゃんさんより、式を示され、その式に合うように意味付けしました。
これもたけちゃんさんからの情報ですが、
浮浪の館の第703回の正解者掲示板にもこの式が書かれていました。
貴殿もこの式についてコメントされていますね。
私は解いた翌日に正解者掲示板を見ていませんでしたので、初見の式でした。

ヤドカリ  
No title

スモークマンさん、コメントを有難うございます。
740C3 から引くのは大変だと思われます。
740C3=67263780 になり、正解の9倍ほどの値です。
引き算する方が大変な計算になる可能性が高いです。

uch*n*an  
No title

[追記]ですが,
>(n+3)C6+(n+2)C5-nC6 のほうが良いと思います。
は,(n+3)C6+(n+2)C6-nC6,の書き間違いではないのかな?
意味的にもこの方が自然だし,計算でも,
(n+3)C6 + (n+1)C5 + nC5
= (n+3)C6 + (n+1)C5 + (nC5 + nC6) - nC6
= (n+3)C6 + ((n+1)C5 + (n+1)C6) - nC6
= (n+3)C6 + (n+2)C6 - nC6
なので。
確かにこの方が,意味が少しは分かりやすい感じがありますね。

ヤドカリ  
No title

uch*n*anさん、コメントを有難うございます。
仰るとおり、書き間違いで、早速、訂正しました。
(n+2)C5 では後の説明が台無しですね。