شخصی به نام سی.دادلی.لانگفورد (من متوجه نشدم که ریاضیدان بوده یا صرفن علاقه مند به ریاضی ) متوجه می شود که پسرش هنگام بازی با سه جفت مکعب (سه رنگ هر جفت از رنگی ) و قراردادن آنها در یک ردیف به چیدمانهای جالبی می رسد.از جمله فاصله بین مکعبهای هم رنگ که برای رنگ اول یکی و برای رنگ دوم دوتا و برای رنگ سوم سه تاست.ایشان این پرسش برایش ایجاد می شود که اگر جفت ها را زیاد کرد آیا باز هم چنین چیدمانی امکان دارد.ایشان مساله را برای مجلهای ریاضی میفرستد و شخصی به نام (Roy O. Davies) در ژورنال ( Mathematical Gazette v. 43 (1959)) در سال (1959) جواب سوال را می دهد.
آیا جایگشتی از دنبالۀ:
$$1,1,2,2,3,3,...,n,n$$
وجود دارد که برای هر $1 \leq k \leq n$ ، $k$ عدد بین $k$ و $k$ باشد؟
برای $n=1$ و $n=2$ امکان پذیر نیست.و مثلن برای $n=3$ داریم:
$$3,1,2,1,3,2$$
$$2,3,1,2,1,3$$
آقای داویس این نوع دنبالهها را دنباله های لانگفورد نامید.ایشان به صورت زیر نشان داد که چنین جایگشتهایی وجود دارد اگر و تنها اگر $n=4m$ یا $n=4m-1$ که در آن $m \in N$.
برای اثبات طرف اول فرض کرد چنین دنبالای موجود باشد.اگر مکانها را از چپ به راست نامگذاری کنیم و برای هر $1 \leq k \leq n$ مکانی را که برای اولین بار $k$ ظاهر میشود $x_k$ و مکانی را که برای بار دوم $k$ ظاهر میشود $y_k$ بنامیم داریم:
$$y_k-x_k=k+1, A:=\sum_{k=1}^nx_k+\sum_{k=1}^ny_k=\sum_{k=1}^n(x_k+y_k)=\sum_{k=1}^{2n}k=n(2n+1)$$
$$,B:=\sum_{k=1}^ny_k+\sum_{k=1}^nx_k=\sum_{k=1}^n(k+1)= \frac{1}{2} n(n+3)$$
$$ \Rightarrow B-A=2\sum_{k=1}^ny_k \Rightarrow n(2n+1) \equiv \frac{1}{2} n(n+3)(mod 2)$$
$$ \Rightarrow n=4m \vee 4m-1,m \in N$$
برای طرف دوم ایشان دنباله ارائه داد:
$if:n=4m$
$4m-4,4m-6,...,2m,4m-2,2m-3,2m-5,...,3,1,4m-1,1,3,...,2m-5,2m-3,2m,2m+2,...,4m-4,4m,4m-3,4m-5,...,2m+1,4m-2,2m-2,2m-4,...,2,2m-1,4m-1,2,4,...,2m-2,2m+1,2m+3,...,4m-3,2m-1,4m$
$if:n=4m-1$
$4m-4,4m-6,...,2m,4m-2,2m-3,2m-5,...,3,1,4m-1,1,3,...,2m-5,2m-3,2m,2m+2,...,4m-4,2m-1,4m-3,4m-5,...,2m+1,4m-2,2m-2,2m-4,...,2,2m-1,4m-1,2,4,...,2m-2,2m+1,2m+3,...,4m-3$
به طریق مشابه دنبالههای اسکولم تعریف میشود به این ترتیب که $y_k-x_k=k$.به طریق مشابه دنباله های اسکولم وجود دارند اگر و تنها اگر:
$$n=4m \vee n=4m+1,m \in N$$
حالا توجه شود که مسأله سخت اینه که تعداد جایگشتها یا دنبالههای لانگفورد و اسکولم چندتاست.اگر این تعداد را به ترتیب با $L(n)$ و $S(n)$ نشان دهیم نشان داده شده است که:
$$L(27) = 111, 683, 611, 098, 764, 903, 232$$
$$L(28) = 1, 607, 383, 260, 609, 382, 393, 152$$
$$S(24) = 102, 388, 058, 845, 620, 672.$$
$$S(25) = 1, 317, 281, 759, 888, 482, 688$$
$$S(28) = 3, 532, 373, 626, 038, 214, 732, 032$$
$$S(29) = 52, 717, 585, 747, 603, 598, 276, 736$$
البته الگوریتمهای جالبی برای پیداکردن این جایگشتها وجود دارد که زمان بر است.برای اطلاعات بیشتر به مراجع زیر مراجعه کنید:
$01)$ https://arxiv.org/pdf/1507.00315
$02)$ http://www.dialectrix.com/langford.html
$ \Box $
