Dtjytyk

What about the virus in 12 Monkeys?

Avoiding the "not like other girls" trope?

What killed these X2 caps?

How do I gain back my faith in my PhD degree?

What does “the session was packed” mean in this context?

Plagiarism or not?

Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?

Zip/Tar file compressed to larger size?

Could the museum Saturn V's be refitted for one more flight?

ssTTsSTtRrriinInnnnNNNIiinngg

Is it inappropriate for a student to attend their mentor's dissertation defense?

Bullying boss launched a smear campaign and made me unemployable

Why doesn't using multiple commands with a || or && conditional work?

Gatling : Performance testing tool

Why didn't Boeing produce its own regional jet?

Ambiguity in the definition of entropy

One verb to replace 'be a member of' a club

I would say: "You are another teacher", but she is a woman and I am a man

Venezuelan girlfriend wants to travel the USA to be with me. What is the process?

Why didn't Miles's spider sense work before?

Avoiding direct proof while writing proof by induction

Is there a hemisphere-neutral way of specifying a season?

How do I deal with an unproductive colleague in a small company?

Im going to France and my passport expires June 19th

Number of Sequences of $1$'s $2$'s and $3$'s with Restriction

Counting number of $k$-sequencesNumber of permutations given a sequence of 5 letters that are offset from 1-9Number of seating arrangements in 5 carsCount permutations with given cost and divisbiltycount permutations that do not contain repeated combinationsNumber of subsets from an ordered set where adjacent elements may or may not be tied togetherNumber of ordered permutations within a larger permutation.Binary Permutations With RestrictionFinding the number of permutationsRecognizing combinations/permutation problems.

2

$begingroup$

We want to write down a sequence of $n$ numbers, where each number
must be a $1,2$ or a $3$. The restriction is that there must be a $1$
between each two $2$'s and a $2$ between each two $1$'s. In how many
ways can this be done?

Starting with $n=1$ we have simply $1,2$ or $3$ so these are only 3 ways.

for $n=2$ we can write $12,13,21,23,31,32,33$ so we have 7 ways.

For $n=3$ we have $$121,123,133,212,213,233,312,321,333,323,313,332,331,132,231$$

which is counted to be $15$. So we have the number of ways as the sequence $3,7,15,...$ for $n=1,2,3,...$.

Proceeding like this is not a smart way since we start getting lots of different permutations of these sequence. Is there any smart way of thinking?

combinatorics discrete-mathematics permutations

share|cite|improve this question

edited Mar 18 at 20:26

Isaac Browne

5,38751334

asked Mar 18 at 20:03

ParsevalParseval

3,0721719

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm not sure I quite understand the question statement, as for $n=3$, you put $131$ and $232$ as possibilities. Was this a mistake? Otherwise, the question simply reduces to how many sequences are there where there are no consecutive $2$'s or $3$'s.
  $endgroup$
  – Isaac Browne
  Mar 18 at 20:12
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, I bet it's a mistake, and so is $131$ then. The answer is $2^{n+1}-1$ by the way, So it seems I found 13 of 15 permutations for $n=3.$
  $endgroup$
  – Parseval
  Mar 18 at 20:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, 132 is fine. I edited.
  $endgroup$
  – Parseval
  Mar 18 at 20:23
  

  
  
  
  

add a comment | 

2

$begingroup$

We want to write down a sequence of $n$ numbers, where each number
must be a $1,2$ or a $3$. The restriction is that there must be a $1$
between each two $2$'s and a $2$ between each two $1$'s. In how many
ways can this be done?

Starting with $n=1$ we have simply $1,2$ or $3$ so these are only 3 ways.

for $n=2$ we can write $12,13,21,23,31,32,33$ so we have 7 ways.

For $n=3$ we have $$121,123,133,212,213,233,312,321,333,323,313,332,331,132,231$$

which is counted to be $15$. So we have the number of ways as the sequence $3,7,15,...$ for $n=1,2,3,...$.

Proceeding like this is not a smart way since we start getting lots of different permutations of these sequence. Is there any smart way of thinking?

combinatorics discrete-mathematics permutations

share|cite|improve this question

edited Mar 18 at 20:26

Isaac Browne

5,38751334

asked Mar 18 at 20:03

