On the Density of Languages Representing Finite Set Partitions ^{1}

Nelma Moreira and Rogério Reis DCC-FC & LIACC Universidade do Porto R. do Campo Alegre 823 4150 Porto Portugal

                         nam@ncc.up.pt
                         rvr@ncc.up.pt

Abstract We present a family of regular languages representing partitions of a set of n elements in less or equal c parts. The density of those languages is given by partial sums of Stirling numbers of second kind for which we obtain explicit formulas. We also determine the limit frequency of those languages. This work was motivated by computational representations of the configurations of some numerical games.

1 The languages L_{c}

Consider a game where natural numbers are to be placed, by increasing order, in a fixed number of columns, subject to some specific constraints. In these games column order is irrelevant. Numbering the columns, game configurations can be seen as sequences of column numbers where the successive integers are placed. For instance, the string

11213

stands for a configuration where 1, 2, 4 were placed in the first column, 3 was placed in the second and 5 was placed in the third. Because column order is irrelevant, and to have a unique representation for each configuration, it is not allowed to place an integer in the kth column if the (k − 1)th is still empty, for any k > 1. Blanchard and al. [BHR04] and Reis and al. [RMP04] used this kind of representation to study the possible configurations of sum-free games.

1Work partially funded by Fundação para a Ciência e Tecnologia (FCT) and Program POSI.

Given c columns, let ℕ_{c} = {1, …, c}. We are interested in studying the set of game configurations as strings in (ℕ_{c})^{⋆}, i.e., in the set of finite sequences of elements of ℕ_{c}. Game configurations can be characterised by the following language L_{c} ⊂ (ℕ_{c})^{⋆}:

L_{c} = {a_{1}a_{2} ⋯ a_{k} ∈ (ℕ_{c})^{⋆} | ∀i ∈ ℕ_{k}, a_{i} ≤ max{a_{1}, …, a_{i−1}} + 1}.

For c = 4, there are only 15 strings in L_{4} of length 4, instead of the total possible 256 in (ℕ_{4})^{4}:

1111 1112 1121 1122 1123
1211 1212 1213 1221 1222
1223 1231 1232 1233 1234

Given a finite set Σ, a regular expression (r.e.) α over Σ represents a (regular) language L(α) ⊆ Σ^{⋆} and is inductively defined by: ∅ is a r.e and L(∅) = ∅; ϵ (empty string) is a r.e and L(ϵ) = {ϵ}; a ∈ Σ is a r.e and L(a) = {a}; if α_{1} and α_{2} are r.e., α_{1} +α_{2}, α_{1}α_{2} and α_{1}^{⋆} are r.e., respectively with L(α_{1} + α_{2}) = L(α_{1}) ∪ L(α_{2}), L(α_{1}α_{2}) = L(α_{1})L(α_{2}) and L(α_{1}^{⋆}) = L(α_{1})^{⋆} , where we assume the usual precedence of the operators (see [HMU00]). A regular expression α is unambiguous if for each w ∈ L(α) there is only one path through α that matches w.

Theorem 1.1. For all c ≥ 1, L_{c} is a regular language.

Proof. For c = 1, we have L_{1} = L(11^{⋆}). We define by induction on c, a family of regular expressions:

α_{1} = 11^{⋆},  (1)
α_{c} = α_{c−1} + ∏_{j=1}^{c} j(1 + ⋯ + j)^{⋆}.  (2)

It is trivial to see that

α_{c} = ∑_{i=1}^{c} ∏_{j=1}^{i} j(1 + ⋯ + j)^{⋆}.  (3)

For instance, α_{4} is

11^{⋆} + 11^{⋆}2(1 + 2)^{⋆} + 11^{⋆}2(1 + 2)^{⋆}3(1 + 2 + 3)^{⋆} + 11^{⋆}2(1 + 2)^{⋆}3(1 + 2 + 3)^{⋆}4(1 + 2 + 3 + 4)^{⋆}.

It is also obvious that L(α_{c−1}) ⊆ L(α_{c}), for c > 1. For any c ≥ 1, we prove that

L_{c} = L(α_{c}).

