Bell Numbers Algorithm

Question

I am trying to write an algorithm to determine the number of ways in which n numbers can be ordered. For example, two numbers say that a and b can be ordered in three ways.

Similarly, 3 rooms can be arranged in 13 ways.

I found out that I can solve the problem using dynamic programming. And that’s what I think, to have layers that represent different orders. Ex. a > bhave two layers, and a = b- one layer, etc. So that I can use it for subsequent purposes, as is done in dynamic programming. But I cannot write a repetition relation for the same. Can someone tell me how I can write this?

Answer 1

Suppose f (n, k) = the number of possible paths using k inequality (and therefore nk-1 equality), therefore: suppose you have the number n-1, now you want to add another number and calculate f (n, k), then we have two possibilities:

1) There are (k-1) inequalities in those (n-1) numbers, and there are (k + 1) (f (n-1, k-1)) ways to add an n-dimensional number so a new inequality is added.

2) These (n-1) numbers have k inequalities, and there are (k + 1) (f (n-1, k)) ways to add the nth number without additional inequality.

f(n,k) = (k+1)(f(n-1,k-1) + f(n-1,k))

and what you want is their sum (from zero to n-1), the Bellow code is in C # (just checked for simple cases), in fact we just calculate the number of possible ways that do not generate all the paths.

class EqualInequalPermutation
{
    public int OrderingsNumber(int n)
    {
        int[][] f = new int[n+1][];
        for (int i = 0; i < n+1; i++)
        {
            f[i] = new int[n];
            for (int j = 0; j < n; j++)
                f[i][j] = 0;
        }
        f[1][0] = 1;
        int factorial = 1;
        for (int i = 1; i <= n; i++)
        {
            f[i][0] = 1;
            factorial *= i;
            f[i][i - 1] = factorial;
            for (int k = 1; k < n; k++)
            {
                f[i][k] = (k + 1) * (f[i - 1][k - 1] + f[i - 1][k]);
            }
        }
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            answer += f[n][i];
        }
        return answer;
    }
}

Answer 2

, On-Line Encyclopedia of Integer Sequences - . , . , . . , , , - . 1,1,3,13 , , , " , n , ". , . Mathematica ( ):

f[0] = 1
f[1] = 1
f[n_] := f[n] = Sum[ Binomial[n,k] * f[n-k], {k,1,n}]   (* memoizes the values *)

, .

, , OEIS !

Answer 3

, ant .

, .

, n! (), ( n-), 3

3! + 2 * (3 2) + (3 3) = 13

Answer 4

# , :

static void Main(string[] args)
{
    if (args.Length < 1)
    {
        Console.WriteLine("Missing argument - the number of items");
        return;
    }
    int n;
    if (!int.TryParse(args[0], out n))
    {
        Console.WriteLine("Could not parse number of items");
        return;
    }
    if (n < 0)
    {
        Console.WriteLine("Number of items must not be negative");
        return;
    }
    var count = GetOrderings(n);
    Console.WriteLine("Total: {0}", count);
}

private static int GetOrderings(int n)
{
    var items = Enumerable.Range(0, n).Select(i => (char)('a' + i)).ToList();
    // Produce distinct orderings of the input items
    return GetOrderings(new List<char>(), items);
}

private static int GetOrderings(List<char> current, List<char> items)
{
    // If we have a complete permutation in current, produce the possible arrangements of signs between them
    if (items.Count == 0) return GetSigns(new List<char>(), current, 0);
    var result = 0;
    for (var i = 0; i < items.Count; i++)
    {
        // nextCurrent = current + i'th element of items
        var nextCurrent = new List<char>(current) { items[i] };
        // nextItems = items excluding the i'th element
        var nextItems = new List<char>(items.Where((c, n) => n != i));
        result += GetOrderings(nextCurrent, nextItems);
    }
    return result;
}

private static int GetSigns(List<char> signs, List<char> items, int n)
{
    if (signs.Count >= items.Count - 1)
    {
        // Once we have sufficient signs, write out the items interleaved with them
        var str = string.Empty;
        for (var i = 0; i < items.Count; i++)
        {
            if (i > 0) str += signs[i - 1];
            str += items[i];
        }
        Console.WriteLine(str);
        return 1;
    }
    var result = GetSigns(new List<char>(signs) { '<' }, items, n + 1);
    // To prevent duplicate orderings, only allow "=" between two items if they are in lexicographic order
    // (i.e. allow "a = b" but not "b = a")
    if (items[n] >= items[n + 1]) return result;
    return result + GetSigns(new List<char>(signs) { '=' }, items, n + 1);
}

( n = 3):

a<b<c
a<b=c
a=b<c
a=b=c
a<c<b
a=c<b
b<a<c
b<a=c
b<c<a
b=c<a
c<a<b
c<a=b
c<b<a
Total: 13