Counting the Lipschitz-Functions of two Sets [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I'm doing a course on discrete maths at coursera and there is an unintuitive question about the amount of Lipschitz-Functions between two sets.
A function $0, …, n rightarrow mathbbZ$ is a Lipschitz function if consecutive values differ by at most $1$, i.e., $|f(i) - f(i-1)| leq 1$ for all $i = 1, …, n$. Let $L(n)$ be the number of Lipschitz functions $f:0,…,n rightarrow mathbbZ$ with $f(0) = f(n) = f(0)$. What is $L(7)$?
Could anybody help me out?
combinatorics discrete-mathematics
asked Aug 7 at 15:18
John Smith
285
closed as off-topic by amWhy, Jendrik Stelzner, Claude Leibovici, José Carlos Santos, Adrian Keister Aug 10 at 0:35
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." РamWhy, Jendrik Stelzner, Claude Leibovici, Jos̩ Carlos Santos, Adrian Keister
add a comment |Â
up vote
0
down vote
favorite
I'm doing a course on discrete maths at coursera and there is an unintuitive question about the amount of Lipschitz-Functions between two sets.
A function $0, …, n rightarrow mathbbZ$ is a Lipschitz function if consecutive values differ by at most $1$, i.e., $|f(i) - f(i-1)| leq 1$ for all $i = 1, …, n$. Let $L(n)$ be the number of Lipschitz functions $f:0,…,n rightarrow mathbbZ$ with $f(0) = f(n) = f(0)$. What is $L(7)$?
Could anybody help me out?
combinatorics discrete-mathematics
asked Aug 7 at 15:18
John Smith
285
closed as off-topic by amWhy, Jendrik Stelzner, Claude Leibovici, José Carlos Santos, Adrian Keister Aug 10 at 0:35
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." РamWhy, Jendrik Stelzner, Claude Leibovici, Jos̩ Carlos Santos, Adrian Keister
1
What have you tried? It shouldn't be hard to count them by picturing possibilities on a number line. Also, without some fixed $f(0)=f(n)=c$, there are for sure infinitely many...
– Dzoooks
Aug 7 at 15:25
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I'm doing a course on discrete maths at coursera and there is an unintuitive question about the amount of Lipschitz-Functions between two sets.
A function $0, …, n rightarrow mathbbZ$ is a Lipschitz function if consecutive values differ by at most $1$, i.e., $|f(i) - f(i-1)| leq 1$ for all $i = 1, …, n$. Let $L(n)$ be the number of Lipschitz functions $f:0,…,n rightarrow mathbbZ$ with $f(0) = f(n) = f(0)$. What is $L(7)$?
Could anybody help me out?
combinatorics discrete-mathematics
asked Aug 7 at 15:18
John Smith
285
I'm doing a course on discrete maths at coursera and there is an unintuitive question about the amount of Lipschitz-Functions between two sets.
A function $0, …, n rightarrow mathbbZ$ is a Lipschitz function if consecutive values differ by at most $1$, i.e., $|f(i) - f(i-1)| leq 1$ for all $i = 1, …, n$. Let $L(n)$ be the number of Lipschitz functions $f:0,…,n rightarrow mathbbZ$ with $f(0) = f(n) = f(0)$. What is $L(7)$?
Could anybody help me out?
combinatorics discrete-mathematics
asked Aug 7 at 15:18
John Smith
285
asked Aug 7 at 15:18
John Smith
285
asked Aug 7 at 15:18
John Smith
285
asked Aug 7 at 15:18
John Smith
285
285
closed as off-topic by amWhy, Jendrik Stelzner, Claude Leibovici, José Carlos Santos, Adrian Keister Aug 10 at 0:35
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." РamWhy, Jendrik Stelzner, Claude Leibovici, Jos̩ Carlos Santos, Adrian Keister
closed as off-topic by amWhy, Jendrik Stelzner, Claude Leibovici, José Carlos Santos, Adrian Keister Aug 10 at 0:35
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." РamWhy, Jendrik Stelzner, Claude Leibovici, Jos̩ Carlos Santos, Adrian Keister
1
What have you tried? It shouldn't be hard to count them by picturing possibilities on a number line. Also, without some fixed $f(0)=f(n)=c$, there are for sure infinitely many...
– Dzoooks
Aug 7 at 15:25
add a comment |Â
1
What have you tried? It shouldn't be hard to count them by picturing possibilities on a number line. Also, without some fixed $f(0)=f(n)=c$, there are for sure infinitely many...
– Dzoooks
Aug 7 at 15:25
1
1
What have you tried? It shouldn't be hard to count them by picturing possibilities on a number line. Also, without some fixed $f(0)=f(n)=c$, there are for sure infinitely many...
– Dzoooks
Aug 7 at 15:25
What have you tried? It shouldn't be hard to count them by picturing possibilities on a number line. Also, without some fixed $f(0)=f(n)=c$, there are for sure infinitely many...
– Dzoooks
Aug 7 at 15:25
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
Thinking about the combinatorics (there are three ways to construct a function with $f(0)=f(n)=0$: you can choose $f(n-1)=1$, $f(n-1)=0$ or $f(n-1)=-1$ and then need to consider how many ways there are to connect $f(0)=0$ with each of those) leads to the Pascal-like triangle (just summing THREE numbers every time)
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
OEIS then tells you a lot about this and also that $L(7)=393$ if you are too lazy to compute it yourself (like me).
answered Aug 7 at 16:41
Kusma
1,212112
Perfect, that was the path I needed. Thank you!
– John Smith
Aug 8 at 6:26
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Thinking about the combinatorics (there are three ways to construct a function with $f(0)=f(n)=0$: you can choose $f(n-1)=1$, $f(n-1)=0$ or $f(n-1)=-1$ and then need to consider how many ways there are to connect $f(0)=0$ with each of those) leads to the Pascal-like triangle (just summing THREE numbers every time)
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
OEIS then tells you a lot about this and also that $L(7)=393$ if you are too lazy to compute it yourself (like me).
answered Aug 7 at 16:41
Kusma
1,212112
Perfect, that was the path I needed. Thank you!
– John Smith
Aug 8 at 6:26
add a comment |Â
up vote
1
down vote
Thinking about the combinatorics (there are three ways to construct a function with $f(0)=f(n)=0$: you can choose $f(n-1)=1$, $f(n-1)=0$ or $f(n-1)=-1$ and then need to consider how many ways there are to connect $f(0)=0$ with each of those) leads to the Pascal-like triangle (just summing THREE numbers every time)
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
OEIS then tells you a lot about this and also that $L(7)=393$ if you are too lazy to compute it yourself (like me).
answered Aug 7 at 16:41
Kusma
1,212112
Perfect, that was the path I needed. Thank you!
– John Smith
Aug 8 at 6:26
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Thinking about the combinatorics (there are three ways to construct a function with $f(0)=f(n)=0$: you can choose $f(n-1)=1$, $f(n-1)=0$ or $f(n-1)=-1$ and then need to consider how many ways there are to connect $f(0)=0$ with each of those) leads to the Pascal-like triangle (just summing THREE numbers every time)
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
OEIS then tells you a lot about this and also that $L(7)=393$ if you are too lazy to compute it yourself (like me).
answered Aug 7 at 16:41
Kusma
1,212112
Thinking about the combinatorics (there are three ways to construct a function with $f(0)=f(n)=0$: you can choose $f(n-1)=1$, $f(n-1)=0$ or $f(n-1)=-1$ and then need to consider how many ways there are to connect $f(0)=0$ with each of those) leads to the Pascal-like triangle (just summing THREE numbers every time)
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
OEIS then tells you a lot about this and also that $L(7)=393$ if you are too lazy to compute it yourself (like me).
answered Aug 7 at 16:41
Kusma
1,212112
edited Aug 7 at 19:15
answered Aug 7 at 16:41
Kusma
1,212112
answered Aug 7 at 16:41
Kusma
1,212112
answered Aug 7 at 16:41
Kusma
1,212112
1,212112
Perfect, that was the path I needed. Thank you!
– John Smith
Aug 8 at 6:26
add a comment |Â
Perfect, that was the path I needed. Thank you!
– John Smith
Aug 8 at 6:26
Perfect, that was the path I needed. Thank you!
– John Smith
Aug 8 at 6:26
Perfect, that was the path I needed. Thank you!
– John Smith
Aug 8 at 6:26
add a comment |Â
1
What have you tried? It shouldn't be hard to count them by picturing possibilities on a number line. Also, without some fixed $f(0)=f(n)=c$, there are for sure infinitely many...
– Dzoooks
Aug 7 at 15:25