Das Lucassche Ehepaarproblem. Yon

Waldemar SchSbe in S t u ~ z. Zt. ha Felde.

Ein auch in zusammenfassenden Werken mehffach behA-deltes, abet noch nicht erledigtes kombinatorisches Problem ist die folgende Aufgabe yon LucAs 1): Auf wieviele Arten k6nnen um einen Tisch mit 2n Stiitden n Ehe- paare derart Platznetunen, da~ jeder Mann zwischen zwei Frauen, abet kein Mann neben seiner Ehefrau sitzt ?

Mit ~4~ soil die Anzahl der Sitzordnungen bezeiclmet werden, die die M/inner entsprechend der Bedingung des Problems einnelnnen kSnnen, nach- dem zuvor die Frauen, jeden zweiten Stuhl freilassend, irgendwie Platz ge- nommen haben. Um fiir ~fn eine Rekursionsformel abzuleiten, werden noch zwei andere Anzahlf~mlrtionen betrachtet: die Anzatd Bmder Sitzordnungen der MKnnex derart, daft ein bestimmter Mann auf einer bestlmmt~n Seite neben seiner Ehefrau, die iibrigen M~nner abernicht neben ihren F_~efrauen sitzen, und die Anzald (~ all der Sitzordnungen, bei denen ein bestlmmter Mann auf einer bestlmmten Seite neben seiner Ehef~au, irgendein weiterer Mann auf irgendeiner Seite neben seiner Ehefrau und aile tibrigen M~nner nicht neben ihren Ehefrauen sitzen. Dann gelten die Rekursionaformeln

�9 ~n+l ffi (71 - - ~ ) ~ s + ( 3 n - 4) B n + ~tt, (I) B . + , ----- A . -i- B . ,

~n+l = ( 2 n - - I) B . + G..

Hie.xnseh mul~ jede Anzah]fimktion einer linesren homogenen Rekursions- forme] 3. Ordnung geniigen, l~iir B . wild diese besonders einfaeh:

(2) B . + s ---- n Bn+l -~ ~ B . -~- B n - l .

Die Anfangswerte sind As = 0, Bs = 0, (~s = 1 flit (1) bzw. Bs = 0, Bs = 0, B4 = I fiir (2). Es wird dann B5 ----- 3. Einer dariiber hinaus noch bekannten Rekursionsformel 2. Ordnung fiir A, begegnen wit weiter unten. Ein ge- schIossener Ausdruck im iiblichen Sinne f'tir die Fo]gen A, , B~, (~s ist jedoch . bisher nicht angegeben worden. Das soil bier geschehen.

1) E. LUCAS, Th~orie des hombres, Psris 1891, Bd. I, Nr. 128, S. 215 u. 491--495 (Note III). -- Vgl. such W. AWa~NS, Mathem&t~ische Unterhaltungen und Spiele, 2. Aufl., Leipzig 1918, Bd. II, S. 73--79, und H. DOlmr~_, Triumph der Mathemstil~ 2. Aufl., Breslau 1940, S. 25--32.

782 W. 8ohSbe.

Die Fragestelhng, die zu den A~ fiihrt, ist unverkennbar verwandt mit dem altbekannten Problem, auf wieviele Arten ~ Briefe in n Umschliige so gesteckt werden kSnnen, dab kein Brief in den richtigen UmschIag gelangt, oder, in der Sprechweise unseres Problems: auf wieviele Arten die M~n~er so Platz nehmen kSnnen, dab keiner li~s neben seiner Ehefrau sitzt. Fiir diese Anzahlfunlction h~ kann die ReImrsionsforme|

(3) h,,+1 = . h . + - h , ~ _ l

hergeleitet werden, die sich dutch den Ansatz h~ -- -h~_l = g . sofort auf g~ +1 + g. = 0 reduziert. Die LSsung ist bekannt]ich

(4) h. = ~,! ~ ( - 1)"

h. and fiix unbegrenzt wa~hsendes ~ strebt ~ -~ e-L Hiernach mSchte man aus

heuristi~hen Watm~heinlichkeitsbe~rachtungen fiir das Ehepaarproblem At ,-'T-~ r vermuten, und das werden wit bestiitigen.

Der ~hnlichkeit yon (2) mit (3) Reclmung tragend, gehen wit mit dem Ansatz B.+I -- uBn -- b~_s in (2) ein und erhalten zun~ichst

(a)

und dann weiter

b . - a = B . + I -- nB~ = 0 . + 1 + b~) -- ,~ (b. + b ._ l ) oder

(b.+x - - . b . - - bn-1) -k (b~ - - (n - - 1) b . - 1 - - b ._~) = 0.

Also ist b.+x--ttb~--b._l = K - ( - 1 ) " , mad aus den Anfangswerten be ---- 0, bx ---- 1, b2 --=" -- 1 ergibt sich K = 2. Damit ist gewonnen

