How many combinations does Android pattern have? Rules-
1) At-least 4 and at-max 9 dots must be connected.
2) There can be no jumps

3) Once a dot is crossed, you can jump over it.
I think it's impossible to find it in a combinatory way, I used a recursive research to find it and it gave me the answer 487272. Under there is the c++ code. But a lot of sites posts a lesser answer, 389112. I'd like to see a more matematical way to solve this.

#include &lt;iostream&gt;
#include &lt;stdlib.h&gt;
using namespace std;

int combo;  //counter

void research(int Ipoints /*number of points already took*/, bool Icheck[9]/*points matrix*/,int Ilast/*last took point*/,
                   int Icomboval/*combination representation, only for printing purpose*/, int deep/*number of iteration, only for printing purpose*/)
{

    //  int numcall = 0;  //DEBUG


     for( int i=0; i&lt;9; i++) //Controlling every free point in search of a valid way to contimue
          if( Icheck[i] == false )
          {   
              //Just for security, coping every variable in a new variable. I don't know how c++ works but I will make it works
              int points = Ipoints;
              int last = Ilast;
              int comboval = Icomboval;
              bool check[9];
                   for( int j=0; j&lt;9; j++)
                        check[j] = Icheck[j];   

              int e1,e2; 
              int middle = -1;
              e1=i; e2=last;  //Controlling duble jumps
              if( e1 == 0 &amp;&amp; e2 == 2 ) middle = 1;
              if( e1 == 3 &amp;&amp; e2 == 5 ) middle = 4;
              if( e1 == 6 &amp;&amp; e2 == 8 ) middle = 7;
              if( e1 == 0 &amp;&amp; e2 == 6 ) middle = 3;
              if( e1 == 1 &amp;&amp; e2 == 7 ) middle = 4;
              if( e1 == 2 &amp;&amp; e2 == 8 ) middle = 5;
              if( e1 == 0 &amp;&amp; e2 == 8 ) middle = 4;
              if( e1 == 6 &amp;&amp; e2 == 2 ) middle = 4;

              e2=i; e1=last;  // in both way 
              if( e1 == 0 &amp;&amp; e2 == 2 ) middle = 1;
              if( e1 == 3 &amp;&amp; e2 == 5 ) middle = 4;
              if( e1 == 6 &amp;&amp; e2 == 8 ) middle = 7;
              if( e1 == 0 &amp;&amp; e2 == 6 ) middle = 3;
              if( e1 == 1 &amp;&amp; e2 == 7 ) middle = 4;
              if( e1 == 2 &amp;&amp; e2 == 8 ) middle = 5;
              if( e1 == 0 &amp;&amp; e2 == 8 ) middle = 4;
              if( e1 == 6 &amp;&amp; e2 == 2 ) middle = 4;

              if((middle != -1) &amp;&amp; !(check[middle])) {       
                        check[middle] = true;
                        points++;                      //adding middle points
                        comboval *= 10;
                        comboval += middle;
              }        

              check[i] = true;
              points++;           // get the point

              comboval*=10;
              comboval += i+1;

              if(points &gt; 3) 
              {
                  combo++; // every iteration over tree points is a valid combo

                // If you want to see they all, beware because printing they all is truly slow:
                    // cout &lt;&lt; "Combination n. " &lt;&lt; combo &lt;&lt; " found: " &lt;&lt; comboval  &lt;&lt; " , points " &lt;&lt; points &lt;&lt; " with " &lt;&lt; deep &lt;&lt; " iterations\n"; 
              }

              if(points &gt; 9)   //Just for sure, emergency shutdown,
              { exit(1); }


              research(points,check,i,comboval,deep+1); /*Recursive, here is the true program!*/

              // numcall++; //DEBUG
          }

       //   cout &lt;&lt; "Ended " &lt;&lt; deep &lt;&lt; " , with " &lt;&lt; numcall &lt;&lt; " subs called\n";   // Only for debug purposes,remove with all the //DEBUG thing

}



int main ()
{ 
    combo = 0; //no initial knows combo
    bool checkerboard[9];
    for( int i=0; i&lt;9; i++) checkerboard[i]=false; //blank initial pattern

    research(0/*no point taken*/,checkerboard,-1/*just a useless value*/,0/*blank combo*/,1/*it's the firs iteration*/); //let's search!

    cout &lt;&lt; "\n"  ;             
    cout &lt;&lt; "And the answer is ... " &lt;&lt; combo &lt;&lt; "\n"; //out

    char ans='\0';
    while(ans=='\0')
    {                   //just waiting
    cin &gt;&gt; ans;
    }

    return 0;
}
I try with combinatorics addition and multiplication principle. I just share my try. if there is any improvement, please suggest.