Printer Friendly

Statistics for 3-letter patterns with repetitions in compositions.

A composition [pi] = [[pi].sub.1][[pi].sub.2]... [[pi].sub.m] of a positive integer n is an ordered collection of one or more positive integers whose sum is n. The number of summands, namely m, is called the number of parts of [pi]. Using linear algebra, we determine formulas for generating functions that count compositions of n with m parts, according to the number of occurrences of the subword pattern [tau], and according to the sum, over all occurrences of [tau], of the first integers in their respective occurrences, where [tau] is any pattern of length three with exactly 2 distinct letters.

Keywords: Subwords, generating functions, Cramer's method.

1 Introduction

A composition [pi] = [[pi].sub.1][[pi].sub.2]... [[pi].sub.m] of a positive integer n [member of] N is an ordered collection of m positive integers whose sum is n. The number m of summands is called the number of parts of [pi] and is denoted by ord([pi]). For example, the compositions of 3 are 3, 12, 21 and 111. We denote the set of compositions of n by [C.sub.n], and the set of compositions of n with parts in [d] = {1, 2,... , d} by [C.sub.n;d]. Clearly, the number of compositions of n is given by |[C.sub.n]| = [2.sup.n-1] (for instance, see [6]).

Let [pi] = [[pi].sub.1][[pi].sub.2]... [[pi].sub.m] be any composition of n with exactly m parts in [d] and let [sigma] = [[sigma].sub.1][[sigma].sub.2]... [[sigma].sub.s] be any word of length s, where m [greater than or equal to] s. An occurrence of [sigma] in [pi] is a subword [[pi].sub.i][[pi].sub.i+1]... [[pi].sub.i+s-1] which is order isomorphic to [sigma], i.e., [[pi].sub.i-1+a] < [[pi].sub.i-1+b] if and only if [[sigma].sub.a] < [[sigma].sub.b] for all 1 [less than or equal to] a [less than or equal to] b [less than or equal to] s. Here, the word [sigma] is usually called a pattern of length s (or an s-letter pattern). We denote the number of the occurrences of [sigma] in [pi] by [occ.sub.[sigma]] ([pi]) and we denote the sum of the values of the first letters over all occurrences of [sigma] in [pi] by [sfl.sub.[sigma]]([pi]). For example, the occurrences of the pattern 121 in the composition [pi] = 12122421 of 15 are 121 and 242, so occ121([pi]) = 2 and [sfl.sub.121]([pi]) = 1 + 2 = 3.

In last decade, statistics on compositions (a statistic on set A is a function A [right arrow] [N.sub.0] = {0,1,2,...}) has been received a lot of attention (see [6] and references therein). For instance, Heubach and Mansour [5] studied the generating function for the number of compositions of n with exactly m parts according to the number of occurrences of the patterns 11,12and21. Mansour and Sirhan [8] discussed the generating function for the number of compositions of n with exactly m parts according to the number of occurrences of several families of patterns (for other reference, see also [1, 3, 4] and references therein).

Recently, by using linear algebra, Askaly and Mansour [2] determined formulas for generating functions that count compositions of n with m parts, according to the numbers of pattern [tau] of length 2, and according to the sum, over all occurrences of [tau], of the first integers in their respective occurrences.

Let [F.sub.[tau]] = [F.sub.[tau]](x, y, u, v) be the generating function for the number of compositions of n with parts in [d] according to the statistics ord, [occ.sub.[tau]] and [sfl.sub.[tau]], that is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this paper, by using linear algebra, we extend the results of [2] to derive the generating functions for the number of compositions, the number of parts, and the statistics [occ.sub.[tau]] and [sfl.sub.[tau]]. This unified framework generalizes earlier works.

The paper is organized as follows. In the next section, we obtain generating functions for the number of compositions of n with parts in [d], according to the above mentioned statistics. Finally, in the last section, we use our results to derive the average sum of the values of the first letters of the occurrences of [sigma] in words of [[d].sup.n], where [sigma] [member of] {112,121,122, 211, 212, 221}.

In order to achieve our results, we need the following notation. We define

[F.sub.[tau]]([a.sub.1][a.sub.2]... [a.sub.s]) = [F.sub.[tau]](x, y, u, v|[a.sub.1][a.sub.2]... [a.sub.s])

