Counting Sequences with Repetition Using Stars and Bars Method

In summary: For b), do you know how many sequences there are with each number appearing exactly once? How could you use that to answer the question?In summary, the student's attempt at a solution for a problem involving counting the number of sequences with specific conditions was incorrect. They used the stars and bars method and came up with an answer of 3^10, but this did not take into account the condition of increasing from left to right. For part b), the student used 3^10 - 3x 2^10 as a solution, but this also was not correct as it did not consider all possible cases. The student is seeking guidance on how to use the stars and
  • #1
Sarina3003
20
0

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!
 
Physics news on Phys.org
  • #2
Sarina3003 said:

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?
 
  • #3
Ray Vickson said:
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!
 
  • #4
Sarina3003 said:
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?
 
  • #5
Sarina3003 said:
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?
 
  • #6
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?
 
  • #7
nuuskur said:
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”
 
  • #8
Ray Vickson said:
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
 
  • #9
Sarina3003 said:
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?
 
  • #10
Sarina3003 said:
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.
 

1. What is discrete mathematics?

Discrete mathematics is a branch of mathematics that deals with discrete objects, such as integers, graphs, and sets. It is primarily concerned with the study of discrete structures and their properties.

2. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting, arrangements, and combinations of objects. It includes the study of permutations, combinations, and probability, as well as the analysis of algorithms and graph theory.

3. How is discrete mathematics used in computer science?

Discrete mathematics is a fundamental tool in computer science, as it provides the necessary foundation for understanding and analyzing algorithms, data structures, and computer systems. It is used in areas such as cryptography, coding theory, and optimization.

4. What are some real-world applications of combinatorics?

Combinatorics has numerous real-world applications, such as in scheduling and optimization problems, computer science and data analysis, and in the design of experiments and surveys. It is also used in fields like genetics, chemistry, and physics.

5. How can I improve my skills in discrete mathematics and combinatorics?

To improve your skills in discrete mathematics and combinatorics, you can practice solving problems and puzzles, read textbooks and online resources, attend workshops and seminars, and participate in mathematical competitions. Collaborating with others and seeking guidance from experts can also be beneficial.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
85
  • Precalculus Mathematics Homework Help
Replies
8
Views
319
  • Calculus and Beyond Homework Help
Replies
2
Views
667
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
564
  • Calculus and Beyond Homework Help
Replies
1
Views
688
  • General Math
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
4K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Back
Top