# ON THE DEFINITION AND PROPERTIES OF PARTITIONS IN A FUZZY FRAMEWORK

Bernadette Bouchon-Meunier

► To cite this version:

Bernadette Bouchon-Meunier. ON THE DEFINITION AND PROPERTIES OF PARTITIONS IN A FUZZY FRAMEWORK. Bulletin pour les sous-ensembles flous et leurs applications, 1983, 17, pp.48-57. hal-04579455

HAL Id: hal-04579455

https://hal.science/hal-04579455

Submitted on 17 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
ON THE DEFINITION AND PROPERTIES OF PARTITIONS

IN A FUZZY FRAMEWORK

Bernadette BOUCHON*

ABSTRACT

For a given finite universe of discourse, we define a fuzzy partition as a family of fuzzy subsets of the universe, every element belonging to several classes of the partition with various grades of membership. This concept is particularly useful in the case where a given population is studied through imprecise factors, depending on the reliability of personal appreciations, the accuracy of measures of the use of subjective criteria. In this paper, we characterise several types of fuzzy partitions ; we evaluate their fuzziness by using infor- mational measures and comparing them with associated ordinary partitions of the universe. We also give combinatorial results concerning the number of such fuzzy partitions.

<footnote>CNRS, Groupe de Recherche C.F. PICARD, Université Paris VI
Tour 45, 4 place Jussieu, 75230 PARIS Cédex 05, France

and Departamento de Estatística e Matemática Aplicada,
Universidade Federal do Ceará, 60 000 Fortaleza-Ceára
(From June to August, 1983).</footnote>
ON THE DEFINITION AND PROPERTIES OF PARTITIONS

IN A FUZZY FRAMEWORK

Bernadette BOUCHON*

ABSTRACT

For a given finite universe of discourse, we define a fuzzy partition as a family of fuzzy subsets of the universe, every element belonging to several classes of the partition with various grades of membership. This concept is particularly useful in the case where a given population is studied through imprecise factors, depending on the reliability of personal appreciations, the accuracy of measures of the use of subjective criteria. In this paper, we characterise several types of fuzzy partitions ; we evaluate their fuzziness by using infor- mational measures and comparing them with associated ordinary partitions of the universe. We also give combinatorial results concerning the number of such fuzzy partitions.

<footnote>CNRS, Groupe de Recherche C.F. PICARD, Université Paris VI
Tour 45, 4 place Jussieu, 75230 PARIS Cédex 05, France

and Departamento de Estatística e Matemática Aplicada,
Universidade Federal do Ceará, 60 000 Fortaleza-Ceára
(From June to August, 1983).</footnote>
# 1 - DEFINITION OF FUZZY PARTITIONS

Let $U = \{x_1, ..., x_n\}$ be a finite universe of discourse. A *fuzzy partition* $E = \{E_1, ..., E_m\}$ of $U$ is a family of non-empty fuzzy subsets of $U$.

Each class $E_i$, $1 \le i \le m$ of $E$ is defined by a membership function $f_i : U \to [0, 1]$. For every $i \in \{1, ..., m\}$, we denote by $f_{ij} = f_i(x_j)$ the grade of membership of the element $x_j$ corresponding to the class $E_i$, and $h(E_i)$ its maximum value, called the height of $E_i$. Let $F(E)$ be the mxn matrix having $f_{ij}$ as an element in the j-th line and the i-th column. It verifies

$$ \Sigma_i f_{ij} > 0 \quad \forall i \in \{1, ..., m\}. $$

In the sequel, $\wedge$ and $\vee$ will denote the infimum and the supremum.

For every $j \in \{1, ..., n\}$, $f_i^j = \vee_{j=1}^m f_{ij}$ is the maximum grade of membership of the element $x_j$ in a class of $E$. It is supposed not to be null.

Ordinary (or crisp) subsets of $U$ are characterized by
memberships functions $f_i : U \to \{0, 1\}$ and ordinary (or crisp) partitions
of $U$ are particular cases of fuzzy partitions. However, we generally get
a covering of $U$ from the definition of a fuzzy partition, when all the
classes $E_i$ are crisp subsets of $U$.

**Example 1 :** $U = \{x_1, ..., x_n\}$.

$$ E = \{E_1, E_2, E_3\}. $$

$$ E' = \{E_4, E_5, E_6\} $$

$$ F(E) = \begin{bmatrix} 0.8 & 0.1 & 0.1 \\ 0.7 & 0.1 & 0.3 \\ 0.2 & 0.4 & 0.4 \\ 0.1 & 0.1 & 0.8 \end{bmatrix} $$

