Does changing the order make a different outcome?

Begin with two selections from four labels without replacement. Predict the ordered count, then switch to unordered. Find the pair of ordered outcomes represented by one unordered selection. The stage names its labels A through H; the examples and Python use numbers 1 through 8 for the same distinct items.

Intuition: count what the experiment distinguishes

Giving a first prize to label 1 and a second prize to label 2 differs from giving the prizes in the reverse order. Choosing a two-person team from those labels ignores that order. The same labels therefore support different outcome spaces depending on the experiment’s question.

Replacement asks a separate question: can a label be used again? Keeping these two choices separate prevents a correct counting formula from being used for the wrong experiment.

Definition

Let $n$ be the number of distinct labels and $k$ the number selected, both integers. For ordered selection without replacement, there are

outcomes when $0\le k\le n$. Ignoring order gives the combination count $\binom nk=n!/(k!(n-k)!)$. The factorial convention is $0!=1$.

With replacement, ordered sequences number $n^k$. Unordered selections are multisets, which record how many times each label appears; for $n\ge1$ they number $\binom{n+k-1}{k}$. These are counts, not automatically a uniform probability model.

Mechanics: classify before calculating

The stage’s state records $n$, $k$, order, and replacement. Its outcome representation and count follow those choices. Read the derivation trace from the same state: identify available labels for each slot, multiply choices, and account for ignored order when appropriate.

The interactive range is $2\le n\le8$, $0\le k\le4$. It includes $k>n$ without replacement so you can see an impossible selection. Changing a control does not authorize an impossible draw or a probability with zero total outcomes. Reset returns to $n=4$, $k=2$, without replacement.

Derivation: multiplication and grouping

Without replacement, the first slot has $n$ choices, the next has $n-1$, and so on. Multiply because each partial selection branches into that many next choices. Every unordered set of $k$ distinct labels has exactly $k!$ orderings. Dividing the ordered count by $k!$ therefore gives combinations.

With replacement, every slot has $n$ choices, giving $n^k$. To count unordered multisets, distribute $k$ indistinguishable marks among $n$ labelled boxes. A row of $k$ marks and $n-1$ separators encodes the counts. Choosing the mark positions gives $\binom{n+k-1}{k}$.

Repeated labels make the number of orderings vary by multiset. If a multiset has counts $c_1,\ldots,c_n$ summing to $k$, its number of ordered preimages is $k!/(c_1!\cdots c_n!)$. Under independent uniform draws its probability is that number divided by $n^k$; this is why “ignore order” does not automatically mean “make all unordered results uniform.”

Worked examples

For $n=4$, $k=2$, without replacement, the ordered total is $4\times3=12$. Each pair occurs in two orders, so there are $12/2=6$ unordered pairs. The event “select labels 1 and 2” has probability $2/12=1/6$ under uniform ordered draws; equivalently it is one of six equally likely unordered pairs.

With replacement, there are $4^2=16$ sequences and $\binom52=10$ multisets. Four multisets repeat a label; six contain distinct labels. The result $\{1,1\}$ has one preimage and mass $1/16$. The result $\{1,2\}$ has two preimages and mass $1/8$. Assigning $1/10$ to each describes a different experiment: direct uniform selection of multisets.

Executable reference code

The Python program uses standard-library formulas and independently enumerates outcomes with itertools to check them throughout the stage’s small parameter range. It groups replacement sequences by sorted tuples and assigns exact Fraction masses from preimage counts. NumPy checks the same finite grouping using rows of sequences, row sorting, and occurrence counts; no random sampling is needed.

"""Count outcomes, then justify their masses; never assume multisets are uniform.

Enumeration is bounded to the stage's n = 2..8, k = 0..4. Formulas return exact
integers; probabilities below use Fraction, not floating-point count ratios.
"""
from collections import Counter
from fractions import Fraction as F
from itertools import combinations, combinations_with_replacement, permutations, product
from math import comb, perm


def validate(n, k):
    if type(n) is not int or type(k) is not int or not 2 <= n <= 8 or not 0 <= k <= 4:
        raise ValueError("This explorer requires integer n = 2..8 and k = 0..4")


