CODEWITHSUNDEEP
algorithmcombinatorics
sdrtg ghytui
sdrtg ghytui

Reputation: 433

How to count the number of different sequences possible?

Lets consider all matrices with N rows (numbered 1 through N) and M columns (numbered 1 through M) containing only integers between 0 and K−1 (inclusive). For each such matrix A, let's form a sequence L[1],L[2],…,L[N+M]

For each 'i' (1≤i≤N), L[i] is the maximum of all elements in the i-th row of A. For each 'i' (1≤i≤M), L[N+i] is the maximum of all elements in the i-th column of A. Find the number of different sequences formed this way. My approach is simple brute-force.

Example:- N=2;M=2;K=2

Answer:-10

All 16 different possible matrices are as follows:-

[0, 0]

[0, 0] = (0, 0, 0, 0) (sequence generated)

[0, 0]

[0, 1] = (0, 1, 0, 1)

[0, 0]

[1, 0] = (0, 1, 1, 0)

[0, 1]

[0, 0] = (1, 0, 0, 1)

[1, 0]

[0, 0] = (1, 0, 1, 0)

[1, 0]

[1, 0] = (1, 1, 1, 0)

[1, 1]

[0, 0] = (1, 0, 1, 1)

[0, 0]

[1, 1] = (0, 1, 1, 1)

[0, 1]

[0, 1] = (1, 1, 0, 1)

[1, 0]

[0, 0] = (1, 0, 1, 0)

[0, 1]

[1, 0] = (1, 1, 1, 1)

[1, 1]

[1, 0] = (1, 1, 1, 1)

[1, 1]

[0, 1] = (1, 1, 1, 1)

[1, 1]

[0, 1] = (1, 1, 1, 1)

[1, 0]

[1, 1] = (1, 1, 1, 1)

[1, 1]

[1, 1] = (1, 1, 1, 1)

Upvotes: 1

Views: 502

Answers (1)

Ingix
Ingix

Reputation: 111

I'll give a series of hints:

For a given matrix A and the associated L, find a relation between the maximum of L[1],...,L[N] (the row maximums) and the maximum of L[N+1],...,L[N+M] (the column maximums).

Next, try to prove that any L-sequence with integers from 0 to K-1 that fulfills these conditions can actually be obtained by some matrix A.

Finally, count those sequences.

Upvotes: 1

Related Questions