组合问题

倪举鹏

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

fungarwai

{?,?,...}={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

matlab代码，给出符合条件的组合

1. [a,b,c,d,e,f,g,h]=ndgrid([1 2 4]);
   
2. p=[a(:) b(:) c(:) d(:) e(:) f(:) g(:) h(:)];
   
3. s=diff(p,[],2);
   
4. id=~any(s==1|s==-1,2);
   
5. tab='ac b';
   
6. tab(p(id,:))
   
7. disp(['以上便是满足ac不相邻的8位字串，共' num2str(sum(id)) '种.'])

复制代码

>>
aaaaaaaa
baaaaaaa
abaaaaaa
cbaaaaaa
...
abbbbbbb
cbbbbbbb
bbbbbbbb

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

kastin

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

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

fungarwai

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

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

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

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

kastin

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

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

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

fungarwai

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

根据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直接刻计算出

1. SeriesCoefficient[-((3 (x^3 + 4 x^2 + 6 x + 4))/(
   
2.   2 x^4 + 8 x^3 + 12 x^2 + 8 x - 1)), {x, 0, n}]

复制代码

这个给出的是n+1位密码锁所有组分方式种数的通项公式