def selection_count(n, k, ordered, replacement):
    validate(n, k)
    if replacement:
        return n ** k if ordered else comb(n + k - 1, k)
    if k > n:
        return 0
    return perm(n, k) if ordered else comb(n, k)


def enumerate_selections(n, k, ordered, replacement):
    validate(n, k)
    labels = range(1, n + 1)
    if replacement:
        return tuple(product(labels, repeat=k) if ordered else combinations_with_replacement(labels, k))
    return tuple(permutations(labels, k) if ordered else combinations(labels, k))


def multiset_masses(n, k):
    sequences = enumerate_selections(n, k, ordered=True, replacement=True)
    preimages = Counter(tuple(sorted(row)) for row in sequences)
    return {multiset: F(count, len(sequences)) for multiset, count in preimages.items()}


def main():
    assert selection_count(4, 2, True, False) == 12
    assert selection_count(4, 2, False, False) == 6
    assert selection_count(4, 2, True, True) == 16
    assert selection_count(4, 2, False, True) == 10
    assert selection_count(2, 3, True, False) == 0
    assert selection_count(2, 3, False, False) == 0
    for n in range(2, 9):
        for k in range(5):
            for ordered, replacement in product((False, True), repeat=2):
                outcomes = enumerate_selections(n, k, ordered, replacement)
                assert len(outcomes) == selection_count(n, k, ordered, replacement)
                if k == 0:
                    assert outcomes == ((),)
            masses = multiset_masses(n, k)
            assert sum(masses.values(), F(0)) == 1
    for n, k in ((1, 2), (9, 2), (4, -1), (4, 5), (4.0, 2), (4, True)):
        try:
            selection_count(n, k, True, False)
        except ValueError:
            pass
        else:
            raise AssertionError("Out-of-range or noninteger input was accepted")
    pairs = enumerate_selections(4, 2, True, False)
    target_mass = F(sum(set(row) == {1, 2} for row in pairs), len(pairs))
    assert target_mass == F(1, 6)
    masses = multiset_masses(4, 2)
    assert masses[(1, 1)] == F(1, 16)
    assert masses[(1, 2)] == F(1, 8)
    print("Two of four, without replacement: ordered 12, unordered 6; P({1,2}) =", target_mass)
    print("With replacement: ordered 16, unordered 10; exact induced multiset masses:", masses)
    print("k = 0: one empty outcome; k > n without replacement: no sampling space")


if __name__ == "__main__":
    main()

"""Group bounded ordered selections with NumPy, keeping multiplicities visible.

Counts in this n = 2..8, k = 0..4 explorer fit fixed-width integers. Derived
floating-point probabilities use absolute tolerance 1e-12, relative tolerance 0.
"""
from fractions import Fraction as F
from itertools import permutations, product
from math import comb, perm
import numpy as np

ATOL = 1e-12


def grouped_selections(n, k, replacement):
    if type(n) is not int or type(k) is not int or not 2 <= n <= 8 or not 0 <= k <= 4:
        raise ValueError("Use integer n = 2..8 and k = 0..4")
    labels = range(1, n + 1)
    sequences = tuple(product(labels, repeat=k) if replacement else permutations(labels, k))
    rows = np.asarray(sequences, dtype=np.int64).reshape(len(sequences), k)
    if len(rows) == 0:
        return rows, np.empty((0, k), dtype=np.int64), np.empty(0, dtype=np.int64), None
    # Sorting removes order; counts retain how many ordered rows each result had.
    unordered, multiplicities = np.unique(np.sort(rows, axis=1), axis=0, return_counts=True)
    masses = multiplicities / len(rows)
    return rows, unordered, multiplicities, masses