L_{c} ⊇ L(α_{c}): If x ∈ L(α_{c}) it is obvious that x ∈ L_{c}.

L_{c} ⊆ L(α_{c}): By induction on the length of x ∈ L_{c}: If |x| = 1 then x ∈ L(α_{1}) ⊆ L(α_{c}). Suppose that for any string x of length ≤ n, x ∈ L(α_{c}). Let |x| = n + 1 and x = ya, where a ∈ ℕ_{c} and y ∈ L(α_{c}). Let c′ = max{a_{i} | a_{i} ∈ y}. If c′ = c, obviously x ∈ L(α_{c}). If c′ < c, then y ∈ L(α_{c′}), and x ∈ L(α_{c′+1}) ⊆ L(α_{c}).

2 Counting the strings of L_{c}

The density of a language L over a finite set Σ, ρ_{L}(n), is the number of strings of length n that are in L, i.e.,

ρ_{L}(n) = |L ∩ Σ^{n}|.

In particular, the density of L_{c} is

ρ_{L_{c}}(n) = |L_{c} ∩ ℕ_{c}^{n}|.

Using generating functions we can determine a closed form for ρ_{L_{c}}(n). Recall that, a (ordinary) generating function for a sequence {a_{n}} is a formal series (see [GKP94])

G(z) = ∑_{i=0}^{∞} a_{n}z^{n}.

If A(z) and B(z) are generating functions for the density functions of the languages represented by unambiguous regular expressions A and B, and A + B, AB and A^{⋆} are also

unambiguous r.e., we have that A(z) + B(z), A(z)B(z) and \frac{1}{1 − A(z)}, are the generating

functions for the density functions of the corresponding languages (see [SF96], page 378).

As α_{c} are unambiguous regular expressions, from (3), we obtain the following generating function for {ρ_{L_{c}}(n)}:

T_{c}(z) = ∑_{i=1}^{c} ∏_{j=1}^{i} \frac{z}{(1 − jz)} = ∑_{i=1}^{c} \frac{z^{i}}{∏_{j=1}^{i} (1 − jz)}.

Notice that

S_{i}(z) = \frac{z^{i}}{∏_{j=1}^{i} (1 − jz)}

are the generating functions for the Stirling numbers of second kind

S(n, i) = \frac{1}{i!} ∑_{j=0}^{i−1}(−1)^{j}\binom{i}{j}(i − j)^{n},

which are, for each n, the number of ways of partitioning a set of n elements into i nonempty sets (see [GKP94] and \underline{A008277}).

Then, a closed form for the density of L_{c}, ρ_{L_{c}}(n), is given by

ρ_{L_{c}}(n) = ∑_{i=1}^{c} S(n, i),  (4)

i.e., a partial sum of Stirling numbers of second kind.

In Table 1 we present the values of ρ_{L_{c}}(n), for c = 1..8 and n = 1..13. For some sequences, we also indicate the corresponding number in Sloane’s On-Line Encyclopedia of Integer Sequences [Slo03]. The closed forms were calculated using the Maple computer algebra system [Hec03].

From expression (4), it is also easy to see that Theorem 2.1.

lim_{c→∞} ρ_{L_{c}}(n) = B_{n},

where B_{n} are the Bell numbers, i.e., for each n, the number of ways a set of n elements can be partitioned into nonempty subsets. Proof. Bell numbers, B_{n}, can be defined by the sum

B_{n} = ∑_{i=1}^{n} S(n, i).

And, as S(n, i) = 0 for i > n, we have

lim_{c→∞} ρ_{L_{c}}(n) = ∑_{i=1}^{n} S(n, i) + lim_{c→∞} ∑_{i=n+1}^{c} S(n, i) = B_{n}.

In Table 1, for each c ≥ 1, the subsequence for n ≤ c coincides with the first c elements of B_{n} (\underline{A000110}).

Moreover, we can express ρ_{L_{c}}(n), and then the partial sums of Stirling numbers of second kind, as a generic linear combination of nth powers of k, for k ∈ ℕ_{c}. Let S^{j}(n, i) denote the jth term in the summation of a Stirling number S(n, i), i.e.,

