Recursive algorithm for permutations of 4 objects in n spaces

I have solved the following algorithm shown below.

public static long park(int n)
{
   // precondition:  n >= 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));
        }
}

What I need help on is figuring o开发者_如何学Gout a followup problem which is to include empty parking spaces in the permutation. This should be solved recursively.

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

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.

Any guidance would be appreciated.

---

I think this works:

public static long park(int n)
{
    if(n==1)
        { return 2; }
    else if(n==2)
        { return 5; }
    else if(n==3)
        { return 13; }
    else
        {
        return (park(n-1) + park(n-1) + park(n-2) + park(n-3));
        }
}

---

To make it simple, i will explain where is going wrong in N < 3 using recursive.

For one space, there is two situation, E and 1, so when n = 1, it should be 2.

When it is 2, it should return 1 + park(1) + park(1), because 2 is 2, 1E, E1,11, It is still ok when it is two.

When it is 3, it should return 1 + park(2) + park(1) + park(1) + park(2) + park(1) + park(1) + park(1) but you can see, in Park(1) + Park(2) and Park(2) + Park(1) will count some situation more than once. You have to remove all these repeat.

I don't think this is a good way to deal with this problem.

Math will be easier.

Consider empty slots is N1, 1 slot car is N2, 2 slots car is N3, 3 slots car is N4.

N1 + N2 + 2 * N3 + 3 * N4 = N

I think you can figure rest of it out by yourself.