Ways that N items can have equal values

Question

For a problem, I have N inputs. The only thing that matters is when inputs agree with one another, or disagree. Examples show how to enumerate cases where inputs agree, for N = 3 and 4. For larger N, the possible pairings get considerably more complex. Without explicit enumeration, I'd like a way to count the possibilities.

N = 3: I find 5 possibilities. (Here A, B, C are unique; ⌼s are equal to one another.)

    A B C
    ⌼ ⌼ C
    ⌼ B ⌼
    A ⌼ ⌼
    ⌼ ⌼ ⌼

• 1 way for all different (none equal)
• 3 orderings for 2 alike
• 1 way for all the same.

N = 4: I find 15 possibilities. (Here A, B, C, D are unique; ⌼s are equal to one another; and ⌹s differ from ⌼s but are equal to one another.)

    A B C D
    ⌼ ⌼ C D
    ⌼ B ⌼ D
    ⌼ B C ⌼
    A ⌼ ⌼ D
    A B ⌼ ⌼
    A ⌼ C ⌼
    ⌼ ⌼ ⌹ ⌹
    ⌼ ⌹ ⌼ ⌹
    ⌼ ⌹ ⌹ ⌼
    ⌼ ⌼ ⌼ D
    ⌼ ⌼ C ⌼
    ⌼ B ⌼ ⌼
    A ⌼ ⌼ ⌼
    ⌼ ⌼ ⌼ ⌼

• 1 way for all different
• 6 ways where 2 are equal while the other two are unique]
• 3 ways there are two pairs
• 4 ways there are 3 the same
• 1 way for all alike

N = 5 (without enumeration): I find 52 possibilities:

• 1 way for all different
• 10 ways for a single pair (3 unique)
• 15 ways for 2 pair (1 unique)
• 10 ways for a pair and a triple (none unique)
• 10 ways for a triple (two unique)
• 5 ways for 4 identical (1 unique)
• 1 way for all identical

Answer 1

You might look into set partitions.

This is the number of ways that you can arrange a set, like ABC, into nonempty subsets (and these subsets relate in you case to the fact that the members of this subset represent inputs that are equal).

E.g. for ABC you have five partitions

• A|B|C all different
• A|BC BC in a same group
• B|AC AC in a same group
• C|AB AB in a same group
• ABC all in a same group

The number of partitions are given by the Bell numbers.