S^{j}(n, i) = \frac{1}{i!}(−1)^{j}\binom{i}{j}(i − j)^{n}.

Lemma 2.1. For all n and 0 ≤ i ≤ n,

S^{0}(n, i) = −S^{1}(n, i + 1).  (5)

Proof.

S^{1}(n, i + 1) = \frac{1}{(i + 1)!}(−1)\binom{i + 1}{1}i^{n} = (−1)\frac{1}{i!}i^{n} = −S^{0}(n, i).

Applying (5) in the summation (4) of ρ_{L_{c}}(n), each term S(n, i) simplifies the subterm S^{1}(n, i) with the subterm S^{0}(n, i − 1), for i ≥ 2. We obtain

ρ_{L_{1}}(n) = S^{0}(n, 1),
ρ_{L_{2}}(n) = S^{0}(n, 2),
ρ_{L_{c}}(n) = S^{0}(n, c) + ∑_{i=3}^{c} ∑_{j=2}^{i−1} S^{j}(n, i),  for c > 2;

= \frac{c^{n}}{c!} + ∑_{i=3}^{c} ∑_{j=2}^{i−1} S^{j}(n, i),  for c > 2.

c ρ_{L_{c}}(n)  OEIS
1 1

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …

2 \frac{1}{2} 2^{n}

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, …

3 \frac{1}{6} 3^{n} + \frac{1}{2}
1, 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, 265721, … \underline{A007051}
4 \frac{1}{24} 4^{n} + \frac{1}{4} 2^{n} + \frac{1}{3}
1, 2, 5, 15, 51, 187, 715, 2795, 11051, 43947, 175275, 700075, 2798251, … \underline{A007581}
5 \frac{1}{120} 5^{n} + \frac{1}{12} 3^{n} + \frac{1}{6} 2^{n} + \frac{3}{8}
1, 2, 5, 15, 52, 202, 855, 3845, 18002, 86472, 422005, 2079475, 10306752, … \underline{A056272}
6 \frac{1}{720} 6^{n} + \frac{1}{48} 4^{n} + \frac{1}{18} 3^{n} + \frac{3}{16} 2^{n} + \frac{11}{30}
1, 2, 5, 15, 52, 203, 876, 4111, 20648, 109299, 601492, 3403127, 19628064, … \underline{A056273}
7 \frac{1}{5040} 7^{n} + \frac{1}{240} 5^{n} + \frac{1}{72} 4^{n} + \frac{1}{16} 3^{n} + \frac{11}{60} 2^{n} + \frac{53}{144}
1, 2, 5, 15, 52, 203, 877, 4139, 21110, 115179, 665479, 4030523, 25343488, … \underline{A099262}
8 \frac{1}{40320} 8^{n} + \frac{1}{1440} 6^{n} + \frac{1}{360} 5^{n} + \frac{1}{64} 4^{n} + \frac{11}{180} 3^{n} + \frac{53}{288} 2^{n} + \frac{103}{280}
1, 2, 5, 15, 52, 203, 877, 4140, 21146, 115929, 677359, 4189550, 27243100, … \underline{A099263}

Table 1: Density functions of L_{c}, for c = 1..8.

If the sums are rearranged such that i = k + j, we have

ρ_{L_{c}}(n) = \frac{c^{n}}{c!} + ∑_{k=1}^{c−2} ∑_{j=2}^{c−k} S^{j}(n, k + j),  (6)

where

S^{j}(n, k + j) = \frac{k^{n}}{(k + j)!}(−1)^{j}\binom{k + j}{j}  (7)
= \frac{k^{n}}{k!j!}(−1)^{j}.  (8)

Replacing (8) into equation (6) we get

ρ_{L_{c}}(n) = \frac{c^{n}}{c!} + ∑_{k=1}^{c−2} \frac{k^{n}}{k!} (∑_{j=2}^{c−k} \frac{(−1)^{j}}{j!} ) .  (9)

In equation (9), the coefficients of k^{n}, 1 ≤ k ≤ c, can be calculated using the following recurrence relation:

