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

Multi tool use
Multi tool use

Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?

Illegal assignment from sObject to Id

Why does the remaining Rebel fleet at the end of Rogue One seem dramatically larger than the one in A New Hope?

Project Euler #1 in C++

Why is it faster to reheat something than it is to cook it?

How does the math work when buying airline miles?

Sum letters are not two different

Can a new player join a group only when a new campaign starts?

Maximum summed subsequences with non-adjacent items

Take 2! Is this homebrew Lady of Pain warlock patron balanced?

Crossing US/Canada Border for less than 24 hours

Did Krishna say in Bhagavad Gita "I am in every living being"

How do living politicians protect their readily obtainable signatures from misuse?

How fail-safe is nr as stop bytes?

How to compare two different files line by line in unix?

How does light 'choose' between wave and particle behaviour?

What is a fractional matching?

Do any jurisdictions seriously consider reclassifying social media websites as publishers?

Find 108 by using 3,4,6

Do I really need to have a message in a novel to appeal to readers?

Is there hard evidence that the grant peer review system performs significantly better than random?

SF book about people trapped in a series of worlds they imagine

What does it mean that physics no longer uses mechanical models to describe phenomena?

Most bit efficient text communication method?



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










3












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










share|cite|improve this question









$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-4qquad textfor 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
    2 hours ago















3












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










share|cite|improve this question









$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-4qquad textfor 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
    2 hours ago













3












3








3





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










share|cite|improve this question









$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






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 4 hours ago









furfurfurfur

1069




1069











  • $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-4qquad textfor 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
    2 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$
    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-4qquad textfor 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
    2 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-4qquad textfor 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
2 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-4qquad textfor 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
2 hours ago










3 Answers
3






active

oldest

votes


















2












$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(beginarrayccccc
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\
endarray
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(beginarrayccccc
-1&0&0&0&0\
0&0&0&0&0\
0&0&1&0&0\
0&0&0&-sqrt3&0\
0&0&0&0&sqrt3\
endarray
right)$$



$$P=left(beginarrayccccc
-1&1&-1&1&1\
1&0&-1&-sqrt3&sqrt3\
0&-1&0&2&2\
-1&0&1&-sqrt3&sqrt3\
1&1&1&1&1\
endarray
right)$$

So, we can compute $A^999=PD^999P^-1$ whose entries will be a linear combination of $(-1)^999, (1)^999, (-sqrt3)^999,(sqrt3)^999$.






share|cite|improve this answer











$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


















1












$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



$beginbmatrix
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 \
endbmatrix^999 * beginbmatrix
1 \
1 \
1 \
1 \
1 \
endbmatrix$






share|cite|improve this answer











$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


















1












$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=begincaseshphantom18cdot 3^fracn-22,& ntext even,\14 cdot 3^fracn-32,& ntext odd.endcasestag1$$



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)$.






share|cite|improve this answer











