CODEWITHSUNDEEP
algorithm
Parimal
Parimal

Reputation: 11

Can this problem be solved using combinatorics?

Given two numbers N and M, find the number of arrays of length N which satisfy the following conditions -

  1. All elements must be between 1 and M, inclusive
  2. First and last element of the array must be same
  3. No two consecutive elements should be similar

For example, let

N = 3, M = 3

Possible arrays are

[1, 2, 1]

[1, 3, 1]

[2, 1, 2]

[2, 3, 2]

[3, 1, 3]

[3, 2, 2]

Hence output would be 6.

Range of N and M are from 3 to 10^18, inclusive.

Can I get any hints on how to approach this problem? I tried finding a mathematical formula but it gave wrong answers for N > 4.

My approach ->

For N = 3, first and last places are fixed, and we can place M - 1 elements in the middle. So count = M * (M - 1)

For N = 4, the formula changes to (M - 1) * (M - 2) * M

For N > 5 I came up with a generalized formula but it was giving wrong answer.

Upvotes: 1

Views: 46

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Another way to define the problem is to find the number of ways to color an N−1 node cycle with M colors such that no two adjacent nodes have the same color. We can count colorings using the deletion-contraction recurrence. Let C(n, k) be the number of ways to color an n-node cycle with k colors and P(n, k) be the number of ways to color an n-node path with k colors. We get recurrences

C(2, k) = k (k−1),    as you observed;
C(n, k) = k P(n, k) − C(n−1, k),
    since an n-node cycle with an edge deleted is an n-node path,
    and an n-node cycle with an edge contracted is an (n−1)-node cycle.

P(1, k) = k,   obviously;
P(n, k) = k P(n−1, k) − P(n−1, k)
        = (k−1) P(n−1, k)
     since an n-node path with the first or last edge deleted
     is an (n−1)-node path with an isolated node
     that can be colored independently in one of k ways,
     and an n-node path with an edge contracted is an (n−1)-node path.

We can write a closed form formula for P(n, k) and get a new recurrence for C(n, k):

P(n, k) = k (k−1)^(n−1)
C(n, k) = k (k−1)^(n−1) − C(n−1, k).

This recurrence can be turned into a linear-time algorithm, or if you like, if we expand out C(n, k), we can express it as an alternating sum

           n      (n−i)                     (n-2)
C(n, k) = Sum (−1)      k (k−1)^(i−1) + (−1)      k (k−1)
          i=3

and then ask WolframAlpha for a closed form.

Upvotes: 1

Related Questions