繁體
|
簡體
Sclub交友聊天~加入聊天室當版主
(檢舉)
分享
新浪微博
QQ空间
人人网
腾讯微博
Facebook
Google+
Plurk
Twitter
Line
快速注册
登录
论坛
搜索
帮助
原始风格
brown
purple
green
red
orange
gray
pink
violet
blue
greyish-green
jeans
greenwall
私人消息 (0)
公共消息 (0)
系统消息 (0)
好友消息 (0)
帖子消息 (0)
应用通知 (0)
应用邀请 (0)
悠闲数学娱乐论坛(第2版)
»
初等数学讨论
» 不允许出现两个相继数字的排列数
返回列表
发帖
青青子衿
发短消息
加为好友
青青子衿
当前离线
UID
230
帖子
1123
主题
411
精华
0
积分
7553
威望
2
阅读权限
150
在线时间
3476 小时
注册时间
2013-9-20
最后登录
2022-6-6
1
#
跳转到
»
倒序看帖
打印
字体大小:
t
T
发表于 2019-9-13 09:16
|
只看该作者
[组合]
不允许出现两个相继数字的排列数
在\(\,\{1,2,\cdots,n\}\,\)的排列中,不允许出现两个相继(相邻两个数,右边比左边大个1)数字的数目
\(\,\begin{align*}
&a_{n}= n\cdot\,\!a_{n-1}+ (n-1)\cdot\,\!a_{n-2}\\
&\begin{cases}
a_0=1\\
a_1=1
\end{cases}
\end{align*}\,\)
...
Cases[Cases[
Cases[Permutations[{1, 2, 3, 4}], Except[{___, 1, 2, ___}]],
Except[{___, 2, 3, ___}]], Except[{___, 3, 4, ___}]]
复制代码
...
1 3 2 4; 1 4 3 2; 2 1 4 3;
2 4 1 3; 3 2 1 4; 3 2 4 1;
4 1 3 2; 4 2 1 3; 4 3 2 1;
2 4 3 1; 3 1 4 2.
收藏
分享
分享到:
QQ空间
腾讯微博
腾讯朋友
kuing
发短消息
加为好友
kuing
当前离线
UID
1
帖子
8832
主题
619
精华
0
积分
66354
威望
113
阅读权限
200
性别
男
来自
广东广州
在线时间
21788 小时
注册时间
2013-6-13
最后登录
2024-3-9
2
#
发表于 2019-9-13 11:46
|
只看该作者
无需三个 Cases 啊
Cases[Permutations[{1, 2, 3, 4}], Except[{___, 1, 2, ___} | {___, 2, 3, ___} | {___, 3, 4, ___}]]
TOP
kuing
发短消息
加为好友
kuing
当前离线
UID
1
帖子
8832
主题
619
精华
0
积分
66354
威望
113
阅读权限
200
性别
男
来自
广东广州
在线时间
21788 小时
注册时间
2013-6-13
最后登录
2024-3-9
3
#
发表于 2019-9-13 12:28
|
只看该作者
你那递推式不知该怎么理解,但我发现用容斥原理就可以直接得出结果:
全部 `n!`;
有一个相继,即 *12*、*23*、*34* 这类,每个 `(n-1)!`,有 `n-1` 个,所以共 `(n-1)(n-1)!`;
有两个相继,包括 *12*34* 这种,还包括 *123* 这种(看成 12 和 23 两个相继),每个都是 `(n-2)!`,有 `C_{n-1}^2` 个,所以共 `C_{n-1}^2(n-2)!`;
同理,有 `k` 个相继的共 `C_{n-1}^k(n-k)!`。
于是由容斥原理知结果为:
\[n!-(n-1)(n-1)!+C_{n-1}^2(n-2)!-C_{n-1}^3(n-3)!+\cdots+(-1)^{n-1},\]写成和式即
\[\sum_{k=0}^{n-1}(-1)^kC_{n-1}^k(n-k)!.\]
不知还能不能化简……
TOP
kuing
发短消息
加为好友
kuing
当前离线
UID
1
帖子
8832
主题
619
精华
0
积分
66354
威望
113
阅读权限
200
性别
男
来自
广东广州
在线时间
21788 小时
注册时间
2013-6-13
最后登录
2024-3-9
4
#
发表于 2019-9-13 16:35
|
只看该作者
PS、你的公式代码
\(\,\begin{align*}
&a_{n}= n\cdot\,\!a_{n-1}+ (n-1)\cdot\,\!a_{n-2}\\
&\begin{cases}
a_0=1\\
a_1=1
\end{cases}
\end{align*}\,\)
复制代码
在真 latex 中是会报错的,align* 一般只能~裸~用,不能放在其他数学环境里面,得换用 aligned。
$\href{https://kuingggg.github.io/}{\text{About Me}}$
TOP
tommywong
发短消息
加为好友
tommywong
当前离线
UID
445
帖子
452
主题
77
精华
0
积分
4837
威望
11
阅读权限
90
在线时间
2953 小时
注册时间
2013-10-26
最后登录
2022-5-1
5
#
发表于 2019-9-13 21:30
|
只看该作者
可以寫成錯排,唔知係唔係同錯排有關
$\displaystyle (-1)^n+(n+1)
\sum_{k=0}^{n-1}(-1)^k\frac{(n-1)!}{k!}
=(n+1)D_{n-1}+(-1)^n$
但係就知道唔可以再化簡
TOP
返回列表
回复
发帖
[收藏此主题]
[关注此主题的新回复]
[通过 QQ、MSN 分享给朋友]