A367540 Number of discrete implications I : L_n^2 -> L_n defined on the finite chain L_n = {0,1,...n} which satisfy the consequent boundary, i.e., I(x,y) >= y for all x,y in L_n.

1, 8, 205, 17108, 4693632, 4253751084, 12768573248145, 127147160484338304, 4204352991963054866432

Offset: 1

Author

Marc Munar, Nov 22 2023

Keywords

• nonn
• hard
• more

Comments

Number of discrete implications I : L_n^2 -> L_n defined on the finite chain L_n={0,1,...n} satisfying the consequent boundary, i.e., the number of binary functions I : L_n^2 -> L_n such that I is decreasing in the first argument, increasing in the second argument, I(0,0) = I(n,n) = n and I(n,0) = 0 (discrete implication), and I(x,y) >= y for all x,y in L_n (consequent boundary).

The proposed formula is recursive and implemented using dynamic programming using Python. Only the first 9 terms could be obtained. See GitHub link.

Links

• Marc Munar, Python program.
• Marc Munar, S. Massanet and D. Ruiz-Aguilera, On the cardinality of some families of discrete connectives, Information Sciences, Volume 621, 2023, 708-728.
• Marc Munar, S. Massanet and D. Ruiz-Aguilera, DiscreteFuzzyOperators - A Python library for computing with fuzzy operators, Zenodo, Version 1.13.

Crossrefs

Particular case of the enumeration of discrete implications in general, enumerated in A360612.

Programs

Python

See GitHub link

Formula

a(n) = Sum_{x in V_n'} G(v), where V_n' is the set of decreasing vectors v of n components whose entries are taken from L_n, v_1=n and v_i <= n-i+1 for all i in {2,...,n}, and G(v) is defined recursively as

G(v) = det(A(v)) - Sum_{x in V_n(v)\v} G(v), where

A(v)_{i,j} = binomial(n+v_j, n-i+j).

V_n(v) is the set of decreasing vectors x of n components, whose entries are taken from L_n, and x_i <= v_i for all i in {1,...,n}.

G(v) = binomial(n+k-1,k), if v=(k,0,...,0), with v being a vector of n components and 1 <= k <= n.