A365447 Number of nonempty choice functions on a set of n alternatives

1, 3, 189, 26254935, 392654823152462915625, 28032331438680332717218961936012273854096893310546875

Offset

1,2

Comments

Number of choice functions f:2^A\{{}}->2^A\{{}} where A is an n-element set of variants such that f(X) is a nonempty subset of any nonempty X in 2^A (here 2^A denotes the power set of A).

References

F. Aleskerov, D. Bouyssou, and B. Monjardet, Utility, Maximization, Choice and Preference, Springer, 2007, pp. 28-31.

Links

Table of n, a(n) for n=1..6.

Dmitry I. Ignatov, A Note on Counting Basic Choice Functions with Formal Concept Analysis, FCA4AI@IJCAI 2023, 47-56.

Formula

a(n) = Product_{k=1..n} (2^k-1)^binomial(n, k).

log_2 a(n) = n*2^(n-1) + O(2^n/sqrt(n)).

Example

a(1) = 1 since 2^{1} = {{}, {1}} and there exists only one function f:2^{1}/{{}}->2^{1}/{{}} satisfying f(X) is a nonempty subset of any nonempty X in 2^A, i.e., f({1})={1}.

Mathematica

a[n_] := Product[(2^k - 1)^Binomial[n, k], {k, 1, n}]; Array[a, 6] (* Amiram Eldar, Oct 03 2023 *)

Crossrefs

Cf. A061301, A229333.

Sequence in context: A058856 A158469 A261000 * A032594 A159658 A257038

Adjacent sequences: A365444 A365445 A365446 * A365448 A365449 A365450

Keyword

nonn,easy

Author

Dmitry I. Ignatov, Oct 03 2023

Status

approved