$endgroup$













    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
    );



    );













    draft saved

    draft discarded


















    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









    2












    $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(beginarrayccccc
    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\
    endarray
    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(beginarrayccccc
    -1&0&0&0&0\
    0&0&0&0&0\
    0&0&1&0&0\
    0&0&0&-sqrt3&0\
    0&0&0&0&sqrt3\
    endarray
    right)$$



    $$P=left(beginarrayccccc
    -1&1&-1&1&1\
    1&0&-1&-sqrt3&sqrt3\
    0&-1&0&2&2\
    -1&0&1&-sqrt3&sqrt3\
    1&1&1&1&1\
    endarray
    right)$$

    So, we can compute $A^999=PD^999P^-1$ whose entries will be a linear combination of $(-1)^999, (1)^999, (-sqrt3)^999,(sqrt3)^999$.






    share|cite|improve this answer











    $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















    2












    $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(beginarrayccccc
    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\
    endarray
    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(beginarrayccccc
    -1&0&0&0&0\
    0&0&0&0&0\
    0&0&1&0&0\
    0&0&0&-sqrt3&0\
    0&0&0&0&sqrt3\
    endarray
    right)$$



    $$P=left(beginarrayccccc
    -1&1&-1&1&1\
    1&0&-1&-sqrt3&sqrt3\
    0&-1&0&2&2\
    -1&0&1&-sqrt3&sqrt3\
    1&1&1&1&1\
    endarray
    right)$$

    So, we can compute $A^999=PD^999P^-1$ whose entries will be a linear combination of $(-1)^999, (1)^999, (-sqrt3)^999,(sqrt3)^999$.






    share|cite|improve this answer











    $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













    2












    2








    2





    $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(beginarrayccccc
    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\
    endarray
    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(beginarrayccccc
    -1&0&0&0&0\
    0&0&0&0&0\
    0&0&1&0&0\
    0&0&0&-sqrt3&0\
    0&0&0&0&sqrt3\
    endarray
    right)$$



    $$P=left(beginarrayccccc
    -1&1&-1&1&1\
    1&0&-1&-sqrt3&sqrt3\
    0&-1&0&2&2\
    -1&0&1&-sqrt3&sqrt3\
    1&1&1&1&1\
    endarray
    right)$$

    So, we can compute $A^999=PD^999P^-1$ whose entries will be a linear combination of $(-1)^999, (1)^999, (-sqrt3)^999,(sqrt3)^999$.






    share|cite|improve this answer











    $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(beginarrayccccc
    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\
    endarray
    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(beginarrayccccc
    -1&0&0&0&0\
    0&0&0&0&0\
    0&0&1&0&0\
    0&0&0&-sqrt3&0\
    0&0&0&0&sqrt3\
    endarray
    right)$$



    $$P=left(beginarrayccccc
    -1&1&-1&1&1\
    1&0&-1&-sqrt3&sqrt3\
    0&-1&0&2&2\
    -1&0&1&-sqrt3&sqrt3\
    1&1&1&1&1\
    endarray
    right)$$

    So, we can compute $A^999=PD^999P^-1$ whose entries will be a linear combination of $(-1)^999, (1)^999, (-sqrt3)^999,(sqrt3)^999$.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    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












    • 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











    1












    $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



    $beginbmatrix
    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 \
    endbmatrix^999 * beginbmatrix
    1 \
    1 \
    1 \
    1 \
    1 \
    endbmatrix$






    share|cite|improve this answer











    $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















    1












    $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



    $beginbmatrix
    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 \
    endbmatrix^999 * beginbmatrix
    1 \
    1 \
    1 \
    1 \
    1 \
    endbmatrix$






    share|cite|improve this answer











    $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













    1












    1








    1





    $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



    $beginbmatrix
    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 \
    endbmatrix^999 * beginbmatrix
    1 \
    1 \
    1 \
    1 \
    1 \
    endbmatrix$






    share|cite|improve this answer











    $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



    $beginbmatrix
    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 \
    endbmatrix^999 * beginbmatrix
    1 \
    1 \
    1 \
    1 \
    1 \
    endbmatrix$







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    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
















    • $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











    1












    $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=begincaseshphantom18cdot 3^fracn-22,& ntext even,\14 cdot 3^fracn-32,& ntext odd.endcasestag1$$



    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)$.






    share|cite|improve this answer











    $endgroup$

















      1












      $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=begincaseshphantom18cdot 3^fracn-22,& ntext even,\14 cdot 3^fracn-32,& ntext odd.endcasestag1$$



      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)$.






      share|cite|improve this answer











      $endgroup$















        1












        1








        1





        $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=begincaseshphantom18cdot 3^fracn-22,& ntext even,\14 cdot 3^fracn-32,& ntext odd.endcasestag1$$



        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)$.






        share|cite|improve this answer











        $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=begincaseshphantom18cdot 3^fracn-22,& ntext even,\14 cdot 3^fracn-32,& ntext odd.endcasestag1$$



        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)$.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited 10 mins ago

























        answered 3 hours ago









        useruser

        6,69011031




        6,69011031



























            draft saved

            draft discarded
















































            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.




            draft saved


            draft discarded














            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





















































            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







            Zga,a8ZSMfpGbPKvQkCBuLx5QNxNv6Pyuwb2UAI96,t9KqcMI1xi4l,4I9fX6R,KMV,5tpWrvDlpzvw Se2CyprIo
            SNinHl0G1UKWSBBhSlnR5ThXzsoU7UnkZYU

            Popular posts from this blog

            名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠-名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局

            香港授勳及嘉獎制度 目录 勳章及獎狀類別 嘉獎等級 授勳及嘉獎提名 統計數字 多次獲頒勳章或獎狀的人士 爭議 褫奪機制 参考文献 外部連結 参见 导航菜单統計數字一九九七年七月二日(星期三)香港特別行政區的授勳制度六七暴動領袖獲大紫荊勳章 董建華被斥為肯定殺人放火董建華授勳楊光 議員窮追猛打蘋論:顛倒是非黑白的大紫荊董讚楊光有貢獻避談暴動董拒答授勳楊光原因撤除勳銜撤除勳銜撤除勳銜特首掌「搣柴」生殺權行為失當罪 隨時「搣柴」失長糧政府刊憲 許仕仁郭炳江遭「搣柴」去年中終極上訴失敗 許仕仁郭炳江撤勳章太平紳士猛料阿Sir講古—— 「搣柴」有故一九九八年授勳名單一九九九年授勳名單二○○三年授勳名單二○○八年授勳名單二○○七年授勳名單政府總部禮賓處 - 授勳及嘉獎香港特別行政區勳章綬帶一覽(PDF)(非官方)

            Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar