组合问题

倪举鹏 发表于 2014-5-26 08:46:26

由a,b,c三个字母组成8个字母的单词，字母可以重复，要求a与c不能挨着，可以组成多少个单词？（aaaaaaaa可以，aaaaaaac不行）
很久以前百度的问题，我编程搞定的，有没有母函数或其他方法

fungarwai 发表于 2014-5-26 14:22:08

{?,?,...}={a,?,...}+{b,?,...}+{c,?,...}
{a,?,...}={c,?,...},{b,?,...}={?,...}

{?,?,...}={?,...}+2{a,?,...}
$a_n=a_{n-1}+2b_{n-1}$

{a,?,?,...}={a,a,?,...}+{a,b,?,...}={a,?,...}+{?,...}
$b_n=a_{n-1}+b_{n-1}$

$\begin{pmatrix} 1 & 2\\1 & 1\end{pmatrix}^7\begin{pmatrix} 3\\2 \end{pmatrix}=\begin{pmatrix} 1393\\985 \end{pmatrix}$

$a_8=1393$

kastin 发表于 2014-5-26 16:06:25

matlab代码，给出符合条件的组合
=ndgrid();
p=;
s=diff(p,[],2);
id=~any(s==1|s==-1,2);
tab='ac b';
tab(p(id,:))
disp(['以上便是满足ac不相邻的8位字串，共' num2str(sum(id)) '种.'])
>>
aaaaaaaa
baaaaaaa
abaaaaaa
cbaaaaaa
...
abbbbbbb
cbbbbbbb
bbbbbbbb

以上便是满足ac不相邻的8位字串，共1393种.

kastin 发表于 2014-5-26 17:18:23

fungarwai 发表于 2014-5-26 14:22
{?,?,...}={a,?,...}+{b,?,...}+{c,?,...}
{a,?,...}={c,?,...},{b,?,...}={?,...}

这个递推法很不错，如果题目换为a,b,c,d四个字母，要求a与c不能相邻，b与d不能相邻，这种方法还有效吗？

fungarwai 发表于 2014-5-26 18:45:48

kastin 发表于 2014-5-26 17:18
这个递推法很不错，如果题目换为a,b,c,d四个字母，要求a与c不能相邻，b与d不能相邻，这种方法还有效吗？

我不清楚这种方法在什么时候用得上，但这个题目还是可以递推的。

{?,?,...}={a,?,...}+{b,?,...}+{c,?,...}+{d,?,...}
=2{a,?,...}+2{b,?,...}
$x_n=2a_{n-1}+2b_{n-1}$

{a,?,?,...}={a,a,?,...}+{a,b,?,...}+{a,d,?,...}
={a,?,...}+2{b,?,...}
$a_n=a_{n-1}+2b_{n-1}$

{b,?,?,...}={b,a,?,...}+{b,b,?,...}+{b,c,?,...}
=2{a,?,...}+{b,?,...}
$b_n=2a_{n-1}+b_{n-1}$

$x_n=\begin{pmatrix} 2 & 2 \end{pmatrix} \begin{pmatrix} 1 & 2\\2 & 1\end{pmatrix}^{n-1}\begin{pmatrix} 1 \\ 1 \end{pmatrix}$

wayne 发表于 2014-5-26 19:12:29

fungarwai 发表于 2014-5-26 18:45
我不清楚这种方法在什么时候用得上，但这个题目还是可以递推的。

{?,?,...}={a,?,...}+{b,?,...}+{c,? ...

楼上的第二个和第三个可以加起来，然后得出$ a_n+b_n = 3^{n-1}*2$ ,所以 $x_n= 4*3^{n-1}$

kastin 发表于 2014-5-26 20:50:14

fungarwai 发表于 2014-5-26 18:45
我不清楚这种方法在什么时候用得上，但这个题目还是可以递推的。

{?,?,...}={a,?,...}+{b,?,...}+{c,? ...

这个问题的升级版，你看看 http://tieba.baidu.com/p/411865183?pn=1&statsInfo=frs_pager

fungarwai 发表于 2014-5-27 07:24:53

kastin 发表于 2014-5-26 20:50
这个问题的升级版，你看看 http://tieba.baidu.com/p/411865183?pn=1&statsInfo=frs_pager

A,B,C对称
D,E,F对称
a,b,c,AA,BB,CC对称
d,e,f,DD,EE,FF对称

S=3A+3D+3a+3d

A=2A+3D+3a+3d
D=2A+2D+2a+3d
a=2A+3D+2a+3d
d=2A+2D+2a+2d

$\begin{pmatrix}3 & 3 & 3 & 3\end{pmatrix}\begin{pmatrix}2 & 3 & 3 & 3\\2 & 2 & 2 & 3\\2 & 3 & 2 & 3\\2 & 2 & 2 & 2\end{pmatrix}^{n-1}\begin{pmatrix}1\\1\\1\\1\end{pmatrix}$

kastin 发表于 2014-5-27 17:45:12

根据8#的递推关系，简单的一阶线性递推方程组，可以求出问题的母函数
`\begin{align*}G(x)&=\begin{pmatrix}3 & 3 & 3 & 3\end{pmatrix} \begin{pmatrix}1-2x & -3x & -3x & -3x\\-2x & 1-2x & -2x & -3x\\-2x & -3x & 1-2x & -3x\\-2x & -2x & -2x & 1-2x\end{pmatrix}^{-1}\begin{pmatrix}1\\1\\1\\1\end{pmatrix}\\
&=-\frac{3(x^3+4x^2+6x+4)}{2x^4+8x^3+12x^2+8x-1}\end{align*}`
这个有理式已经是最简真分式，因此通项公式需要根据分母中4次方程的根来表示，Mathematica直接刻计算出SeriesCoefficient[-((3 (x^3 + 4 x^2 + 6 x + 4))/(
2 x^4 + 8 x^3 + 12 x^2 + 8 x - 1)), {x, 0, n}]
这个给出的是n+1位密码锁所有组分方式种数的通项公式

页: [1]

数学研发论坛's Archiver

组合问题