Counting Sequences with Repetition Using Stars and Bars Method

[Sarina3003]

Homework Statement

The question is counting how many sequence length 10 with 1,2,3 if

a) increasing from left to right with repetition allowed

b) increase from left to right with each number appear at least once (still with repetition allowed)

Homework Equations

It is the stars and bars method

The Attempt at a Solution

For a) i did 3^10. Please tell if it is wrong :( that is the only option i have

And for b) i use 3^10 - 3x 2^10 , the reason for 2^10 is this is for the case one of them not appear at all, and times 3 for each of the case for 1,2,3 respectively

As stated above, i am almost sure that this can be done by using the stars and the bar method, however i do not know how to compute it so i was tried to do what make the most sense to me

Please give me some guide

Thanks so much!

 

[Ray Vickson]

Homework Statement

The question is counting how many sequence length 10 with 1,2,3 if

a) increasing from left to right with repetition allowed

b) increase from left to right with each number appear at least once (still with repetition allowed)

Homework Equations

It is the stars and bars method

The Attempt at a Solution

For a) i did 3^10. Please tell if it is wrong :( that is the only option i have

And for b) i use 3^10 - 3x 2^10 , the reason for 2^10 is this is for the case one of them not appear at all, and times 3 for each of the case for 1,2,3 respectively

As stated above, i am almost sure that this can be done by using the stars and the bar method, however i do not know how to compute it so i was tried to do what make the most sense to me

Please give me some guide

Thanks so much!

You tell us why you think that $3^{10}$ is correct for part (a). What reasoning did you use to get that answer?

Also: why mention the "stars and bars" method if you do not know how it could (or should) be used in this problem?

 

[Sarina3003]

You tell us why you think that $3^{10}$ is correct for part (a). What reasoning did you use to get that answer?

Also: why mention the "stars and bars" method if you do not know how it could (or should) be used in this problem?

Hi,
Thanks for your reply
The reason for the answer in my part a) is because i think each of the digit can have 3 ways of choosing. I know it looks not ok but this is what i had to put down in my test paper
The reason i said for the stars and bars method is that i realized it shortly after, when dealing with identical objects, we usually use the stars and bars method. In fact, i can use the stars and bars method for the questions such as distributing n identical objects to k people or boxes or etc. But i don't know how to do it here since 1 2 3 are not identical objects but if you repeat each one by itself, i would consider as identical objects. So this is why i don't know how to compute it

Please help me if you can
Thanks so much!

 

[Dick]

Hi,
Thanks for your reply
The reason for the answer in my part a) is because i think each of the digit can have 3 ways of choosing. I know it looks not ok but this is what i had to put down in my test paper
The reason i said for the stars and bars method is that i realized it shortly after, when dealing with identical objects, we usually use the stars and bars method. In fact, i can use the stars and bars method for the questions such as distributing n identical objects to k people or boxes or etc. But i don't know how to do it here since 1 2 3 are not identical objects but if you repeat each one by itself, i would consider as identical objects. So this is why i don't know how to compute it

Please help me if you can
Thanks so much!

You aren't likely to find a method to do problems like this in your book. You need to think about it long enough to reduce it to problems you do know how to do. I'll get you started. The first digit must be a 1, 2, or 3, right? Start with the easy case, suppose you start with a 3. Where can you go from there?

 

[Ray Vickson]

Hi,
Thanks for your reply
The reason for the answer in my part a) is because i think each of the digit can have 3 ways of choosing. I know it looks not ok but this is what i had to put down in my test paper
The reason i said for the stars and bars method is that i realized it shortly after, when dealing with identical objects, we usually use the stars and bars method. In fact, i can use the stars and bars method for the questions such as distributing n identical objects to k people or boxes or etc. But i don't know how to do it here since 1 2 3 are not identical objects but if you repeat each one by itself, i would consider as identical objects. So this is why i don't know how to compute it

Please help me if you can
Thanks so much!

I assume that you want to do more than just answer a specific exam question, but, rather, want to understand how to tackle such problems in general. If so, start with an easier case, where you can list all the possibilities. Suppose that you want to know how many sequences of length 4 you can have, where the entries are 1 or 2 or 3, increasing from left to right and with repetitions allowed. Start with that problem, and work it through from start to finish. Can you see now what is happening?

 

[nuuskur]

You have counted too many for a). You have $3^{10}$ of all possible sequences. Furthermore, increasing strictly or non-strictly? For example, is a constant sequence increasing?

 

[Sarina3003]

You have counted too many for a). You have $3^{10}$ of all possible sequences. Furthermore, increasing strictly or non-strictly? For example, is a constant sequence increasing?

Thanks for your reply
I have written that increasing with repetition allowed, so this literally mean “weakly increasing”

 

[Sarina3003]

I assume that you want to do more than just answer a specific exam question, but, rather, want to understand how to tackle such problems in general. If so, start with an easier case, where you can list all the possibilities. Suppose that you want to know how many sequences of length 4 you can have, where the entries are 1 or 2 or 3, increasing from left to right and with repetitions allowed. Start with that problem, and work it through from start to finish. Can you see now what is happening?

I got
1) 1 2 2 3
2) 1 1 2 3
3) 1 2 3 3
The first one has 1 way to choose, second has 2, third has 2 and last has 1. Finally it should be 4 :(. I then stuck again. I might get wrong somewhere

 

[Dick]

I got
1) 1 2 2 3
2) 1 1 2 3
3) 1 2 3 3
The first one has 1 way to choose, second has 2, third has 2 and last has 1. Finally it should be 4 :(. I then stuck again. I might get wrong somewhere

I don't understand how you think you are counting 4 nor things like why 'second has 2'. If the three sequences you listed are your solution to the case where you use all three numbers, I agree. So isn't the total three?

 

[Ray Vickson]

I got
1) 1 2 2 3
2) 1 1 2 3
3) 1 2 3 3
The first one has 1 way to choose, second has 2, third has 2 and last has 1. Finally it should be 4 :(. I then stuck again. I might get wrong somewhere

It seems you have answered question (b), but presumably not question (a). In fact, questions (a) and (b) could be different only if (a) does not require all three numbers to be used, in which case (a) would also allow sequences like 1111, 1333 and 2233, for example; there would be many, many others as well.