当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。
（平成２６年７月３０日付け）
電車のシートに座っていく光景を眺めていると、既に座っている人の隣には余り座ろうとせ
ず、一つ飛ばしのシートか、もしくはなるだけ離れた位置に座ろうとする。
もちろんその余裕がとれないときは隣に座っていく。
そこで、今、７人がけのシートが全て空いていて、そこへ７人の乗客が一人ずつ乗り込んで
くるとする。
もちろん最初の乗客はこのシートの任意の位置に腰を下ろす。
（座る席は１〜7の番号で指定されているとする。）
２番目の乗客は、最初の客と隣り合わないように離れた位置に座る。
以下、同じように、なるだけ接触しない位置を選んで座っていく。ある程度人が座ると、もう
そんな位置がとれなくなり、仕方なく任意の客の隣に席をとることになる。
さて、このシートの席が７人で埋め尽くされる順序のパターンは、全部で何通り起こるでしょ
うか？
これを任意の人数のシートでその数をプログラムを使って算出しようと試みていましたが、
力量不足で果たせませんでした。
どなたか挑戦してもらい、２０人ぐらいまでのシートの座り方の数を調べてくれませんか？
（答） ＹＩ さんが考察されました。（平成２６年７月３０日付け）
とりあえず、７人の場合だけ、これ以上隣り合わずに座ることができない座り方をリストアッ
プします。 ○：座っている ×：空席
○×○×○×○
○×○××○×
○××○×○×
○××○××○
×○×○×○×
×○×○××○
×○××○×○
それぞれ、（○の入り方）×（×の入り方）なので、それぞれ ３！４！＝１４４
重複は無いので、 １４４×７＝１００８（通り） でしょうか？
※ ８人になると全く通用しませんけど．．．。
らすかるさんが考察されました。（平成２６年７月３０日付け）
５０人までの計算結果です。
1：1
2：2
3：4
4：12
5：48
6：192
7：1008
8：5760
9：36000
10：259200
11：1987200
12：16692480
13：152409600
14：1480550400
15：15473203200
16：171918028800
17：2022780211200
18：25218127872000
19：330960494592000
20：4567605977088000
21：66143376617472000
22：1001899059904512000
23：15855869577461760000
24：261608521820405760000
25：4492161486886993920000
26：80172602431529287680000
27：1484793256348644802560000
28：28498951455840888422400000
29：566223265941970039603200000
30：11631079000329128666726400000
31：246760225074235945097625600000
32：5401431261912294167150592000000
33：121872760563765068276170752000000
34：2831953644713406414584807424000000
35：67713945962803883950397718528000000
36：1664710135475538649425779884032000000
37：42047667635552721319030312402944000000
38：1090379166922121789922415088762880000000
39：29010351685655195195033400807260160000000
40：791387828437960832997761651866337280000000
41：22121848477121849668148554541794590720000000
42：633281758702987795902124328611699752960000000
43：18555608548317596828278943065449273753600000000
44：556194116324059197270101627148220288204800000000
45：17046337258517163343500516219362669808844800000000
46：533923743779898437574542309109776581342003200000000
47：17083225791039656262422233291465729667550412800000000
48：558097875888591366686949868193740379652096000000000000
49：18608694954996018755058415366800430985662955520000000000
50：633007944754854918108578143074426536214543728640000000000
ＤＣＯさんが考察されました。（平成２６年７月３１日付け）
あまりに面白そうな問題だったため、チャレンジしてみました。
ｎ人席において、ｋ人座ったところで初めて隣の人のいない席がなくなった(飽和状態)とし
ます。
例えば、○を人のいる席、×を空席とすると、飽和状態の一例として、○×○××○×が
あります。このときは、ｎ=7、ｋ=3 です。同じ ｎ=7 でも、○×○×○×○であれば、ｋ=4にな
ります。
ここで、○と×を区別しない時、飽和状態になるような席の取り方は、漸化式等を使うと、
k+1Ｃn-2k+1
で与えられることが分かります。
○への人の入り方が ｋ! 通り、×への人の入り方が (ｎ-ｋ)!
ですから、ｎ人席で、ｋ人座って初めて飽和状態になったときの座り方は、
k+1Ｃn-2k+1 ｋ!(ｎ-ｋ)!
となるようですね。ｋで考えられるものは、
[(ｎ+2)/3]≦ｋ≦[(ｎ+1)/2] (ただし、[ ]はガウス記号)
を満たすもののみですから、その範囲で、ｋについての総和 Σk+1Ｃn-2k+1 ｋ!(ｎ-ｋ)! を計算す
れば、一般解が求まるようです。
(私には、これ以上この式を簡単にすることはできませんでした。)
ｎ=7 程度なら、ｋ=3、4 の時のみ考えればいいので、手計算でも出来ますね。
ｎ=20 となると、ｋ=7、8、9、10 の４通りがあり、数字も大きくなるので大変ですが．．．。
（コメント） 飽和状態になるような席の取り方の総数「k+1Ｃn-2k+1 通り」は、次のように考え
ればいいのでしょう．．．。（平成２６年８月２日付け）
・○がｋ個並んでいる。 → ○○・・・○
・もうこれ以上隣り合わずに座ることができないということは、○の間に１個または２個の×
が入る。○の間に×が１個（合計 ｋ−１個）は入るときを考える。 → ○×○×・・・×○
・ｎ人なので、あと ｎ−ｋ−（ｋ−１）＝ｎ−２ｋ＋１個の×が残っている。その×を、 ｋ＋１個
の○同士の隙間または端に選んで入れればよい。 → ○××○×・・・×○ など．．．。
したがって、飽和状態になるような席の取り方は、k+1Ｃn-2k+1 通りとなる。
※ ＤＣＯさんは、この式を漸化式等で求められたとのことですが、どのような漸化式を用
いられたのか少し興味があるところです。
ＧＡＩ さんからのコメントです。（平成２６年７月３１日付け）
一般式の提示、有難うございます。因みに、Mathematicaでプログラムを組んで実行しまし
た。
T[n_]:=Sum[Binomial[k+1,n-2k+1]k!*(n-k)!,{k,Floor[(n+2)/3],Floor[(n+1)/2]}]
Table[T[#]&]/@Range[50]//ColumnForm
すると、らすかるさんの結果が入手できました。
ＹＩ さんが類題を考えられました。（平成２６年７月３１日付け）
１．同様の方法で、ｎ×ｎに席が配置されている。
２．ｎ人掛けのシートで、乗客は「隣り合う人が最も少なくなる」ように座る。
（隣に人がいないように座れなくなったら、一人と隣り合う席に座る）
らすかるさんからのコメントです。（平成２６年７月３１日付け）
「ｎ×ｎの席」を考えると、畳に座布団がｎ×ｎに敷き詰められているような状態（つまり、端
でない人は「隣」が４席）に思えますが、「ｎ人掛けのシートｎ個」という前提なのでしょうか？
ＹＩ さんからのコメントです。（平成２６年８月１日付け）
縦方向も、「隣り」であるとします。
らすかるさんからのコメントです。（平成２６年８月１日付け）
なるほど。そういう条件ならば、（私には）解けそうな気がしません。
ＰＩ さんからのコメントです。（平成２６年７月３１日付け）
この問題とは関係ありませんが、かつてクイズ番組でやっていた問題を思い出しました。
７人掛けのロングシート(座る位置は、1〜7 とする)に、なるべく他の人の遠くになるように
１人ずつ座るとき、１人目は(1)、２人目は(7)、３人目は(4)と座ってしまうと、後の２人は、(2.5)
(5.5)の場所に座ってしまい５人しか座れない事態が発生する。
(実際には膝送りで、７人分を確保しますが．．．。)
これを避けるには、３人目はどこに座ればよいか？ ・・・・・・→答えは、(3)
すると、４人目は(5)に座り(5と3は逆でも可)、(2)(4)(6)が空席として空くのでそこに３人座る。
という内容だったと思います。
これを一般化すると、「左右に空席が ２n−１ 席できるように座るとよい」になるのでしょう
か？
らすかるさんからのコメントです。（平成２６年７月３１日付け）
例えば、８人掛けのロングシートに、１人目が(1)、２人目が(8)に座った後、３人目が「左右
に空席が ２n−１ 席できるように座る」のは無理ですね。
ＰＩ さんからのコメントです。（平成２６年８月１日付け）
最初の２人が(3)(7)に座ると可能ですね！(●を人のいる席、数字を空席とすると、
(1)(2)●(4)(5)(6)●(8) → 次の人は隣りあわない(1)(5)に座る)
７人掛けの場合も、実は１人目が(3)に座るだけでいいみたいです。
ルールを追加して、私も出題してみます。
ｎ人掛けのロングシートに以下のような状況になるように座るとする。
・人と人の間に空席が、２k−１＝0、1、3、7、15、・・・席
・人と端の間に空席が、２k＝0、1、2、4、8、16、・・・.席
最低何人で、この状況を生み出せるか？
らすかるさんからのコメントです。（平成２６年８月１日付け）
(3)に座る人が、「左右に空席が ２n−１ 席できるように座る」という条件を満たしませんね。
私の例でも(8)に座る人が条件を満たしていませんでした。
再度考え直したら、７人掛けのとき、(4)(2)(6)の順に座れば条件を満たし、８人掛けのとき、
(1)(5)(3)(7)の順に座れば条件を満たしますね。
しかし、９人掛けの場合は最初の一人が条件を満たすように座るのが不可能ですね。
ＰＩ さんからのコメントです。（平成２６年８月１日付け）
最初に投稿した、「なるべく他の人の遠くになるように1人ずつ座るとき定員ピッタリ座る方
法」について、言ったつもりでした。
「人と人の間に空席が ２n−１ 席、人と端の間に空席が ２n 席できるように座る」とすると、
残りの人が既に座っている人のなるべく遠くになるように座っても定員通り座れると思うので
すが、いかがでしょう？
らすかるさんからのコメントです。（平成２６年８月１日付け）
私もそのつもりですが…、そうすると、８人掛けの時に最初の人が座る場所がないですね。
ＧＡＩ さんからのコメントです。（平成２６年８月１１日付け）
上記の話題に関連して、次のような先人の研究がされているのを読みました。
レーニィの駐車定数
x＞1 である１次元区間 [0，x] を考える。道の一方だけに駐車することが許されていると仮
定する。単位長さの車が道にランダムに一台ずつ駐車する。
このとき、駐車できる車の平均台数M(x)は？
これに対しRenyi(レーニィ)は、
0≦x＜1 のとき、M(x)=0 、x≧1 のとき、M(x)=1+2/(x-1)*∫0x-1 M(t)dt
の積分方程式を満たすことから、ラプラス変換などの高度なテクニックを駆使して、区間[0，x]
の車の極限平均密度ｍが、
ｍ＝limx→∞M(x)/x＝0．7475979･････
であることを算出している。（→参考：「A050996」）
即ち、約0．7476･･･（全体の74．76%）を駐車の車で占めることを教える。
さらに、他の人が道に駐車できる車の分散V(x)が、
Ｖ＝limx→∞ V(x)/x＝0．0381563991･････
で与えられると結果を導いている。（→参考：「A086245」）
これらは、中心極限定理が成り立つようになるという。即ち、車が駐車できる総数は漸近的
に十分大きなxに対して、平均が、ｍｘ＝0．7475979･･･x 、分散が、Ｖx＝0．0381564･･･x の
正規分布となるらしい。
また、変形バージョンとして、長さ ｘ＞１、幅 ｙ＞１ の２次元長方形を考え、この駐車場の長
方形に平行に単位正方形の車を駐車すると仮定すると、駐車できる車の台数の平均M(x，y)
は、予想として、
limx→∞limy→∞ M(x，y)/(xy)＝ｍ2＝(0．7475979･･･)2＝0．558902･･･
であるが、徹底的なコンピュータシュミレーションで計測すると予想ははずれ、真の値は、
0．562009･･･になるという。（つまり、２次元への拡張は１次元とは微妙に差異が生じる。）
いやはや奥が深いものがある。(→参考：「Renyi's Parking Constants」）
以下、工事中！