γ_{1}^{1} = 1;
γ_{1}^{c} = γ_{1}^{c−1} + \frac{(−1)^{c−1}}{(c − 1)!} , for c > 1;
γ_{k}^{c} = \frac{γ_{k−1}^{c−1}}{k} , for c > 1 and 2 ≤ k ≤ c.

And, we have

Theorem 2.2. For all c ≥ 1,

ρ_{L_{c}}(n) = ∑_{k=1}^{c} γ_{k}^{c}k^{n}.  (10)

From the expression (10), the closed forms in Table 1 are easily derived.

Finally, we can obtain the limit frequency of L_{c} in (ℕ_{c})^{⋆}. Since

ρ_{(ℕ_{c})^{⋆}}(n) = c^{n},

and lim_{n→∞} (\frac{k}{c})^{n} = 0, for 1 ≤ k ≤ c − 2, we have

Theorem 2.3. For all c ≥ 1,

lim_{n→∞} \frac{ρ_{L_{c}}(n)}{ρ_{(ℕ_{c})^{⋆}}(n)} = \frac{1}{c!}.

3 A bijection between strings of L_{c} and partitions of finite sets

The connection between the density of L_{c} and Stirling numbers of second kind is not accidental. Each string of L_{c} with length n corresponds to a partition of ℕ_{n} with no more than c parts. This correspondence can be made explicit as follows.

Let a_{1}a_{2} ⋯ a_{n} be a string of L_{c}. This string corresponds to the partition {A_{j}}_{j∈ℕ_{c′}} of ℕ_{n} with c′ = max{a_{1}, …, a_{n}}, such that for each i ∈ ℕ_{n}, i ∈ A_{a_{i}}. For example, the string 1123 corresponds to the partition {{1, 2}, {3}, {4}} of ℕ_{4} into 3 parts.

This defines a bijection. That each string corresponds to a unique partition is obvious. Given a partition {A_{j}}_{j∈ℕ_{c′}} of ℕ_{n} with c′ ≤ c, we can construct the string b_{1} ⋯ b_{n}, such that for i ∈ ℕ_{n}, b_{i} = j if i ∈ A_{j}. For the partition {{1, 2}, {3}, {4}}, we obtain 1123.

4 Counting the strings of L_{c} of length equal or less than a certain value

Although strings of L_{c} of arbitrary length represent game configurations, for computational reasons^{2} we consider all game configurations with the same length, padding with zeros the positions of integers not yet in one of the c columns. In this way, we obtain the languages L_{c}^{0} = L_{c}{0^{⋆}}. So, determining the number of strings of length equal or less than n that are in L_{c} is tantamount to determining the density of L_{c}^{0}, i.e.,

ρ_{L_{c}^{0}}(n) = |L_{c}^{0} ∩ ({0} ∪ ℕ_{c})^{n}|.

As seen in Section 2, and because L_{c}{0^{⋆}} = L(α_{c}0^{⋆}), the generating function T′_{c}(z) of ρ_{L_{c}^{0}}(n) can be obtained as the product of a generating function for ρ_{L_{c}}(n), T_{c}(z), by a generating

function for ρ_{\{0\}^{⋆}}(n), e.g., \frac{1}{1 − z}. Thus, the generating function for \{ρ_{L_{c}^{0}}(n)\} is

T′_{c}(z) = T_{c}(z)\frac{1}{1 − z} = ∑_{i=1}^{c} \frac{z^{i}}{(1 − z) ∏_{j=1}^{i} (1 − jz)}

and a closed form for ρ_{L_{c}^{0}}(n) is (as expected)

ρ_{L_{c}^{0}}(n) = ∑_{m=1}^{n} ∑_{i=1}^{c} S(m, i),  (11)

where m starts at 1 because S(m, i) = 0, for i > m.

2The data structures used in the programs are arrays of fixed length.

Using expression (9) in (11) we have

ρ_{L_{1}^{0}}(n) = n;
ρ_{L_{2}^{0}}(n) = 2^{n} − 1;
ρ_{L_{c}^{0}}(n) = ∑_{m=1}^{n} (\frac{c^{m}}{c!} + ∑_{k=1}^{c−2} \frac{k^{m}}{k!} ∑_{j=2}^{c−k} \frac{(−1)^{j}}{j!} ) ,  for c > 2;