to be the generating function for the number of compositions [pi] = [a.sub.1][a.sub.2]... [a.sub.s][pi]' of n with parts in [d] according to the statistics ord, [occ.sub.[tau]] and [sfl.sub.[tau]], that is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

We will conclude the paper with a short description on future work.

2 Three letters pattern

This section is divided into several subsections, where in each subsection we study a fixed pattern from the set {112,121,122,211, 212,221}.

2.1 The case [tau] =112

In this subsection, we find an explicit formula for the generating function [F.sub.112;d]. Firstly, we find a recurrence relation for the generating function [F.sub.112;d](a). By the definitions, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which, by (1), implies

[F.sub.112;d](a) = [x.sup.a]y([F.sub.112;d] - [F.sub.112;d](a)) + [F.sub.112;d](aa). (2)

Now, we express [F.sub.112;d](aa) in terms of generating functions [F.sub.112;d](j). Again, by definitions, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore, by (1), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

By substituting (3) into (2), we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is equivalent to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Let [[alpha].sub.a] = [x.sup.2a][y.sup.2](1 - [u.sup.a]v) and [[beta].sub.a] = [x.sup.a]y [F.sub.112;d]. Then (4) can be written as

[M.sub.112;d][x.sub.112;d] = [v.sub.112;d],

where [v.sub.112;d] = [([beta]1,... , [beta]d).sup.T], [x.sub.112;d] = [([F.sub.112;d](1),..., [F.sub.112;d](d)).sup.T], and [M.sub.112;d] = [([m.sub.ij]).sub.1[less than or equal to]i,j[less than or equal to]d] with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We solve this system by Cramer's method and obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a matrix obtained from the matrix [M.sub.112;d] by replacing the a-th column by the vector [v.sub.112;d]. By the definitions, we have (we omit the zeros)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By simple induction on j [greater than or equal to] 1, one can show

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By substituting this into (1), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

On the other hand,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, by definitions of [[alpha].sub.a] and [[beta].sub.a], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which gives the following result.

