Arrangements with the following conditions

Question

Given a matrix AxB with comprising of integers >=0. The sum of each column of the matrix should be non decreasing on moving from left to right. Also the sum of B^th column (last column) is less than or equal to A.

Find the number of distinct matrices of such type for a given A and B.

I tried to solve it using recursion and memoization as follows-

The function solve() is-

ll solve(ll i,ll curlevel)
{
 if(dp[i][curlevel]!=-1)
    return dp[i][curlevel];
 if(i<0)
    return dp[i][curlevel]=0;
 if(curlevel==B)
    return dp[i][curlevel]=test(i,c);
 if(curlevel>B)
    return dp[i][curlevel]=0;
 ll ans=0;
 for(ll k=i;k>=0;k--)
 {
     ans+= test(i,A)* solve(k, curlevel+1);
 }
 return dp[i][curlevel]=ans;
}

The function test is defined as follows- (It calculates the no of ways a sum ='sum' can occur as a sum of distinct non-negative numbers='places')

ll test(ll sum,ll places)
{
 if(mem[sum][places] != -1)
    return mem[sum][places];
 if(sum==0)
    return mem[sum][places]=1;
 if(places==0)
    return mem[sum][places]=0;
 ll val=0;
 for(ll i=0;i<=sum;i++)
 {
    val+=test(sum-i,places-1);
 }
 return mem[sum][places]=val;
}

This method however is too slow.

Is there a faster way to do this?(Maybe a better combinatorics approach)

Answer 1

You have to precalculate Partitions array - numbers of integer partitions of A into A non-negative parts (including zeros) and taking part order into account (i.e. counting both 0 0 1 and 0 1 0 etc).

Edit: Partitions(k) = C(A + k - 1, A - 1)
Example for A = 4
Partitions[4] = C(7,3)=7!/(4!3!)=35
whole array: Partitions = {1,4,10,20,35}
To calculate Partitions, use table - rotated Pascal triangle

1  1  1  1  1 
1  2  3  4  5  //sum of 1st row upto ith element
1  3  6  10 15  //sum of 2st row
1  4  10 20 35   //sum of upper row

for A = 1000 you need about 1000*sizeof(int64) memory (one or two rows) and about 10^6 modulo additions. If you need to make calculations for many A values, just store the whole table (8 MBytes)

Then use this formula: //corrected

S(columns, minsum) = Partitions[k] * Sum[k=minsum..A]{ S(columns - 1, k) }
S(1,k) = Partitions[k]
Result = Sum[k=0..A] { S[B,k] }

Answer 2

Starting from the last cell of the last column, if that cell has the value A, then all the other cells in the last column must be 0, so in that case the last column has 1 possible arrangement.

If the last cell has the value A-1, then the cell next to it in the same column can be 0 or 1, so there is one arrangement in which the last column sums to A-1 and A-1 arrangements in which the column sums to A.

In general, the recursive function is:

NumberOfArrangementsOfColumn( cells_remaining, value_remaining ){
    if( value_remaining == 0 ) return 1;
    if( cells_remaining == 1 ) return value_remaining + 1;
    int total = 0;
    for( int sub_value = 1; sub_value <= value_remaining; sub_value++ ){
        total += 
          NumberOfArrangementsOfColumn( cells_remaining - 1, sub_value );
    }
    return total;
}

This function will determine the number of arrangements for the last column. You then need to create another recursive function for computing each of the remaining columns starting with the next to last column etc. for each possible value.