ParsevalParseval

3,0721719

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I'm not sure I quite understand the question statement, as for $n=3$, you put $131$ and $232$ as possibilities. Was this a mistake? Otherwise, the question simply reduces to how many sequences are there where there are no consecutive $2$'s or $3$'s.
  $endgroup$
  – Isaac Browne
  Mar 18 at 20:12
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, I bet it's a mistake, and so is $131$ then. The answer is $2^{n+1}-1$ by the way, So it seems I found 13 of 15 permutations for $n=3.$
  $endgroup$
  – Parseval
  Mar 18 at 20:18
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, 132 is fine. I edited.
  $endgroup$
  – Parseval
  Mar 18 at 20:23
  

  
  
  
  

add a comment | 

$begingroup$

We want to write down a sequence of $n$ numbers, where each number
must be a $1,2$ or a $3$. The restriction is that there must be a $1$
between each two $2$'s and a $2$ between each two $1$'s. In how many
ways can this be done?

Starting with $n=1$ we have simply $1,2$ or $3$ so these are only 3 ways.

for $n=2$ we can write $12,13,21,23,31,32,33$ so we have 7 ways.

For $n=3$ we have $$121,123,133,212,213,233,312,321,333,323,313,332,331,132,231$$

which is counted to be $15$. So we have the number of ways as the sequence $3,7,15,...$ for $n=1,2,3,...$.

Proceeding like this is not a smart way since we start getting lots of different permutations of these sequence. Is there any smart way of thinking?

combinatorics discrete-mathematics permutations

share|cite|improve this question

edited Mar 18 at 20:26

Isaac Browne

5,38751334

asked Mar 18 at 20:03

ParsevalParseval

3,0721719

$endgroup$

share|cite|improve this question

edited Mar 18 at 20:26

Isaac Browne

5,38751334

asked Mar 18 at 20:03

ParsevalParseval

3,0721719

share|cite|improve this question

edited Mar 18 at 20:26

Isaac Browne

5,38751334

asked Mar 18 at 20:03

ParsevalParseval

3,0721719

edited Mar 18 at 20:26

Isaac Browne

5,38751334

edited Mar 18 at 20:26

Isaac Browne

5,38751334

asked Mar 18 at 20:03

ParsevalParseval

3,0721719

asked Mar 18 at 20:03

ParsevalParseval

3,0721719

2 Answers
2

active

oldest

votes

4

$begingroup$

If we construct the sequence term by term, we notice that after we encounter a $1$ or a $2$, we only have two options for each subsequent term, as we'll need a $2$ or a $1$ before we can write a $1$ or a $2$ again, respectively.

Thus, we can case on how many $3$'s are in the beginning of the sequence. Doing so, we get the sum
$$sum_{i=0}^n 2^{n-i} = 2^{n+1} - 1$$
where $i$ is the number of $3$'s starting the sequence (so $n-i$ is the amount leftover).

share|cite|improve this answer

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,38751334

$endgroup$

add a comment | 

4

$begingroup$

Suppose the list is not all $3$s. Choose which subset of the entries are $3$ in $2^n-1$ ways. What remains consists of a nonzero number $1$s and $2$s, and must alternate either $1212dots$ or $2121dots$ There are two choices, for a grand total of $(2^n-1)cdot 2$ sequences. Adding in the sequence of all threes, you get $$2(2^n-1)+1=2^{n+1}-1.$$

share|cite|improve this answer

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.8k22152

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why can I choose which subset of the entries are $3$ in $2^n-1$ ways? I don't see how you came up with $2^n-1$.
  $endgroup$
  – Parseval
  Mar 19 at 10:14
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Parseval It's because for each entry, there are two possibilities, either it is a $3$, or it is not a $3$. And so the total possibilites of choosing the subset of entries which are $3$ is $2^n$, but then we subtract $1$ because we supposed the list was not all $3$'s.
  $endgroup$
  – Isaac Browne
  Mar 19 at 13:12
  
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3153246%2fnumber-of-sequences-of-1s-2s-and-3s-with-restriction%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

If we construct the sequence term by term, we notice that after we encounter a $1$ or a $2$, we only have two options for each subsequent term, as we'll need a $2$ or a $1$ before we can write a $1$ or a $2$ again, respectively.