= \frac{c^{n+1} − c}{(c − 1)c!} + n ∑_{j=2}^{c−1} \frac{(−1)^{j}}{j!} + ∑_{k=2}^{c−2} \frac{k^{n+1} − k}{(k − 1)k!} (∑_{j=2}^{c−k} \frac{(−1)^{j}}{j!} )

= \frac{c^{n} − 1}{(c − 1)(c − 1)!} + n ∑_{j=2}^{c−1} \frac{(−1)^{j}}{j!} + ∑_{k=2}^{c−2} \frac{k^{n} − 1}{(k − 1)(k − 1)!} (∑_{j=2}^{c−k} \frac{(−1)^{j}}{j!} ) .

If we use the equation (10), we have

Theorem 4.1. For all c ≥ 1,

ρ_{L_{c}^{0}}(n) = nγ_{1}^{c} + ∑_{k=2}^{c} \frac{γ_{k}^{c}(k^{n+1} − k)}{k − 1}.

Proof.

ρ_{L_{c}^{0}}(n) = ∑_{m=1}^{n} ∑_{k=1}^{c} γ_{k}^{c}k^{m} = ∑_{k=1}^{c} γ_{k}^{c} ∑_{m=1}^{n} k^{m} = nγ_{1}^{c} + ∑_{k=2}^{c} \frac{γ_{k}^{c}(k^{n+1} − k)}{k − 1}.

In the Table 2 we present the values of ρ_{L_{c}^{0}}(n), for c = 1..8 and n = 1..13. As before, the limiting sequence as c → ∞ is the sequence of partial sums of Bell numbers.

Finally, we determine the limit frequency of L_{c}^{0} in (ℕ_{c})^{⋆}{0}^{⋆}. Notice that

ρ_{(ℕ_{c})^{⋆}\{0\}^{⋆}}(n) = \frac{c^{n+1} − 1}{c − 1},

as it is a sum of the first n terms of a geometric progression of ratio c. We have,

Theorem 4.2. For all c ≥ 1,

lim_{n→∞} \frac{ρ_{L_{c}^{0}}(n)}{ρ_{(ℕ_{c})^{⋆}\{0\}^{⋆}}(n)} = \frac{1}{c!}.

c ρ_{L_{c}^{0}}(n)  OEIS
1 n

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, …

2 2^{n} − 1
1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, … \underline{A000225}
3 \frac{1}{4} 3^{n} + \frac{1}{2} n − \frac{1}{4}
1, 3, 8, 22, 63, 185, 550, 1644, 4925, 14767, 44292, 132866, 398587, … \underline{A047926}
4 \frac{1}{18} 4^{n} + \frac{1}{2} 2^{n} + \frac{1}{3} n − \frac{5}{9}

1, 3, 8, 23, 74, 261, 976, 3771, 14822, 58769, 234044, 934119, 3732370, …

5 \frac{1}{96} 5^{n} + \frac{1}{8} 3^{n} + \frac{1}{3} 2^{n} + \frac{3}{8} n − \frac{15}{32}
1, 3, 8, 23, 75, 277, 1132, 4977, 22979, 109451, 531456, 2610931, 12917683, … \underline{A099265}
6 \frac{1}{600} 6^{n} + \frac{1}{36} 4^{n} + \frac{1}{12} 3^{n} + \frac{3}{8} 2^{n} + \frac{11}{30} n − \frac{439}{900}
1, 3, 8, 23, 75, 278, 1154, 5265, 25913, 135212, 736704, 4139831, 23767895, … \underline{A099266}
7 \frac{1}{4320} 7^{n} + \frac{1}{192} 5^{n} + \frac{1}{54} 4^{n} + \frac{3}{32} 3^{n} + \frac{11}{30} 2^{n} + \frac{53}{144} n − \frac{31}{64}

1, 3, 8, 23, 75, 278, 1155, 5294, 26404, 141583, 807062, 4837585, 30181073, …