Theorem 2.1 The generating function [F.sub.112;d](x, y, u, v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By taking d [right arrow] [infinity] in Theorem 2.1, we obtain the main result of this section.

Theorem 2.2 The generating function [F.sub.112] (x, y, u, v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2.2 The case [tau] = 122

In this subsection, we find an explicit formula for the generating function [F.sub.122;d]. By using similar arguments as in the previous section, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

Now, we express [F.sub.122;d](ak) with a < k [less than or equal to] d in terms of generating functions [F.sub.122;d](j). Again, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which, by (5), gives

[F.sub.122;d](ak) = [x.sup.a]y(1 + [x.sup.k] y([u.sup.a]v - 1))[F.sub.122;d](k).

Therefore, by substituting this into (5), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

Let [[alpha].sub.a] = [x.sup.2a+1][y.sup.2](1 - [u.sup.a]v) and [[beta].sub.a] = [x.sup.a]y[F.sub.122;d]. Then (6) can be written as

[M.sub.122;d][x.sub.122;d] = [v.sub.122;d],

where [v.sub.122;d] = [([[beta].sub.1],... , [[beta].sub.d]).sup.T], [x.sub.122;d] = [([F.sub.122;d](1),... , [F.sub.122;d](d)).sup.T], and [M.sub.122;d] = [([m.sub.ij]).sub.1[less than or equal to]i,j[less than or equal to]d] with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We solve this system by Cramer's method and obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a matrix obtained from the matrix [M.sub.122;d] by replacing the a-th column by the vector [v.sub.122;d]. By the definitions, we have (we omit the zeros)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By simple induction on j [greater than or equal to] 1, one can show

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By substituting this into (1), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, by definitions of [[alpha].sub.a] and [[beta].sub.a], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which gives the following result.

Theorem 2.3 The generating function [F.sub.122;d](x, y, u, v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By taking d [right arrow] [infinity] in Theorem 2.1, we obtain the main result of this section.

Theorem 2.4 The generating function [F.sub.122] (x, y, u,v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2.3 The case [tau] = 221

In this subsection, we find an explicit formula for the generating function [F.sub.221;d]. By using similar techniques as showed in the previous subsection, we obtain

[F.sub.221;d](a) = [x.sup.a]y([F.sub.221;d] - [F.sub.221;d](a)) + [F.sub.221;d](aa) (7)

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (8)

By substituting (8) into (7), we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

which is equivalent to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

Let [[alpha].sub.a] = [x.sup.2a][y.sup.2](1 - [u.sup.a]v) and [[beta].sub.a] = [x.sup.a]y[F.sub.221;d]. Then (9) can be written as

[M.sub.221;d] [x.sub.221;d] = [v.sub.221;d],

where [v.sub.221;d] = [([[beta].sub.1],... , [[beta].sub.d]).sup.T], [x.sub.221;d] = ([F.sub.221;d](1),... , [F.sub.221;d](d)), and [M.sub.221;d] = [([m.sub.ij]).sub.1[less than or equal to]i,j[less than or equal to]d] with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We solve this system by Cramer's method and obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a matrix obtained from the matrix [M.sub.221;d] by replacing the a-th column by the vector [v.sub.221;d]. By the definitions, we have (we omit the zeros)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By simple induction on j [greater than or equal to] 1, one can show (see Lemma (2.1) with x = 1)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By substituting this into (1), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

On the other hand, it is not hard to see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, by definitions of [[alpha].sub.a] and [[beta].sub.a], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which gives the following result.

Theorem 2.5 The generating function [F.sub.221;d](x, y, u, v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By taking d [right arrow] [infinity] in Theorem 2.5, we obtain the main result of this section.

Theorem 2.6 The generating function [F.sub.221] (x, y, u,v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2.4 The case [tau] = 211

In this section, we find an explicit formula for the generating function [F.sub.211;d]. Firstly, we find a recurrence relation for the generating function [F.sub.211;d](a). By the definitions, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

Now, we express [F.sub.211;d](ak) with a > k [greater than or equal to] 1 in terms of generating functions [F.sub.211;d](j). Again, by definitions, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By (10), we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus,

[F.sub.211;d](ak) = [x.sup.a]y[F.sub.211;d](k) + [x.sup.a+k] [y.sup.2] ([u.sup.a]v - 1)[F.sub.211;d](k),

for any 1 [less than or equal to] k [less than or equal to] a - 1. Therefore, by substituting into (10), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which, by (1), implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (11)

In order to solve this recurrence relation, we need the following lemma.

Lemma 2.1 For all m [greater than or equal to] 1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: We denote this determinant by [p.sub.m]([[alpha].sub.1],..., [[alpha].sub.m]). By expanding the determinant according to the rightmost column, we obtain

[p.sub.m]([[alpha].sub.1],... , [[alpha].sub.m]) = [x.sup.m-1] [[alpha].sub.m][p.sub.m-1]([[alpha].sub.1],... , [[alpha].sub.m-1]) ~ [p.sub.m-2]([[alpha].sub.1],... , [[alpha].sub.m-2], [[alpha].sub.m]).

Thus, by induction on the size of the determinant, we obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], as required. []

Let [[alpha].sub.a] = [x.sup.a+1][y.sup.2](1 - [u.sup.a]v) and [[beta].sub.a] = [x.sup.a]y[F.sub.211;d]. Then (11) can be written as

[M.sub.211;d][x.sub.211;d] = [v.sub.211;d],

where [v.sub.211;d] = [([[beta].sub.1],... , [[beta].sub.d]).sup.T], [x.sub.211;d] = [([F.sub.211;d](1),... , [F.sub.211;d](d)).sup.T], and [M.sub.211;d] = [([m.sub.ij]).sub.1[less than or equal to]i,j[less than or equal to]d] with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We solve this system by Cramer's method and obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a matrix obtained from the matrix [M.sub.211;d] by replacing the a-th column by the vector [v.sub.211;d]. By the definitions, we have (we omit the zeros)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, by Lemma 2.1, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By substituting this into (1), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, by definitions of [[alpha].sub.a] and [[beta].sub.a], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which gives the following result.

Theorem 2.7 The generating function [F.sub.211;d](x, y, u, v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By taking d [right arrow] [infinity] in Theorem 2.7, we obtain the main result of this section.

Theorem 2.8 The generating function [F.sub.211] (x, y, u, v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2.5 The case [tau] = 121

In this section, we find an explicit formula for the generating function [F.sub.121;d]. Firstly, we find a recurrence relation for the generating function [F.sub.121;d](a). By the definitions, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

Now, we express [F.sub.121;d](ak) with a < k [less than or equal to] d in terms of generating functions [F.sub.121;d](j). Again, by definitions, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By (12), we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which gives

[F.sub.121;d](ak) = [x.sup.a]y[F.sub.121;d](k) + [x.sup.a+] y ([u.sup.a]v - 1) [F.sub.121;d](a),

for any a + 1 [less than or equal to] k [less than or equal to] d. Therefore, by substituting into (12), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which, by (1), implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By solving for [F.sub.121;d](a), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By substituting into (1), we derive our main result.

Theorem 2.9 The generating function [F.sub.121;d](x, y, u, v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2.6 The case [tau] = 212

In this section, we find an explicit formula for the generating function [F.sub.212;d]. Firstly, we find a recurrence relation for the generating function [F.sub.212;d](a). By the definitions, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

Now, we express F212;d(ak) with a > k [greater than or equal to] 1 in terms of generating functions [F.sub.212;d](j). Again, by definitions, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By (13), we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which gives

[F.sub.212;d](ak) = [x.sup.a]y[F.sub.212;d](k) + [x.sup.a+k][y.sup.2]([u.sup.a]v - 1)[F.sub.212;d](a),

for any 1 [less than or equal to] k [less than or equal to] a - 1. Therefore, by substituting into (13), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which, by (1), implies

[F.sub.212;d](a) = [x.sup.a]y[F.sub.212;d] + [x.sup.a]y ([u.sup.a]v - 1) [[x-[x.sup.a]]/[1-x]] [F.sub.212;d](a).

By solving for [F.sub.212;d](a), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By substituting into (1), we derive the following result.

Theorem 2.10 The generating function F212;d(x, y, u, v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By taking d [right arrow] [infinity] in Theorem 2.10, we obtain the main result of this section.

Theorem 2.11 The generating function F212 (x, y,u,v) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Next we recover some of the results presented in [7]. Note that Theorem 2.2 for u = 1 gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as given in the first part of Theorem 2.2 in [7]. Also Theorem 2.6 for u = 1 gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as given in the second part of Theorem 2.2 in [7]. Next we recover some basic results related to compositions of n with k parts and compositions of n, respectively. Substituting u = 1, v = 1 in Theorem 2.2 (as well as in all main Theorems of each section) gives

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is the generating function for a composition of n with k parts. Moreover, setting y = 1 in the last equation one obtains the generating function for the number of compositions of n, that is [[1-x]/[1-2x]].

3 The mean of [sfl.sub.[tau]]([pi])

This section is divided into several subsections. In each subsection we discuss the results of the average value of [sfl.sub.[tau]]([pi]) over all compositions of n as [pi] ranges over the set {112,121,122,211, 212, 221}. In what follows, we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to be 1 if 3 divides n and 0 otherwise.

3.1 The case [tau] =112

In this subsection, we find the average of the sum of the values of first letters of the occurrences of the subword 112 in all compositions of n.

Corollary 3.1 The mean of [sfl.sub.112], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: By differentiating the generating function [F.sub.112](x, y,u, 1) with respect to u and evaluating it at u = 1, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which implies that the mean of [sfl.sub.112], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

as claimed.

For example, the generating function for the total values of [sfl.sub.112] taken over all compositions of n is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.2 The case [tau] = 122

In this subsection, we find the average of the sum of the values of first letters of the occurrences of the subword 122 in all compositions of n.

Corollary 3.2 The mean of [sfl.sub.122], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: By differentiating the generating function [F.sub.122](x,y,u, 1) with respect to u and evaluating it at u = 1, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which implies that the mean of [sfl.sub.122], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] []

For example, the generating function for the total values of [sfl.sub.122] taken over all compositions of n is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.3 The case [tau] = 221

In this subsection, we find the average of the sum of the values of first letters of the occurrences of the subword 221 in all compositions of n.

Corollary 3.3 The mean of [sfl.sub.221], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: By differentiating the generating function F221(x,y, u, 1) with respect to u and evaluating it at u = 1, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which implies that the mean of [sfl.sub.221], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which completes the proof. []

For example the generating function for the total values of sfl221 taken over all compositions of n is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.4 The case [tau] = 211

In this subsection, we find the average of the sum of the values of first letters of the occurrences of the subword 211 in all compositions of n.

Corollary 3.4 The mean of [sfl.sub.211], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: By differentiating the generating function [F.sub.211](x, y, u, 1) with respect to u and evaluating it at u = 1, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which implies that the mean of [sfl.sub.211], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which completes the proof. []

For example, the generating function for total values of [sfl.sub.211] taken over all compositions of n is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.5 The case [tau] = 121

In this subsection, we find the average of the sum of the values of first letters of the occurrences of the subword 121 in all compositions of n.

Corollary 3.5 The mean of [sfl.sub.121], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: By differentiating the generating function [F.sub.121;d](x, y,u, 1) with respect to u and evaluating it at u = 1, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, by taking y = 1 and d [right arrow] [infinity], we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which, by Corollary 3.1, completes the proof. []

3.6 The case [tau] = 212

In this subsection, we find the average of the sum of the values of first letters of the occurrences of the subword 212 in all compositions of n.

Corollary 3.6 The mean of [sfl.sub.212], taken over all compositions of n, is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: By differentiating the generating function [F.sub.212](x, y,u, 1) with respect to u and evaluating it at u = 1, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, by taking y = 1, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which, by Corollary 3.3, completes the proof. []

Remark 3.1 Note that the total values of [sfl.sub.121] (resp. sfl212) taken over all compositions of n equals the total values of [sfl.sub.112] (resp. [sfl.sub.221]) taken over all compositions of n. However we failed to prove these facts directly.

We end this paper by showing the possible directions this work can be extended. In our future work will try to cover 3-letters patterns in [S.sub.3] = {123,132, 213,231,312, 321}. Also, we will try to obtain results related to studied statistics for other families of compositions, such as: Carlitz compositions, Palindromic compositions, Carlitz palindromic compositions, k-Carlitz compositions and so on.

Acknowledgements

Authors would like to thank the anonymous referees for thoughtful suggestions.

References

[1] M. Archibald and A. Knopfmacher, The largest missing value in a composition of an integer, Discrete Math. 311 (2011) 723-731.

[2] W. Asakly and T. Mansour, Enumeration of compositions according to the sum of the values of the first letters of the occurrences of a 2-letter pattern, Linear Alg. and its Appl. 449 (2014) 43-59.

[3] C. Brennan and Knopfmacher, The distribution of ascents of size d or more in compositions, Discrete Math. Theor. Comput. Sci. 11 (2009) 1-10.

[4] C. Brennan and A. Knopfmacher, The first ascent of size d or more in compositions, Discrete Math. Theor. Comput. Sci. Proc. AG, Nancy, 2006.

[5] S. Heubach and T. Mansour, Counting rises, levels, and drops in compositions, Integers 5 (2005) Article A11.

[6] S. Heubach and T. Mansour, Combinatorics of compositions and words, CRC Press, Boca Raton, FL, 2010.

[7] S. Heubach and T. Mansour, Enumeration of 3-Letter Patterns in Compositions, Combinatorial Number Theory in Celebration of the 70-th Birthday of Ronald Graham, 2007, 243-264, de Gruyter.

[8] T. Mansour and B.O. Sirhan, Counting l-letter subwords in compositions, Discr. Math. Theor. Comput. Sci. 8 (2006) 285-298.

Armend Sh. Shabani

Rexhep Gjergji

Department of Mathematics, University of Prishtina

received 5th May 2015, revised 21st June 2015, 7th Apr. 2016, accepted 11th Apr. 2016.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Shabani, Armend Sh.; Gjergji, Rexhep
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:4593
Previous Article:Planar graphs with [DELTA] [greater than or equal to] 7 and no triangle adjacent to a [C.sub.4] are minimally edge and total choosable.
Next Article:Permutations of context-free, ET0L and indexed languages.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters