Distribute Items

As we need to divide N items into 3 parts satisfying the given conditions, each part can have values lying between [1, N - 2] as a minimum each should get at least 1, at max can get (N-2)(when the other two have minimum values i.e 1). So we will explore all possible ways to divide and satisfying the given conditions,

• Let ‘count’, be the total number of possible ways to distribute N items (initially 0)
• Fixing the first part value (i), using the outer loop, i.e from 1 to N - 2
  • Similarly choosing the second value(j) i.e from 1 to N - 2.
  • Now we will calculate the third value(k) i.e equals to N - (i + j)
  • We will increment our count value by 1 if all three values(i, j, k) satisfy the given conditions i.e (all three i,j,k should be > 0 and one should be strictly greater than the other two).
• Return count

Using permutation & combination we can find the total number of ways to distribute the N items to 3 persons i.e(distribute N identical objects into R distinct groups = (N + R - 1)C(R - 1) where any group can get any number of items including 0),

Using the above formula we can also find that,

The total number of ways to distribute N identical items into R distinct groups such that each group should get at least 1 item = (N - 1)C(R-1) 

Given R = 3,

• Let totalWays be the total number of possible ways to distribute N items satisfying the given conditions, totalWays = (N - 1)C(R-1) = (N - 1)C2 =(N - 1) * (N - 2) / 2
• Now we will find the total number of ways that violate the given conditions lets says those be equals to count, there are only two possible such cases
  • When all three persons get the same number of items, this could be possible only if N is divisible by 3, for ex, N = 9 and the distribution is (3,3,3). Increment count by 1 if N % 3 == 0.
  • When exactly any two of them get the same number of items and the third person gets fewer items than the other two (for ex, N = 7 and the distribution is (3, 3, 1) for each such case there are three possible ways i.e (1,3,3), (3,1,3),(3, 3, 1). So count += 3 for such cases.
• To find these we will be fixing the value(i) for two equal times i.e iterating from (1 to n) and then finding the third value(k) = N - (2 * i). If this distribution i.e (i, i, k) satisfies the given conditions simply do count += 3.
• 3.Return (totalWays - count).

Using permutation & combination we can find the total number of ways to distribute the N items to 3 persons i.e(distribute N identical objects into R distinct groups = N + R - 1CR - 1 where any group can get any number of items including 0),

Using the above formula we can also find that,

The total number of ways to distribute N identical items into R distinct groups such that each group should get at least 1 item = N - 1CR-1 

Given R = 3,

• Let totalWays be the total number of possible ways to distribute N items satisfying the given conditions, totalWays = N - 1CR-1 = N - 1C2 =(N - 1) (N - 2)2
• Now we will find the total number of ways that violate the given conditions lets says those be equals to count, there are only two possible such cases
  • When all three persons get the same number of items, this could be possible only if N is divisible by 3, forex, N = 9 and the distribution is (3,3,3). Increment count by 1 if N % 3 == 0.
  • When exactly any two of them get the same number of items and the third person gets fewer items than the other two (forex, N = 7 and the distribution is (3, 3, 1) for each such case there are three possible ways i.e (1,3,3), (3,1,3),(3, 3, 1). So count += 3 for such cases.

To find these let’s solve some equations,

The given case can be represented as (x, x, y) x + x + y = N 2x + y = N,

Now y is the third value should be greater than 0, the maximum value of x will be possible when y is minimum and minimum y = 1,

y > 0 ,  N - 2x > 0,  x<N2

Also, y should be less than x

y < x

N - 2x < x

x > N3

Thus total such ways of selecting (x, y) pair equals = 3 *((N- 1)2 - (N - 3)3) 

Add this to count.

• Return (totalWays - count).