Number of distinct sequences of fixed length which can be generated using a given set of numbers

Question

I am trying to find different sequences of fixed length which can be generated using the numbers from a given set (distinct elements) such that each element from set should appear in the sequence. Below is my logic:

eg. Let the set consists of S elements, and we have to generate sequences of length K (K >= S)

1) First we have to choose S places out of K and place each element from the set in random order. So, C(K,S)*S!

2) After that, remaining places can be filled from any values from the set. So, the factor

(K-S)^S should be multiplied.

So, overall result is

C(K,S)S!((K-S)^S)

But, I am getting wrong answer. Please help.

PS: C(K,S) : No. of ways selecting S elements out of K elements (K>=S) irrespective of order. Also, ^ : power symbol i.e 2^3 = 8.

Here is my code in python:

# m is the no. of element to select from a set of n elements
# fact is a list containing factorial values i.e. fact[0] = 1, fact[3] = 6& so on. 
def ways(m,n):
    res = fact[n]/fact[n-m+1]*((n-m)**m)
    return res

Answer 1

What you are looking for is the number of surjective functions whose domain is a set of K elements (the K positions that we are filling out in the output sequence) and the image is a set of S elements (your input set). I think this should work:

    static int Count(int K, int S)
    {
        int sum = 0;
        for (int i = 1; i <= S; i++)
        {
            sum += Pow(-1, (S-i)) * Fact(S) / (Fact(i) * Fact(S - i)) * Pow(i, K);
        }
        return sum;
    }

...where Pow and Fact are what you would expect.

Check out this this math.se question.

Here's why your approach won't work. I didn't check the code, just your explanation of the logic behind it, but I'm pretty sure I understand what you're trying to do. Let's take for example K = 4, S = {7,8,9}. Let's examine the sequence 7,8,9,7. It is a unique sequence, but you can get to it by:

• Randomly choosing positions 1,2,3, filling them randomly with 7,8,9 (your step 1), then randomly choosing 7 for the remaining position 4 (your step 2).

• Randomly choosing positions 2,3,4, filling them randomly with 8,9,7 (your step 1), then randomly choosing 7 for the remaining position 1 (your step 2).

By your logic, you will count it both ways, even though it should be counted only once as the end result is the same. And so on...