Given an alphabet of k symbols, {s_1,s_2,…,s_k}, how many words of length n, w(n), can be generated knowing that, Only two of the k available symbols participate; The symbol si must appear exactly ni times and the symbol sj must appear exactly nj times and ni+nj=n (the length of the word); To ilustrate the problem suppose that the alphabet is {A,B,C} and that I want words of length 4 with two A and two B. With the stated restrictions all of the possible words are {AABB,ABAB,ABBA,BBAA,BAAB,BABA}

skystasvs 2022-09-15 Answered
Given an alphabet of k symbols, { s 1 , s 2 , , s k }, how many words of length n, w ( n ), can be generated knowing that,
Only two of the k available symbols participate;
The symbol s i must appear exactly n i times and the symbol s j must appear exactly n j times and n i + n j = n (the length of the word);
To ilustrate the problem suppose that the alphabet is { A , B , C } and that I want words of length 4 with two A and two B. With the stated restrictions all of the possible words are
{ A A B B , A B A B , A B B A , B B A A , B A A B , B A B A }
So, I need to know what this w ( n ) = w ( n i , n j ) is. Some references on aproaches on how to solve this kind of problems and related algorithms to generate such words would be apreciated.
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 (2)

nizkem0c
Answered 2022-09-16 Author has 13 answers
Hint: For this problem, you first have to select two of the symbols from your list. How many ways can that be done? Should the order matter? Second, you have to select which n 1 positions in the word can take the first of the two symbols. How many ways can that be done? As the two selections are independent, you then multiply the two numbers. You also have to worry about factors of 2-is there some way that interchanging the selected letters in the first choice and interchanging the selected positions in the second can get you to the same word in different ways? This is particularly a problem when n 1 = n 2 .
Not exactly what you’re looking for?
Ask My Question
dizxindlert7
Answered 2022-09-17 Author has 2 answers
This is kind of late, but the correct approach would be to use binomial coefficients.
For instance, here we have words of length 4 and we're looking for a binary chain with 2 "1"s and 2 "0"s which would translate to C(4,2), which is 6.
And with the number of different pairs of symbols you'd have k x (k-1) different combinations.
So the answer would be k x (k-1) x C(n,r) where k is your "alphabet", and C(n,r) is your binomial coefficient of a mathematical word of n letters and r instances of a letter.
Not exactly what you’re looking for?
Ask My Question

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-08
A restaurant offers a $12 dinner special that has 7 choices for an appetizer, 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-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 2022-07-08
There are 400 dormitory rooms along with 400 distinct room numbers for 60 math students. Any math student can stay in any of the 400 dormitory rooms.
Suppose you are a math student and are recording the room number for all math students, one at a time until you have found a match (This means that a room number has already been recorded).
i) What is the probability that it takes more than 30 students for this to happen?
ii) What is the probability that is takes exactly 25 people for this to happen?
Suppose you are a math student and are recording the room number for all math students, one at a time you have found a student who shares the same dormitory room with you. What is the probability that it takes exactly 28 math students for this to happen?
Well, I think that for 1(i), I may first select 30 persons out of 400 students as the numerator, then all those 30 students have 400 choices, so the denominator would be 400^30.
As for 1(ii), I just did it in the same way as (i) but to change 30 into 25. I also multiply 25 since 1 out of 25 has the same choice.
As for 2, I think that everyone just make a different choice than me so i put (399/400)^28 as my answer.
asked 2022-07-13
If I create a 10 digit password with the following requirements:
At least one uppercase letter A-Z: 26
At least one lowercase letter a-z: 26
At least one digit from 0 9: 10
At least one common symbol ( ( # , $ , % , etc): 32
By inclusion-exclusion, I have ~ 3.2333 E + 19 possible combinations
However, if I change one of the requirements to at least two digits 0 9, how can I calculate the possible combinations?
asked 2022-02-16
A population of 19 scores has a mean of 8. One score of X = 6 is removed from the population. What is the value of the new mean?
asked 2021-05-28
A glue company needs to make some glue that it can sell at $120 per barrel. It wants to use 150 barrels of glue worth $100 per barrel, along with some glue worth $150 per barrel and glue worth $190 per barrel. It must use the same number of barrels of $150 and $190 glue. How much of the $150 and $190 glue will be needed? How many barrels of $120 glue will be produced?
asked 2022-09-10
Summations can really get complicated - esp. when you have convoluted n-fold summations with all kinds of different indices. Is there some software (or add-on) with which you can find and prove (complicated) summation identities?

New questions