Let k>=1 be fix and b_n be the amount of possible words w=v_1⋯v_n of length n on the alphabet {1,…,k}, such that v_i not = v_i+1,1<=i<=n−1. a) Show by counting that b_0=1 and b_n=k(k−1)^(n−1) for n>=1. b) Identify the generating function Sum_(n>=0) b_n x^n

oliadas73 2022-09-03 Answered
Let k 1 be fix and b n be the amount of possible words w = v 1 v n of length n on the alphabet { 1 , , k }, such that v i v i + 1 , 1 i n 1.
a) Show by counting that
b 0 = 1  and  b n = k ( k 1 ) n 1  for  n 1..
b) Identify the generating function n 0 b n x n
My try:
a) first. For the first element of each word there are k possibilities. For every successor there are ( k 1 ) possibilities because they depend on the element before themselves.
Is this correct and complete?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Kaleb Harrell
Answered 2022-09-04 Author has 14 answers
Yes, your proof for a) is correct. For the generating function, observe that
n = 0 b n x n = 1 + k x n = 0 [ ( k 1 ) x ] n
and recall what a geometric series is.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-09-09
In a fuel economy study, each of 3 race cars is tested using 5 different brands of gasoline at 7 test sites located in different regions of the country. If 2 drivers are used in the study, and test runs are made once under each distinct set of conditions, how many test runs are needed?
asked 2021-09-08

A restaurant offers a $12 dinner special with seven appetizer options, 12 choices for an entree, and 6 choices for a dessert. How many different meals are available when you select an appetizer, an entree,and a dessert?

asked 2021-11-15
Suppose that A and B are independent events such that the probability that neither occurs is a and the probability of B is b. Show that
P(A)=1ba1b
asked 2022-02-11
A bowl has 4 green marbles 3 red marbles and 2yellow marbles what is the probability that you are going to select a red marble and a yellow marble. You replace the marble before another marble is selected
asked 2022-07-16
How many different phone numbers are possible in the area code 503, if the first number cannot start with a 0 or 1
asked 2021-06-06

Let L be an SList. Define a recursive function Wham as follows. B. Suppose L = x. Then Wham(L)=x˙x.R. Suppose L = (X, Y). Then Wham(L)=Wham(X)+Wham(Y). Evaluate Wham (2, 4), (7, 9) , showing all work.

asked 2022-03-23

A drug for the relief of asthma can be purchased from 5 different manufacturers in liquid, tablet, or capsule form, all of which come in regular and extra strength. How many different ways can a doctor prescribe the drug for a patient suffering from asthma?

New questions