求通式f(n)

aimisiyou

有一向量A,
$$A=(a_{n},a_{n-1},a_{n-2}...a_{1})$$,其中每一元素\(a_k \in \{ 0, 1 \}\).
$$A对应的权值向量B=((-1)^n,(-1)^{n-1},(-1)^{n-2}...,1,-1),c为A点乘B,现求要求c=0 (mod 3),求满足此条件A的个数f(n)=?$$
显然有$$f(1)=1,f(2)=2,f(3)=3,f(4)=6,f(5)=11,f(6)=22............$$

gxqcn

感觉题目应该是 \(a_k \in \{ 0, 1 \}\)，而不该是在 \([0,1]\) 区间内。

通俗点，楼主的要求是：\(c = \left(a_1 + a_3 + \cdots + a_{2[\frac{n-1}{2}]+1}\right) -  \left(a_2 + a_4 + \cdots + a_{2[\frac{n}{2}]}\right)\), 要求满足： \(3 | c\)，

当 \(n=1,2,\cdots\),依次求满足上述条件的向量（或数列）的个数。

aimisiyou

gxqcn 发表于 2015-10-8 11:47
感觉题目应该是 \(a_k \in \{ 0, 1 \}\)，而不该是在 \([0,1]\) 区间内。

通俗点，楼主的要求是：\(c =  ...

嗯,是的.不知道属于0,1中其中一个元素的表达式不知怎么写.

aimisiyou

我通过找规律得到通项公式,谁能通过具体组合分析演算得到计算结果?

mathe

设满足$c=0(mod 3)$的个数为$f(n)$,满足$c=1(mod 3)$的个数为$g(n)$,满足$c=2(mod 3)$的个数为$h(n)$
于是就可以非常容易给出递推式了,而且显然是不超过6阶的线性递推式

aimisiyou

我开始也这么想过，但越绕越复杂，最终没得出。用这方法你算出结果了吗？

你能否发下你写的递推式？

creasson

构造函数s(n,x)=(1+x)(1+1/x)(1+x)(1+1/x)...
s(2n,x)=(1+x)^2n/x^n,  s(2n+1,x)=(1+x)^(2n+1)/x^n
于是，f(2n)=C(2n,n)+C(2n,n+3)+C(2n,n+6)+...
f(2n+1)=C(2n+1,n)+C(2n+1,n+3)+C(2n+1,n+6)+...
(这个和式可以用复数求出来，略)

aimisiyou

谢谢你的思路！构造函数确实很好理解，但组合式化简对我来说很难，你所说的用复数求出来是怎么个过程？最后纠正一下，你没考虑a_k*x^k，k为–3的倍数情况！

aimisiyou

说下我的思路。考虑从权值向量中取x个1，y个–1，则原问题转化为求区域x>=0，y>=0，x+y<=n中满足x-y是3的倍数的(x,y)点数f(n)。显然，当n为偶数时，f(n)=f(n-1)+(02468……n)中3的倍数的个数，当n为奇数时，f(n)=f(n-1)+(1357……n)中3的倍数的个数。

aimisiyou

不对，x个1的排列数就有好多。