巧铺地板

shshsh_0510

呵呵，不求甚解是我的本性，出错是正常的。
对于n*m的棋盘的2*1覆盖好像叫做domino tilings,在“晶体统计力学”（也不知是不是这么译）中被研究过，看看2N*2N时的公式就知道自己解不出了

$\prod_{i=1}^{n}\prod_{j=1}^{n}(4cos^2{\pi i}/{2n+1} + 4cos^2{\pi j}/{2n+1})$

mathe

漂亮的结果。
也就是只余下2N*(2N+1)的结果了

gxqcn

to shshsh_0510:
我将你传的图片内容直接以数学公式形式编辑进帖子了，原图片就删除了。
另，请注意我早上给你发过短消息，请注意接收并回复。

shshsh_0510

(2m)*(2n)的domino tilings计数公式为：
$4^{mn}\prod_{k=1}^{m}\prod_{j=1}^{n}(cos^2{\pi k}/{2m+1} + cos^2{\pi j}/{2n+1})$

这个数也是比较有意思的，除了$4^{mn}$乘积的其他各项都不是整数，结果却是整数。
从那个公式不太容易看出来这个数大约到底有多大，这里有个估计公式
N(2n,2n)约为$C^{4*n^2}$
其中$C=e^{G/pi}=1.338.....$
G为卡特林常数=1-1/3^2+1/5^2-1/7^2...=0.9159...
(现学现卖 )

[ 本帖最后由 mathe 于 2008-5-6 13:29 编辑 ]

mathe

你这个公式从哪里得到的？显然同m=n=2N时候的结论不符合？

mathe

我的计算方法基本上同你的递推式类似，只是每次递推关系都要计算机重新分析一次（多余了 ）
计算结果n*(2k)的解的数目是

2k	count
2	8
4	95
6	1183
8	14824
10	185921
12	2332097
14	29253160
16	366944287
18	4602858719
20	57737128904
22	724240365697
24	9084693297025
26	113956161827912
28	1429438110270431
30	17930520634652959
32	224916047725262248
34	2821291671062267585

[ 本帖最后由 mathe 于 2008-5-6 11:57 编辑 ]

shshsh_0510

是吗？没注意，看完前还是不说话了为好，直接把附件给出
[local]stanley_ardila_tilings.pdf[/local]

shshsh_0510

怎么上传不了呀？给了链接吧
stanley_ardila_tilings.pdf (811 KB)

gxqcn：之所以上传不成功，只因文件超出了论坛允许上传size的上限500KB

mathe

里面还提到一个marriage theorem也挺有意思,同这个问题也相关,wolfram里面这样描述这个定理:
If a group of men and women may date only if they have previously been introduced, then a complete set of dates is possible iff every subset of men has collectively been introduced to at least as many women, and vice versa (Hall 1935; Chartrand 1985, p. 121; Skiena 1990, p. 240).

shshsh_0510

没注意作者中居然有stanley，是不是比较渊博呀
记得当初去蹭陈永川的课听（这个名字可以在这里找到： http://bbs.emath.ac.cn/thread-44-1-2.html），陈对knuth都有些不屑一顾，但对stanly好像比较的服