def main():
    for n in range(2, 9):
        for k in range(5):
            for replacement in (False, True):
                rows, unordered, counts, masses = grouped_selections(n, k, replacement)
                ordered_count = n ** k if replacement else (perm(n, k) if k <= n else 0)
                unordered_count = comb(n + k - 1, k) if replacement else (comb(n, k) if k <= n else 0)
                assert len(rows) == ordered_count and len(unordered) == unordered_count
                if masses is not None:
                    assert counts.sum() == ordered_count
                    np.testing.assert_allclose(masses.sum(), 1.0, rtol=0, atol=ATOL)
                if k == 0:
                    assert rows.shape == unordered.shape == (1, 0) and counts.tolist() == [1]
    rows, pairs, counts, masses = grouped_selections(4, 2, False)
    assert len(rows) == 12 and len(pairs) == 6 and np.all(counts == 2)
    np.testing.assert_allclose(masses, float(F(1, 6)), rtol=0, atol=ATOL)
    rows_r, multisets, counts_r, masses_r = grouped_selections(4, 2, True)
    assert len(rows_r) == 16 and len(multisets) == 10
    repeated = np.all(multisets == [1, 1], axis=1)
    distinct = np.all(multisets == [1, 2], axis=1)
    np.testing.assert_allclose(masses_r[repeated], float(F(1, 16)), rtol=0, atol=ATOL)
    np.testing.assert_allclose(masses_r[distinct], float(F(1, 8)), rtol=0, atol=ATOL)
    assert grouped_selections(2, 3, False)[3] is None
    for n, k in ((1, 2), (9, 2), (4, -1), (4, 5), (4.0, 2)):
        try:
            grouped_selections(n, k, False)
        except ValueError:
            pass
        else:
            raise AssertionError("Invalid explorer inputs were accepted")
    print("Without replacement: 12 sequences, 6 pairs; probabilities ≈", masses)
    print("With replacement: 16 sequences, 10 multisets")
    for row, count, mass in zip(multisets, counts_r, masses_r):
        print(tuple(row), ": ordered preimages", count, "; probability ≈", mass)
    print("Impossible without-replacement selection: no normalized masses (None)")


if __name__ == "__main__":
    main()

Explore

Set $k=0$ in all four modes. There is exactly one empty selection, including one empty ordered tuple. Under this valid experiment its probability is one. Then set $n=2$, $k=3$ without replacement: there are zero selections, so a normalized uniform selection model cannot be formed. Turn replacement on and observe that ordered choices become possible again.

Predict counts for $n=5$, $k=3$ without replacement: $5\times4\times3=60$ ordered and $60/6=10$ unordered. Return to two-of-four with replacement and inspect which unordered results represent more sequences.

Common mistakes and counterexamples

Dividing every ordered replacement count by $k!$ fails when labels repeat. For two-of-four it gives $16/2=8$, but there are ten multisets. Using $n^k$ without replacement also overcounts repeated-label sequences that the experiment excludes.

An impossible selection is not an empty selection. One has no outcome; the other has the single empty outcome. Do not evaluate a factorial with a negative argument to extend the without-replacement formula past $k=n$; report count zero and the unavailable sampling model.

Numerical considerations

Counts are exact integers and probabilities are exact rational ratios in the standard-library reference. The bounded explorer permits enumeration, but $n^k$ grows quickly outside that range. A finite display must never be mistaken for an exhaustive list in a much larger experiment.

Python integers grow as needed. NumPy integer arrays have fixed-width types, so a larger counting implementation must consider overflow before arithmetic. Here the bounded counts fit exactly; division into floating-point masses is approximate, checked with absolute tolerance $10^{-12}$ and zero relative tolerance. The reference does not claim a rounded array sum is an exact proof of normalization.

Engineering and ML connections

Sampling a minibatch without replacement differs from independently choosing training examples with replacement. Sequence order matters for temporal input, whereas a selected subset may ignore it. Counting helps estimate search-space size and memory requirements, but probabilities still depend on the sampling rule. Grouping randomized outputs can introduce unequal category probabilities even when the underlying draws are uniform.

Exercises

Summary and checkpoints

Choose an outcome space by specifying order and replacement. Multiply successive choices; divide by equal-size ordering groups only when justified. Check that you can explain 12 versus 6, 16 versus 10, the nonuniform replacement multisets, and the difference between one empty outcome and no possible outcome.