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

Why aren't air breathing engines used as small first stages?

Did Deadpool rescue all of the X-Force?

How to install press fit bottom bracket into new frame

How does the math work when buying airline miles?

Project Euler #1 in C++

NumericArray versus PackedArray in MMA12

Is grep documentation about ignoring case wrong, since it doesn't ignore case in filenames?

Why does it sometimes sound good to play a grace note as a lead in to a note in a melody?

Can an alien society believe that their star system is the universe?

Is there a kind of relay only consumes power when switching?

Question about debouncing - delay of state change

What was the first language to use conditional keywords?

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

Chebyshev inequality in terms of RMS

Why doesn't SQL Optimizer use my constraint?

Why do we bend a book to keep it straight?

Significance of Cersei's obsession with elephants?

What initially awakened the Balrog?

What is the appropriate index architecture when forced to implement IsDeleted (soft deletes)?

Is there any word for a place full of confusion?

Crossing US/Canada Border for less than 24 hours

Central Vacuuming: Is it worth it, and how does it compare to normal vacuuming?

Why do we need to use the builder design pattern when we can do the same thing with setters?

An adverb for when you're not exaggerating



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
    3 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
      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
      3 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 3 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
      3 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
      3 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
    3 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
    3 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 22 secs 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







            Popular posts from this blog

            Disable / Remove link to Product Items in Cart Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How can I limit products that can be bought / added to cart?Remove item from cartHide “Add to Cart” button if specific products are already in cart“Prettifying” the custom options in cart pageCreate link in cart sidebar to view all added items After limit reachedLink products together in checkout/cartHow to Get product from cart and add it againHide action-edit on cart page if simple productRemoving Cart items - ObserverRemove wishlist items when added to cart

            Helsingin valtaus Sisällysluettelo Taustaa | Yleistä sotatoimista | Osapuolet | Taistelut Helsingin ympäristössä | Punaisten antautumissuunnitelma | Taistelujen kulku Helsingissä | Valtauksen jälkeen | Tappiot | Muistaminen | Kirjallisuutta | Lähteet | Aiheesta muualla | NavigointivalikkoTeoksen verkkoversioTeoksen verkkoversioGoogle BooksSisällissota Helsingissä päättyi tasan 95 vuotta sittenSaksalaisten ylivoima jyräsi punaisen HelsinginSuomalaiset kuvaavat sotien jälkiä kaupungeissa – katso kuvat ja tarinat tutuilta kulmiltaHelsingin valtaus 90 vuotta sittenSaksalaiset valtasivat HelsinginHyökkäys HelsinkiinHelsingin valtaus 12.–13.4. 1918Saksalaiset käyttivät ihmiskilpiä Helsingin valtauksessa 1918Teoksen verkkoversioTeoksen verkkoversioSaksalaiset hyökkäävät Etelä-SuomeenTaistelut LeppävaarassaSotilaat ja taistelutLeppävaara 1918 huhtikuussa. KapinatarinaHelsingin taistelut 1918Saksalaisten voitonparaati HelsingissäHelsingin valtausta juhlittiinSaksalaisten Helsinki vuonna 1918Helsingin taistelussa kaatuneet valkokaartilaisetHelsinkiin haudatut taisteluissa kaatuneet punaiset12.4.1918 Helsingin valtauksessa saksalaiset apujoukot vapauttavat kaupunginVapaussodan muistomerkkejä Helsingissä ja pääkaupunkiseudullaCrescendo / Vuoden 1918 Kansalaissodan uhrien muistomerkkim

            Adjektiivitarina Tarinan tekeminen | Esimerkki: ennen | Esimerkki: jälkeen | Navigointivalikko