Thus, we can case on how many $3$'s are in the beginning of the sequence. Doing so, we get the sum
$$sum_{i=0}^n 2^{n-i} = 2^{n+1} - 1$$
where $i$ is the number of $3$'s starting the sequence (so $n-i$ is the amount leftover).

share|cite|improve this answer

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,38751334

$endgroup$

add a comment | 

4

$begingroup$

If we construct the sequence term by term, we notice that after we encounter a $1$ or a $2$, we only have two options for each subsequent term, as we'll need a $2$ or a $1$ before we can write a $1$ or a $2$ again, respectively.

Thus, we can case on how many $3$'s are in the beginning of the sequence. Doing so, we get the sum
$$sum_{i=0}^n 2^{n-i} = 2^{n+1} - 1$$
where $i$ is the number of $3$'s starting the sequence (so $n-i$ is the amount leftover).

share|cite|improve this answer

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,38751334

$endgroup$

add a comment | 

$begingroup$

If we construct the sequence term by term, we notice that after we encounter a $1$ or a $2$, we only have two options for each subsequent term, as we'll need a $2$ or a $1$ before we can write a $1$ or a $2$ again, respectively.

Thus, we can case on how many $3$'s are in the beginning of the sequence. Doing so, we get the sum
$$sum_{i=0}^n 2^{n-i} = 2^{n+1} - 1$$
where $i$ is the number of $3$'s starting the sequence (so $n-i$ is the amount leftover).

share|cite|improve this answer

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,38751334

$endgroup$

share|cite|improve this answer

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,38751334

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,38751334

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,38751334

4

$begingroup$

Suppose the list is not all $3$s. Choose which subset of the entries are $3$ in $2^n-1$ ways. What remains consists of a nonzero number $1$s and $2$s, and must alternate either $1212dots$ or $2121dots$ There are two choices, for a grand total of $(2^n-1)cdot 2$ sequences. Adding in the sequence of all threes, you get $$2(2^n-1)+1=2^{n+1}-1.$$

share|cite|improve this answer

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.8k22152

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why can I choose which subset of the entries are $3$ in $2^n-1$ ways? I don't see how you came up with $2^n-1$.
  $endgroup$
  – Parseval
  Mar 19 at 10:14
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Parseval It's because for each entry, there are two possibilities, either it is a $3$, or it is not a $3$. And so the total possibilites of choosing the subset of entries which are $3$ is $2^n$, but then we subtract $1$ because we supposed the list was not all $3$'s.
  $endgroup$
  – Isaac Browne
  Mar 19 at 13:12
  
  
  

  
  
  
  

add a comment | 

4

$begingroup$

Suppose the list is not all $3$s. Choose which subset of the entries are $3$ in $2^n-1$ ways. What remains consists of a nonzero number $1$s and $2$s, and must alternate either $1212dots$ or $2121dots$ There are two choices, for a grand total of $(2^n-1)cdot 2$ sequences. Adding in the sequence of all threes, you get $$2(2^n-1)+1=2^{n+1}-1.$$

share|cite|improve this answer

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.8k22152

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Why can I choose which subset of the entries are $3$ in $2^n-1$ ways? I don't see how you came up with $2^n-1$.
  $endgroup$
  – Parseval
  Mar 19 at 10:14
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @Parseval It's because for each entry, there are two possibilities, either it is a $3$, or it is not a $3$. And so the total possibilites of choosing the subset of entries which are $3$ is $2^n$, but then we subtract $1$ because we supposed the list was not all $3$'s.
  $endgroup$
  – Isaac Browne
  Mar 19 at 13:12
  
  
  

  
  
  
  

add a comment | 

$begingroup$

Suppose the list is not all $3$s. Choose which subset of the entries are $3$ in $2^n-1$ ways. What remains consists of a nonzero number $1$s and $2$s, and must alternate either $1212dots$ or $2121dots$ There are two choices, for a grand total of $(2^n-1)cdot 2$ sequences. Adding in the sequence of all threes, you get $$2(2^n-1)+1=2^{n+1}-1.$$

share|cite|improve this answer

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.8k22152

$endgroup$

share|cite|improve this answer

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.8k22152

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.8k22152

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.8k22152