$$ F(E') = \begin{bmatrix} 1 & 0.1 & 0.1 \\ 1 & 0.3 & 0.2 \\ 0.1 & 1 & 0.1 \\ 0 & 0.2 & 1 \end{bmatrix} $$

$$ E'' = \{E_7, E_8, E_9\} $$

$$ \bar{E} = \{\bar{E}_1, \bar{E}_2, \bar{E}_3\}. $$

$$ F(E'') = \begin{bmatrix} 0.9 & 0.1 & 0 \\ 0.8 & 0.5 & 0.1 \\ 0.5 & 0.6 & 0.3 \\ 0.1 & 0.2 & 0.9 \end{bmatrix} $$

$$ F(\bar{E}) = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$
# 1 - DEFINITION OF FUZZY PARTITIONS

Let $U = \{x_1, ..., x_n\}$ be a finite universe of discourse. A *fuzzy partition* $E = \{E_1, ..., E_m\}$ of $U$ is a family of non-empty fuzzy subsets of $U$.

Each class $E_i$, $1 \le i \le m$ of $E$ is defined by a membership function $f_i : U \to [0, 1]$. For every $i \in \{1, ..., m\}$, we denote by $f_{ij} = f_i(x_j)$ the grade of membership of the element $x_j$ corresponding to the class $E_i$, and $h(E_i)$ its maximum value, called the height of $E_i$. Let $F(E)$ be the mxn matrix having $f_{ij}$ as an element in the j-th line and the i-th column. It verifies

$$ \Sigma_i f_{ij} > 0 \quad \forall i \in \{1, ..., m\}. $$

In the sequel, $\wedge$ and $\vee$ will denote the infimum and the supremum.

For every $j \in \{1, ..., n\}$, $f_j^j = \vee_i f_{ij}$ is the maximum grade of membership of the element $x_j$ in a class of $E$. It is supposed not to be null.

Ordinary (or crisp) subsets of $U$ are characterized by
memberships functions $f_i : U \to \{0, 1\}$ and ordinary (or crisp) partitions
of $U$ are particular cases of fuzzy partitions. However, we generally get
a covering of $U$ from the definition of a fuzzy partition, when all the
classes $E_i$ are crisp subsets of $U$.

**Example 1 :** $U = \{x_1, ..., x_n\}$.

$$ E = \{E_1, E_2, E_3\}. $$

$$ E' = \{E_4, E_5, E_6\} $$

$$ F(E) = \begin{bmatrix} 0.8 & 0.1 & 0.1 \\ 0.7 & 0.1 & 0.3 \\ 0.2 & 0.4 & 0.4 \\ 0.1 & 0.1 & 0.8 \end{bmatrix} $$

$$ F(E') = \begin{bmatrix} 1 & 0.1 & 0.1 \\ 1 & 0.3 & 0.2 \\ 0.1 & 1 & 0.1 \\ 0 & 0.2 & 1 \end{bmatrix} $$

$$ E'' = \{E_7, E_8, E_9\} $$

$$ \bar{E} = \{\bar{E}_1, \bar{E}_2, \bar{E}_3\}. $$

$$ F(E'') = \begin{bmatrix} 0.9 & 0.1 & 0 \\ 0.8 & 0.5 & 0.1 \\ 0.5 & 0.6 & 0.3 \\ 0.1 & 0.2 & 0.9 \end{bmatrix} $$

$$ F(\bar{E}) = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} $$
For instance, partition $\tilde{E}$ is a crisp partition of U, but any fuzzy partition described by a matrix containing more than one 1 in at least one line would be a covering of U. Therefore, we must specify characteristics of a fuzzy partition in order to preserve the compatibility between ordinary and fuzzy concepts. This can be realized in the three following ways, more peculiarly :

- type 1 : *normalized partition E*.

The sum of the terms of every line of F(E) equals 1 :

$$ \sum_{i} f_{ij} = 1 $$

(For instance, partition E in example 1).

- type 2 : *natural partition E*.

For every element $x_j$ of U, there exists only one class such that $f_{ij} = f^j$.

(For instance, partition $E^*$ in example 1).

- type 3 : *maximized partition E*.

The matrix $F(E)$ has exactly one element equal to 1 in each line and at least one in each column.

(For instance, partition $E'$ in example 1).

A maximized partition is natural.

## 2 - COMPARISON OF THE FUZZINESS OF FUZZY PARTITIONS

In order to evaluate the fuzziness of a fuzzy partition E, we compare it with a crisp partition $\tilde{E}$ as close as possible to E [2].

For a given threshold $\alpha \in [0, 1]$, the *α-level set* $A^\alpha$ of a fuzzy subset A of U is the set of elements $x \in U$ corresponding to a grade of membership $f(x)$ at least equal to $\alpha$.

Let $\mathcal{E}_\alpha$ be the family of crisp partitions associated with E for the threshold $\alpha$ and defined in the following way : if $\tilde{E} = \{\tilde{E}_1, ..., \tilde{E}_m\} \in \mathcal{E}_\alpha$, then $x_j \in \tilde{E}_i$ for $1 \le j \le m$ and $1 \le i \le n$ implies that $f_{ij} \ge \alpha$. It is possible that some classes of $\tilde{E}$ are empty.

If there exists a value $\alpha \in [0, 1]$ such that the $\alpha$-level sets of $E_i$, $1 \le i \le m$, are disjoints, E is called a $\alpha$-partition and $\mathcal{E}_\alpha$ contains only one crisp partition E, $\alpha$-associated with E. For instance, $E^*$ in example 1
For instance, partition $\tilde{E}$ is a crisp partition of $U$, but any fuzzy partition described by a matrix containing more than one 1 in at least one line would be a covering of $U$. Therefore, we must specify characteristics of a fuzzy partition in order to preserve the compatibility between ordinary and fuzzy concepts. This can be realized in the three following ways, more peculiarly :

- type 1 : normalized partition E.

The sum of the terms of every line of $F(E)$ equals 1 :

$$ \sum_{i} f_{ij} = 1 $$

(For instance, partition E in example 1).

- type 2 : natural partition E.

For every element $x_j$ of $U$, there exists only one class such that $f_{ij} = f^j$.

(For instance, partition $E^*$ in example 1).

- type 3 : maximized partition E.

The matrix $F(E)$ has exactly one element equal to 1 in each line and at least one in each column.

(For instance, partition $E'$ in example 1).

A maximized partition is natural.

## 2 - COMPARISON OF THE FUZZINESS OF FUZZY PARTITIONS

In order to evaluate the fuzziness of a fuzzy partition $E$, we compare it with a crisp partition $\tilde{E}$ as close as possible to $E$ [2].

For a given threshold $\alpha \in [0, 1]$, the $\alpha$-level set $A^\alpha$ of a fuzzy subset $A$ of $U$ is the set of elements $x \in U$ corresponding to a grade of membership $f(x)$ at least equal to $\alpha$.

Let $\mathcal{C}_\alpha$ be the family of crisp partitions associated with $E$ for the threshold $\alpha$ and defined in the following way : if $\tilde{E} = \{\tilde{E}_1, ..., \tilde{E}_m\} \in \mathcal{C}_\alpha$, then $x_j \in \tilde{E}_i$ for $1 \le j \le m$ and $1 \le i \le n$ implies that $f_{ij} \ge \alpha$. It is possible that some classes of $\tilde{E}$ are empty.

If there exists a value $\alpha \in [0, 1]$ such that the $\alpha$-level sets of $E_i$, $1 \le i \le m$, are disjoints, $E$ is called a $\alpha$-partition and $\mathcal{C}_\alpha$ contains only one crisp partition $E$, $\alpha$-associated with $E$. For instance, $E^*$ in example 1
is a 0.6-partition and $\bar{E}$ is $\alpha$-associated with it.

More particularly, if E is a maximized partition of U, then it is a 1-partition. For instance, E' in example 1 is a 1-partition and $\bar{E}$ is 1-associated with E.

The values of $\alpha$ such that $\mathcal{E}_\alpha$ is not empty lie in the interval $[\alpha_0, \alpha_M]$, with $\alpha_0 = \bigwedge_j \wedge f_{ij}$ and $\alpha_M = \bigwedge_j f^j$. If E is a natural partition, there is a crisp partition $\bar{E}$ in $\mathcal{E}_\alpha$ such that :

$$x_j \in \bar{E}_j \Leftrightarrow f_{ij} = f^j.$$

This is the case, for instance, in example 1 if we consider the natural partition $E''$ and the crisp partition $\bar{E}$, 0.6-associated with it. Consequently, $E''$ is a 0.6-partition.

However, $\mathcal{E}_\alpha$ generally contains more than one crisp partition. For instance, partition E corresponds to a family $\mathcal{E}_{0.4}$ made of two crisp partitions, $\bar{E}$ and $\bar{E}' = \{\bar{E}_1, \bar{E}'_3\}$ with $\bar{E}'_3 = \{x_3, x_4\}$.

We propose to use an informational concept to determine the crisp partition closest to E, and we introduce the relative cardinality of :

a class $E_i$ of E, for the threshold $\alpha$, with regard to $\bar{E} \in \mathcal{E}_\alpha$ :

$$p_{\alpha}(E_i/\bar{E}) = \frac{1}{n} \sum_{x_j \in E_i} f_{ij}$$

a class $\bar{E}_i$ of $\bar{E}$ :

$$q(\bar{E}_i) = \frac{1}{n} |\bar{E}_i|.$$

These quantities verify :

$$0 \le p_{\alpha}(E_i/\bar{E}) \le q(\bar{E}_i) \le 1.$$

If E is crisp, $\mathcal{E}_1 = \{E\}$ and $\mathcal{E}_\alpha = \emptyset$ $\forall \alpha \ne 1$, and $p_1(E_i/\bar{E})$ represents the ratio of elements in $E_i$.

Let us define the gain of information of E with regard to $\bar{E} \in \mathcal{E}_\alpha$ by the following :

$$H_{\alpha}(E; \bar{E}) = \sum_{i=1}^{m} L(p_{\alpha}(E_i/\bar{E}), q(\bar{E}_i)) \quad (1)$$

with the notation $L(x, y) = y \log(y/x)$.

This quantity is positive and null if and only if $p_{\alpha}(E_i/\bar{E}) = q(\bar{E}_i)$. Vi. It is easy to see that :
is a 0.6-partition and $\bar{E}$ is $\alpha$-associated with it.

More particularly, if $E$ is a maximized partition of $U$, then it is a 1-partition. For instance, $E'$ in example 1 is a 1-partition and $\bar{E}$ is 1-associated with $E$.

The values of $\alpha$ such that $\mathcal{E}_\alpha$ is not empty lie in the interval $[\alpha_0, \alpha_M]$, with $\alpha_0 = \bigwedge_j f_{ij}$ and $\alpha_M = \bigwedge_j f^j$. If $E$ is a natural partition, there is a crisp partition $\bar{E}$ in $\mathcal{E}_\alpha$ such that :

$$x_j \in \bar{E}_j \Leftrightarrow f_{ij} = f^j.$$

This is the case, for instance, in example 1 if we consider the natural partition $E''$ and the crisp partition $\bar{E}$, 0.6-associated with it. Consequently, $E''$ is a 0.6-partition.

However, $\mathcal{E}_\alpha$ generally contains more than one crisp partition. For instance, partition $E$ corresponds to a family $\mathcal{E}_{0.4}$ made of two crisp partitions, $\bar{E}$ and $\bar{E}' = \{\bar{E}_1, \bar{E}'_3\}$ with $\bar{E}'_3 = \{x_3, x_4\}$.

We propose to use an informational concept to determine the crisp partition closest to $E$, and we introduce the *relative cardinality* of :

a class $E_i$ of $E$, for the threshold $\alpha$, with regard to $\bar{E} \in \mathcal{E}_\alpha$ :

$$p_{\alpha}(E_i/\bar{E}) = \frac{1}{n} \sum_{x_j \in E_i} f_{ij}$$

a class $\bar{E}_i$ of $\bar{E}$ :

$$q(\bar{E}_i) = \frac{1}{n} |\bar{E}_i|.$$

These quantities verify :

$$0 \le p_{\alpha}(E_i/\bar{E}) \le q(\bar{E}_i) \le 1.$$

If $E$ is crisp, $\mathcal{E}_1 = \{E\}$ and $\mathcal{E}_\alpha = \emptyset$ $\forall \alpha \ne 1$, and $p_1(E_i/\bar{E})$ represents the ratio of elements in $E_i$.

Let us define the *gain of information* of $E$ with regard to $\bar{E} \in \mathcal{E}_\alpha$ by the following :

$$H_{\alpha}(E; \bar{E}) = \sum_{i=1}^{m} L(p_{\alpha}(E_i/\bar{E}), q(\bar{E}_i)) \quad (1)$$

with the notation $L(x, y) = y \log(y/x)$.

This quantity is positive and null if and only if $p_{\alpha}(E_i/\bar{E}) = q(\bar{E}_i)$. Vi. It is easy to see that :
**Property 1** : If E is a maximized partition, then $H_1(E; \bar{E}) = 0$ for $\xi_1 = \{\bar{E}\}$. It is particularly true if E is crisp. If E is normalized, then $H_\alpha(E; \bar{E}) = 0$ for some $\alpha$ and $\bar{E} \in \xi_\alpha$ if and only if E is crisp. If E is a natural partition then $H(E; \bar{E}) = 0$ for some $\alpha$ and $\bar{E} \in \xi_\alpha$ if and only if E is maximized and $\xi_1 = \{\bar{E}\}$.

In the case where there are more than one crisp partition in $\xi_\alpha$ for the threshold $\alpha$, we propose to consider the crisp partition $\bar{E}_0$ minimizing $H_\alpha(E; \bar{E})$ for $\bar{E} \in \xi_\alpha$ as the crisp partition closest to E. To justify this criterion, we show that the gain of information is a good representation of the fuzziness of E.

We say that the fuzzy partition $E' = \{E'_1, \dots, E'_m\}$ of U defined by grades of membership $f'_{ij}$ is **α-sharper** than $E = \{E_1, \dots, E_m\}$. If

$$ \forall i \quad f'_{ij} \ge \alpha \Rightarrow f'_{ij} \ge f_{ij} $$

$$ f'_{ij} < \alpha \Rightarrow f'_{ij} \le f_{ij}. $$

We now prove the following

**Property 2** : If E and $E'$ are two fuzzy partitions such that $E'$ is **α-sharper** than E, then :

$$ H_{\alpha}(E; \bar{E}) \ge H_{\alpha}(E'; \bar{E}) \quad \forall \bar{E} \in \xi_{\alpha} \qquad (2) $$

$$ \text{and} \quad \neg \bigwedge_{\bar{E} \in \xi_{\alpha}} H_{\alpha}(E; \bar{E}) \ge \neg \bigwedge_{\bar{E} \in \xi_{\alpha}} H_{\alpha}(E'; \bar{E}). \qquad (3) $$

**Proof.** If $E'$ is **α-sharper** than E, then $f'_{ij} \ge \alpha \Leftrightarrow f'_{ij} \ge \alpha$ and $\xi_\alpha = \xi'_\alpha$.

For every $i \in \{1, \dots, m\}$, we have :

$$ p_{\alpha}(E'_i; \bar{E}) \ge p_{\alpha}(E_i; \bar{E}) \quad \forall \bar{E} \in \xi_{\alpha}, \text{ and (2) is easily deduced.} $$

Furthermore, if we note

$$ H_{\alpha}(E) = \neg \bigwedge_{\bar{E} \in \xi_{\alpha}} H_{\alpha}(E; \bar{E}), $$

we obtain :

$$ H_{\alpha}(E) = H_{\alpha}(E; \bar{E}_{0}) \ge H_{\alpha}(E'; \bar{E}_{0}) \ge H_{\alpha}(E'), $$

which completes the proof.

Obviously, the particular form of function L is not important and its only interesting properties in this context are, on the one hand the fact that it is null if and only if $x = y$, on the other hand its decrease with regard to x.
**Property 1** : If E is a maximized partition, then $H_1(E; \bar{E}) = 0$ for $\xi_1 = \{\bar{E}\}$. It is particularly true if E is crisp. If E is normalized, then $H_\alpha(E; \bar{E}) = 0$ for some $\alpha$ and $\bar{E} \in \xi_\alpha$ if and only if E is crisp. If E is a natural partition then $H(E; \bar{E}) = 0$ for some $\alpha$ and $\bar{E} \in \xi_\alpha$ if and only if E is maximized and $\xi_1 = \{\bar{E}\}$.

In the case where there are more than one crisp partition in $\xi_\alpha$ for the threshold $\alpha$, we propose to consider the crisp partition $\bar{E}_0$ minimizing $H_\alpha(E; \bar{E})$ for $\bar{E} \in \xi_\alpha$ as the crisp partition closest to E. To justify this criterion, we show that the gain of information is a good representation of the fuzziness of E.

We say that the fuzzy partition $E' = \{E'_1, \dots, E'_m\}$ of U defined by grades of membership $f'_{ij}$ is **α-sharper** than $E = \{E_1, \dots, E_m\}$. If

$$ \forall i \quad f'_{ij} \ge \alpha \Rightarrow f'_{ij} \ge f_{ij} $$

$$ f'_{ij} < \alpha \Rightarrow f'_{ij} \le f_{ij}. $$

We now prove the following

**Property 2** : If E and $E'$ are two fuzzy partitions such that $E'$ is **α-sharper** than E, then :

$$ H_{\alpha}(E; \bar{E}) \ge H_{\alpha}(E'; \bar{E}) \quad \forall \bar{E} \in \xi_{\alpha} \qquad (2) $$

$$ \text{and} \quad \bar{E} \in \xi_{\alpha} \quad H_{\alpha}(E; \bar{E}) \ge \bar{E} \in \xi'_{\alpha} \quad H_{\alpha}(E'; \bar{E}). \qquad (3) $$

**Proof.** If $E'$ is **α-sharper** than E, then $f'_{ij} \ge \alpha \Leftrightarrow f'_{ij} \ge \alpha$ and $\xi_\alpha = \xi'_\alpha$.

For every $i \in \{1, \dots, m\}$, we have :

$$ p_{\alpha}(E'_i; \bar{E}) \ge p_{\alpha}(E_i; \bar{E}) \quad \forall \bar{E} \in \xi_{\alpha}, \text{ and (2) is easily deduced.} $$

Furthermore, if we note

$$ H_{\alpha}(E) = \bigwedge_{\bar{E} \in \xi_{\alpha}} H_{\alpha}(E; \bar{E}), $$

we obtain :

$$ H_{\alpha}(E) = H_{\alpha}(E; \bar{E}_{0}) \ge H_{\alpha}(E'; \bar{E}_{0}) \ge H_{\alpha}(E'), $$

which completes the proof.

Obviously, the particular form of function L is not important and its only interesting properties in this context are, on the one hand the fact that it is null if and only if $x = y$, on the other hand its decrease with regard to x.
### 3 - COMBINATORIAL RESULTS

It is interesting to give combinatorial results concerning the number of fuzzy partitions of U and to generalize well-known quantities used in classical combinatorics. We suppose, in this part, that the set $I \subseteq [0, 1]$ of possible grades of membership is finite, with $|I| = k$. For a given fuzzy subset $A$ of $U$, with membership function $f$, we denote by $p = \sum_{x \in U} f(x)$ its fuzzy cardinality. Let $\mathcal{F}$ be the family of fuzzy partitions of a given type.

We remark that a fuzzy partition $E$ of type 1, 2 or 3 defined on $U = \{x_1, \dots, x_n\}$ can be obtained from a partition $E'$ of the same type on $U' = \{x_1, \dots, x_{n-1}\}$, by adding the element $x_n$, either in a class of $E'$ (which constitutes the subfamily $\mathcal{F}'$ of $\mathcal{F}$), or in a new class of $E$ (which constitutes the subfamily $\mathcal{F}''$ of $\mathcal{F}$).

#### 3.1. - Number of normalized partitions of U

We evaluate the number $S_n^m(I)$ of normalized fuzzy partitions with $m$ classes which can be defined on a set of $n$ elements by using grades of membership belonging to $I$. We must solve the conditions :

$$ egin{cases} \sum_{i} f_{ij} = 1 & \forall j \in \{1, \dots, n\} \\ \sum_{j} f_{ij} > 0 & \forall i \in \{1, \dots, m\}. \end{cases} $$

We must consider the number $C_n^p(I)$ fuzzy subsets of U with cardinality $p$. It can be proved [3] that it satisfies an equality analogous to the one defining Pascal's triangle :

**Property 3** : For $k \ge 2$, $n \ge 2$, $p > 0$, we have :

$$ egin{array}{ll} \text{and} & C_n^p(I) = \sum_{i \in I} C_{n-1}^{p-i}(I) \\ & n \\ \text{with} & \sum_{p=0} C_n^p(I) = k^n, \end{array} $$

$$ C_1^p(I) = 1 \qquad \forall p \in I, $$

$$ C_1^p(I) = 0 \qquad \forall p \notin I, $$

$$ C_n^0(I) = 1 \qquad \forall n \ge 1. $$
## 3 - COMBINATORIAL RESULTS

It is interesting to give combinatorial results concerning the number of fuzzy partitions of U and to generalize well-known quantities used in classical combinatorics. We suppose, in this part, that the set $I \subseteq [0, 1]$ of possible grades of membership is finite, with $|I| = k$. For a given fuzzy subset $A$ of $U$, with membership function $f$, we denote by $p = \sum_{x \in U} f(x)$ its fuzzy cardinality. Let $\mathcal{F}$ be the family of fuzzy partitions of a given type.

We remark that a fuzzy partition $E$ of type 1, 2 or 3 defined on $U = \{x_1, \dots, x_n\}$ can be obtained from a partition $E'$ of the same type on $U' = \{x_1, \dots, x_{n-1}\}$, by adding the element $x_n$, either in a class of $E'$ (which constitutes the subfamily $\mathcal{F}'$ of $\mathcal{F}$), or in a new class of $E$ (which constitutes the subfamily $\mathcal{F}''$ of $\mathcal{F}$).

### 3.1. - Number of normalized partitions of U

We evaluate the number $S_n^m(I)$ of normalized fuzzy partitions with $m$ classes which can be defined on a set of $n$ elements by using grades of membership belonging to $I$. We must solve the conditions :

$$ egin{cases} \sum_{i} f_{ij} = 1 & \forall j \in \{1, \dots, n\} \\ \sum_{j} f_{ij} > 0 & \forall i \in \{1, \dots, m\}. \end{cases} $$

We must consider the number $C_n^p(I)$ fuzzy subsets of U with cardinality $p$. It can be proved [3] that it satisfies an equality analogous to the one defining Pascal's triangle :

**Property 3** : For $k \ge 2$, $n \ge 2$, $p > 0$, we have :

$$ \begin{array}{ll} \text{and} & C_n^p(I) = \sum_{i \in I} C_{n-1}^{p-i}(I) \\ & n \\ & \sum_{p=0} C_n^p(I) = k^n, \end{array} $$

$$ \text{with} \quad C_1^p(I) = 1 \quad \forall p \in I, $$

$$ C_1^p(I) = 0 \quad \forall p \notin I, $$

$$ C_n^0(I) = 1 \quad \forall n \ge 1. $$
We use these quantities to determine the number of normalized
partition and we note $I^° = I - \{0\}$.

**Property 4 :** For $k \ge 2$, $n \ge 2$, $m \ge 2$, we have :

$$
S_n^m(I) = S_{n-1}^m(I) C_m^1(I) + \sum_{j=1}^{m-1} S_{n-1}^j(I) D_m^j(I) \quad (4)
$$

$$
\text{with} \quad D_m^j(I) = \binom{m}{j} \sum_{n=0}^{j} \binom{j}{n} C_{m-j+r}^1(I^\circ),
$$

and $S_n^1(I) = 1 \quad \forall n \ge 1$.

**Proof :** The first subclass $\mathcal{F}'$ of $\mathcal{F}$ corresponds to $S_{n-1}^m$ partitions of $U$, each of them associated with $C_m^1(I)$ definitions of the grades $f_{in}$, $1 \le i \le m$. Thus we get the first part of (4).

The second subclass $\mathcal{F}''$ of $\mathcal{F}$ corresponds to partitions $E'$ of $U'$ with $j$ classes, for $1 \le j \le m-1$, and there exist $S_{n-1}^i(I)$ such partitions using $j$ given classes of $E$. But $\binom{m}{j}$ choices of these classes are possible. For every given partitions $E'$, we define $E$ by giving the values of $f_{in}$, $1 \le i \le m$; ($m-j$) such values must be non-null, corresponding to the classes of $E$ which do not belong to $E'$. We can also choose $r$ other classes of $E'$ corresponding to non-null values of $f_{in}$, for $0 \le r \le j$; there exist $\binom{j}{r}$ such choices, each of them associated with $C_{m-j+r}^1(I^\circ)$ definitions of the grades of membership $f_{in}$, which complete the proof of (4).

In the case where the set of possible grades of membership is

$I_0 = \{0, \frac{1}{k-1}, \frac{2}{k-1}, \dots, 1\}$, the exact value of $S_n^m(I)$ can be deduced [3] from

result on the number of compositions of vectors [1] :

$$
S_n^m(I_0) = \sum_{i=0}^{m} (-1)^i \binom{m}{i} \binom{k-2+m-i}{k-1}^n
$$

3.2. - Number of natural partitions of U

We evaluate the number $I_n^m(I)$ of natural partitions with $m$ classes
which can be defined on $U$ by means of values taken in $I$. They satisfy the
conditions :
We use these quantities to determine the number of normalized
partition and we note $I^° = I - \{0\}$.

**Property 4 :** For $k \ge 2$, $n \ge 2$, $m \ge 2$, we have :

$$
S_n^m(I) = S_{n-1}^m(I) C_m^1(I) + \sum_{j=1}^{m-1} S_{n-1}^j(I) D_m^j(I) \quad (4)
$$

$$
\text{with } D_m^j(I) = \sum_{r=0}^{j} \binom{j}{r} C_{m-j+r}^{1}(I^{\circ}),
$$

and $S_n^1(I) = 1 \quad \forall n \ge 1.$

**Proof :** The first subclass $\mathcal{F}'$ of $\mathcal{F}$ corresponds to $S_{n-1}^m$ partitions of $U$, each of them associated with $C_m^1(I)$ definitions of the grades $f_{in}$, $1 \le i \le m$. Thus we get the first part of (4).

The second subclass $\mathcal{F}''$ of $\mathcal{F}$ corresponds to partitions $E'$ of $U'$ with $j$ classes, for $1 \le j \le m-1$, and there exist $S_{n-1}^i(I)$ such partitions using $j$ given classes of $E$. But $\binom{m}{j}$ choices of these classes are possible. For every given partitions $E'$, we define $E$ by giving the values of $f_{in}$, $1 \le i \le m$; ($m-j$) such values must be non-null, corresponding to the classes of $E$ which do not belong to $E'$. We can also choose $r$ other classes of $E'$ corresponding to non-null values of $f_{in}$, for $0 \le r \le j$; there exist $\binom{j}{r}$ such choices, each of them associated with $C_{m-j+r}^1(I^\circ)$ definitions of the grades of membership $f_{in}$, which complete the proof of (4).

In the case where the set of possible grades of membership is

$I_0 = \{0, \frac{1}{k-1}, \frac{2}{k-1}, \dots, 1\}$, the exact value of $S_n^m(I)$ can be deduced [3] from

result on the number of compositions of vectors [1] :

$$
S_n^m(I_0) = \sum_{i=0}^{m} (-1)^i \binom{m}{i} \binom{k-2+m-i}{k-1}^n
$$

3.2. - Number of natural partitions of U

We evaluate the number $I_n^m(I)$ of natural partitions with $m$ classes
which can be defined on $U$ by means of values taken in $I$. They satisfy the
conditions :
$$
\left\{
\begin{array}{lll}
\sum_{i} f_{ij} > 0 & \forall j \\
\sum_{j} f_{ij} > 0 & \forall i \\
& f^j \text{ is unique in } \{f_{ij}, 1 \le i \le m\} \quad \forall j.
\end{array}
\right.
$$

**Property 5** : For $k \ge 3$, $n \ge 2$, $m \ge 2$, we have :

$$
T_{n}^{m}(I) = T_{n-1}^{m}(I)m R_{k-1}^{m-1} + \sum_{j=1}^{m-1} T_{n-1}^{j}(I) F_{m}^{j}(I) \quad (5)
$$

$$
\text{with} \quad R_a^b = \sum_{i=1}^{a} i^b, \quad \forall a \ge 1, \forall b \ge 1, \qquad (6)
$$

$$
R_a^0 = a + 1 \qquad \forall a \ge 1
$$

$$
\text{and} \quad F_m^j(I) = \binom{m}{j} \sum_{r=0}^{j} \binom{j}{r} (m-j+r) R_{k-2}^{m-j+r-1} \quad (7)
$$

**Proof.** : Any partition E of S' is deduced from one of the $T_{n-1}^m(I)$
partitions E' of U' by choosing the situation of the maximum value $f^n$
of $f_{in}, 1 \le i \le m$, and $m$ possibilities exist. Then, we choose the value
$q$ of $f^n$ in $I^o$, and we get $N(q) = |\{x \in I, x < q\}|$ possible values for
every element $f_{in}$ different from $f^n$. Therefore, we obtain :

$$
T_{n-1}^{m}(I) m \sum_{q \in I^{o}} N(q)^{m-1} = T_{n-1}^{m}(I) m R_{k-1}^{m-1}
$$

possible natural partitions in $\mathcal{S}'$, with $R_a^b$ defined by (4).

Now, any partition E of S'' is deduced from one of the $T_{n-1}^j(I)$
partitions E' of U' containing j classes, for $1 \le j \le m-1$. For every
value j and one of the $\binom{m}{j}$ choices of j classes in those of E, we must
determine the values $f_{in}$; (m-j) of them are non-null and correspond
to the classes of E which are not in E'. We have $\binom{j}{r}$ possibilities of
non-null other coefficients corresponding to r classes of E', for $0 \le r \le j$.
For one of the (m-j+r) possible situations of $f^n$, and a given value $q \in I^o$
for $f^n$, we obtain $N'(q) = |\{x \in I^o, x < q\}|$ possible values for every $f_{in}$
different from $f^n$. Consequently, for all the possible values q, we obtain:
$$
\left\{
\begin{array}{ll}
\sum_{i} f_{ij} > 0 & \forall j \\
\sum_{j} f_{ij} > 0 & \forall i \\
& f^j \text{ is unique in } \{f_{ij}, 1 \le i \le m\} \quad \forall j.
\end{array}
\right.
$$

**Property 5 :** For $k \ge 3$, $n \ge 2$, $m \ge 2$, we have :

$$
T_{n}^{m}(I) = T_{n-1}^{m}(I)m R_{k-1}^{m-1} + \sum_{j=1}^{m-1} T_{n-1}^{j}(I) F_{m}^{j}(I) \quad (5)
$$

$$
\text{with} \quad R_a^b = \sum_{i=1}^{a} i^b, \quad \forall a \ge 1, \forall b \ge 1, \qquad (6)
$$

$$
R_a^0 = a + 1 \qquad \forall a \ge 1
$$

$$
\text{and} \quad F_m^j(I) = \binom{m}{j} \sum_{r=0}^{j} \binom{j}{r} (m-j+r) R_{k-2}^{m-j+r-1} \quad (7)
$$

**Proof.** : Any partition E of S' is deduced from one of the $T_{n-1}^m(I)$
partitions E' of U' by choosing the situation of the maximum value $f^n$
of $f_{in}, 1 \le i \le m$, and $m$ possibilities exist. Then, we choose the value
$q$ of $f^n$ in $I^o$, and we get $N(q) = |\{x \in I, x < q\}|$ possible values for
every element $f_{in}$ different from $f^n$. Therefore, we obtain :

$$
T_{n-1}^{m}(I) m \sum_{q \in I^{o}} N(q)^{m-1} = T_{n-1}^{m}(I) m R_{k-1}^{m-1}
$$

possible natural partitions in $\mathcal{S}'$, with $R_a^b$ defined by (4).

Now, any partition E of S'' is deduced from one of the $T_{n-1}^j(I)$
partitions E' of U' containing j classes, for $1 \le j \le m-1$. For every
value j and one of the $\binom{m}{j}$ choices of j classes in those of E, we must
determine the values $f_{in}$; (m-j) of them are non-null and correspond
to the classes of E which are not in E'. We have $\binom{j}{r}$ possibilities of
non-null other coefficients corresponding to r classes of E', for $0 \le r \le j$.
For one of the (m-j+r) possible situations of $f^n$, and a given value $q \in I^o$
for $f^n$, we obtain $N'(q) = |\{x \in I^o, x < q\}|$ possible values for every $f_{in}$
different from $f^n$. Consequently, for all the possible values q, we obtain:
$$ \sum_{q \in I^\circ} N'(q)^{m-j+r-1} = R_{k-2}^{m-j+r-1} $$

possible values for all the non-null $f_{in}$. We must remark that, when $m-j+r = 1$, we have one value of $f_{in}$ different from 0 and equal to $f^n$; there exist $(k-1)$ possible values and we note $R_{k-2}^0 = k-1$ by convention in order to preserve the notation in (7) in this limit case. We have completed the proof of (5).

### 3.3. - Number of maximized partitions of U

We evaluate the number $V_n^m(I)$ of maximized partitions of U with m classes defined by means of values taken in I. They satisfy the conditions :

$$ \begin{cases} f^j = 1 & \text{is unique in } \{f_{ij}, 1 \le i \le m\} & \forall j. \\ h(E_i) = 1 & \forall i. \end{cases} $$

**Property 6** : For $n \ge 2$, and $k \ge 2$, we have, if $2 \le m \le n$ :

$$ V_n^m(I) = (V_{n-1}^m(I) + V_{n-1}^{m-1}(I) (k-1)^{n-1}) m (k-1)^{m-1}, \quad (8) $$

$$ V_n^m(I) = 0 \quad \forall m > n $$

$$ \text{and} \quad V_n^1(I) = 1. $$

**Proof.** : Any partition E of $\mathcal{S}$ is obtained from one of the $V_{n-1}^m(I)$ partitions E' of U' by choosing for $x_n$ the place of the $f_{in}$ equal to 1 (m possibilities) and the value of every other coefficient $f_{in}$, different from 1. There exist $(k-1)^{m-1}$ such choices.

Now, we consider the partitions of $\mathcal{S}'$. As every class of E must contain one element with coefficient equal to 1 and as there exist only one value $f_{in}$ equal to 1, E must be deduced from a partition E' of U' containing m-1 classes. The new class $E_i$ constructed for $x_n$ can be one of the m classes of E and it corresponds to $f_{\ell n} = 1$. We have $(k-1)^{m-1}$ possible choices of the $f_{in}$, $i \ne \ell$ and, further, we may choose coefficients $f_{\ell j}$ different from 1 for the other elements $x_j = j \ne n$ in the new class
$$ \sum_{q \in I^0} N'(q)^{m-j+r-1} = R_{k-2}^{m-j+r-1} $$

possible values for all the non-null $f_{in}$. We must remark that, when $m-j+r = 1$, we have one value of $f_{in}$ different from 0 and equal to $f^n$; there exist $(k-1)$ possible values and we note $R_{k-2}^0 = k-1$ by convention in order to preserve the notation in (7) in this limit case. We have completed the proof of (5).

### 3.3. - Number of maximized partitions of U

We evaluate the number $V_n^m(I)$ of maximized partitions of U with m classes defined by means of values taken in I. They satisfy the conditions :

$$ \begin{cases} f^j = 1 & \text{is unique in } \{f_{ij}, 1 \le i \le m\} & \forall j. \\ h(E_i) = 1 & \forall i. \end{cases} $$

**Property 6** : For $n \ge 2$, and $k \ge 2$, we have, if $2 \le m \le n$ :

$$ V_n^m(I) = (V_{n-1}^m(I) + V_{n-1}^{m-1}(I) (k-1)^{n-1}) m (k-1)^{m-1}, \quad (8) $$

$$ V_n^m(I) = 0 \quad \forall m > n $$

$$ \text{and} \quad V_n^1(I) = 1. $$

**Proof.** : Any partition E of $\mathcal{S}$ is obtained from one of the $V_{n-1}^m(I)$ partitions E' of U' by choosing for $x_n$ the place of the $f_{in}$ equal to 1 (m possibilities) and the value of every other coefficient $f_{in}$, different from 1. There exist $(k-1)^{m-1}$ such choices.

Now, we consider the partitions of $\mathcal{S}'$. As every class of E must contain one element with coefficient equal to 1 and as there exist only one value $f_{in}$ equal to 1, E must be deduced from a partition E' of U' containing m-1 classes. The new class $E_i$ constructed for $x_n$ can be one of the m classes of E and it corresponds to $f_{\ell n} = 1$. We have $(k-1)^{m-1}$ possible choices of the $f_{in}$, $i \ne \ell$ and, further, we may choose coefficients $f_{\ell j}$ different from 1 for the other elements $x_j = j \ne n$ in the new class
$E_\ell$; there are $(k-1)^{n-1}$ such possibilities. Then, we have $v_{n-1}^{m-1}(I)m(k-1)^{n+m-2}$
maximized classes of $\mathcal{F}$ in $\mathcal{F}'$.

### 3.4. Conclusion

We have proved that the number of fuzzy partitions of $U$ of
every type satisfies a recurrent equality, generalizing the formula
defining Stirling's numbers in the case of crisp partitions.

Example 2 : $I = \{0, \frac{1}{2}, 1\}$.

$$ c_n^p(I) : \begin{array}{c|ccccc} n^p & 0 & \frac{1}{2} & \frac{3}{2} & 2 & 3 \\ \hline 1 & 1 & 1 & 1 & 0 & 0 \\ 2 & 1 & 2 & 3 & 2 & 1 \\ 3 & 1 & 3 & 6 & 7 & 6 \\ 4 & 1 & 4 & 10 & 16 & 19 \end{array} $$

$$ S_n^m(I) : \begin{array}{c|ccc} n^m & 1 & 2 & 3 \\ \hline 1 & 1 & 1 & 0 \\ 2 & 1 & 7 & 12 \\ 3 & 1 & 25 & 138 \end{array} $$

$$ T_n^m(I) : \begin{array}{c|ccc} n^m & 1 & 2 & 3 \\ \hline 1 & 2 & 2 & 3 \\ 2 & 4 & 28 & 129 \\ 3 & 3 & 200 & 2751 \end{array} $$

$$ V_n^m(I) : \begin{array}{c|ccc} n^m & 1 & 2 & 3 \\ \hline 1 & 1 & 0 & 0 \\ 2 & 1 & 8 & 0 \\ 3 & 1 & 48 & 384 \end{array} $$

### REFERENCES

[1] G.A. ANDREWS: The theory of partitions; Addison-Wesley (1976).

[2] B. BOUCHON: Comparison of experiments and improvement of models;
2^d World Conf. on Math. at the Service of Man (Las Palmas, 1982).

[3] B. BOUCHON, G. COHEN: On fuzzy relations and partitions; in
Advances in fuzzy set theory and applications, ed. P.P. Wang (Plenum
Publ. Co., to appear).
$E_\ell$; there are $(k-1)^{n-1}$ such possibilities. Then, we have $v_{n-1}^{m-1}(I)m(k-1)^{n+m-2}$ maximized classes of $\mathcal{F}$ in $\mathcal{F}'$.

### 3.4. Conclusion

We have proved that the number of fuzzy partitions of $U$ of every type satisfies a recurrent equality, generalizing the formula defining Stirling's numbers in the case of crisp partitions.

**Example 2 :** $I = \{0, \frac{1}{2}, 1\}$.

$$ c_n^p(I) : \begin{array}{c|ccccc} n^p & 0 & \frac{1}{2} & \frac{3}{2} & 2 & 1 \\ \hline 1 & 1 & 1 & 1 & 0 & 0 \\ 2 & 1 & 2 & 3 & 2 & 1 \\ 3 & 1 & 3 & 6 & 7 & 6 \\ 4 & 1 & 4 & 10 & 16 & 19 \end{array} $$

$$ S_n^m(I) : \begin{array}{c|ccc} n^m & 1 & 2 & 3 \\ \hline 1 & 1 & 1 & 0 \\ 2 & 1 & 7 & 12 \\ 3 & 1 & 25 & 138 \end{array} $$

$$ T_n^m(I) : \begin{array}{c|ccc} n^m & 1 & 2 & 3 \\ \hline 1 & 2 & 2 & 3 \\ 2 & 4 & 28 & 129 \\ 3 & 3 & 200 & 2751 \end{array} $$

$$ V_n^m(I) : \begin{array}{c|ccc} n^m & 1 & 2 & 3 \\ \hline 1 & 1 & 0 & 0 \\ 2 & 1 & 8 & 0 \\ 3 & 1 & 48 & 384 \end{array} $$

### REFERENCES

[1] G.A. ANDREWS : The theory of partitions ; Addison-Wesley (1976).

[2] B. BOUCHON : Comparison of experiments and improvement of models ; 2^d World Conf. on Math. at the Service of Man (Las Palmas, 1982).

[3] B. BOUCHON, G. COHEN : On fuzzy relations and partitions ; in Advances in fuzzy set theory and applications, ed. P.P. Wang (Plenum Publ. Co., to appear).