8 \frac{1}{35280} 8^{n} + \frac{1}{1200} 6^{n} + \frac{1}{288} 5^{n} + \frac{1}{48} 4^{n} + \frac{11}{120} 3^{n} + \frac{53}{144} 2^{n} + \frac{103}{280} n − \frac{57023}{117600}

1, 3, 8, 23, 75, 278, 1155, 5295, 26441, 142370, 819729, 5009279, 32252379, …

Table 2: Density functions of L_{c}^{0}, for c = 1..8.

Proof.

lim_{n→∞} \frac{ρ_{L_{c}^{0}}(n)}{ρ_{(ℕ_{c})^{⋆}\{0\}^{⋆}}(n)} = lim_{n→∞} (\frac{(c^{n+1} − c)(c − 1)}{(c − 1)c!(c^{n+1} − 1)} + \frac{n(c − 1)}{c^{n+1} − 1} ∑_{j=2}^{c−1} \frac{(−1)^{j}}{j!} )

+ lim_{n→∞} (∑_{k=2}^{c−2} \frac{(k^{n+1} − k)(c − 1)}{(k − 1)k!(c^{n+1} − 1)} (∑_{j=2}^{c−k} \frac{(−1)^{j}}{j!} ))

= \frac{1}{c!} ( lim_{n→∞} \frac{1}{1 − \frac{1}{c^{n+1}}} − lim_{n→∞} \frac{c}{c^{n+1} − 1})

+ ∑_{j=2}^{c−1} \frac{(−1)^{j}}{j!} lim_{n→∞} (\frac{n(c − 1)}{c^{n+1} − 1})

+ ∑_{k=2}^{c−2} \frac{(c − 1)}{(k − 1)(k − 1)!} ∑_{j=2}^{c−k} \frac{(−1)^{j}}{j!} lim_{n→∞} (\frac{(\frac{k}{c})^{n}}{c − \frac{1}{c^{n}}} − \frac{1}{c^{n+1} − 1})

= \frac{1}{c!}.

5 Conclusion

In this note we presented a family of regular languages representing finite set partitions and studied their densities. Although it is well-known that the number of partitions of a set of n elements into no more than c nonempty sets is given by partial sums of Stirling numbers of second kind, we determined explicit formulas for their closed forms, as linear combinations of k^{n}, for k ∈ ℕ_{c}. We also determined the limit frequency of those languages, which gives an estimate of the space saved with those representations.

Acknowledgements

We thank Miguel Filgueiras and the referee for their comments in previous versions of the manuscript. We also thank J. Shallit for pointing us a connection between the density of L_{c} and the Bell numbers.

References

[BHR04] Peter Blanchard, Frank Harary, and Rogério Reis, Partitions into sum-free sets, Integers: Electronic Journal of Combinatorial Number Theory, (to appear), 2004.

[GKP94] Roland Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics. Addison-Wesley, 1994.

[Hec03] Andri Heck.  Introduction to Maple.  Springer, 3rd edition, 2003.

http://remote.science.uva.nl/%7Eheck/Maplebook/.

[HMU00] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 2nd edition, 2000.

[RMP04] Rogério Reis, Nelma Moreira, and João Pedro Pedroso. Educated brute-force to get h(4). Technical Report DCC-2004-04, DCC-FC& LIACC, Universidade do Porto, July 2004.

[SF96] Robert Sedgewick and Philippe Flajolet. Analysis of Algorithms. Addison-Wesley, 1996.

[Slo03] N.J.A. Sloane. The On-line Encyclopedia of Integer Sequences, 2003. http://www.research.att.com/∼njas/sequences.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A18, 11B73, 68Q45. Keywords: Partions of sets, Stirling numbers, regular languages, enumeration

(Concerned with sequences \underline{A000110} \underline{A000225} \underline{A007051} \underline{A007581} \underline{A008277} \underline{A047926} \underline{A056272} \underline{A056273} \underline{A099262} \underline{A099263} \underline{A099265} \underline{A099266} .)

Received October 14 2004; revised version received April 17 2005. Published in Journal of Integer Sequences, May 18 2005.

Return to Journal of Integer Sequences home page.