(6) b . § ---- n b . -k b . _ l q- 2 - ( - - 1) n.

Mittels dieser Rekursionsformel kann man die Folge dor b. aneh nach riick- wgrts fortsetzen. Es w i ~ b_ 1 = -- 1. hus der Gleichmag (6), gebildet flit n and flit --•, folgt dutch Subtraktion fiir t~----b. -k b_. die Rekursions- formel tn+ 1 = tttn -1- t . _ l . Da die Anfangswer~e to -~ 2 be ---- 0 und t 1 = bl -}- q- b_l = 0 sind. ist immer tn ----- 0, also

(7) b_. ---- -- b.,

eine Eigenschaft, die iibrigens nut bei den bier in Betracht kommenden An- fangswerten mi~ (6) vertr~iglich ist und im folgenden auch die explizite Be- nutzung der Anfangswerte vSllig ersetzt.

Das Lucassche Ehepaarproblem. 783

Mit Hiffe der b~ lassen sich die A. , B. , G~ einfach ausdriicken:

A ~ = b ~ + l - b ~ - l ,

(8) B~ ~- b~ + bn_l ,

C ~ = 2 b ~ + 3 b ~ _ l + 2 b ~ _ ~ .

Die zweite dieser Gleichungen hatten wir schon in (5), die beiden anderen folgen daraus nach (1) und (6). Fiihrt man dutch

(9) A~ = nb, + 2. (--1) n

As start bn in (6) ein, so ergibt sich die bereits erw~lmte, bier aher nieht gebrauchte Rekarsionsfolanel yon I~ISA~T

(n-- 1) A~+I ---- ( # - - 1 ) A~ + (n +1) A,_~ + 4- (--1)5

der sioh ii.tmliche fiir B,, und Ca an die Seite steUen lassen. Um nun (6) mit (7) aufzulSsen, fii]lren wit die HilfsgrSl]en

2 bk_, Ck, u ~ - ~ ! '

v ~ - 0

ein. Es wird

2bk+l_v 2(k--~')bk_,,+bk_,,_, + 2.(--1) k-" Ck+l' n ~--- V! ~--- V!

�9 ~ 0 v = O

= k ~ - - A e * ~ bk-o+ ,,: ,~ o=o e. (e ~ + 2-(--1)~ (--1)" ~--o

(wobei bier, ebenso wie einige Zeilen spiiter, fitr e = 0 ~ ~-0 zu setzen ist~ (o -- 1) !

b k _ n _ 1 1"~ n = kck,,,+ ,~! +2.(--1)k~i., ,

%+l,n ~ bk-n-1 (--1) k h n kt ( k - - 1 ) t - - ntkt + 2 k.t "n~"

also

Dutch Summation iiber k von 0 bis m folgt unter Beriicksichtigung von (7)

~m+l,n 1 2 b n + l - . h . 2 ( - - 1 ) ' mz + ~., k.~ = 9 . ~ k---7--

k - ~ 0 k=0 oder

und far m = n:

2 b~+~_~ k~ (. = O, 1, 2, .). v----~--- = en+l,n = n'-[ "" ~ - 0

78~ W. 8oh0be, Das Lueamohe Ehepasrproblem.

(11)

sehreibt man

a n - 1 F.rsetzt man fiir den Augenblick bn dutch ~ und ~ dutch ~ --/~, so l~St

sich das Ergebnis in die Form setzen n

= ,u ~' h~ ( n = O , 1 , 2 , . . . ) ,

so dab die % die Anfiinge der Differenzenfolgen zur Folge h~ darstellen. Dutch Umkehrung folgt

2 (") ' a,, = ~tl b.+l = (--1). u /t,,_u,

so dal~ nun mittels (8) die geschlossene Darstellung der A,,, B~, C_I~ geleistet

ist. Es wird A, = 2. (--1)" + ~ b , = 2. (--1) n + ~ a , _ l , also mit v = / ~ + l

Z (_ i ) , - i hll.-- ir (10) A . = 2 . ( - - 1 ) n + n (v--l)! (n-- , )!"

~ 1

Zum Beweis der Grenzbeziehlmg

A,, ~ e- 2 lim

n , , . , - 1 , . . )2 ~-"~" = 2 "-'-'nT-.t "[" (n -- v)! (v --i)! '

v = l

wobei ~ stets < 1 ist, und hat

-- ',,(~, - - 1 )u ~., + 2 1 1 -- ~ - 1 (~ -- ' ,=2 (,__1) -~ 1)!~ 0

well die Randglieder der Summe ~v, die Gr61~enordnung 1 , die inneren 1 hSchstens die Gr61~enorclnung ~ haben.

(Eingegangen am 20. November 1942.)