Combinatorics problem on counting. Announcing the arrival of Valued Associate #679: Cesar...
Does the Weapon Master feat grant you a fighting style?
Localisation of Category
When a candle burns, why does the top of wick glow if bottom of flame is hottest?
Effects on objects due to a brief relocation of massive amounts of mass
Sum letters are not two different
Crossing US/Canada Border for less than 24 hours
Did Deadpool rescue all of the X-Force?
What initially awakened the Balrog?
How to react to hostile behavior from a senior developer?
Do any jurisdictions seriously consider reclassifying social media websites as publishers?
Why do we need to use the builder design pattern when we can do the same thing with setters?
How to write the following sign?
What would you call this weird metallic apparatus that allows you to lift people?
Why does the remaining Rebel fleet at the end of Rogue One seem dramatically larger than the one in A New Hope?
What's the meaning of "fortified infraction restraint"?
What is the font for "b" letter?
Central Vacuuming: Is it worth it, and how does it compare to normal vacuuming?
Performance gap between vector<bool> and array
Time to Settle Down!
Find 108 by using 3,4,6
Drawing without replacement: why is the order of draw irrelevant?
How come Sam didn't become Lord of Horn Hill?
Illegal assignment from sObject to Id
How does the math work when buying airline miles?
Combinatorics problem on counting.
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Combinatorics and elementary probabilityFinding Number Of Cases,Simple Counting Questionhow many integers are there between 10 000 and 99 999…Coloring integers: there exist 2000 consecutive integers among which 1000 of each colorSubset Counting questionCounting Techniques with CombinatoricsHow many odd $100$-digit numbers such that every two consecutive digits differ by exactly 2 are there?Combinatorics and countCounting elementsCounting the equal-differences of an permutation
$begingroup$
How many positive integers n are there such that all of the following take place:
1) n has 1000 digits.
2) all of the digits are odd.
3) the absolute value of the difference of any two consecutive (neighboring) digits is equal to 2.
Please help. I don’t even know how to start.
combinatorics
$endgroup$
|
show 2 more comments
$begingroup$
How many positive integers n are there such that all of the following take place:
1) n has 1000 digits.
2) all of the digits are odd.
3) the absolute value of the difference of any two consecutive (neighboring) digits is equal to 2.
Please help. I don’t even know how to start.
combinatorics
$endgroup$
$begingroup$
Start with an easier problem: how many two-digit numbers are there? what about three-digit?
$endgroup$
– Vasya
4 hours ago
$begingroup$
I could simply guess the case of two digit numbers. How does it help me prove the general one?
$endgroup$
– furfur
4 hours ago
$begingroup$
You do not need to guess, you can count. How many choices for the first digit do you have? what about the second?
$endgroup$
– Vasya
4 hours ago
$begingroup$
For the first digit (call it a1) there are 5 choices. For the second digit at most 2 choices. Either a1-2 or a1+2. But it depends if a1 is greater than 2/ smaller than 8 etc. I’m stuck on this.
$endgroup$
– furfur
4 hours ago
2
$begingroup$
Letting $a_m$ be the number of such integers with $m$ digits, then $a_m$ obeys the recurrence $$a_m=4a_{m-2}-3a_{m-4}qquad text{for all }mge 6.$$ The proof is based on Julian Mejia's answer, along with the Cayley-Hamilton theorem, but perhaps you can give a combinatorial proof of that recurrence, then solve it.
$endgroup$
– Mike Earnest
3 hours ago
|
show 2 more comments
$begingroup$
How many positive integers n are there such that all of the following take place:
1) n has 1000 digits.
2) all of the digits are odd.
3) the absolute value of the difference of any two consecutive (neighboring) digits is equal to 2.
Please help. I don’t even know how to start.
combinatorics
$endgroup$
How many positive integers n are there such that all of the following take place:
1) n has 1000 digits.
2) all of the digits are odd.
3) the absolute value of the difference of any two consecutive (neighboring) digits is equal to 2.
Please help. I don’t even know how to start.
combinatorics
combinatorics
asked 5 hours ago
furfurfurfur
1119
1119
$begingroup$
Start with an easier problem: how many two-digit numbers are there? what about three-digit?
$endgroup$
– Vasya
4 hours ago
$begingroup$
I could simply guess the case of two digit numbers. How does it help me prove the general one?
$endgroup$
– furfur
4 hours ago
$begingroup$
You do not need to guess, you can count. How many choices for the first digit do you have? what about the second?
$endgroup$
– Vasya
4 hours ago
$begingroup$
For the first digit (call it a1) there are 5 choices. For the second digit at most 2 choices. Either a1-2 or a1+2. But it depends if a1 is greater than 2/ smaller than 8 etc. I’m stuck on this.
$endgroup$
– furfur
4 hours ago
2
$begingroup$
Letting $a_m$ be the number of such integers with $m$ digits, then $a_m$ obeys the recurrence $$a_m=4a_{m-2}-3a_{m-4}qquad text{for all }mge 6.$$ The proof is based on Julian Mejia's answer, along with the Cayley-Hamilton theorem, but perhaps you can give a combinatorial proof of that recurrence, then solve it.
$endgroup$
– Mike Earnest
3 hours ago
|
show 2 more comments
$begingroup$
Start with an easier problem: how many two-digit numbers are there? what about three-digit?
$endgroup$
– Vasya
4 hours ago
$begingroup$
I could simply guess the case of two digit numbers. How does it help me prove the general one?
$endgroup$
– furfur
4 hours ago
$begingroup$
You do not need to guess, you can count. How many choices for the first digit do you have? what about the second?
$endgroup$
– Vasya
4 hours ago
$begingroup$
For the first digit (call it a1) there are 5 choices. For the second digit at most 2 choices. Either a1-2 or a1+2. But it depends if a1 is greater than 2/ smaller than 8 etc. I’m stuck on this.
$endgroup$
– furfur
4 hours ago
2
$begingroup$
Letting $a_m$ be the number of such integers with $m$ digits, then $a_m$ obeys the recurrence $$a_m=4a_{m-2}-3a_{m-4}qquad text{for all }mge 6.$$ The proof is based on Julian Mejia's answer, along with the Cayley-Hamilton theorem, but perhaps you can give a combinatorial proof of that recurrence, then solve it.
$endgroup$
– Mike Earnest
3 hours ago
$begingroup$
Start with an easier problem: how many two-digit numbers are there? what about three-digit?
$endgroup$
– Vasya
4 hours ago
$begingroup$
Start with an easier problem: how many two-digit numbers are there? what about three-digit?
$endgroup$
– Vasya
4 hours ago
$begingroup$
I could simply guess the case of two digit numbers. How does it help me prove the general one?
$endgroup$
– furfur
4 hours ago
$begingroup$
I could simply guess the case of two digit numbers. How does it help me prove the general one?
$endgroup$
– furfur
4 hours ago
$begingroup$
You do not need to guess, you can count. How many choices for the first digit do you have? what about the second?
$endgroup$
– Vasya
4 hours ago
$begingroup$
You do not need to guess, you can count. How many choices for the first digit do you have? what about the second?
$endgroup$
– Vasya
4 hours ago
$begingroup$
For the first digit (call it a1) there are 5 choices. For the second digit at most 2 choices. Either a1-2 or a1+2. But it depends if a1 is greater than 2/ smaller than 8 etc. I’m stuck on this.
$endgroup$
– furfur
4 hours ago
$begingroup$
For the first digit (call it a1) there are 5 choices. For the second digit at most 2 choices. Either a1-2 or a1+2. But it depends if a1 is greater than 2/ smaller than 8 etc. I’m stuck on this.
$endgroup$
– furfur
4 hours ago
2
2
$begingroup$
Letting $a_m$ be the number of such integers with $m$ digits, then $a_m$ obeys the recurrence $$a_m=4a_{m-2}-3a_{m-4}qquad text{for all }mge 6.$$ The proof is based on Julian Mejia's answer, along with the Cayley-Hamilton theorem, but perhaps you can give a combinatorial proof of that recurrence, then solve it.
$endgroup$
– Mike Earnest
3 hours ago
$begingroup$
Letting $a_m$ be the number of such integers with $m$ digits, then $a_m$ obeys the recurrence $$a_m=4a_{m-2}-3a_{m-4}qquad text{for all }mge 6.$$ The proof is based on Julian Mejia's answer, along with the Cayley-Hamilton theorem, but perhaps you can give a combinatorial proof of that recurrence, then solve it.
$endgroup$
– Mike Earnest
3 hours ago
|
show 2 more comments
3 Answers
3
active
oldest
votes
$begingroup$
Define $n_i=2i-1$ (so a bijection between 1,2,3,4,5 with 1,3,5,7,9).
Consider the 5x5 matrix $A=(a_{i,j})$ with $a_{i,j}=1$ if $n_i$ and $n_j$ differ by 2 and $a_{i,j}=0$ otherwise. Then, the number of positive integers with "m" digits satisfying your properties is the sum of entries of $A^{m-1}$. So you want to find the sum of entries of $A^{999}$. I don't know if this is easy to compute without computers.
Edit:
We have $$A=left(begin{array}{ccccc}
0&1&0&0&0\
1&0&1&0&0\
0&1&0&1&0\
0&0&1&0&1\
0&0&0&1&0\
end{array}
right)$$
So, thanks to @Mike's comment, it shouldn't be difficult to find the entries of $A^{999}$ we have that $A=PDP^{-1}$ with
$$D=left(begin{array}{ccccc}
-1&0&0&0&0\
0&0&0&0&0\
0&0&1&0&0\
0&0&0&-sqrt{3}&0\
0&0&0&0&sqrt{3}\
end{array}
right)$$
$$P=left(begin{array}{ccccc}
-1&1&-1&1&1\
1&0&-1&-sqrt{3}&sqrt{3}\
0&-1&0&2&2\
-1&0&1&-sqrt{3}&sqrt{3}\
1&1&1&1&1\
end{array}
right)$$
So, we can compute $A^{999}=PD^{999}P^{-1}$ whose entries will be a linear combination of $(-1)^{999}, (1)^{999}, (-sqrt{3})^{999},(sqrt{3})^{999}$.
$endgroup$
1
$begingroup$
It shouldn't be too bad to diagonalize $A$. The characteristic polynomial is $lambda^5-4lambda^3+3lambda=lambda(lambda^2-1)(lambda^2-3)$, etc.
$endgroup$
– Mike Earnest
3 hours ago
add a comment |
$begingroup$
Here is a OCaml program that computes the number of numbers in term of the size of the number:
type 'a stream= Eos| StrCons of 'a * (unit-> 'a stream)
let hdStr (s: 'a stream) : 'a =
match s with
| Eos -> failwith "headless stream"
| StrCons (x,_) -> x;;
let tlStr (s : 'a stream) : 'a stream =
match s with
| Eos -> failwith "empty stream"
| StrCons (x, t) -> t ();;
let rec listify (s : 'a stream) (n: int) : 'a list =
if n <= 0 then []
else
match s with
| Eos -> []
| _ -> (hdStr s) :: listify (tlStr s) (n - 1);;
let rec howmanynumber start step=
if step = 0 then 1 else
match start with
|1->howmanynumber 3 (step-1)
|3->howmanynumber 1 (step-1) + howmanynumber 5 (step-1)
|5->howmanynumber 3 (step-1) + howmanynumber 7 (step-1)
|7->howmanynumber 5 (step-1) + howmanynumber 9 (step-1)
|9->howmanynumber 7 (step-1)
|_->failwith "exception error"
let count n=
(howmanynumber 1 n)+(howmanynumber 3 n)+(howmanynumber 5 n)+(howmanynumber 7 n)+(howmanynumber 9 n)
let rec thisseq n = StrCons(count n , fun ()-> thisseq (n+1))
let result = thisseq 1
So Based on @Julian solution, the answer is the sum of entries of
$begin{bmatrix}
0 & 1 & 0 & 0 & 0 \
1 & 0 & 1 & 0 & 0 \
0 & 1 & 0 & 1 & 0 \
0 & 0 & 1 & 0 & 1\
0 & 0 & 0 & 1 & 0 \
end{bmatrix}^{999} * begin{bmatrix}
1 \
1 \
1 \
1 \
1 \
end{bmatrix}$
$endgroup$
$begingroup$
Thank you! But it was supposed to be a mathematical proof, since we are on math.stackexchange. Thank you for your effort though!
$endgroup$
– furfur
4 hours ago
add a comment |
$begingroup$
The text was too lengthy for a comment and aims on finalizing the previous answers and comments, which boil down to a very simple final answer for $nge2$: $$a_n=begin{cases}hphantom18cdot 3^{frac{n-2}2},& ntext{ even},\14 cdot 3^{frac{n-3}2},& ntext{ odd}.end{cases}tag1$$
The most simple way to prove $(1)$ is to count directly the number of ways for the cases $n=2,3,4,5$ obtaining $a_n=8,14,24,42$, and then proceed by induction applying the recurrence relation suggested by Mike Earnest on the base of the characteristic polynomial of the matrix introduced by Julian Mejia:
$$
a_n=4a_{n-2}-3a_{n-4}.tag2
$$
In fact the simplicity of the answer suggests that there is possibly a simpler way to prove $(2)$ or even directly $(1)$.
$endgroup$
add a comment |
Your Answer
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%2f3192709%2fcombinatorics-problem-on-counting%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Define $n_i=2i-1$ (so a bijection between 1,2,3,4,5 with 1,3,5,7,9).
Consider the 5x5 matrix $A=(a_{i,j})$ with $a_{i,j}=1$ if $n_i$ and $n_j$ differ by 2 and $a_{i,j}=0$ otherwise. Then, the number of positive integers with "m" digits satisfying your properties is the sum of entries of $A^{m-1}$. So you want to find the sum of entries of $A^{999}$. I don't know if this is easy to compute without computers.
Edit:
We have $$A=left(begin{array}{ccccc}
0&1&0&0&0\
1&0&1&0&0\
0&1&0&1&0\
0&0&1&0&1\
0&0&0&1&0\
end{array}
right)$$
So, thanks to @Mike's comment, it shouldn't be difficult to find the entries of $A^{999}$ we have that $A=PDP^{-1}$ with
$$D=left(begin{array}{ccccc}
-1&0&0&0&0\
0&0&0&0&0\
0&0&1&0&0\
0&0&0&-sqrt{3}&0\
0&0&0&0&sqrt{3}\
end{array}
right)$$
$$P=left(begin{array}{ccccc}
-1&1&-1&1&1\
1&0&-1&-sqrt{3}&sqrt{3}\
0&-1&0&2&2\
-1&0&1&-sqrt{3}&sqrt{3}\
1&1&1&1&1\
end{array}
right)$$
So, we can compute $A^{999}=PD^{999}P^{-1}$ whose entries will be a linear combination of $(-1)^{999}, (1)^{999}, (-sqrt{3})^{999},(sqrt{3})^{999}$.
$endgroup$
1
$begingroup$
It shouldn't be too bad to diagonalize $A$. The characteristic polynomial is $lambda^5-4lambda^3+3lambda=lambda(lambda^2-1)(lambda^2-3)$, etc.
$endgroup$
– Mike Earnest
3 hours ago
add a comment |
$begingroup$
Define $n_i=2i-1$ (so a bijection between 1,2,3,4,5 with 1,3,5,7,9).
Consider the 5x5 matrix $A=(a_{i,j})$ with $a_{i,j}=1$ if $n_i$ and $n_j$ differ by 2 and $a_{i,j}=0$ otherwise. Then, the number of positive integers with "m" digits satisfying your properties is the sum of entries of $A^{m-1}$. So you want to find the sum of entries of $A^{999}$. I don't know if this is easy to compute without computers.
Edit:
We have $$A=left(begin{array}{ccccc}
0&1&0&0&0\
1&0&1&0&0\
0&1&0&1&0\
0&0&1&0&1\
0&0&0&1&0\
end{array}
right)$$
So, thanks to @Mike's comment, it shouldn't be difficult to find the entries of $A^{999}$ we have that $A=PDP^{-1}$ with
$$D=left(begin{array}{ccccc}
-1&0&0&0&0\
0&0&0&0&0\
0&0&1&0&0\
0&0&0&-sqrt{3}&0\
0&0&0&0&sqrt{3}\
end{array}
right)$$
$$P=left(begin{array}{ccccc}
-1&1&-1&1&1\
1&0&-1&-sqrt{3}&sqrt{3}\
0&-1&0&2&2\
-1&0&1&-sqrt{3}&sqrt{3}\
1&1&1&1&1\
end{array}
right)$$
So, we can compute $A^{999}=PD^{999}P^{-1}$ whose entries will be a linear combination of $(-1)^{999}, (1)^{999}, (-sqrt{3})^{999},(sqrt{3})^{999}$.
$endgroup$
1
$begingroup$
It shouldn't be too bad to diagonalize $A$. The characteristic polynomial is $lambda^5-4lambda^3+3lambda=lambda(lambda^2-1)(lambda^2-3)$, etc.
$endgroup$
– Mike Earnest
3 hours ago
add a comment |
$begingroup$
Define $n_i=2i-1$ (so a bijection between 1,2,3,4,5 with 1,3,5,7,9).
Consider the 5x5 matrix $A=(a_{i,j})$ with $a_{i,j}=1$ if $n_i$ and $n_j$ differ by 2 and $a_{i,j}=0$ otherwise. Then, the number of positive integers with "m" digits satisfying your properties is the sum of entries of $A^{m-1}$. So you want to find the sum of entries of $A^{999}$. I don't know if this is easy to compute without computers.
Edit:
We have $$A=left(begin{array}{ccccc}
0&1&0&0&0\
1&0&1&0&0\
0&1&0&1&0\
0&0&1&0&1\
0&0&0&1&0\
end{array}
right)$$
So, thanks to @Mike's comment, it shouldn't be difficult to find the entries of $A^{999}$ we have that $A=PDP^{-1}$ with
$$D=left(begin{array}{ccccc}
-1&0&0&0&0\
0&0&0&0&0\
0&0&1&0&0\
0&0&0&-sqrt{3}&0\
0&0&0&0&sqrt{3}\
end{array}
right)$$
$$P=left(begin{array}{ccccc}
-1&1&-1&1&1\
1&0&-1&-sqrt{3}&sqrt{3}\
0&-1&0&2&2\
-1&0&1&-sqrt{3}&sqrt{3}\
1&1&1&1&1\
end{array}
right)$$
So, we can compute $A^{999}=PD^{999}P^{-1}$ whose entries will be a linear combination of $(-1)^{999}, (1)^{999}, (-sqrt{3})^{999},(sqrt{3})^{999}$.
$endgroup$
Define $n_i=2i-1$ (so a bijection between 1,2,3,4,5 with 1,3,5,7,9).
Consider the 5x5 matrix $A=(a_{i,j})$ with $a_{i,j}=1$ if $n_i$ and $n_j$ differ by 2 and $a_{i,j}=0$ otherwise. Then, the number of positive integers with "m" digits satisfying your properties is the sum of entries of $A^{m-1}$. So you want to find the sum of entries of $A^{999}$. I don't know if this is easy to compute without computers.
Edit:
We have $$A=left(begin{array}{ccccc}
0&1&0&0&0\
1&0&1&0&0\
0&1&0&1&0\
0&0&1&0&1\
0&0&0&1&0\
end{array}
right)$$
So, thanks to @Mike's comment, it shouldn't be difficult to find the entries of $A^{999}$ we have that $A=PDP^{-1}$ with
$$D=left(begin{array}{ccccc}
-1&0&0&0&0\
0&0&0&0&0\
0&0&1&0&0\
0&0&0&-sqrt{3}&0\
0&0&0&0&sqrt{3}\
end{array}
right)$$
$$P=left(begin{array}{ccccc}
-1&1&-1&1&1\
1&0&-1&-sqrt{3}&sqrt{3}\
0&-1&0&2&2\
-1&0&1&-sqrt{3}&sqrt{3}\
1&1&1&1&1\
end{array}
right)$$
So, we can compute $A^{999}=PD^{999}P^{-1}$ whose entries will be a linear combination of $(-1)^{999}, (1)^{999}, (-sqrt{3})^{999},(sqrt{3})^{999}$.
edited 1 hour ago
answered 3 hours ago
Julian MejiaJulian Mejia
64229
64229
1
$begingroup$
It shouldn't be too bad to diagonalize $A$. The characteristic polynomial is $lambda^5-4lambda^3+3lambda=lambda(lambda^2-1)(lambda^2-3)$, etc.
$endgroup$
– Mike Earnest
3 hours ago
add a comment |
1
$begingroup$
It shouldn't be too bad to diagonalize $A$. The characteristic polynomial is $lambda^5-4lambda^3+3lambda=lambda(lambda^2-1)(lambda^2-3)$, etc.
$endgroup$
– Mike Earnest
3 hours ago
1
1
$begingroup$
It shouldn't be too bad to diagonalize $A$. The characteristic polynomial is $lambda^5-4lambda^3+3lambda=lambda(lambda^2-1)(lambda^2-3)$, etc.
$endgroup$
– Mike Earnest
3 hours ago
$begingroup$
It shouldn't be too bad to diagonalize $A$. The characteristic polynomial is $lambda^5-4lambda^3+3lambda=lambda(lambda^2-1)(lambda^2-3)$, etc.
$endgroup$
– Mike Earnest
3 hours ago
add a comment |
$begingroup$
Here is a OCaml program that computes the number of numbers in term of the size of the number:
type 'a stream= Eos| StrCons of 'a * (unit-> 'a stream)
let hdStr (s: 'a stream) : 'a =
match s with
| Eos -> failwith "headless stream"
| StrCons (x,_) -> x;;
let tlStr (s : 'a stream) : 'a stream =
match s with
| Eos -> failwith "empty stream"
| StrCons (x, t) -> t ();;
let rec listify (s : 'a stream) (n: int) : 'a list =
if n <= 0 then []
else
match s with
| Eos -> []
| _ -> (hdStr s) :: listify (tlStr s) (n - 1);;
let rec howmanynumber start step=
if step = 0 then 1 else
match start with
|1->howmanynumber 3 (step-1)
|3->howmanynumber 1 (step-1) + howmanynumber 5 (step-1)
|5->howmanynumber 3 (step-1) + howmanynumber 7 (step-1)
|7->howmanynumber 5 (step-1) + howmanynumber 9 (step-1)
|9->howmanynumber 7 (step-1)
|_->failwith "exception error"
let count n=
(howmanynumber 1 n)+(howmanynumber 3 n)+(howmanynumber 5 n)+(howmanynumber 7 n)+(howmanynumber 9 n)
let rec thisseq n = StrCons(count n , fun ()-> thisseq (n+1))
let result = thisseq 1
So Based on @Julian solution, the answer is the sum of entries of
$begin{bmatrix}
0 & 1 & 0 & 0 & 0 \
1 & 0 & 1 & 0 & 0 \
0 & 1 & 0 & 1 & 0 \
0 & 0 & 1 & 0 & 1\
0 & 0 & 0 & 1 & 0 \
end{bmatrix}^{999} * begin{bmatrix}
1 \
1 \
1 \
1 \
1 \
end{bmatrix}$
$endgroup$
$begingroup$
Thank you! But it was supposed to be a mathematical proof, since we are on math.stackexchange. Thank you for your effort though!
$endgroup$
– furfur
4 hours ago
add a comment |
$begingroup$
Here is a OCaml program that computes the number of numbers in term of the size of the number:
type 'a stream= Eos| StrCons of 'a * (unit-> 'a stream)
let hdStr (s: 'a stream) : 'a =
match s with
| Eos -> failwith "headless stream"
| StrCons (x,_) -> x;;
let tlStr (s : 'a stream) : 'a stream =
match s with
| Eos -> failwith "empty stream"
| StrCons (x, t) -> t ();;
let rec listify (s : 'a stream) (n: int) : 'a list =
if n <= 0 then []
else
match s with
| Eos -> []
| _ -> (hdStr s) :: listify (tlStr s) (n - 1);;
let rec howmanynumber start step=
if step = 0 then 1 else
match start with
|1->howmanynumber 3 (step-1)
|3->howmanynumber 1 (step-1) + howmanynumber 5 (step-1)
|5->howmanynumber 3 (step-1) + howmanynumber 7 (step-1)
|7->howmanynumber 5 (step-1) + howmanynumber 9 (step-1)
|9->howmanynumber 7 (step-1)
|_->failwith "exception error"
let count n=
(howmanynumber 1 n)+(howmanynumber 3 n)+(howmanynumber 5 n)+(howmanynumber 7 n)+(howmanynumber 9 n)
let rec thisseq n = StrCons(count n , fun ()-> thisseq (n+1))
let result = thisseq 1
So Based on @Julian solution, the answer is the sum of entries of
$begin{bmatrix}
0 & 1 & 0 & 0 & 0 \
1 & 0 & 1 & 0 & 0 \
0 & 1 & 0 & 1 & 0 \
0 & 0 & 1 & 0 & 1\
0 & 0 & 0 & 1 & 0 \
end{bmatrix}^{999} * begin{bmatrix}
1 \
1 \
1 \
1 \
1 \
end{bmatrix}$
$endgroup$
$begingroup$
Thank you! But it was supposed to be a mathematical proof, since we are on math.stackexchange. Thank you for your effort though!
$endgroup$
– furfur
4 hours ago
add a comment |
$begingroup$
Here is a OCaml program that computes the number of numbers in term of the size of the number:
type 'a stream= Eos| StrCons of 'a * (unit-> 'a stream)
let hdStr (s: 'a stream) : 'a =
match s with
| Eos -> failwith "headless stream"
| StrCons (x,_) -> x;;
let tlStr (s : 'a stream) : 'a stream =
match s with
| Eos -> failwith "empty stream"
| StrCons (x, t) -> t ();;
let rec listify (s : 'a stream) (n: int) : 'a list =
if n <= 0 then []
else
match s with
| Eos -> []
| _ -> (hdStr s) :: listify (tlStr s) (n - 1);;
let rec howmanynumber start step=
if step = 0 then 1 else
match start with
|1->howmanynumber 3 (step-1)
|3->howmanynumber 1 (step-1) + howmanynumber 5 (step-1)
|5->howmanynumber 3 (step-1) + howmanynumber 7 (step-1)
|7->howmanynumber 5 (step-1) + howmanynumber 9 (step-1)
|9->howmanynumber 7 (step-1)
|_->failwith "exception error"
let count n=
(howmanynumber 1 n)+(howmanynumber 3 n)+(howmanynumber 5 n)+(howmanynumber 7 n)+(howmanynumber 9 n)
let rec thisseq n = StrCons(count n , fun ()-> thisseq (n+1))
let result = thisseq 1
So Based on @Julian solution, the answer is the sum of entries of
$begin{bmatrix}
0 & 1 & 0 & 0 & 0 \
1 & 0 & 1 & 0 & 0 \
0 & 1 & 0 & 1 & 0 \
0 & 0 & 1 & 0 & 1\
0 & 0 & 0 & 1 & 0 \
end{bmatrix}^{999} * begin{bmatrix}
1 \
1 \
1 \
1 \
1 \
end{bmatrix}$
$endgroup$
Here is a OCaml program that computes the number of numbers in term of the size of the number:
type 'a stream= Eos| StrCons of 'a * (unit-> 'a stream)
let hdStr (s: 'a stream) : 'a =
match s with
| Eos -> failwith "headless stream"
| StrCons (x,_) -> x;;
let tlStr (s : 'a stream) : 'a stream =
match s with
| Eos -> failwith "empty stream"
| StrCons (x, t) -> t ();;
let rec listify (s : 'a stream) (n: int) : 'a list =
if n <= 0 then []
else
match s with
| Eos -> []
| _ -> (hdStr s) :: listify (tlStr s) (n - 1);;
let rec howmanynumber start step=
if step = 0 then 1 else
match start with
|1->howmanynumber 3 (step-1)
|3->howmanynumber 1 (step-1) + howmanynumber 5 (step-1)
|5->howmanynumber 3 (step-1) + howmanynumber 7 (step-1)
|7->howmanynumber 5 (step-1) + howmanynumber 9 (step-1)
|9->howmanynumber 7 (step-1)
|_->failwith "exception error"
let count n=
(howmanynumber 1 n)+(howmanynumber 3 n)+(howmanynumber 5 n)+(howmanynumber 7 n)+(howmanynumber 9 n)
let rec thisseq n = StrCons(count n , fun ()-> thisseq (n+1))
let result = thisseq 1
So Based on @Julian solution, the answer is the sum of entries of
$begin{bmatrix}
0 & 1 & 0 & 0 & 0 \
1 & 0 & 1 & 0 & 0 \
0 & 1 & 0 & 1 & 0 \
0 & 0 & 1 & 0 & 1\
0 & 0 & 0 & 1 & 0 \
end{bmatrix}^{999} * begin{bmatrix}
1 \
1 \
1 \
1 \
1 \
end{bmatrix}$
edited 3 hours ago
answered 4 hours ago
mathpadawanmathpadawan
2,175522
2,175522
$begingroup$
Thank you! But it was supposed to be a mathematical proof, since we are on math.stackexchange. Thank you for your effort though!
$endgroup$
– furfur
4 hours ago
add a comment |
$begingroup$
Thank you! But it was supposed to be a mathematical proof, since we are on math.stackexchange. Thank you for your effort though!
$endgroup$
– furfur
4 hours ago
$begingroup$
Thank you! But it was supposed to be a mathematical proof, since we are on math.stackexchange. Thank you for your effort though!
$endgroup$
– furfur
4 hours ago
$begingroup$
Thank you! But it was supposed to be a mathematical proof, since we are on math.stackexchange. Thank you for your effort though!
$endgroup$
– furfur
4 hours ago
add a comment |
$begingroup$
The text was too lengthy for a comment and aims on finalizing the previous answers and comments, which boil down to a very simple final answer for $nge2$: $$a_n=begin{cases}hphantom18cdot 3^{frac{n-2}2},& ntext{ even},\14 cdot 3^{frac{n-3}2},& ntext{ odd}.end{cases}tag1$$
The most simple way to prove $(1)$ is to count directly the number of ways for the cases $n=2,3,4,5$ obtaining $a_n=8,14,24,42$, and then proceed by induction applying the recurrence relation suggested by Mike Earnest on the base of the characteristic polynomial of the matrix introduced by Julian Mejia:
$$
a_n=4a_{n-2}-3a_{n-4}.tag2
$$
In fact the simplicity of the answer suggests that there is possibly a simpler way to prove $(2)$ or even directly $(1)$.
$endgroup$
add a comment |
$begingroup$
The text was too lengthy for a comment and aims on finalizing the previous answers and comments, which boil down to a very simple final answer for $nge2$: $$a_n=begin{cases}hphantom18cdot 3^{frac{n-2}2},& ntext{ even},\14 cdot 3^{frac{n-3}2},& ntext{ odd}.end{cases}tag1$$
The most simple way to prove $(1)$ is to count directly the number of ways for the cases $n=2,3,4,5$ obtaining $a_n=8,14,24,42$, and then proceed by induction applying the recurrence relation suggested by Mike Earnest on the base of the characteristic polynomial of the matrix introduced by Julian Mejia:
$$
a_n=4a_{n-2}-3a_{n-4}.tag2
$$
In fact the simplicity of the answer suggests that there is possibly a simpler way to prove $(2)$ or even directly $(1)$.
$endgroup$
add a comment |
$begingroup$
The text was too lengthy for a comment and aims on finalizing the previous answers and comments, which boil down to a very simple final answer for $nge2$: $$a_n=begin{cases}hphantom18cdot 3^{frac{n-2}2},& ntext{ even},\14 cdot 3^{frac{n-3}2},& ntext{ odd}.end{cases}tag1$$
The most simple way to prove $(1)$ is to count directly the number of ways for the cases $n=2,3,4,5$ obtaining $a_n=8,14,24,42$, and then proceed by induction applying the recurrence relation suggested by Mike Earnest on the base of the characteristic polynomial of the matrix introduced by Julian Mejia:
$$
a_n=4a_{n-2}-3a_{n-4}.tag2
$$
In fact the simplicity of the answer suggests that there is possibly a simpler way to prove $(2)$ or even directly $(1)$.
$endgroup$
The text was too lengthy for a comment and aims on finalizing the previous answers and comments, which boil down to a very simple final answer for $nge2$: $$a_n=begin{cases}hphantom18cdot 3^{frac{n-2}2},& ntext{ even},\14 cdot 3^{frac{n-3}2},& ntext{ odd}.end{cases}tag1$$
The most simple way to prove $(1)$ is to count directly the number of ways for the cases $n=2,3,4,5$ obtaining $a_n=8,14,24,42$, and then proceed by induction applying the recurrence relation suggested by Mike Earnest on the base of the characteristic polynomial of the matrix introduced by Julian Mejia:
$$
a_n=4a_{n-2}-3a_{n-4}.tag2
$$
In fact the simplicity of the answer suggests that there is possibly a simpler way to prove $(2)$ or even directly $(1)$.
edited 13 mins ago
answered 3 hours ago
useruser
6,69011031
6,69011031
add a comment |
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%2f3192709%2fcombinatorics-problem-on-counting%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$
Start with an easier problem: how many two-digit numbers are there? what about three-digit?
$endgroup$
– Vasya
4 hours ago
$begingroup$
I could simply guess the case of two digit numbers. How does it help me prove the general one?
$endgroup$
– furfur
4 hours ago
$begingroup$
You do not need to guess, you can count. How many choices for the first digit do you have? what about the second?
$endgroup$
– Vasya
4 hours ago
$begingroup$
For the first digit (call it a1) there are 5 choices. For the second digit at most 2 choices. Either a1-2 or a1+2. But it depends if a1 is greater than 2/ smaller than 8 etc. I’m stuck on this.
$endgroup$
– furfur
4 hours ago
2
$begingroup$
Letting $a_m$ be the number of such integers with $m$ digits, then $a_m$ obeys the recurrence $$a_m=4a_{m-2}-3a_{m-4}qquad text{for all }mge 6.$$ The proof is based on Julian Mejia's answer, along with the Cayley-Hamilton theorem, but perhaps you can give a combinatorial proof of that recurrence, then solve it.
$endgroup$
– Mike Earnest
3 hours ago