Tile 1xn walkway with selective repetition
up vote
1
down vote
favorite
Consider the following problem:
3 1x1 tiles (T1, T2, and T3) - let's call them blue, red, yellow - are used to tile a 1xN walkway. The question is: How many possible ways are there to construct a walkway N units long while ensuring that there are no blue tiles next to each other?
Obviously the question is trivial without the final condition, but with it included it becomes much harder. Looking for a) both an open and closed-form formula for walkway N, and b) a generalization of the problem if possible. I'm interested to see how the problem behaves for NxN walkways, different conditions and Nx1/1xN/NxN tiles.
Preemptively: Not a duplicate of Tile a 1 x n walkway with 4 different types of tiles... - this question considers exclusion, extending its bounds.
combinatorics discrete-mathematics recurrence-relations
asked Nov 16 at 19:05
Jon Persan
61
add a comment |
up vote
1
down vote
favorite
Consider the following problem:
3 1x1 tiles (T1, T2, and T3) - let's call them blue, red, yellow - are used to tile a 1xN walkway. The question is: How many possible ways are there to construct a walkway N units long while ensuring that there are no blue tiles next to each other?
Obviously the question is trivial without the final condition, but with it included it becomes much harder. Looking for a) both an open and closed-form formula for walkway N, and b) a generalization of the problem if possible. I'm interested to see how the problem behaves for NxN walkways, different conditions and Nx1/1xN/NxN tiles.
Preemptively: Not a duplicate of Tile a 1 x n walkway with 4 different types of tiles... - this question considers exclusion, extending its bounds.
combinatorics discrete-mathematics recurrence-relations
asked Nov 16 at 19:05
Jon Persan
61
First thoughts (which may already have occurred to you). For each $k$ count the number of tilings with exactly $k$ nonadjacent blue tiles. (The sum of those counts is known - it's Fibonacci). Then fill in the remaining spaces at will. Comment not an answer since I haven't worked it out and don't expect too. It might not be easy.
– Ethan Bolker
Nov 16 at 19:14
@EthanBolker Thanks for your thoughts - will try this.
– Jon Persan
Nov 16 at 19:34
The simplest case is given by OEIS A028859. The recurrence relation is $a_{n+2} = 2a_{n+1} + 2a_n$ with $(a_0,a_1) = (1,3)$. When you try to construct a $n+2$ tiling. If the first tile is R/G, there is no restriction on what the remaining $n+1$ tiles are. This contributes $2a_{n+1}$ to $a_{n+2}$. Otherwise, the first tile is $B$ and second tile need to be either R/G. there will be no more restriction on the remaining $n$ tiles. This contributes $2a_n$ to $a_{n+2}$. This is how you setup the recurrence relation. The rest is figure out what $a_0,a_1$ are.
– achille hui
Nov 16 at 19:39
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Consider the following problem:
3 1x1 tiles (T1, T2, and T3) - let's call them blue, red, yellow - are used to tile a 1xN walkway. The question is: How many possible ways are there to construct a walkway N units long while ensuring that there are no blue tiles next to each other?
Obviously the question is trivial without the final condition, but with it included it becomes much harder. Looking for a) both an open and closed-form formula for walkway N, and b) a generalization of the problem if possible. I'm interested to see how the problem behaves for NxN walkways, different conditions and Nx1/1xN/NxN tiles.
Preemptively: Not a duplicate of Tile a 1 x n walkway with 4 different types of tiles... - this question considers exclusion, extending its bounds.
combinatorics discrete-mathematics recurrence-relations
asked Nov 16 at 19:05
Jon Persan
61
Consider the following problem:
3 1x1 tiles (T1, T2, and T3) - let's call them blue, red, yellow - are used to tile a 1xN walkway. The question is: How many possible ways are there to construct a walkway N units long while ensuring that there are no blue tiles next to each other?
Obviously the question is trivial without the final condition, but with it included it becomes much harder. Looking for a) both an open and closed-form formula for walkway N, and b) a generalization of the problem if possible. I'm interested to see how the problem behaves for NxN walkways, different conditions and Nx1/1xN/NxN tiles.
Preemptively: Not a duplicate of Tile a 1 x n walkway with 4 different types of tiles... - this question considers exclusion, extending its bounds.
combinatorics discrete-mathematics recurrence-relations
combinatorics discrete-mathematics recurrence-relations
asked Nov 16 at 19:05
Jon Persan
61
asked Nov 16 at 19:05
Jon Persan
61
asked Nov 16 at 19:05
Jon Persan
61
asked Nov 16 at 19:05
Jon Persan
61
asked Nov 16 at 19:05
Jon Persan
61
61
First thoughts (which may already have occurred to you). For each $k$ count the number of tilings with exactly $k$ nonadjacent blue tiles. (The sum of those counts is known - it's Fibonacci). Then fill in the remaining spaces at will. Comment not an answer since I haven't worked it out and don't expect too. It might not be easy.
– Ethan Bolker
Nov 16 at 19:14
@EthanBolker Thanks for your thoughts - will try this.
– Jon Persan
Nov 16 at 19:34
The simplest case is given by OEIS A028859. The recurrence relation is $a_{n+2} = 2a_{n+1} + 2a_n$ with $(a_0,a_1) = (1,3)$. When you try to construct a $n+2$ tiling. If the first tile is R/G, there is no restriction on what the remaining $n+1$ tiles are. This contributes $2a_{n+1}$ to $a_{n+2}$. Otherwise, the first tile is $B$ and second tile need to be either R/G. there will be no more restriction on the remaining $n$ tiles. This contributes $2a_n$ to $a_{n+2}$. This is how you setup the recurrence relation. The rest is figure out what $a_0,a_1$ are.
– achille hui
Nov 16 at 19:39
add a comment |
First thoughts (which may already have occurred to you). For each $k$ count the number of tilings with exactly $k$ nonadjacent blue tiles. (The sum of those counts is known - it's Fibonacci). Then fill in the remaining spaces at will. Comment not an answer since I haven't worked it out and don't expect too. It might not be easy.
– Ethan Bolker
Nov 16 at 19:14
@EthanBolker Thanks for your thoughts - will try this.
– Jon Persan
Nov 16 at 19:34
The simplest case is given by OEIS A028859. The recurrence relation is $a_{n+2} = 2a_{n+1} + 2a_n$ with $(a_0,a_1) = (1,3)$. When you try to construct a $n+2$ tiling. If the first tile is R/G, there is no restriction on what the remaining $n+1$ tiles are. This contributes $2a_{n+1}$ to $a_{n+2}$. Otherwise, the first tile is $B$ and second tile need to be either R/G. there will be no more restriction on the remaining $n$ tiles. This contributes $2a_n$ to $a_{n+2}$. This is how you setup the recurrence relation. The rest is figure out what $a_0,a_1$ are.
– achille hui
Nov 16 at 19:39
First thoughts (which may already have occurred to you). For each $k$ count the number of tilings with exactly $k$ nonadjacent blue tiles. (The sum of those counts is known - it's Fibonacci). Then fill in the remaining spaces at will. Comment not an answer since I haven't worked it out and don't expect too. It might not be easy.
– Ethan Bolker
Nov 16 at 19:14
First thoughts (which may already have occurred to you). For each $k$ count the number of tilings with exactly $k$ nonadjacent blue tiles. (The sum of those counts is known - it's Fibonacci). Then fill in the remaining spaces at will. Comment not an answer since I haven't worked it out and don't expect too. It might not be easy.
– Ethan Bolker
Nov 16 at 19:14
@EthanBolker Thanks for your thoughts - will try this.
– Jon Persan
Nov 16 at 19:34
@EthanBolker Thanks for your thoughts - will try this.
– Jon Persan
Nov 16 at 19:34
The simplest case is given by OEIS A028859. The recurrence relation is $a_{n+2} = 2a_{n+1} + 2a_n$ with $(a_0,a_1) = (1,3)$. When you try to construct a $n+2$ tiling. If the first tile is R/G, there is no restriction on what the remaining $n+1$ tiles are. This contributes $2a_{n+1}$ to $a_{n+2}$. Otherwise, the first tile is $B$ and second tile need to be either R/G. there will be no more restriction on the remaining $n$ tiles. This contributes $2a_n$ to $a_{n+2}$. This is how you setup the recurrence relation. The rest is figure out what $a_0,a_1$ are.
– achille hui
Nov 16 at 19:39
The simplest case is given by OEIS A028859. The recurrence relation is $a_{n+2} = 2a_{n+1} + 2a_n$ with $(a_0,a_1) = (1,3)$. When you try to construct a $n+2$ tiling. If the first tile is R/G, there is no restriction on what the remaining $n+1$ tiles are. This contributes $2a_{n+1}$ to $a_{n+2}$. Otherwise, the first tile is $B$ and second tile need to be either R/G. there will be no more restriction on the remaining $n$ tiles. This contributes $2a_n$ to $a_{n+2}$. This is how you setup the recurrence relation. The rest is figure out what $a_0,a_1$ are.
– achille hui
Nov 16 at 19:39
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3001524%2ftile-1xn-walkway-with-selective-repetition%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
First thoughts (which may already have occurred to you). For each $k$ count the number of tilings with exactly $k$ nonadjacent blue tiles. (The sum of those counts is known - it's Fibonacci). Then fill in the remaining spaces at will. Comment not an answer since I haven't worked it out and don't expect too. It might not be easy.
– Ethan Bolker
Nov 16 at 19:14
@EthanBolker Thanks for your thoughts - will try this.
– Jon Persan
Nov 16 at 19:34
The simplest case is given by OEIS A028859. The recurrence relation is $a_{n+2} = 2a_{n+1} + 2a_n$ with $(a_0,a_1) = (1,3)$. When you try to construct a $n+2$ tiling. If the first tile is R/G, there is no restriction on what the remaining $n+1$ tiles are. This contributes $2a_{n+1}$ to $a_{n+2}$. Otherwise, the first tile is $B$ and second tile need to be either R/G. there will be no more restriction on the remaining $n$ tiles. This contributes $2a_n$ to $a_{n+2}$. This is how you setup the recurrence relation. The rest is figure out what $a_0,a_1$ are.
– achille hui
Nov 16 at 19:39