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

NumericArray versus PackedArray in MMA12

What was the first language to use conditional keywords?

Combinatorics problem on counting.

How could we fake a moon landing now?

Amount of permutations on an NxNxN Rubik's Cube

Can anything be seen from the center of the Boötes void? How dark would it be?

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

How were pictures turned from film to a big picture in a picture frame before digital scanning?

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

What initially awakened the Balrog?

How to write the following sign?

Significance of Cersei's obsession with elephants?

How would a mousetrap for use in space work?

Generate an RGB colour grid

Drawing without replacement: why is the order of draw irrelevant?

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

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

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

Why doesn't SQL Optimizer use my constraint?

Did Deadpool rescue all of the X-Force?

Dating a Former Employee

How do I make this wiring inside cabinet safer?

Chebyshev inequality in terms of RMS

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







            Popular posts from this blog

            Францішак Багушэвіч Змест Сям'я | Біяграфія | Творчасць | Мова Багушэвіча | Ацэнкі дзейнасці | Цікавыя факты | Спадчына | Выбраная бібліяграфія | Ушанаванне памяці | У філатэліі | Зноскі | Літаратура | Спасылкі | НавігацыяЛяхоўскі У. Рупіўся дзеля Бога і людзей: Жыццёвы шлях Лявона Вітан-Дубейкаўскага // Вольскі і Памідораў з песняй пра немца Адвакат, паэт, народны заступнік Ашмянскі веснікВ Минске появится площадь Богушевича и улица Сырокомли, Белорусская деловая газета, 19 июля 2001 г.Айцец беларускай нацыянальнай ідэі паўстаў у бронзе Сяргей Аляксандравіч Адашкевіч (1918, Мінск). 80-я гады. Бюст «Францішак Багушэвіч».Яўген Мікалаевіч Ціхановіч. «Партрэт Францішка Багушэвіча»Мікола Мікалаевіч Купава. «Партрэт зачынальніка новай беларускай літаратуры Францішка Багушэвіча»Уладзімір Іванавіч Мелехаў. На помніку «Змагарам за родную мову» Барэльеф «Францішак Багушэвіч»Памяць пра Багушэвіча на Віленшчыне Страчаная сталіца. Беларускія шыльды на вуліцах Вільні«Krynica». Ideologia i przywódcy białoruskiego katolicyzmuФранцішак БагушэвічТворы на knihi.comТворы Францішка Багушэвіча на bellib.byСодаль Уладзімір. Францішак Багушэвіч на Лідчыне;Луцкевіч Антон. Жыцьцё і творчасьць Фр. Багушэвіча ў успамінах ягоных сучасьнікаў // Запісы Беларускага Навуковага таварыства. Вільня, 1938. Сшытак 1. С. 16-34.Большая российская1188761710000 0000 5537 633Xn9209310021619551927869394п

            Беларусь Змест Назва Гісторыя Геаграфія Сімволіка Дзяржаўны лад Палітычныя партыі Міжнароднае становішча і знешняя палітыка Адміністрацыйны падзел Насельніцтва Эканоміка Культура і грамадства Сацыяльная сфера Узброеныя сілы Заўвагі Літаратура Спасылкі НавігацыяHGЯOiТоп-2011 г. (па версіі ej.by)Топ-2013 г. (па версіі ej.by)Топ-2016 г. (па версіі ej.by)Топ-2017 г. (па версіі ej.by)Нацыянальны статыстычны камітэт Рэспублікі БеларусьШчыльнасць насельніцтва па краінахhttp://naviny.by/rubrics/society/2011/09/16/ic_articles_116_175144/А. Калечыц, У. Ксяндзоў. Спробы засялення краю неандэртальскім чалавекам.І ў Менску былі мамантыА. Калечыц, У. Ксяндзоў. Старажытны каменны век (палеаліт). Першапачатковае засяленне тэрыторыіГ. Штыхаў. Балты і славяне ў VI—VIII стст.М. Клімаў. Полацкае княства ў IX—XI стст.Г. Штыхаў, В. Ляўко. Палітычная гісторыя Полацкай зямліГ. Штыхаў. Дзяржаўны лад у землях-княствахГ. Штыхаў. Дзяржаўны лад у землях-княствахБеларускія землі ў складзе Вялікага Княства ЛітоўскагаЛюблінская унія 1569 г."The Early Stages of Independence"Zapomniane prawdy25 гадоў таму было аб'яўлена, што Язэп Пілсудскі — беларус (фота)Наша вадаДакументы ЧАЭС: Забруджванне тэрыторыі Беларусі « ЧАЭС Зона адчужэнняСведения о политических партиях, зарегистрированных в Республике Беларусь // Министерство юстиции Республики БеларусьСтатыстычны бюлетэнь „Полаўзроставая структура насельніцтва Рэспублікі Беларусь на 1 студзеня 2012 года і сярэднегадовая колькасць насельніцтва за 2011 год“Индекс человеческого развития Беларуси — не было бы нижеБеларусь занимает первое место в СНГ по индексу развития с учетом гендерного факцёраНацыянальны статыстычны камітэт Рэспублікі БеларусьКанстытуцыя РБ. Артыкул 17Трансфармацыйныя задачы БеларусіВыйсце з крызісу — далейшае рэфармаванне Беларускі рубель — сусветны лідар па дэвальвацыяхПра змену коштаў у кастрычніку 2011 г.Бядней за беларусаў у СНД толькі таджыкіСярэдні заробак у верасні дасягнуў 2,26 мільёна рублёўЭканомікаГаласуем за ТОП-100 беларускай прозыСучасныя беларускія мастакіАрхитектура Беларуси BELARUS.BYА. Каханоўскі. Культура Беларусі ўсярэдзіне XVII—XVIII ст.Анталогія беларускай народнай песні, гуказапісы спеваўБеларускія Музычныя IнструментыБеларускі рок, які мы страцілі. Топ-10 гуртоў«Мясцовы час» — нязгаслая легенда беларускай рок-музыкіСЯРГЕЙ БУДКІН. МЫ НЯ ЗНАЕМ СВАЁЙ МУЗЫКІМ. А. Каладзінскі. НАРОДНЫ ТЭАТРМагнацкія культурныя цэнтрыПублічная дыскусія «Беларуская новая пьеса: без беларускай мовы ці беларуская?»Беларускія драматургі па-ранейшаму лепш ставяцца за мяжой, чым на радзіме«Працэс незалежнага кіно пайшоў, і дзяржаву турбуе яго непадкантрольнасць»Беларускія філосафы ў пошуках прасторыВсе идём в библиотекуАрхіваванаАб Нацыянальнай праграме даследавання і выкарыстання касмічнай прасторы ў мірных мэтах на 2008—2012 гадыУ космас — разам.У суседнім з Барысаўскім раёне пабудуюць Камандна-вымяральны пунктСвяты і абрады беларусаў«Мірныя бульбашы з малой краіны» — 5 непраўдзівых стэрэатыпаў пра БеларусьМ. Раманюк. Беларускае народнае адзеннеУ Беларусі скарачаецца колькасць злачынстваўЛукашэнка незадаволены мінскімі ўладамі Крадзяжы складаюць у Мінску каля 70% злачынстваў Узровень злачыннасці ў Мінскай вобласці — адзін з самых высокіх у краіне Генпракуратура аналізуе стан са злачыннасцю ў Беларусі па каэфіцыенце злачыннасці У Беларусі стабілізавалася крымінагеннае становішча, лічыць генпракурорЗамежнікі сталі здзяйсняць у Беларусі больш злачынстваўМУС Беларусі турбуе рост рэцыдыўнай злачыннасціЯ з ЖЭСа. Дазволіце вас абкрасці! Рэйтынг усіх службаў і падраздзяленняў ГУУС Мінгарвыканкама вырасАб КДБ РБГісторыя Аператыўна-аналітычнага цэнтра РБГісторыя ДКФРТаможняagentura.ruБеларусьBelarus.by — Афіцыйны сайт Рэспублікі БеларусьСайт урада БеларусіRadzima.org — Збор архітэктурных помнікаў, гісторыя Беларусі«Глобус Беларуси»Гербы и флаги БеларусиАсаблівасці каменнага веку на БеларусіА. Калечыц, У. Ксяндзоў. Старажытны каменны век (палеаліт). Першапачатковае засяленне тэрыторыіУ. Ксяндзоў. Сярэдні каменны век (мезаліт). Засяленне краю плямёнамі паляўнічых, рыбакоў і збіральнікаўА. Калечыц, М. Чарняўскі. Плямёны на тэрыторыі Беларусі ў новым каменным веку (неаліце)А. Калечыц, У. Ксяндзоў, М. Чарняўскі. Гаспадарчыя заняткі ў каменным векуЭ. Зайкоўскі. Духоўная культура ў каменным векуАсаблівасці бронзавага веку на БеларусіФарміраванне супольнасцей ранняга перыяду бронзавага векуФотографии БеларусиРоля беларускіх зямель ва ўтварэнні і ўмацаванні ВКЛВ. Фадзеева. З гісторыі развіцця беларускай народнай вышыўкіDMOZGran catalanaБольшая российскаяBritannica (анлайн)Швейцарскі гістарычны15325917611952699xDA123282154079143-90000 0001 2171 2080n9112870100577502ge128882171858027501086026362074122714179пппппп

            ValueError: Expected n_neighbors <= n_samples, but n_samples = 1, n_neighbors = 6 (SMOTE) The 2019 Stack Overflow Developer Survey Results Are InCan SMOTE be applied over sequence of words (sentences)?ValueError when doing validation with random forestsSMOTE and multi class oversamplingLogic behind SMOTE-NC?ValueError: Error when checking target: expected dense_1 to have shape (7,) but got array with shape (1,)SmoteBoost: Should SMOTE be ran individually for each iteration/tree in the boosting?solving multi-class imbalance classification using smote and OSSUsing SMOTE for Synthetic Data generation to improve performance on unbalanced dataproblem of entry format for a simple model in KerasSVM SMOTE fit_resample() function runs forever with no result