Number of Sequences of $1$'s $2$'s and $3$'s with Restriction The Next CEO of Stack OverflowCounting 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.
Do I need to enable Dev Hub in my PROD Org?
What flight has the highest ratio of time difference to flight time?
Would a completely good Muggle be able to use a wand?
Why is the US ranked as #45 in Press Freedom ratings, despite its extremely permissive free speech laws?
How to start emacs in "nothing" mode (`fundamental-mode`)
Is there an analogue of projective spaces for proper schemes?
MessageLevel in QGIS3
What is ( CFMCC ) on ILS approach chart?
I believe this to be a fraud - hired, then asked to cash check and send cash as Bitcoin
Unreliable Magic - Is it worth it?
Rotate a column
If a black hole is created from light, can this black hole then move at speed of light?
How to count occurrences of text in a file?
Bold, vivid family
sp_blitzCache results Memory grants
Can we say or write : "No, it'sn't"?
Are there any unintended negative consequences to allowing PCs to gain multiple levels at once in a short milestone-XP game?
Indicator light circuit
Can I equip Skullclamp on a creature I am sacrificing?
How do scammers retract money, while you can’t?
How fast would a person need to move to trick the eye?
WOW air has ceased operation, can I get my tickets refunded?
How did the Bene Gesserit know how to make a Kwisatz Haderach?
Written every which way
Number of Sequences of $1$'s $2$'s and $3$'s with Restriction
The Next CEO of Stack OverflowCounting 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.
$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
edited Mar 18 at 20:26
Isaac Browne
5,32751334
asked Mar 18 at 20:03
ParsevalParseval
3,0771719
$endgroup$
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
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
edited Mar 18 at 20:26
Isaac Browne
5,32751334
asked Mar 18 at 20:03
ParsevalParseval
3,0771719
$endgroup$
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
combinatorics discrete-mathematics permutations
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
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
edited Mar 18 at 20:26
Isaac Browne
5,32751334
5,32751334
asked Mar 18 at 20:03
ParsevalParseval
3,0771719
asked Mar 18 at 20:03
ParsevalParseval
3,0771719
asked Mar 18 at 20:03
ParsevalParseval
3,0771719
3,0771719
$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$
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
$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
$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
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, 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
$begingroup$
Yes, 132 is fine. I edited.
$endgroup$
– Parseval
Mar 18 at 20:23
add a comment |
2 Answers
2
active
oldest
votes
$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).
answered Mar 18 at 20:21
Isaac BrowneIsaac Browne
5,32751334
$endgroup$
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.$$
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
);
);
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
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
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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).
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).
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).
answered Mar 18 at 20:21
Isaac BrowneIsaac Browne
5,32751334
$endgroup$
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).
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
answered Mar 18 at 20:21
Isaac BrowneIsaac Browne
5,32751334
5,32751334
add a comment |
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.$$
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.$$
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.$$
answered Mar 18 at 20:32
Mike EarnestMike Earnest
26.2k22151
$endgroup$
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.$$
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
answered Mar 18 at 20:32
Mike EarnestMike Earnest
26.2k22151
26.2k22151
$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$
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
$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
$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
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
$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 |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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