Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Combinations.

Julius Hamilton (Jan 12 2025 at 02:24):

Imagine there are 2 options for 3 independent things.

You could have $(a, a, a)$, $(a, b, a)$, $(b, b, a)$, etc.

I claim there are $2 \times 2 \times 2 = 2^3 = 8$ possible versions of such a choice.

For $8$ things, I claim there are $8! = 40320$ ways to put them in an order, because there are $8$ choices for the first position, $7$ for the second, etc.

Some of these orderings appear methodical. For example:

$(a, a, a), a, a, b), (a, b, a), (a, b, b),$
$(b, a, a), (b, a, b), (b, b, a), (b, b, b)$ is an order that seems like it can be described by a rule. But other orders may appear random.

What theory analyzes which orderings are describable by a rule of some kind? Of the number of possible orderings, is there a number of orderings which are the result of a rule?

Peva Blanchard (Jan 12 2025 at 07:37):

It is not specifically about orderings, but algorithmic information theory deals with this kind of question. Especially, the Kolmogorov complexity of a binary sequence $x = 1100101001$ is defined, roughly speaking, as the length $K(x)$ of the shortest computer program that can generate that sequence.

The sequence $x$ is said to be random when $K(x)$ is about the same size as the sequence $x$ itself. Intuitively, this says that there is not a better computer program than the one that just prints out the sequence.

Peva Blanchard (Jan 12 2025 at 07:40):

By the way, I don't follow the step between your first example with three things, and the second one with eight things. In the second case, if you have an infinite supply of both options $a$ and $b$, you should have $2^8$ sequences.