0
$\begingroup$

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
$\endgroup$
2
  • 2
    $\begingroup$ It is truly unclear what you mean by "can have some or no equal values when order matters." Although a couple of examples helps, could you please specify exactly what you're trying to count? $\endgroup$
    – whuber
    Oct 5, 2021 at 16:24
  • $\begingroup$ Thanks for your comment @whuber. I think I lack the statistical language to specify things as clearly as some might. An explanatory note: this is for machine learning training, and I need to know the ways there can be agreement between N inputs. It matters how many inputs agree, and how they are matched. Counting the combinations is important so I can know how large an N is feasible for the work. Description edited above. $\endgroup$
    – user3897315
    Oct 5, 2021 at 16:50

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you @Sextus Empiricus. Exactly what I needed. Slowly I had been working my way to the 52 partitions for N = 5, and the Wikipedia page showed me what I had been missing. The numbers are large for N = 8 (most I am likely to need to consider), but workable. $\endgroup$
    – user3897315
    Oct 5, 2021 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.