Q: Permutations of multiple, non-equal shapes on 2-Dimensional grid

Situation:

The following components exist for this problem:

• Two-dimensional, rectangular grid ("r" rows by "c" columns)


• One or more shapes: here a shape is defined as a straight line that is one segment by "L" adjacent segments in length. Each segment is equivalent in size to one cell of the grid.

Objective:

Algebraically calculate the total number of unique ways (permutations) that all shapes may be arranged on the grid simultaneously.

Ultimately, I will be using this function in either R or JavaScript; however, this is primarily a math/algebra question. I am comfortable converting any solutions provided into the appropriate language, as long as I understand how the solution works. All thoughts/languages are welcome and appreciated.

Criteria:

• All shapes must fit on the grid at once (and entirely).


• Shapes may not over lap. Only one segment may occupy a grid cell at a time.


• Shapes may be positioned vertically.


• Shapes may be positioned horizontally.


• Shapes may NOT be positioned diagonally.


• Shapes must remain intact (i.e., a 2-segment shape may not be split into two, one-segment shapes)

Background:

If each shape has a single segment (i.e., occupies only one cell of the grid) then factorials may be used:

Let x = r * c (the number of cells in the grid)
Let n = the number of single-segment shapes to fit on the grid

P(x,n) = x! / (x-n)!

Therefore, the permutations for two, single-segment shapes on a grid of three rows and three columns may be calculated as:

P((3*3),2) = 9!/(9-2)! = 72

Relatively simple and elegant.

Calculating permutations for a single shape having a length of L >=1 (requiring L <= r and L <= c) the process is somewhat less elegant but still relatively simple:

P(r,c,L) = r*(c-(L-1)) + c*(r-(L-1))  

[I realize this can likely be simplified algebraically but it is clearer for me to illustrate the process this way]

Therefore, the permutations for a single, two-segment shape on a grid of three rows and three columns may be calculated as:

P(3,3,2) = 3*(3-(2-1)) + 3*(3-(2-1)) = 12

The next step is to introduce additional shapes of varying lengths into the equation.

For example, how many permutations exist for positioning a two-segment shape and a three-segment shape simultaneously on a grid of four rows and four columns? This is where I am stuck and feel I may be searching for an algebraic solution that does not exist or that is not possible.

(Incidentally, for testing purposes, I physically tested the example above and found 251 possible unique positions)

Graphic illustration of the problem:

Question:

Can this problem be solved algebraically, or does the problem require iterative functions to actually find all possible positions before providing a count of the number of permutations?

If the problem is solvable algebraically, can anyone provide direction on how this would be accomplished, or recommend a publicly accessible resource that I could use to learn how to solve this problem.