Fdtxjr

Is there a difference between "Fahrstuhl" and "Aufzug"

How to start emacs in "nothing" mode (`fundamental-mode`)

Several mode to write the symbol of a vector

Example of a Mathematician/Physicist whose Other Publications during their PhD eclipsed their PhD Thesis

How does the mv command work with external drives?

Bold, vivid family

Why does the UK parliament need a vote on the political declaration?

Why do we use the plural of movies in this phrase "We went to the movies last night."?

Can you replace a racial trait cantrip when leveling up?

Can I equip Skullclamp on a creature I am sacrificing?

Is there an analogue of projective spaces for proper schemes?

Why didn't Khan get resurrected in the Genesis Explosion?

How to count occurrences of text in a file?

Is it professional to write unrelated content in an almost-empty email?

Can I run my washing machine drain line into a condensate pump so it drains better?

Is it possible to search for a directory/file combination?

How to solve a differential equation with a term to a power?

How fast would a person need to move to trick the eye?

Why is the US ranked as #45 in Press Freedom ratings, despite its extremely permissive free speech laws?

If Nick Fury and Coulson already knew about aliens (Kree and Skrull) why did they wait until Thor's appearance to start making weapons?

To not tell, not take, and not want

Why does standard notation not preserve intervals (visually)

Why don't programming languages automatically manage the synchronous/asynchronous problem?

Are there any limitations on attacking while grappling?

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

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,32751334

asked Mar 18 at 20:03

ParsevalParseval

3,0771719

$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,32751334

asked Mar 18 at 20:03

ParsevalParseval

3,0771719

$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,32751334

asked Mar 18 at 20:03

ParsevalParseval

3,0771719

$endgroup$

share|cite|improve this question

edited Mar 18 at 20:26

Isaac Browne

5,32751334

asked Mar 18 at 20:03

ParsevalParseval

3,0771719

share|cite|improve this question

edited Mar 18 at 20:26

Isaac Browne

5,32751334

asked Mar 18 at 20:03

ParsevalParseval

3,0771719

edited Mar 18 at 20:26

Isaac Browne

5,32751334

edited Mar 18 at 20:26

Isaac Browne

5,32751334

asked Mar 18 at 20:03

ParsevalParseval

3,0771719

asked Mar 18 at 20:03

ParsevalParseval

3,0771719

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,32751334

$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.2k22151

$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,32751334

$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,32751334

$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,32751334

$endgroup$

share|cite|improve this answer

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,32751334

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,32751334

answered Mar 18 at 20:21

Isaac BrowneIsaac Browne

5,32751334

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.2k22151

$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.2k22151

$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.2k22151

$endgroup$

share|cite|improve this answer

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.2k22151

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.2k22151

answered Mar 18 at 20:32

Mike EarnestMike Earnest

26.2k22151