「今月の問題」　第２１３回　（平成２９年６月）
 
＜問題＞　

２種類の記号”（””）”を用いて正しい括弧の式を作るには、次の２つの条件を満たす必要があります。

 ＜条件１＞
　全体として（ と ） の数は同じになる。

＜条件２＞
 　そのどの列のどの位置をとっても、それより左に　
　ある（ の数が ） の数以上になる。

　例えば、（ と ） を３個ずつ使った正しい括弧式は、右図のように５通りあります。

　ここで問題です。（ と ） を４個ずつ使うと正しい括弧の式は何通りになるでしょうか。

 

＜正解者一覧表＞　 　　　　　　　　　　　　　　　　　　　
位 　　　　ｎａｍｅ　　　 　　メール到着日時 　　 　　備　考　　
　１ ゴンとも　さん 2017/6/1　0:23 豊川市　
　２ 男はつらいよ　さん 2017/6/1　0:24 神奈川県　
　３ 次郎長　さん 2017/6/1　0:25 雨が降っている兵庫県
　４ algebra　さん 2017/6/1　0:26 神奈川県　
　５ 源内シンガポール　さん 2017/6/1　0:27 長崎県　
　６ 朝霞おじ　さん 2017/6/1　0:29 埼玉県　
　７ NNR4　さん 2017/6/1　0:31 兵庫県　
　８ kou　さん 2017/6/1　0:32 さいたま　
　９ バニラ　さん 2017/6/1　0:55 　
１０ Mr.ダンディ　さん 2017/6/1　1:00 　
１１ いぬたこ　さん 2017/6/1　4:45 千葉　
１２ うたねこ　さん 2017/6/1　5:22 関東　
１３ やまもと　さん 2017/6/1　5:23 名古屋　
１４ 鯨鯢(Keigei)　さん 2017/6/1　5:33 　
１５ 石原塾　さん 2017/6/1　10:41 　
１６ いちもく　さん 2017/6/1　12:45 立川市　
１７ やぶコウノトリ　さん 2017/6/1　13:34 兵庫県　
１８ uchinyan　さん 2017/6/1　14:14 東京都　
１９ dyslexia　さん 2017/6/1　14:28 大阪府　
２０ teki　さん 2017/6/1　17:07 　
２１ マッキー２７　さん 2017/6/1　22:00 愛知県　
２２ スモークマン　さん 2017/6/1　22:14 雷鳴ってる岡山県
２３ やすかず　さん 2017/6/2　10:22 愛知　
２４ ユートニウム　さん 2017/6/2　11:49 　
２５ けーすけ　さん 2017/6/2　20:49 奈良　
２６ まいすた　さん 2017/6/3　21:37 　
２７ 巷の夢　さん 2017/6/6　16:07 神奈川県在住　
２８ たかひろ　さん 2017/6/9　17:14 埼玉県　
２９ りーくん　さん 2017/6/9　21:24 埼玉県　
３０ あめい　さん 2017/6/9　23:51 　

 

こたえは、１４通りでした

 

[334] もっと多くても、次のように求められます。 投稿者： 鯨鯢(Keigei) <6gatu> 投稿日： 2017/06/01(Thu) 21:38  
左から何番目を「 ( 」にするかで、8Ｃ4＝70 通り、
そのうち、途中で「 ) 」の方が多くなるのは、実は、8Ｃ3＝56 通り、
よって、70－56＝14 通りになります。

途中で「 ) 」の方が多くなるものについては、次の例のように、
「 ) 」が１つ多くなった所より右側を「 ( 」と「 ) 」を逆にしたものを対応させます。
例：　)-(()))(( ⇔ )-))((()) ，())-)(()( ⇔ ())-())() ，()(()))-( ⇔ ()(()))-)
なお、本来不要ですが、「 - 」は「 ) 」が１つ多くなった所の右(区切り)を表しています。
これは、８個のうち「 ( 」が３個ですので、8Ｃ3 です。
[333] Re:[330] カタラン数 投稿者： Mr.ダンディ <6gatu> 投稿日： 2017/06/01(Thu) 09:36  
> （0,0）から　（4,4）まで　ｙ＝ｘ　から上に出ることなく格子点を通っていく行き方の数
> だけあり　１４通り
> としました。

4つの「(」と4つの「）」の配置で、常に「（」の個数が先行（等しいのも含め）
しなくてはならないので
、上記のような考えに至りました。
これくらいの数だと、各格子点までの行き方の数を順に書き込んでいけば、簡単に数えられますね。
[332] 問題の答えの14通りは 投稿者： ゴンとも <6gatu> 投稿日： 2017/06/01(Thu) 02:12  
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

先のプログラムを数え上げる(let)から書く(print)
に変えればでて問題のサイズを4個からあげるのは変数の値が2個なので容易ですね。
[331] 十進Basic で 投稿者： ゴンとも <6gatu> 投稿日： 2017/06/01(Thu) 01:41  
(=-1,)=1として

for a=-1 to -1
for b=-1 to 1 step 2
if a+b>0 then goto 70
for c=-1 to 1 step 2
if a+b+c>0 then goto 60
for d=-1 to 1 step 2
if a+b+c+d>0 then goto 50
for e=-1 to 1 step 2
if a+b+c+d+e>0 then goto 40
for f=-1 to 1 step 2
if a+b+c+d+e+f>0 then goto 30
for g=-1 to 1 step 2
if a+b+c+d+e+f+g>0 then goto 20
for h=-1 to 1 step 2
if a+b+c+d+e+f+g+h>0 then goto 10
if a+b+c+d+e+f+g+h=0 then let s=s+1
10 next h
20 next g
30 next f
40 next e
50 next d
60 next c
70 next b
80 next a
print s
end

f9押して　14・・・・・・(答え)

手で書くと抜けがあるがプログラムなら抜けなく数え上げれますね。
[330] カタラン数 投稿者： Mr.ダンディ <6gatu> 投稿日： 2017/06/01(Thu) 01:06  
（0,0）から　（4,4）まで　ｙ＝ｘ　から上に出ることなく格子点を通っていく行き方の数
だけあり　１４通り
としました。