title: Recursive algorithm for permutations of 4 objects in n spaces
body: <p>I have solved the following algorithm shown below.</p>
  
  <pre><code>public static long park(int n)
  {
     // precondition:  n &gt;= 1
     // postcondition: Return the number of ways to park 3 vehicles,
     //   designated 1, 2 and 3 in n parking spaces, without leaving
     //   any spaces empty. 1 takes one parking space, 2 takes two spaces,
     //   3 takes three spaces. Each vehicle type cannot be distinguished
     //   from others of the same type, ie for n=2, 11 counts only once.
     //   Arrangements are different if their sequences of vehicle types,
     //   listed left to right, are different.
     //   For n=1:  1 is the only valid arrangement, and returns 1
     //   For n=2:  11, 2                     are arrangements and returns 2
     //   For n=3:  111, 12, 21, 3            are arrangements and returns 4
     //   For n=4:  1111,112,121,211,22,13,31 are arrangements and returns 7
  
  
      if(n==1)
          { return 1; }
      else if(n==2)
          { return 2; }
      else if(n==3)
          { return 4; }
      else
          {
          return (park(n-1) + park(n-2) + park(n-3));
          }
  }
  </code></pre>
  
  <p>What I need help on is figuring out a followup problem which is to include empty parking spaces in the permutation. This should be solved recursively.</p>
  
  <pre><code>Let's designate a single empty space as E.
  For n=1:  1,E                and returns 2
  For n=2:  11,2,EE,1E,E1      and returns 5
  For n=3:  111,12,21,3,EEE,EE1,E1E,1EE,11E,1E1,E11,2E,E2     and returns 13
  For n=4:  there are 7 arrangements with no E, and 26 with an E, returns 33
  </code></pre>
  
  <p>I've spent many hours on this. I know how many arrangements there are without an empty space from the above algorithm. So I've been trying to figure out how many arrangements there are with 1 or more empty spaces. The union of these two sets should give me the answer.
  For n, the number of single space permutations with one or more empty spaces is 2^n-1.
  But I don't think this will help me in a recursive solution.</p>
  
  <p>Any guidance would be appreciated.</p>