円形テーブルへの座り方

質問

こんにちは。
数学の問題で悩んでいます。

1<=k<=nとしたとき
n人がk個の円形テーブルに分かれて座るときの座り方を考える問題です。（どのテーブルにも最低１人は座るとします）

いいアイデアが思い浮かばないので、どなたかわかる方がいましたら教えてください。

回答No.7

kumipapa

#5です。済みませんが、最後の最後に誤りあり。

＞　ｎ！／｛Σ(1/Πa_i)｝

ではなくて、
ｎ! { Σ(1/Πa_i)｝
でした。

回答No.6

AssurBanipal

>1<=k<=nとしたとき
>n人がk個の円形テーブルに分かれて座るときの座り方を考える問題です。
>（どのテーブルにも最低１人は座るとします）

テーブルは全て区別するものとします。
求める場合の数を、A(n,k) とすると、A(n,k) は
第一種スターリング数 S(n,k) を用いて次のように書けます。

A(n,k) = ((-1)^(n-k))*(k!)*S(n,k).

( S(n,k) は t についての多項式 t*(t-1)*(t-2)* … *(t-n+1) を
展開したときの t^k の係数に等しいです。)

計算例：
A(6,3)=((-1)^(6-3))*(3!)*S(6,3)=1350,

A(20,5)=((-1)^(20-5))*(5!)*S(20,5)=44566174481427360000,

A(100,14)=((-1)^(100-14))*(14!)*S(100,14)
=684983406866944487848173190201501705233805954669110494537862211
8913615294617961392773518596917970226797056312637796888412544816
32687318880198732294289096704000000000.

回答No.5

kumipapa

#1さんがおっしゃる通り、ちょっと問題がはっきりしていないのですが・・・
わざわざ円形のテーブルって言うのですから、各テーブルでの席順まで含めて考えるんですか？

まず、テーブルは区別するとします。また、一つのテーブルに座れる人数の上限はないとします。１００人でも座れるテーブル・・・ですが。

１番目のテーブルにａ_1 人、２番目のテーブルにａ_2人、・・・ｋ番目のテーブルにａ_k人座ることを考えます。
ａ_i＞０，Σａ_i＝ｎ　（i=1,2,・・・,k)
です。
１番目のテーブルに座る人の選び方は nＣa_1 通りで、その人たちをテーブルに座らせる順序は円順列で (a_1 － １)！ 通りです。ですから、１番目のテーブルだけの座り方は
nＣa_1 (a_1－１）! ＝ ｎ!(a_1－１)!／(（n-a_1)! a_1!) ＝ｎ!／（(n-a_1)! a_1)
通り。
次に、２番目のテーブルに座る人の選び方は(n-a_1)Ｃa_2通りで、席順は(a_2－１)! 通りですから、１番目と２番目のテーブルまでの座り方は、
{ｎ!／（(n-a_1)! a_1)} (n-a_1)Ｃa_2 (a_2－１)! ＝ｎ!/（(n-a_1-a_2)! a_1 a_2）
通り、というようにk番目のテーブルまで計算していくと、各テーブルに座る人数をa_1,a_2,・・・,a_k人ときめてしまった場合には、
ｎ！／（a_1×a_2×a_3×・・・×a_k）・・・（１）
通りの座り方があります。
結局、ｎ人を１列にならべて、(それをk個に区切って普通の順列にした場合に対して)円順列は 1/a_i になるからそれで割って、という式です。
あとは、すべてのa_1,a_2,・・・,a_kの組み合わせについて（１）を足せば良いのですが、それが簡単な式にならないと思う。
で、ｎ人がｋ個の円卓に座るのは、
ｎ！／｛Σ(1/Πa_i)｝　（　適当ですが (a_1,a_2,・・・,a_k)∈｛N^k｜a_i≧1,Σa_i＝n}
通り。

ではないでしょうか。もし、テーブルを区別しないならば、これは単純にk!で割ってよろしかろうと。

回答No.4

nettiw

（テーブルは区別する）ときは、
包含と排他原理が使用できそうですが。
（テーブルは区別しない）ときは、
ｎ、ｋではアルゴリズムに依存するしかなさそうです。

小さい数で記して終わります。
（テーブルは区別する）（人数６）（テーブル３）の場合.
各テーブルに一人ずつ配置します。
○○｜○｜
左から見て、
テーブルＡには（2+1）人、座り方は、2!
テーブルＢには（1+1）人、座り方は、1!
テーブルＣには（0+1）人、座り方は、0!
配置人数の場合の数は、5C2=１０通り、
列挙すると（各一人を除き）、
300---3!0!0!*(6C4)(2C1)(1C1)=6*30
030---
003---
210---2!1!0!*(6C3)(3C2)(1C1)=2*60
201---
120---
102---
021---
012---
111---1!1!1!*(6C2)(4C2)(2C2)=1*90
(180*3)+(120*6)+(1*90)=540+720+90=1350通り。

回答No.3

fuuraibou0

例題、ｎ＝５人、ｋ＝３　の場合、座り方の総数は、ｋ^n＝３^5＝２４３　通り、

（１） 空席テーブルが２つの場合、５人全てが１つのテーブルに座る、その
座り方は、いずれでもよく、テーブルの数だけあり、３　通りです。

（２） 空席テーブルが１つの場合、空席テーブル１つの選び方は、いずれのテーブルでもよいから、これもテーブルの数だけあって、３　通りあり、そして、
この各々の場合に対し、５　人が残りの　２つのテーブルに座る座り方は、
２つのテーブルのうち一方が空席になる場合を除き、２^5－２＝３０　通り、
したがって、空席が　１つ　の座り方は、３＊３０＝９０　通り。よって、

どのテーブルにも最低１人が座る座り方の総数は、先に示した考えの通りで、

　２４３－（３＋９０）＝１５０　通りになります。

回答No.2

fuuraibou0

重複順列と配分の問題
１人 が k 個の円形テーブルに座るときの座り方は、ｋ 個のどれでもよいから ｋ 通りで、ｎ 人にたいしても同様だから、1≦k≦n とした場合の座り方の総数は、積の法則により、ｋ を ｎ　ほど掛けて、

　　ｋ＊ｋ＊ｋ＊・・・＊ｋ＝ｋ^n　通りである。

しかし、どのテーブルにも最低１人が座る場合は、上の場合（ｋ^n）から、空席ができる場合の数を引くと求められます。簡単に云えば、ここまでですが、
まだ、どうしても解らない場合は、簡単な例題で説明いたします。

お礼

ありがとうございます。
参考にもう少し考えて見ます。

回答No.1

Tacosan

何を問題にしているのかが, 文面から読み取れないんですけど....