【用三个字母a,b,c任意写n次（可重复）称为长度为n的单词-查字典问答网

来自林亚平的问题

　　【用三个字母a,b,c任意写n次（可重复）称为长度为n的单词.例：abcb,baab为长度为4的单词.1.求长度为n的单词个数；2.其中a出现奇数次的单词有几个?】

　　用三个字母a,b,c任意写n次（可重复）称为长度为n的单词.例：abcb,baab为长度为4的单词.1.求长度为n的单词个数；2.其中a出现奇数次的单词有几个?

1回答

2020-12-27 01:51

我要回答

请先登录

傅云鹏

　　1.3^n(每个位置三个选择)

　　2.递推a(n)=2a(n-1)+3^(n-1)-a(n-1)

　　a(n)是长度为n的单词中a出现奇数次的单词的个数

　　a(n-1)是长度为n-1的单词中a出现奇数次的单词的个数

　　2a(n-1)是在长度为n-1的单词尾加上b或c

　　3^(n-1)-a(n-1)是长度为n-1的单词中a出现偶数次的单词的个数在这样的单词尾加a也满足要求

　　而a(n)=2a(n-1)+3^(n-1)-a(n-1)

　　可推得a(n)-1/2*3^n=a(n-1)-1/2*3^(n-1)=...=a(1)-3/2=-1/2

　　所以

　　a(n)=1/2*3^n-1/2

2020-12-27 01:56:01