Toufik Mansour

Enumeration of words by the sum of differences between adjacent letters

Keywords: k-ary words, statistics, generating functions, kernel method, Chebyshev polynomials

We consider the sum u of differences between adjacent letters of a word of n letters, chosen uniformly at random from a given alphabet. This paper obtains the enumerating generating function for the number of such words with respect to the sum u, as well as explicit formulas for the mean and variance of u.

Introduction

Given a totally ordered set of k letters [k] = {1, 2, . . . , k}, we refer to the elements of [k] n as k-ary words of length n, or just words. Let σ be any k-ary word of length n, we define u(σ) = u n,k (σ) to be the sum of the differences between each pair of adjacent letters of σ, that is,

u(σ) = n-1 i=1 |σ i -σ i+1 |,
and u is the total variation (or just variation) of σ. For example, the total variation of the word σ = 1121415221 ∈ [START_REF] Curtis | Darts and hoopla board design[END_REF] 10 is u(σ) = 0 + 1 + 1 + 3 + 3 + 4 + 3 + 0 + 1 = 16.

Several authors have studied the statistic u(σ) in different contexts. For example, Curtis [START_REF] Curtis | Darts and hoopla board design[END_REF] discussed the problem of finding a word σ = σ 1 σ 2 • • • σ n over the alphabet {a 1 , a 2 , . . . , a k } which maximizes the risk function n j=1 |σ i -σ i-1 |, where σ 0 = σ n . Chao and Liang [START_REF] Chao | Arranging n distinct numbers on a line or a circle to reach extreme total variations[END_REF] studied the permutations of n distinct letters arranged on a circle or a line and found the arrangements that maximize the risk function. Later, Cohen and Tonkes [START_REF] Cohen | Dartboard arrangements[END_REF] (see also [START_REF] Curtis | Darts and hoopla board design[END_REF][START_REF] Liao | Arranging numbers on circles to reach maximum total variations[END_REF]) analyzed optimal permutations for multisets.

Motivated by the above results, we pose the following problem:

• Given a nonnegative integer m and a multiset of n letters M = {a 1 , a 2 , . . . , a n }, enumerate all permutations σ of M with u(σ) = m. This paper addresses the restricted case of the problem in which σ ∈ [k] n for a fixed integer k > 0.

More precisely, let f k (n, m) be the number of k-ary words σ of length n with u(σ) = m. Clearly,

u(σ) ≤ u(1k1k • • • ) = (n -1)(k -1) for any σ ∈ [k] n .
We denote the correspond generating function by F k (n; q), that is,

F k (n; q) = (n-1)(k-1) m=0 f k (n, m)q m = σ∈[k] n q u(σ) ,
and define

F k (x, q) = n≥0 F k (n; q)x n = n≥0 x n σ∈[k] n q u(σ) .
In the next section we find two different expressions for the bivariate generating function F k (x, q). The first expression is obtained by using the scanning element algorithm as described in [START_REF] Firro | Restricted k-ary words and functional equations[END_REF] which it is given by the following result.

Theorem 1.1 The bivariate generating function F k (x, q) is given by

F k (x, q) = 1 + k(1 -q)x 1 -q -x(1 + q) - 2x 2 q 1-t k (q) 1-t(q) (1 -q -x(1 + q)) 1 -x 1-qt k (q) 1-qt(q)
, where

t(q) = 1 -x + q 2 (1 + x) -(1 -q)(1 + q)(1 + q -x(1 -q))(1 -q -x(1 + q)) 2q .
A crucial device in proving Theorem 1.1 is the idea of a new statistic on the set of k-ary words of length n defined as follows. The complete total variation (or just complete variation)

of σ = σ 1 σ 2 • • • σ n ∈ [k] n is defined as v(σ) = v n,k (σ) = u(σ) + σ 1 . For example, the complete variation of the word σ = 1121415221 ∈ [5] 10 is v(σ) = 1 + u(σ) = 17.
The bivariate generating function F k (x, q) can be expressed in terms of Chebyshev polynomials of the second kind, see Theorem 1.2. Chebyshev polynomials of the second kind are defined by U r (cos θ) = sin(r+1)θ sin θ

. For example, U 0

(x) = 1, U 1 (x) = 2x, U 2 (x) = 4x 2 -1, and in general, U r (x) = 2xU r-1 (x) -U r-2 (x), r = 0, ±1, ±2, . . . . (1.1)
Chebyshev polynomials were invented for the needs of approximation theory, but are also widely used in various other branches of mathematics, including algebra, combinatorics, and number theory (see [START_REF] Th | Chebyshev polynomials. From approximation theory to algebra and number theory[END_REF]).

Theorem 1.2 The bivariate generating function F k (x, q) is given by

F k (x, q) = 1 + k i=1 (x i -qx i-1 ),
where

x i = x(1 -q) q k-1 j=i U i-1 (ξ/2) j-1 s=0 U s (ξ/2) U j-1 (ξ/2)U j (ξ/2) + xU i-1 (ξ/2) U k-1 (ξ/2) U k-1 (ξ/2) + (1 -q)/q k-1 j=0 U j (ξ/2) U k (ξ/2) -q(1 + x)U k-1 (ξ/2)
,

and ξ = 1+q 2 -x(1-q 2 ) q . Theorem 1.2 with q = 1 (ξ = 2, U j (1) = j + 1 and U k (ξ/2) -q(1 + x)U k-1 (ξ/2) = 1 -kx) gives that x i = ix 1-kx and F k (x, 1) = 1 + kx 1-kx = 1 1-kx
, which is the generating function for all k-ary words of length n. Moreover, using [7, Theorem IX.9 (Meromorphic schema)] with ρ = 1 k we obtain that the random variable u n,k with probability generating function F k (n;q) k n after standardization, converges in distribution to a Gaussian variable, with a speed of convergence that is O(1/ √ n), and the mean and the standard deviation of u n,k are asymptotically linear in n.

In our next theorem, we determine the mean and the variance of the total variation exactly.

Theorem 1.3 The mean and the variance of the total variation of a uniformly chosen k-ary word of length n are given by (n -1)(k + 1)(k -1) 3k ,

and (k -1)(k + 1)(k 2 (6n -7) + 2(3n -1)) 90k 2 ,
respectively.

We present two proofs of the above theorem. The first proof relies on Theorem 1.1, while the second consists of an elegant derivation based solely on counting special types of subsets in [k] n and the additivity of the expected value operator, see Section 3.

Proof of Theorems 1.1 and 1.2

In this section we establish the formula for the generating function F k (x, q) asserted in Theorems 1.1 and 1.2. To this end, let

F k (x, q | i 1 i 2 • • • i s ) denote the generating function for the number of k-ary words σ = σ 1 σ 2 • • • σ n enumerated with respect to the variation statistic u(σ) such that σ 1 σ 2 • • • σ s = i 1 i 2 • • • i s , s ∈ [n], F k (x, q | i 1 i 2 • • • i s ) = n≥0 σ=i1i2•••isσ ′ ∈[k] n
x n q u(σ) .

Our first result is a recurrence relation for the functions

F k (x, q | i). Lemma 2.1 For any i = 1, 2, . . . , k, F k (x, q | i) = x + x k j=1 q |i-j| F k (x, q | j).
Proof: From the definitions we can state that

F k (x, q | i) = x + k j=1 F k (x, q | ij) and F k (x, q | ij) = q |i-j| F k (x, q | j). Thus, F k (x, q | i) = x + x k j=1 q |i-j| F k (x, q | j), as claimed. ✷
Now let us solve the recurrence relation in the statement of Lemma 2.1 either by using kernel method technique (see [START_REF] Banderier | Generating functions for generating trees[END_REF][START_REF] Firro | Restricted k-ary words and functional equations[END_REF][START_REF] Hou | Kernel method and linear recurrence system[END_REF]) or by using tridiagonal matrix algorithm (see [17]).

Kernel method technique

In order to solve the recurrence relation in the statement of Lemma 2.1, we define

F k (x, q; t) = 1 + k i=1 F k (x, q | i)t i-1 .
Clearly, F k (x, q; 1) = F k (x, q). So, in order to specify F k (x, q), we need to study a functional relation for F k (x, q; t).

Lemma 2.2 F k (x, q; t) = 1 + x 1-t k 1-t -1-q k t k 1-qt + x 1-qt F k (x, q; t) -q k t k F k (x, q; 1/q) + x 1-t/q (F k (x, q; q) -F k (x, q; t)) .
Proof: Lemma 2.1 gives

F k (x, q | i) = x + x i j=1 q i-j F k (x, q | j) + x k j=i+1 q j-i F k (x, q | j),
for all i = 1, 2, . . . , k. Multiplying through by t i-1 and summing over i, i ∈ [k], we obtain

k i=1 F k (x, q | i)t i-1 = x k i=1 t i-1 + k i=1 t i-1 k j=1 q |j-i| F k (x, q | j) = x 1-t k 1-t + x k j=1 t j-1 1-(qt) k+1-j 1-qt F k (x, q | j) + x k j=1 q j-1 1-(t/q) j-1 1-t/q F k (x, q | j). Using F k (x, q; t) = 1 + k j=1 t j-1 F k (x, q | j) we get that F k (x, q; t) -1 = x 1-t k 1-t + x 1-qt F k (x, q; t) -1 -q k t k F k (x, q; 1/q) + q k t k + x 1-t/q (F k (x, q; q) -F k (x, q; t)) ,
which completes the proof. ✷

We note the following useful restatement of Lemma 2.2:

1 -x 1-qt + x 1-t/q F k (x, q; t) = 1 + x 1-t k 1-t -1-q k t k 1-qt -xq k t k 1-qt F k (x, q; 1/q) + x 1-t/q F k (x, q; q). (2.1)
We need a result relating F k (x, q; 1/q) and F k (x, q; q). We claim that

F k (x, q; t) -1 = t k-1 (F k (x, q; 1/t) -1) . (2.2)
To see this, define the complement of

σ = σ 1 σ 2 • • • σ n to be σ ′ = (k +1-σ 1 )(k +1-σ 2 ) • • • (k +1-σ n ).
Then it is immediate from the definitions that σ ′ is a k-ary word of length n with u(σ ′ ) = u(σ) and

σ ′ 1 = k + 1 -σ 1 . Hence, t k-1 (F k (x, q; 1/t) -1) = t k-1 n≥1 k i=1 σ=iθ∈[k] n x n (1/t) i-1 q u(σ) = n≥1 k i=1 σ=iθ∈[k] n x n t k-i q u(σ) = n≥1 k i=1 σ ′ =(k+1-i)θ ′ ∈[k] n x n t i-1 q u(σ ′ ) = F k (x, q; t) -1,
as claimed. Equation (2.2) for t = q gives that F k (x, q; 1/q) = 1 + 1 q k-1 (F k (x, q; q) -1). Hence, (2.1) reduces to

1 -x 1-qt + x 1-t/q F k (x, q; t) = 1 + x 1-t k 1-v -1-q k t k 1-qv -xq k t k 1-qt (1 + 1 q k-1 (F k (x, q; q) -1)) + x 1-t/q F k (x, q; q),
which is equivalent to

1 -x 1-qt + x 1-t/q F k (x, q; t) = 1 + x 1-t k 1-t -1-qt k 1-qt -xqt k 1-qt -x 1-t/q F k (x, q; q), (2.3)
This type of functional equation can be solved using the kernel method (see [START_REF] Banderier | Generating functions for generating trees[END_REF][START_REF] Hou | Kernel method and linear recurrence system[END_REF]). In this case, if we assume that

t = t(q) = 1 -x + q 2 (1 + x) -(1 -q)(1 + q)(1 + q -x(1 -q))(1 -q -x(1 + q)) 2q , then (2.3) gives F k (x, q; q) = 1 + x 1-t k (q) 1-t(q) -1-qt k (q) 1-qt(q) xqt k (q) 1-qt(q) - x 1-t(q)/q = 1 + x 1-t k (q) 1-t(q) 1 -x 1-qt k (q) 1-qt(q) . ( 2

.4)

We can formulate the following theorem. Let G k (x, q) be the generating function for the number of k-ary

words σ = σ 1 σ 2 • • • σ n of length n having (complete variation) v(σ) = m, that is, G k (x, q) = n≥0 x n σ∈[k] n q v(σ) .
Theorem 2.3 The generating function G k (x, q) = 1 -q + qF k (x, q; q) is given by

1 + qx 1-t k (q) 1-t(q) 1 -x 1-qt k (q) 1-qt(q)
, where

t(q) = 1 -x + q 2 (1 + x) -(1 -q)(1 + q)(1 + q -x(1 -q))(1 -q -x(1 + q)) 2q .
Proof: Using the definition v(σ) = σ 1 + u(σ), we have that the contribution for nonempty k-ary words in G k (x, q) is q(F k (x, q; q) -1) and the contribution of the empty word in G k (x, q) is 1. Thus G k (x, q) = 1 + q(F k (x, q; q) -1). The rest follows from (2.4). ✷

For example, Theorem 2.3 gives

G 1 (x, q) = 1 + x 1-x q, G 2 (x, q) = 1-x+xq 2 1-x-xq = 1 + x 1-x q + j≥2 x j-1 (1-x) q j , G 3 (x, q) = (1-x) 2 +x(1-x)q-x 2 q 2 +x(1+x)q 3 (1-x) 2 -xq 2 (1+x) = 1 + x 1-x q + j≥0 x j (1+x) j-1 (1-x) 2j q 2j + j≥1 x j (1+x) j (1-x) 2j+1 q 2j+1 .
We are now ready to establish Theorem 1.1.

Proof Proof of Theorem 1.1: By substituting t = 1 in (2.3), we obtain

1 - x(1 + q) 1 -q F k (x, q; 1) = 1 + (k -1)x - 2xq
1 -q F k (x, q; q), which implies

F k (x, q; 1) = 1 -q + (k -1)(1 -q)x 1 -q -x(1 + q) - 2x 1 -q -x(1 + q) (G k (x, q) -1 + q).
Then by applying Theorem 2.3 we obtain the second part of Theorem 1.1. ✷ For example, Theorem 1.1 gives

F 1 (x, q) = 1 1-x , F 2 (x, q) = 1+x-xq 1-x-xq = 1 + 2 j≥0 x j+1 (1-x) j+1 q j , F 3 (x, q) = (1+2x)(1-x)+4x 2 q-x(1+2x)q 2 (1-x) 2 -xq 2 (1+x) = 1+2x 1-x + 2(1 + 2x) j≥1 x j+1 (1+x) j-1 (1-x) 2j+1 q 2j + 4 j≥0 x j+2 (1+x) j (1-x) 2j+2 q 2j+1 .

Tridiagonal matrix algorithm

Let A k = A k (x, q) = (A k (x, q|i, j)) 1≤i,j≤k be the k × k matrix A k (x, q|i, j) = 1 -x, i = j -xq |i-j| , i = j.
Rewriting the equations in the statement of Lemma 2.1 in matrix form we get that

A k    F k (x, q | 1)
. . .

F k (x, q | k)    = x    1 . . . 1    ,
which is equivalent to

B k    x 1 . . . x k    = x      1 -q . . . 1 -q 1      , (2.5)
where

F k (x, q | i) = x i -qx i-1 (here we assume that x 0 = 0) and B k = (b ij ) 1≤i,j≤k is a k × k tridiagonal matrix b ij =        0, |i -j| > 1 -q, |i -j| = 1 1 + q 2 -x(1 -q 2 ), i = j < k 1 -x, i = j = k.
By using the tridiagonal matrix algorithm on (2.5), as described in [17], we get that

x k = d k and x i = d i -c i x i+1 , for all i = k -1, k -2, . . . 1, (2.6)
where

d i =        x(1-q)/q ξ , i = 1 x(1-q)/q+di-1 ξ+ci-1 , 2 ≤ i ≤ k -1 x+qd k-1 1-x+qc k-1 , i = k, c i = -1 ξ , i = 1 -1 ξ+ci-1 , 2 ≤ i ≤ k -1, (2.7)
and ξ = 1+q 2 -x(1-q 2 ) q . Thus, by Equations (1.1) and (2.7) together with induction on i, we obtain that

c i = - U i-1 (ξ/2) U i (ξ/2) , d i =      x(1-q) qUi(ξ/2) i-1 j=0 U j (ξ/2), i < k xU k-1 (ξ/2)+x(1-q)/q P k-1 j=0 Uj (ξ/2) U k (ξ/2)-q(1+x)U k-1 (ξ/2) , i = k. (2.8)
On the other hand, Equation (2.6) together with induction on i = k, k-1, . . . , 1 give that x i = k j=i d j j-1 s=i (-c s ). Thus, by using (2.8) we have that

x i = x(1 -q) q k-1 j=i U i-1 (ξ/2) j-1 s=0 U s (ξ/2) U j-1 (ξ/2)U j (ξ/2) + xU i-1 (ξ/2) U k-1 (ξ/2) U k-1 (ξ/2) + (1 -q)/q k-1 j=0 U j (ξ/2) U k (ξ/2) -q(1 + x)U k-1 (ξ/2)
, for all i = 1, 2, . . . , k. Hence, by using

F k (x, q | i) = x i -qx i-1 , i = 1, 2, . . . , k, together with F k (x, q) = 1 + k i=1 F k (x, q | i), we complete the of Theorem 1.2.
3 Proof of Theorem 1.3

Let [k] n be the set of k-ary words of length n, where we assume that all words occur equally likely. Then

u n,k = u n,k (σ) and v n,k = v n,k (σ) where σ ∈ [k]
n are discrete random variables for the variation and the complete variation that take values 0, 1, . . . , (n -1)(k -1) and 1, 2, . . . , (n -1)(k -1) + k, respectively.

Generating function techniques

As a corollary of Theorem 1.1 we get the following two results.

Theorem 3.1 The mean of the random variables u n,k and v n,k are given by

µ n,k = 1 k n σ∈[k] n u n,k (σ) = (n -1)(k + 1)(k -1) 3k , and
ν n,k = 1 k n σ∈[k] n v n,k (σ) = (k + 1)((2n + 1)k -2(n -1)) 6k .
Proof: After simple algebraic operations, Theorem 2.3 gives

n≥0 ν n,k x n = ∂ ∂q G k (x, q) q=1 = k+1 2 x -k+2 3 x 2 (1 -kx) 2 ,
and Theorem 1.1 gives

n≥0 µ n,k x n = ∂ ∂q F k (x, q) q=1 = 2 k+1 3 x 2 (1 -kx) 2 , which implies that ν n,k = (k+1)((2n+1)k-2(n-1)) 6k and µ n,k = (n-1)(k+1)(k-1) 3k , as claimed. ✷ Theorem 3.2
The variance of the random variables u n,k and v n,k are given by

(k -1)(k + 1)(k 2 (6n -7) + 2(3n -1)) 90k 2 ,
and

(k -1)(k + 1)(12n(k 2 + 1) + k 2 -4) 180k 2 ,
respectively.

Proof: After simple algebraic operations, Theorem 1.1 gives 3 , which implies that the ratio of the second factorial moment of the random variable u n,k by k n is given by

n≥0 µ n,k (µ n,k -1)x n = ∂ 2 ∂q 2 F k (x, q) q=1 = 4x 2 k+1 4 + k 2 +5k-4 10 k+1 3 x -k 3 k+2 5 x 2 (1 -kx)
µ ′ n,k = 1 k n 4k n-2 k+1 4 n 2 + 2k n-3 (k 2 +5k-4) 5 k+1 3 n-1 2 -4k n-3 3 k+2 5 n-2 2
.

Using this expression, the variance of the random variable u n,k is given by

µ ′ n,k + µ n,k -(µ n,k ) 2 = (k-1)(k+1)(k 2 (6n-7)+2(3n-1)) 90k 2 .
Similarly, Theorem 2.3 gives

n≥0 ν n,k (ν n,k -1)x n = ∂ 2 ∂q 2 G k (x, q) q=1
= kx(k-1)(k+1)(30-15kx+6(k 2 -4)x 2 -k(k 2 -4)x 3 90(1-kx) 3 , which implies that the ratio of the second factorial moment of the random variable v n,k by k n is given by ν ′ n,k = (k-1)(k+1)(16k 2 (n+3)+10(k 2 -1)n 2 +26n-12) 90k 2

.

Using this expression, the variance of the random variable v n,k is given by

ν ′ n,k + ν n,k -(ν n,k ) 2 = (k-1)(k+1)(12n(k 2 +1)+k 2 -4) 180k 2
, as required. ✷

Additivity of the expected value operator

In this section, we give an alternative proof of Theorems 3.1 and 3.2 (see Theorem 1.3), which consists of an elegant derivation based solely on counting special types of subsets in [k] n and the additivity of the expected value operator.

In order to do that, let X i = X i (σ), i = 1, 2, . . . , n -1 and σ ∈ [k] n , be the discrete random variable for the absolute difference |σ i -σ i+1 | between values in the i-th and (i+1)-st positions, and X 0 = X 0 (σ) be the discrete random variable for the value of the first letter of σ ∈ [k] n . From the definitions we obtain that

• P (X i = 0) = k n-1 k n = 1 k , • P (X i = m) = 2(k-m)k n-2 k n = 2(k-m) k 2
, for all m = 1, 2, . . . , k -1,

• P (X 0 = m) = 1 k for every m ∈ [k]
, for all m = 1, 2, . . . , k, where P (Y = m) denotes the probability that the discrete random variable Y equals m. Then all X i 's, i = 1, 2, . . . , n -1, have the same distribution and u n,k = n-1 i=1 X i . Thus, the expected value of u n,k is given by E

(u n,k ) = n-1 i=1 E(X i ) = (n -1)E(X 1 ), where E(X 1 ) = k-1 m=0 mP (X 1 = m) = k-1 m=0 2m(k -m) k 2 = (k + 1)(k -1) 3k .
Therefore,

E(u n,k ) = (n -1)(k + 1)(k -1) 3k . ( 3.1)
The discrete random variable v n,k for the complete total variation is given by v n,k = u n,k + X 0 and its expected value equals

E(v n,k ) = E(u n,k ) + E(X 0 ), where E(X 0 ) = k m=1 mP (X 0 = m) = k m=1 m k = k + 1 2 .
Thus, by (3.1) we have that

E(v n,k ) = (n -1)(k + 1)(k -1) 3k + k + 1 2 . ( 3.2)
Hence, Equations (3.1) and (3.2) complete the proof of Theorem 3.1. Now we ready to prove Theorem 3.2. The random variables X i and X j are independent if |i -j| > 1 (that is, the covariance Cov(X i , X j ) equals 0 for all |i -j| > 1), thus the variance of u n,k is given by

V ar(u n,k ) = n-1 i=1 V ar(X i ) + 2 n-2 i=1 n-1 j=i+1 Cov(X i , X j ) = (n -1)V ar(X 1 ) + 2(n -2)Cov(X 1 , X 2 ) with V ar(X 1 ) = E(X 2 1 ) -E(X 1 ) 2 = k-1 m=0 m 2 P (X 1 = m) - (k + 1) 2 (k -1) 2 9k 2 = k-1 m=0 2m 2 (k -m) k 2 - (k + 1) 2 (k -1) 2 9k 2 = (k + 1)(k -1)(k 2 + 2) 18k 2 ,
and

E(X 1 X 2 ) = 2 1≤i≤j≤k j(i -j)(k -i) k 3 + 2 1≤j≤k j 2 (k -j) k 3 + 4 1≤i<j≤k ji(k -i) k 4 = (k + 1)(k -1)(7k 2 -8) 60k 2 ,
where the first sum on first line above corresponds to cases where σ 1 σ 2 σ 3 is an increasing sequence or a decreasing sequence, the second sum corresponds to cases where σ 1 = σ 3 = σ 2 , and the third sum corresponds to the rest of the cases. Hence, by the fact that Cov(X 1 , X 2 ) = E(X 1 X 2 ) -E(X 1 )E(X 2 ) we get that

Cov(X 1 , X 2 ) = E(X 1 X 2 ) -E(X 1 )E(X 2 ) = (k + 1)(k -1)(7k 2 -8) 60k 2 - (k + 1) 2 (k -1) 2 9k 2 = (k + 1)(k -1)(k + 2)(k -2) 180k 2 ,
which implies that V ar(u n,k ) = (n -1) (k+1)(k-1)(k 2 +2) 18k 2

+ 2(n -2) (k+1)(k-1)(k+2)(k-2)

180k 2 = (n -1) (k-1)(k+1)(k 2 +1) 15k 2 -(k-1)(k-2)(k+2)(k+1) 90k 2 , (3.3)
which agrees with Theorem 3.2.

To this end, let us find explicit formula for variance of the discrete random variable v n,k = n-1 i=0 X i . Since the discrete random variables X i and X j are independent if |i -j| > 1, we get that the variance of v n,k is given by V ar(v n,k ) = V ar(X 0 ) + (n -1)V ar(X 1 ) + 2Cov(X 0 , X 1 ) + 2(n -2)Cov(X 1 , X 2 ) = V ar(X 0 ) + 2Cov(X 0 , X 1 ) + V ar(u n,k ) with V ar(X 0 ) = E(X 2 0 ) -E(X 0 ) 2

1365-8050 c 2009

 2009 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Acknowledgements

The author would like to thank Augustine Munagi for reading previous versions of the present paper and for a number of helpful discussions. Also, the author thanks one of the referees that he suggests the probability proof of Theorem 1.3 as described in Section 3.2.

and

where the sums on second line above corresponds to cases where σ 1 σ 2 is an increasing sequence or a decreasing sequence. Therefore,

which completes the proof of Theorem 3.2.


Charlotte Brennan

Arnold Knopfmacher

The distribution of ascents of size d or more in compositions

Keywords: compositions, distributions, generating functions, ascents

A composition of a positive integer n is a finite sequence of positive integers a1, a2, . . . , a k such that a1 + a2 +

Let d be a fixed nonnegative integer. We say that we have an ascent of size d or more if ai+1 ≥ ai + d. We determine the mean, variance and limiting distribution of the number of ascents of size d or more in the set of compositions of n. We also study the average size of the greatest ascent over all compositions of n.

Introduction

A composition of a positive integer n is a finite sequence of positive integers a 1 , a 1 , . . . , a k such that a 1 + a 2 + • • • + a k = n. It is well known that there are 2 n-1 compositions of n. The compositions (denoted by a 1 a 2 a 3 . . . a k ) for n = 1, 2, . . . , 5 are: Let d ≥ 0 be a fixed integer. We say, that we have an ascent of size d or more, whenever a i+1 ≥ a i +d. For example, there are 3 ascents of size 2 or more that occur in the compositions of 5: 14, 113, and 131 .

n
In Sections 2, 3 and 4, respectively, we determine the mean, variance and asymptotic distribution of the number of ascents of size d or more in compositions of n. Ordinary ascents (the cases d = 0 and d = 1) have previously been studied by Carlitz [START_REF] Carlitz | Enumeration of compositions by rises, falls and levels[END_REF] and more recently by Chinn, Heubach and Grimaldi in [START_REF] Chinn | Rises, levels, drops and"+" signs in compositions: extensions of a paper by Alladi and Hoggart[END_REF].

Finally in Section 5 we investigate the maximum value of d for which compositions of n can expect to have an ascent of size d. That is, we find the average value of the largest ascent that occurs in the compositions of n. For example, the compositions of 4 in the table have maximum ascents of sizes 0, 2, 0, 0, 1, 1, 0, 0, respectively, giving an average largest ascent size per composition of 1/2 when n = 4.

We note that the asymptotic expression for the maximum ascent size in Theorem 4 involves a fluctuating function of n of mean zero. A similar phenomenon has been observed when studying averages of certain other statistics for compositions, such as the largest part size [START_REF] Odlyzko | On the compositions of an integer[END_REF] or the number of distinct part sizes ( 8), [START_REF] Hwang | Measures of distinctness for random partitions and compositions of an integer[END_REF].

2 The average number of ascents of size d or more in compositions

For fixed d ≥ 0 we wish to find the average number of ascents of size d or more per composition of n.

We use the "adding-the-slice" technique which was originally used by Flajolet and Prodinger in (4) and more recently, for example, by Knopfmacher and Prodinger in [START_REF] Knopfmacher | On Carlitz compositions[END_REF]. Let j be the value of the last component of the composition with k parts, i.e. a k = j. We proceed from a composition with k parts to a composition with k + 1 parts. We denote by f k (z, u, v) the generating function where z marks the size n, u the value of j and v the number of ascents of size d or more in compositions with k parts.

In moving from a composition with k parts to a composition with k + 1 parts, where a k = j, we have an ascent whenever the new last integer has any value from j + d onwards. This gives the following rule for adding a new part or "slice" to the end of the composition:

u j -→zu + (zu) 2 + (zu) 3 + • • • + (zu) j+d-1 + v (zu) j+d + (zu) j+d+1 + • • • = zu 1 -(zu) j+d-1 1 -zu + v(zu) j+d 1 1 -zu .
This implies that

f k+1 (z, u, v) = zu 1 -zu f k (z, 1, v) - (zu) d 1 -zu f k (z, zu, v) + v(zu) d 1 -zu f k (z, zu, v) = zu 1 -zu f k (z, 1, v) - (1 -v)(zu) d 1 -zu f k (z, zu, v). (2.1) Now define F (z, u, v) := k≥1 f k (z, u, v) . Then summing (2.1) over k ≥ 1 gives F (z, u, v) -f 1 (z, u, v) = zu 1 -zu F (z, 1, v) - (1 -v)(zu) d 1 -zu F (z, zu, v) , so that F (z, u, v) = zu 1 -zu F (z, 1, v) + zu 1 -zu - (1 -v)(zu) d 1 -zu F (z, zu, v) ,
where we have used

f 1 (z, u, v) = zu + (zu) 2 + (zu) 3 + • • • = zu 1 -zu .
At this stage we iterate the recursion for F (z, u, v).

F (z, u, v) = zu 1 -zu F (z, 1, v) + zu 1 -zu - (1 -v)(zu) d 1 -zu × × z 2 u 1 -z 2 u F (z, 1, v) + z 2 u 1 -z 2 u - (1 -v)(z 2 u) d 1 -z 2 u F (z, z 2 u, v) = zu 1 -zu - (1 -v)z 2 u(zu) d (1 -zu)(1 -z 2 u) [F (z, 1, v) + 1] + (1 -v) 2 (zu) d (z 2 u) d (1 -zu)(1 -z 2 u) × × z 3 u 1 -z 3 u F (z, 1, v) + z 3 u 1 -z 3 u - (1 -v)(z 3 u) d 1 -z 3 u F (z, z 3 u, v) = zu 1 -zu - (1 -v)z 2 u(zu) d (1 -zu)(1 -z 2 u) + (1 -v) 2 z 3 u(zu) d (z 2 u) d (1 -zu)(1 -z 2 u)(1 -z 3 u) [F (z, 1, v) + 1] - (1 -v) 3 (zu) d (z 2 u) d (z 3 u) d (1 -zu)(1 -z 2 u)(1 -z 3 u) F (z, z 3 u, v).
We keep iterating, noting that F (z, z m u, v) → 0 as m → ∞ for |z| < 1 2 and u, v in a suitable small neighbourhood of 1, and put u = 1 to obtain

F (z, 1, v) = i≥1 (-1) i-1 z i (1 -v) i-1 z d( i 2 ) (1 -z)(1 -z 2 ) • • • (1 -z i ) [F (z, 1, v) + 1] . (2.2)
By adding the term 1 for the empty composition we obtain the bivariate generating function for compositions according to the number of ascents of size d or more as

F (z, v) := 1 + F (z, 1, v) = 1 1 -τ (z, v) , (2.3)
where

τ (z, v) := i≥1 (-1) i-1 z i (1 -v) i-1 z d( i 2 ) (1 -z)(1 -z 2 ) • • • (1 -z i ) . (2.4)
The expected value of the number of ascents of size d or more is

[z n ] ∂F (z,v) ∂v v=1 2 n-1
. For this we shall need

τ (z, 1) = i≥1 (-1) i-1 z i (1 -v) i-1 z d( i 2 ) (1 -z)(1 -z 2 ) • • • (1 -z i ) v=1 = z 1 -z , (2.5)
and ∂τ (z, v) ∂v

v=1 = i≥2 (-1) i z i (i -1)(1 -v) i-2 z d( i 2 ) (1 -z)(1 -z 2 ) • • • (1 -z i ) v=1 = z 2+d (1 -z)(1 -z 2 ) . (2.6)
In particular, the generating function for all compositions is F (z, 1) =

1 1-τ (z,1) = 1-z 1-2z . Now ∂F (z, v) ∂v v=1 = ∂τ (z,v) ∂v (1 -τ (z, v)) 2 v=1 = z 2+d (1 + z)(1 -2z) 2 = z d 1 9(1 + z) + 1 6(1 -2z) 2 - 5 18(1 -2z)
.

So that

[z n ] ∂F (z, v) ∂v v=1 = (-1) n-d 9 + (n -d + 1)2 n-d 6 - 5 2 n-d 18 = (-1) n-d 9 + (3n -3d -2)2 n-d 18 .
After dividing by 2 n-1 , the total number of compositions of n, we have Theorem 1 The expected number of ascents of size d or more in the compositions of n is

E(n) := 2 -d 9 (3n -3d -2) + 2 9 (-1) n-d 2 n , for n ≥ d.
Hence for fixed d, as n → ∞,

E(n) = 2 -d 3 n + O(1) .
Previously Chinn, Heubach and Grimaldi found the number of ascents for d = 0 and d = 1 in (2). The case d = 0 corresponds to the number of rises plus the number of levels, whereas d = 1 corresponds to the number of rises.

Variance of the number of ascents of size d or more in compositions

To find the variance we first need to compute

∂ 2 F (z,v) ∂v 2
v=1 . In addition to formulas (2.3) to (2.6) from Section 2 we require

∂ 2 τ (z, v) ∂v 2 v=1 = i≥3 (-1) i-1 z i (i -1)(i -2)(1 -v) i-3 z d( i 2 ) (1 -z)(1 -z 2 ) • • • (1 -z i ) v=1 = 2z 3(1+d) (1 -z)(1 -z 2 )(1 -z 3 )
.

Then ∂ 2 F (z, v) ∂v 2 v=1 = (1 -τ ) ∂ 2 τ (z,v) ∂v 2 + 2τ ′ 2 (1 -τ ) 3 v=1 .
Computing the nth coefficient of the second derivative amounts to expanding and combining binomial series. Finally, after adding the expectation and subtracting the square of the expectation we find Theorem 2 The variance of the expected number of ascents of size d or more in the compositions of n is

V(n) := 2 -d -2 9 + n 3 - d 3 + 2 -2d
α(n) =      26 147 if n = 3m, - 4
147 if n = 3m -2, - 22
147 if n = 3m -1, for m ∈ N.
For fixed d we have

V(n) ∼ n 2 -d 3 -2 -2d 13 27 + 2d 9 + 2 -3d 8 21 as n → ∞ .

Limiting distribution

We are interested in finding the limiting distribution of our random variable. We make use of Theorem IX.9 from Flajolet and Sedgewick [START_REF] Flajolet | Analytic Combinatorics[END_REF]. A short version is as follows: Let F (z, u) be a bivariate function that is bivariate analytic at (z, u) = (0, 0) and has nonnegative coefficients there. Assume that F (z, 1) is meromorphic in z ≤ r with only a simple pole at z = ρ for some positive ρ < r. Then, under further conditions stated in [START_REF] Flajolet | Analytic Combinatorics[END_REF], the random variable with probability generating function

p n (u) = [z n ]F (z, u) [z n ]F (z, 1)
converges in distribution to a Gaussian variable with a speed of convergence that is O(n -1/2 ).

Let us introduce the notation

c i,j := ∂ i+j ∂z i ∂u j C(z, u) (ρ,1) . ( 4.1)
From Theorem IX.9 we need to show that

c 0,1 c 1,0 = 0. (4.2)
In addition, we must show that

ρc 2 1,0 c 0,2 -ρc 1,0 c 1,1 c 0,1 + ρc 2,0 c 2 0,1 + c 2 0,1 c 1,0 + c 0,1 c 2 1,0 ρ = 0. (4.3)
For our specific problem

F (z, v) = 1 1 -τ (z, v) ≡ B(z, v) C(z, v) , so that C(z, v) = 1 - i≥1 (-1) i-1 z i (1 -v) i-1 z d( i 2 ) (1 -z)(1 -z 2 ) • • • (1 -z i )
.

We have ρ(1) = ρ = 1 2 and using (4.1),

c 0,1 = - 2 1-d 3 , c 1,0 = -4, c 1,1 = - 3d + 11 9 2 2-d , c 0,2 = - 2 4-3d 21 , c 2,0 = -16.
We are now in a position to check the conditions listed in the theorem. Equation (4.2) is satisfied since Remark In Flajolet and Sedgewick [START_REF] Flajolet | Analytic Combinatorics[END_REF] it is also shown that under the conditions of Theorem IX.9, the mean µ n and variance σ 2 n are of the form

c 0,1 c 1,0 = 8 2 -d 3 = 0. Equation (4.3) is equivalent to
µ n = m ρ(1) ρ(u) n + O(1), σ 2 n = v ρ(1) ρ(u) n + O(1),
where

m(f ) = f ′ (1) f (1) and v(f ) = f ′′ (1) f (1) + f ′ (1) f (1) - f ′ (1) f (1) 2 .
These asymptotic expressions are easily checked to be in agreement with the exact results for the mean and variance found previously in Theorems 1 and 2.

Size of the maximum ascent

Given a composition a 1 a 2 . . . a k of n we shall study the size of the maximum ascent, that is, the parameter X where

X := max{a i+1 -a i | 1 ≤ i < k and a i+1 ≥ a i } .
We assign a value of 0 if no pair of consecutive integers satisfies this condition. The mean value of X is given by the expression

n d=0 P(X > d) = n d=0 (1 -P(X ≤ d)) .
Therefore for each fixed d we need to compute the probability that a composition of n has maximum ascent X ≤ d.

We already know the generating function for compositions with no ascents of size d or more, which we will denote by F d (z). For this we use (2.3) with d + 1 instead of d and v = 0, giving

F d+1 (z) := 1 1 -τ (z, 0) = 1 1 -i≥1 (-1) i-1 z i+(d+1) ( i 2 ) (1-z)(1-z 2 )•••(1-z i )
.

We want the generating function of compositions with X ≤ d . This is equivalent to the generating function of the compositions with no ascent of size d + 1 or more, which is F d+1 (z). We now need to study the dominant poles, ρ d , of F d+1 (z), that is, the dominant zeros of

1 - i≥1 (-1) i-1 z i+(d+1)( i 2 ) (1 -z)(1 -z 2 ) • • • (1 -z i ) = 0 . (5.1)
We follow the approach used by Gourdon and Prodinger in [START_REF] Gourdon | A generating function approach to random subgraphs of the n-cycle[END_REF], which is also analogous to the one found in [START_REF] Knuth | The average time for carry propagation[END_REF]. Now for |z| ≤ 3 5 , say, using the first two terms of the series above, the root ρ d above can be approximated by the smallest positive root of

1 - z 1 -z + z d+3 (1 -z)(1 -z 2 ) + O(z 3d ) = 0 ,
since the omitted terms in (5.1) are O z 3d . This error will be majorized by subsequent O terms below. That is we want the root of

1 -2z + z d+3 1 -z 2 + O(z 3d ) = 0 .
The bootstrapping method gives a suitable approximation to ρ d . Let

ρ d := 1 2 + ε d , then 1 -2 1 2 + ε d + 4 3 2 -d-3 = O 3 5 3d + O d 2 2d
, from which we find

ε d = 2 -d 12 + O d 2 2d as d → ∞.
As F d+1 (z) has a simple pole at ρ d , and by means of Rouche's Theorem, see IX. It follows that

[z n ]F d+1 (z) = [z n ] A d 1 -z/ρ d + O 4 3 n with A d = 1 ρ d dτ (z,0) dz z=ρ d = 2 + O(2 -d ) dτ (z,0) dz z=ρ
, where from (2.4) as d → ∞ dτ (z, 0)

dz z=ρ = ∂ ∂z i≥1 (-1) i-1 z i+(d+1)( i 2 ) (z; z) i z=ρ = z (1 -z) 2 + O(z d ) z=ρ = 4 + O(2 -d ) . Therefore as d → ∞, A d = 1 2 + O(2 -d ) .
Let us now restrict our attention to those d for which n -3 ≤ 2 -d ≤ log n n . The probability that X ≤ d is then approximated as n → ∞ by

A d ρ -n d = A d 1 2 + 2 -d 12 + O d 2 2d -n = 2 n-1 exp - 2 -d n 6 1 + O 2 -d ) + O n d 2 -2d = 2 n-1 exp - 2 -d n 6 1 + O log 3 n n .
So after dividing by 2 n-1 we have for n → ∞ and

n -3 ≤ 2 -d ≤ log n n , P(X ≤ d) = exp - n 2 d 6 1 + O log 3 n n . (5.2)
Turning now to smaller values of d ≥ 1, that is, d such that 2 -d > log n n , a similar computation shows that (5.2) remains valid in this range, although now the probabilities P(X ≤ d) are small, since for such d, exp -n

2 d 6 = O( 1 n ) as n → ∞.
Finally we must consider larger values of d ≤ n that is, d for which n -3 > 2 -d , or equivalently, d ≥ 3 log 2 n. In this range we find that

P(X ≤ d) = 2 n-1 exp - 2 -d n 6 1 + O 1 n 2 . ( 5.3)
In view of the O estimates in (5.2) and (5.3) we may deduce that the mean value of X satisfies

E max (n) := n d=0 (1 -P(X ≤ d)) = n d=0 1 -exp - n 2 d 6 1 + O log 4 n n as n → ∞.
We now use the Mellin transform, (see (3)), to estimate the function

f (t) = d≥0 1 -exp - t 2 d 6 as t → ∞. The Mellin transform of f (t) is f * (s) = - d≥0 2 d 6 s Γ(s) = - Γ(s) 6 s 1 -2 s for -1 < ℜs < 0 .
Next we apply the Mellin inversion formula to recover f (t):

f (t) = - 1 2πi -1 2 +i∞ -1 2 -i∞ Γ(s) 6 s 1 -2 s t -s ds .
We then shift the line of integration to the right and collect the (negative) residues at s = 2kπi L where k ∈ Z and L = log 2.

f (t) = k≥0 Res Γ(s) 6 s 1 -2 s t -s s= 2kπi L + 1 2πi 1 2 +i∞ 1 2 -i∞ Γ(s) 6 s 1 -2 s t -s ds .
To evaluate the residue at the double pole s = 0, we need the expansion of the terms in the integrand to two terms as s → 0, (here γ denotes Euler's constant), Γ(s) ∼ 1 s -γ ,

6 s ∼ 1 + s log 6 , t -s ∼ 1 -s log t , 1 1 -2 s ∼ 1 2 - 1 sL .
Hence the (negative) residue at s = 0 is

[s -1 ] 1 2 - 1 sL (1 + s log 6) 1 s -γ (1 -s log t) = log 2 t - 1 2 -log 2 3 + γ L .
For the residue at s = 2kπi L for k = 0, let ε = s -2kπi L we have

[ε -1 ]Γ 2kπi L t 6 -2kπi L -1 εL = - 1 L Γ 2kπi L t 6 -2kπi L .
The remainder integral 1 2πi 1 2 +i∞ 1 2 -i∞ is of smaller order, so we have found Theorem 4 The mean value of the size of the greatest ascent in the compositions of n satisfies as n → ∞,

E max (n) ∼ log 2 n - 1 2 -log 2 3 + γ L -δ log 2 n 6
where δ(x) is a continuous periodic function of mean zero, period one and small amplitude with Fourier series

δ(x) = 1 L k =0 Γ - 2kπi L e 2kπix .
Computations show that δ(x) < 1.

Theorem 3 2 n

 32 non-negative integer values of d. Thus we deduce The distribution of the number of ascents of size d or more in compositions of n converges to a Gaussian distribution with a speed of convergence of O(n -1/2 ) with the mean µ n and the variance σ are as given in Theorems 1 and 2.

6 .2 in ( 5 ), by comparing | 1 F 4 , we see that 1 F

 65141 d+1 (z) | with |1 -z 1-z | on the circle |z| = 3 d+1 (z) has no other zeros in |z| ≤ 3/4.

7 × 10 - 6 , 2 n 6 ) 6 Fig. 1 :(log 2 n 6 )

 7106266126 Fig. 1: δ(log 2 n 6 ) for 1 ≤ n ≤ 100

† This material is based upon work supported by the National Research Foundation under grant number 2053740 1365-8050 c 2009


Frederic Wolff

Loria BP 239 54506 Vandoe;Fee-les-Nancy wolff@loria.fr LaurefLrt;mary BP 239 54506 Vandoyn;z-les-Nancy romary@loria.fr

REFERRING GESTURES IN MULTIMODAL INTERFACES

Multimodal interfaces offer to users different ways to express their intentions using the most appropriate means. For instance, to refer to the object involved in the mentioned action, the difficulty of naming determines the modality (speech or/and gesture) used to access the referents as shown by De Angeli. However analysis of referring gestures remains based on simple principles which constraint users' gestural expression to unnatural production rules. Our experimental study has shown that the variability of natural gestures is governed by visual context [l]. In this article, we present a contextual modelling of the analysis of spontaneous referring gestures used in multimodal interfaces. So it becomes possible to cope with the designations' diversity and offer a wider freedom of expression for the user.

REFERRING GESTURE AND VISUAL PERCEPTION

Various features of referring gestures are directly determined by the perceptual organization of the visual scene. Our corpus of multimodal dialogues recorded during Wizard of Oz experiments, presents a wider freedom of gestural expression than the usual pointing paradigm of classical interfaces [ 11.

Referring gestures used in coordination with verbal utterances build a taxonomy based on four categories as shown in figure 1. Whereas pointing still remains the most used gesture with 77% of all trajectories, circling movements appear with a frequency of 11%. 8% of all gestures defines the targeting category corresponding to a pointing covering a widespread area. The last type of gesture, scribbling, appears only seldom, 1%.

Pointing targeting circling scribbling

Figure 1: taxonomy of referring gestures

Each type of gesture is performed with a freedom in shape, precision, completeness and access strategy. For instance, it has been observed that the shape of referring trajectories are produced on the one hand to lit the layout of the objects referred to, and on the other hand to avoid surrounding objects. User's movements are thus executed according to the perceptual environment in such a way that it becomes difficult to determine gesture type by considering only the trajectory shape. In the targeting example presented by figure 1, an out of (visual) context analysis of the gestural shape will lead to circling typing (and its corresponding referent searching heuristic) contrary to the user's intention. So we claim that a robust typing of gestures can only be performed by considering the visual context.

A CONTEXT DEPENDENT GESTURAL ANALYSIS

By considering the gestural trajectories and their position relative to the referred ob.jects in our corpus, we observe two kinds of intention: gestures which aim the objects (elective gestures), and gestures which separate referents from the surrounding objects (separative gestures). Such alternatives reflect the use of visual space to access to referents. To determine the user's intention, we build a spatial partition of the visual scene as shown in figure 2. The first area is defined around each visual object, and corresponds to the elective part of visual space. The remaining inter-object space represents the visual area used by the user to carry out separative gestures like circling .

Figure 2: partitioning the eestural space

To determine the gestural intention of an entire trajectory, each point is typed according to its position in one of the two areas. The area most used by the point allows one to type the gesture and choose the heuristic adapted to retrieve the referents. For an elective gesture, the referred objects correspond to elective [areas used by the user, whereas the referents of an separative gesture are found on the side of the trajectory which presents the greatest curvature.


Keywords: low cost, dynamic capability, public transport low cost, dynamic capability, public transport

Low cost strategies to build dynamic capabilities: The creative approach of a French public transport operator

Low cost strategies to build dynamic capabilities: The creative approach of a French public transport operator 1. Introduction

As is indicated by [START_REF] Teece | Explicating dynamic capabilities: the nature and microfoundations of (sustainable) enterprise performance[END_REF], to achieve a real competitive advantage, an innovative company has to do more than invest in R&D, develop and protect its intellectual property: organizational and managerial innovations are needed simultaneously to build and sustain competitiveness. Dynamic capabilities framework [START_REF] Teece | Dynamic Capabilities and Strategic Management[END_REF][START_REF] Eisenhardt | Dynamic capabilities: what are they?[END_REF][START_REF] Winter | Understanding dynamic capabilities[END_REF][START_REF] Lawson | Developing innovation capability in organisations: a dynamic capabilities approach[END_REF] appeared as an attractive theoretical answer to overcome this challenge of continuous organizational innovations but managerial issues remain for its building in large firms [START_REF] Wang | Dynamic capabilities: A review and research agenda[END_REF]. In particular, what could be an effective strategic and unified guidance for simultaneous organizational and managerial innovations is misunderstood. Thus, a research gap exists concerning the introduction of dynamic capabilities in mature companies. This article tackles this issue and aims to describe how a public transport operator adopted a low cost approach to challenge its core capabilities at all the levels of its organization: technology, skills, management systems and corporate values [START_REF] Leonard-Barton | Core capabilities and core rigidities: A paradox in managing new product development[END_REF] and involved the stakeholders of it industrial ecosystem [START_REF] Adner | Match your innovation strategy to your innovation ecosystem[END_REF] in tackling collaboratively the issue of external barriers specific to public transport. The case-study analyzed here demonstrates that low-cost approach is an eligible unified guidance to overcome barriers and rigidities, but it also underlines the impact of an unified guidance for companies' stimulation of dynamic capabilities, and innovation process improvement at the ecosystem level. This allowed managers and decision makers in incumbent companies to improve their competitiveness. This article is organized as follows: after a review of the literature on performance of dynamic capabilities through core rigidities management and low cost products in section 2, the methodology and research settings will be presented in section 3. The case study done in a French public transport operator, RATP, will be exposed and analyzed in section 4. Then, the main findings are exposed in section 5, and section 6 concludes this paper.

Literature review

Performance of dynamic capabilities: a continuous process of overtaking firm's core rigidities and external barriers

Achieving competitive advantage has thoroughly been discussed in strategic management literature for decades, and different approaches like Porter's five forces [START_REF] Porter | The five competitive forces that shape strategy[END_REF] are currently told in management schools, despite broad critics on it oversimplification. A common critique to this approach is the fact that contemporary ecosystems are rapidly changing, and that this is not taken into account by the five forces approach. [START_REF] Teece | Dynamic Capabilities and Strategic Management[END_REF] suggested the dynamic capabilities framework to complete the resource-based view (RBV) and overcome this shortcoming. Authors argued that maintaining competitive advantage over time is possible through dynamic capabilities that allow firms to modify their resource base to adapt to changing conditions.

As pointed out by [START_REF] Wang | Dynamic capabilities: A review and research agenda[END_REF] and [START_REF] Barreto | Dynamic capabilities: A review of past research and an agenda for the future[END_REF], a consequent body of research has already been developed around the dynamic capabilities approach since its founding paper by [START_REF] Teece | Dynamic Capabilities and Strategic Management[END_REF], but the research points in different directions, with different approaches and definitions of dynamic capabilities. Although there is still a discussion if the link between performance (competitive advantage) and dynamic capabilities is direct, as defended by [START_REF] Teece | Explicating dynamic capabilities: the nature and microfoundations of (sustainable) enterprise performance[END_REF], or if it is more indirect, dynamic capabilities being necessary but not sufficient to assure competitive advantage [START_REF] Eisenhardt | Dynamic capabilities: what are they?[END_REF], all authors agree that the link exists. While the dynamic capabilities approach was first developed for rapidly changing ecosystems, more recent work argued that the same is also applicable when change rates are lower [START_REF] Zollo | Deliberate learning and the evolution of dynamic capabilities[END_REF][START_REF] Eisenhardt | Dynamic capabilities: what are they?[END_REF]. Therefore, Zollo and Winter (2002, p340) proposed to define dynamic capability as "a learned and stable pattern of collective activity through which the organization systematically generates and modifies its operating routines in pursuit of improved effectiveness". This definition underlines the depth and the continuity of the organizational innovation process. However, while there is a great number of scholars' work focusing on the existence on dynamic capabilities, the introduction of dynamic capabilities in mature firms is less discussed [START_REF] Borjesson | The challenges of innovation capability building: Learning from longitudinal studies of innovation efforts at Renault and Volvo Cars[END_REF]. According to these scholars, building capabilities to innovate is related to change management and involves overcoming organizational resistance and barriers. On the first hand, [START_REF] Leonard-Barton | Core capabilities and core rigidities: A paradox in managing new product development[END_REF] drew attention to one kind of organizational resistance that induces difficulties to innovate in large firms: their core rigidities. Flip side to the concept of company's core capabilities, core rigidities appeared when technologies, skills, management systems and values become over-stabilized through organizational routines and impede the firm to catch competitive opportunities [START_REF] Levinthal | Three faces of organizational learning: Wisdom, inertia, and discovery[END_REF][START_REF] Hacklin | Core rigidities in the innovation process: a structured benchmark on knowledge management challenges[END_REF].

In addition to these, the company often also has to face external barriers, which are linked to the industrial ecosystem in which the company evolves, for example to the market organization or to sector legislations [START_REF] Adner | Match your innovation strategy to your innovation ecosystem[END_REF]. A largely discussed external barrier for small and medium companies is the access to credit and loans [START_REF] Freel | Barriers to Product Innovation in Small Manufacturing Firms[END_REF]. These barriers can also be overcome by dynamic capabilities, since the entrepreneurial management function that is embedded in dynamic capabilities also has an important role on external activities, including shaping the ecosystem [START_REF] Teece | Explicating dynamic capabilities: the nature and microfoundations of (sustainable) enterprise performance[END_REF]. Some classical barriers identified for innovation in public transport can be cited here, like the fact that the choice of public transport mode is not done only on rational and technical criteria. According to [START_REF] Edwards | Developing new urban public transport systems: An irrational decision-making process[END_REF] this is not only the transport planner's fault; it is linked to a political framework that is not always rational. The lack of rationality is often made worse by the fact that decision makers are often not transport experts. This means that an external barrier exists to choosing the lowest cost offer, and that a transport operator proposing one should know the evaluation framework and have other arguments to convince of the interest of choosing them than only cost. Moreover, the construction and operations of public transport are independent and involve different parties. This often leads to a system that is not optimized, since every company tries to optimize it's own part and the global system optimum is not taken into account. Better communication skills and partnerships need to be developed to allow a systematic view.

Thus, implementing an effective dynamic capability requires combining an organizational innovation process to overtake simultaneously core rigidities and external barriers, but the issue of the nature of managerial guidance to coordinate this effort remains open.

Low cost approach as a federative guidance for organizational innovation

Low cost products and services are currently a hot topic. In addition to having been widely cited in managerial literature, mainly to discuss how to fight low cost new entrants [START_REF] Kumar | Strategies to fight low-cost rivals[END_REF][START_REF] Ryans | Beating Low Cost Competition: How Premium Brands Can Respond to Cut-Price Rivals[END_REF], some are currently being discussed in how to target non-consuming market, for example by frugal or jugaad innovation [START_REF] Radjou | Jugaad Innovation: Think Frugal, Be Flexible, Generate Breakthrough Growth[END_REF], and innovating for the base of the pyramid [START_REF] Ray | Product innovation for the people's car in an emerging economy[END_REF]. In addition to that, for [START_REF] Christensen | The Innovator's Dilemma: When New Technologies Cause Great Firms to Fail[END_REF] low cost products can also be disruptive innovation. Despite the large body of research build around some low cost products and services, like for example low cost airlines, there seems to be a great number of diverging definitions, and little work has been done to model how these products emerge and associated organizations.

Cost reduction is sometimes achieved by selling a "basic" version of the classical product.

That's the case for some of the low cost mobile phone offers: these are less expensive because they do not include a mobile phone, as opposed to the classical bundled offers. However, a multiplicity of other sources of cost reductions have been employed in low cost products, and the different sources are often combined. The first of these sources is the change of technological paradigm. The case of the 'Transmilenio', the low cost metro built in Bogotá, illustrates this kind of change. Significant cost reductions were achieved by using a bus-based system instead of a rail-based. The cost of capital was little more than 10% of the estimated cost of the equivalent heavy rail [START_REF] Cain | Applicability of TransMilenio Bus Rapid Transit System of Bogotá, Colombia, to the United States[END_REF]. Another important source is the change of business model, that according to [START_REF] Yovanof | Disruptive Technologies, Services, or Business Models?[END_REF]) can be as important as innovations to products and services. Some changes in business model worth citing are changes of the relationship with customers and suppliers; changes in the organization of the firm; or changes in the chain of actors involved. These can be observed in the case of IKEA, that made the customers part of the production process, by letting them transport and assemble their furniture themselves (Normann and Ramirez, 1993); or in the case of low cost airlines, where the change from hub-and-spoke to point-to-point flights allowed the removal of complexity and an easy network and tariff structure, and where the travel agents were completely removed by making only direct sales [START_REF] Brüggen | How fleet commonality influences lowcost airline operating performance: Empirical evidence[END_REF].

Organizational change appears as essential for low cost products, not only because it might be a source of cost reduction, but also because it is often necessary when the source of cost reduction is technological. That can be linked to the new market targeted, as is the case of Embrace, an infant warmer aimed at parents in developing countries instead of hospitals that used breakthrough approach of traditional warmers to adapt to the local purchasing power, using a phase-changing material to keep the temperature constant to replace the complex climate control equipment [START_REF] Radjou | Jugaad Innovation: Think Frugal, Be Flexible, Generate Breakthrough Growth[END_REF]; or to the demands linked to the technology, as is the case of the Chinese BYD batteries for mobile phones, that do not need very expensive heated "dry rooms" to be produced as was the case of batteries before, and allowed a different organization.

Based on an extensive literature analysis of low cost practices, Klasing Chen (2013) proposed two different approaches of low cost objects that embedded distinctive managerial goals:

-Low cost adaptation: A reduction and simplification approach of both products and organizational routines. The starting point for this approach is an existing product. It's utility for the client and its cost for each function are evaluated, and the products' functions that are considered superfluous are removed. Associated organization routines are deleted.

The goal is to maximize cost reduction and internal performance with a minimum client utility reduction. The resulting product or service is often described as "no-frills", like for example the low cost airlines.

-Smart low cost design: A design of a new product or service with an aggressive cost goal with low-cost driven development process. The starting point here is a function that needs to be fulfilled associated to a double target of cost and price. A new product and a new organization are simultaneously designed around these two targets. Innovative organizations are targeted to involve the most competent internal and external stakeholders to achieve the low-cost strategy. The goal is to achieve maximal client utility given the cost target. These products are mostly considered radical innovations, since they are supposed to achieve a great cost reduction, and according to O'Connor and Rice (2013), one of the criteria of classifying an innovation as radical is producing a significant (30% or greater) reduction in cost.

Both of these models differ from operational effectiveness, that aims to reduce cost without changing the client utility and, although it is essential to achieve lower cost products, cannot be classified as a strategy according to [START_REF] Porter | What is strategy?[END_REF]. These two low cost models were used as an analytical framework for the study done with the public transport operator.

Methodology and research settings

This research relies on a longitudinal research partnership between the research group of innovative design of Mines ParisTech and RATP, the French Parisian public transport operator. One of the authors was hired in 2012 as an executive PhD student to focus on lowcost as innovative design strategy, as the other was involved on a longitudinal study of organizational capability for innovation since 2008. Data has been collected through intervention research methodology [START_REF] Radaelli | Intervention Research as Management Research in Practice: Learning from a Case in the Fashion Design Industry[END_REF][START_REF] David | From Actionable Knowledge to Universal Theory in Management Research[END_REF] as both authors were involved as players with industrials. Theory building process was conducted with practitioners through a continuous analysis of data and literature insights back and forth [START_REF] Eisenhardt | Theory Building From Cases: Opportunities And Challenges[END_REF].

Research context

Innovations in urban public transport are rare, several reasons are cited in literature (van den [START_REF] Van Den Bergh | Social learning by doing in sustainable transport innovations: Ex-post analysis of common factors behind successes and failures[END_REF] or by transport experts to justify this lack of innovation: the lack of incentive in public services to innovate, the difficulty due to the great number of actors in this industry (each one having it's own agenda), the high path dependency of public transport… All reasons return to core rigidities of main industrial or funding players and to external barriers, which made the case especially relevant for our research.

Public transport operators often face some or several of these difficulties to create innovative organizational solutions. This was also the case of RATP, who wanted to renew its offers and propose a new "low cost" or entry product that would allow it to be competitive outside it's current market. This position could partly be justified by its strategic goals -like trying to increase the revenues from a subsidiary that was implemented in developing countries -and was partly justified by recent developments in the French public transport sector, with an opening to competitors of RATP's historical bus market in 2024. Nevertheless, the first propositions failed to federate the expected enthusiasm among the concerned departments.

A part of the lack of enthusiasm for this idea was linked to the negative image associated to "low cost" products and services within the firm. Indeed, low cost products used to be associated with a degraded product image, with lower quality as the main consequence of cost reductions. Many employees in the public transport operator did not want their company's image associated to a degraded solution, especially as public service is an historic mission of RATP deeply rooted in its corporate culture.

To better understand low-cost products and to verify how the concerns of the employees could be reduced, the company decided to launch a dedicated research program on low cost mobility within the research partnership with Mines Paristech research group on innovative design.

Data collection

The collaborative research program targeted three axis of learning: (1) a benchmark of existing low cost products and the identification of the model behind it (Klasing Chen, 2013);

(2) an oriented creativity method to define the low cost strategy; and (3) a projects development phase, during which the propositions from the oriented creativity method were elaborated and developed by the different departments concerned, having as goal to create low cost offers.

In this paper, main data comes from field notes and observation made during the active involvement of researchers in the oriented creativity method, the KCP method [START_REF] Elmquist | Alternative design strategies to combine environmental and economic sustainability: Lessons from an empirical experiment with an automotive firm[END_REF], which was used in the transport operator to develop a competitive low-cost strategy. Semi-directed interviews were also regularly conducted with the two managers of RATP and the two consultants in charge of the workshop, while the setting-up, between the daily sessions, and throughout the proposition phase of the method. The KCP method was developed from the C-K theory [START_REF] Hatchuel | C-K design theory: an advanced formulation[END_REF] to be applied in the industry by researchers from Mines ParisTech in partnership with RATP managers in 2006, thus both practitioners and researchers were experimented, but this KCP was special as it relied on the managerial guidance of 'Innovative Low Cost', not on a specific breakthrough in the commercial offer (as e.g. 'the subway of the XXI th century', the topic of a former KCP in RATP). Each KCP is composed of three phases: a Knowledge sharing phase (K), a Conceptual exploration phase (C) and a Prototype and proposition phase (P). In the current case the KCP involved 25 participants from Mars 2012. The participants came from different departments in the company that were considered vital for the development of new offers (maintenance, engineering, marketing, operations, accounting…) and from different hierarchical levels. Individuals from different backgrounds are chosen because knowledge diversity facilitates the innovative process [START_REF] Cohen | Absorptive Capacity: A New Perspective on Learning and Innovation[END_REF]. Besides that, having individuals from different departments of the company helps to diffuse the initiatives.

The KCP phases were structured as follows:

-Three half-day K sessions with three presentations from experts in the first and the second sessions and two presentations in the third session. Each session also had one or two group activities to allow the participants to better assimilate the content of the presentations. The Knowledge sharing phase is essential because it creates the basis of knowledge upon which the experts and non-experts will collaborate to develop new concepts. As stated by [START_REF] Cohen | Absorptive Capacity: A New Perspective on Learning and Innovation[END_REF], common knowledge improves communication, which is another reason why this phase is important. This first phase may involve suppliers, users and other partners. For our study, this phase was crucial to identify organization resistance and external barriers the company needed to overtake.

-One whole day C session, where three groups were formed, each being given two subjects to work on. The goal of this phase was to explore a concept and try to identify new research areas. Each concept that had to be explored can be described as a searchlight that tries to light a certain part of the knowledge, shared in the K phase. The concepts that shall be explored in this phase were chosen in order to make sure that the greatest possible space of innovation was covered. To increase the creative power of the whole group, each subgroup was asked to present its work, so that everyone could react to the propositions made. Both authors were involved in the creative workshop animation.

-Two half-day P sessions with a reduced group of experts in the domains identified as essential for developing low cost offers. This phase transforms the concepts explored in the previous phase into actionable research projects. These research projects are still on going inside RATP. It aims at selecting the best ideas of the previous phase, separating and recombining them, in order to make them more actionable and understandable for the organization. It formulates a design strategy, which is not limited to mere product or service new ideas, but includes the roadmap that allows achieving the planned strategy. This roadmap not only includes the actions needed to achieve this strategy but also the actors and their tasks.

The first author of the paper is actively involved in the management of a part of the initiative with the RATP manager of the KCP, being responsible for two research projects.

The longitudinal involvement of one of the author as executive PhD student allowed an indepth understanding of the empirical data and a favored access to rich and extensive observation [START_REF] Hay | Executive PhDs as a solution to the perceived relevance gap between theory and practice: a framework of theory-practice linkages for the study of the executive doctoral scholar-practitioner[END_REF].

Case study analysis

Our case study analysis will be presented in two parts: we start by the identification of the core rigidities and external barriers found in our case, followed by an analysis of strengths and limits of the KCP oriented creativity method deployed to overcome them.

Core rigidities and external barriers in the public transport operator

The research partnership with RATP allowed identifying a few core rigidities of the firm and external barriers that might hinder the development of low cost offers in public transportation.

These were identified thanks to semi-structured interviews of managers in the public transport operator.

Core rigidities linked to the historical background of the company

The first core rigidity identified is due to the historical background of the operator and its high and internationally recognized expertise in underground systems, that induces the firm to consider itself as a technical and engineering company. Because of this, heavier modes that demand more infrastructure construction (underground, rail and light rail) and technological innovations are systematically privileged over other innovations. Nonetheless, these are exactly the opposite of the modes that would be interesting to look into for low cost offers, since they are already the most expensive ones.

Another core rigidity identified is linked to the definition of a transport operator's mission.

The main goal of the transport operator is to supply the offer demanded by its contractor, who can be a transport authority, a city or other governmental organization. Because of that, operators specialize themselves in offering exactly what the contracts demand at the smallest cost. Considerations on trying to reduce the offer to cut costs, or proposing different offers than the ones demanded go against the 'normal' process; and are, tacitly but systematically, rejected by RATP experts.

Yet another core rigidity has its source in recent efforts made to reduce the company's overall costs. These efforts ended up having a negative influence on the innovation department, which was in charge of the low cost initiative. Due to strong budget reductions and to the great importance the operational departments have in the organization, the function of the innovation department had been reduced to accompany, finance and found projects proposed by the more operational departments. That made launching transversal projects inside the company very hard, since each department preferred to submit the projects that concerned it directly. To achieve significant cost reductions however, a system view is yet essential, since all the departments' activities are linked, and technical changes done in one department always affect the others.

Core rigidities linked to exploring low cost offers

And finally the last rigidity identified was linked directly to the fact that the targeted offers were specifically low cost-based. Public transport is seen as a public service, which means that it should be accessible for all. One of the consequences of this view of public services is that subsidies are considered as "normal", since the service is not for-profit. High costs are accepted in some occasions, when there is a reason considered good enough by local public authorities, for example improving a city's national visibility. This means that although efforts to reduce costs are done, it is also considered that service should not be degraded without a very good reason, thereby making the development of low cost services harder than in a competitive market. This first set of core rigidities linked to low cost is not particular to RATP but specific to public transportation industrial ecosystem. Beyond, in our particular case, another rigidity was linked to what was defined as part of the French operator's tasks and what was defined as outside it scope. RATP is not responsible for defining the offer and the minimal service it should supply (which is defined by the contractor, in France mostly the transport authority).

Therefore evaluating the client utility of each of the functions in its service and the cost, to see which could be removed, seems irrelevant, since the service cannot be changed by the operator without the approval of the transport authority. Another task considered outside the operator's task is defining the transport fares. Most low cost products attract consumers by offering a slightly degraded product for a significantly lower price. This is impossible for the public transport operator, since the price is defined by the transport authority and is often disconnected from the costs the operator found through subsidies.

As already cited above, low cost products have a very negative image in the French public transport operator, and RATP experts did not want to develop them, since having high quality is part of their corporate values. The high quality however is not incompatible with low cost products, as stated by [START_REF] Kumar | Strategies to fight low-cost rivals[END_REF]; awareness of this fact needs to be raised in the company. Despite all these organizational obstacles, the company had been making significant efforts on several cost reduction projects, all of them operational effectiveness projects, which demanded the same service quality with fewer resources. These projects' goals have been very hard to achieve for some departments, many employees complaining that they would lead to work overload. The difference between the proposed low cost projects and existing operational effectiveness projects was often unclear, and therefore many managers were reluctant to engage in them or felt their current work was being criticized.

The external barriers

The external barriers currently observed in the transport sector were also identified here.

Although the transport authority in the Parisian region, the STIF, has a significant expertise in public transport, they do not take many of the important transport decisions directly. And due to path dependencies much of the existing systems cannot be changed. One example of diseconomies due to these classical barriers is the existence of metro trains with rubber tires and others that circulate with metal wheels with direct contact on the tracks. The same can be observed in the different bus models that exist in the company. Since every time new material needs to be purchased a new call for tenders is opened, and the transport operator has to work with the cheapest material that responds to its demands.

How these rigidities and barriers were treated will be discussed in the following sections.

Overcoming core rigidities and external barriers: The impacts of the KCP in the public transport operator RATP

According to Leonard-Barton's (1992) framework, there are four levels of core competencies that could evolve in core rigidities: technology, skills, management systems and corporate values. We will discuss next how these levels were treated through the KCP.

To develop its low cost strategy the public transport operator chose to use a KCP, as besides its goal to develop the low cost strategy it also had as a goal to federate the departments around the developed projects, which is known property of the method across the participants (Arnoux and Bejean, 2011). Beyond participants, an approval commission was constituted to make sure top management would support the developed projects and that the developed strategy did not conflict with the company's global strategy. It gathered the directors of five departments that would be deeply impacted by the new offer. This approval commission came together before the KCP was launched to approve the scope and participants of the KCP and to approve the results after every phase, as well as the needed next steps. The creation of such an approval commission is not mandatory when doing a KCP, but proved very useful in this particular case, since the company is very large, that its departments sometimes have conflicting interests. Besides, this kind of commissions is a unique commonplace in the studied organization. The meetings of this commission were also beneficial because it allowed the concerned directors to get more information on the planed projects than is usually the case for innovation projects in this company and to increase the legitimacy of the whole process. Finally, it also made it easier to mobilize the participants for the needed timebetween 2.5 and 4 days, according to if they participated in the P phase or not -since managers found it harder to refuse their collaborators' participation when the invitation was endorsed by five directors, overcoming thereby a rigidity of the managerial system.

Since the aim of the K sessions was to allow a group of participants to acquire and share the knowledge needed to develop low cost mobility offers, a presentation of how a classical offer is made was necessary, because some of the participants did not have a global vision of the company's activities outside their departments. Besides, giving the participants a more systematic view allowed to overcome an organizational rigidity, linked to the strong department view existing in the company. The other presentations were on external knowledge identified as missing to develop a low cost offer: success and failure cases of low cost products and services; information on the target markets; and information on transport modes not operated by the operator. Their goal was first to increase awareness about the nature of low cost products and to show that their quality does not always need to be degraded.

It also tried to show that the value proposition the company had was not adapted to all markets, and that several changes needed to be made if the goal was to target developing countries. Doing that, they tackled the issue of the rigidity of internal skills and technology.

Moreover, one presentation about the two models behind low cost products and services was also given, and the participants were encouraged to develop offers in both models. This presentation aimed to show participants that different ways to create low cost products existed, and that they had different outcomes that completed each other. On the one hand, the adapted low cost offer did not give the most radical cost reduction, but it allowed to simplify the existing offers and to highlight the really important features (that at the time of the research were unknown to the company), reviewing a part of the technology and skills needed in the company, but without deeply changing the organization. On the other hand, the smart low cost design allowed more significant cost reduction, but needed to radically change the organization, often needing the technology, skills, management and corporate values to be changed. The design of a this kind of offer needs the identification of the really important features that need to be targeted, so it can profit immensely from the work done to develop adapted low cost products. Thus, another aim of the presentation of the two models of low cost was to clearly define the difference and similarities between low cost and operational efficiency, thereby reducing the resistance to these projects, because, as much the first was originally considered by experts as antagonistic to corporate value, as much the latter was considered one of a common goal in the business.

Main findings

This paper makes a contribution to theory on the introduction of dynamic capabilities in mature companies by showing how low cost approach combined to the experience of an oriented creativity method have been used in a public transport operator.

A first managerial result from this case was that it allowed the launch of several transversal projects, which were formerly stopped by the rigidity of the management system. While the research projects launched in 2013 were mainly one-department projects suggested by operational departments (with the exception of some European projects in which the company took part), more than half of the projects launched in the beginning of 2014 were transversal and involved more than one department. This was possible because all parties involved had understood the research object, and that it's importance had been integrated thanks to the existence of the approval commission. Thanks to this and to the involvement of the animation team, project leaders coming from operational departments felt legitimate to lead transversal projects. The gain of legitimacy observed in our case is very similar to the effect observed by Kelley et al. (2011, p252), who defends that "managers can offer critical assistance to project leaders needing legitimacy and support for their innovation projects". Thus, low cost appeared as an effective managerial guidance to involve the internal stakeholders of the firm's dynamic capability in a collective action for organizational improvement.

A further managerial result comes from the use of the two different approaches of designing low cost products: this allowed overcoming core rigidities and external barriers across two different ways. First, by using an adapted low cost approach, the product simplification allowed an effective management of the removal of some technologies and skills became core rigidities through the removal of the associated functions. One example would be the removal of the need for new buses to use a specific outdated and expensive information system that had historically been used by removing the need for an information system entirely.

Secondly, by using the smart low cost design approach, the company can create radically innovating offers, and thereby change both the industrial ecosystem and the company, and by this way removing existing rigidities and barriers. One example was the possibility for the company to launch offers that do not replace the existing offers, but complement them. By creating something new, the existing legislation and fare system do not apply. We observed a case where that had already been done: it was in the shared vans leaving from the airport, an alternative to taxi cabs and public transport that had been developed in Paris and that fixed its fares independently both from public transport and taxi cabs. A similar approach might allow the company to develop new core competencies on pricing and yield management, as well as on finding the break-even point of a transport system. It would also support the company in learning more on its final users and on those who are currently not its final users, since in this kind of offer they are the targeted clients. This is not the case on a classical public transport offer, where the clients today are the transport authorities. This additional knowledge on final users might be very valuable for the operator, who would be able to exploit it in order to have a better acceptance of its offer. However it would have to be handled with care on the main business, which remained selling to transport authorities and not directly to the end user.

Thus, the simultaneous use of two different models opens up a larger number of options to overcome rigidities and external barriers, enriching the dynamic capabilities of the transport operator and its industrial ecosystem.

Finally, the KCP on low cost was a way for the public transport operator to improve its absorptive capacity, since it allowed, in a targeted way, to identify and assimilate external knowledge that was essential for the company. [START_REF] Cohen | Absorptive Capacity: A New Perspective on Learning and Innovation[END_REF] indicated that absorptive capacity was key to maintain and achieve competitive advantage, since it has been observed that innovative capabilities are linked to the ability of a firm to recognize the value of new, external information, assimilate it, and apply it to commercial ends. Identifying and targeting relevant knowledge is one of the big challenges companies have nowadays. In this particular case, RATP had decided low cost products were an interesting goal, but did not know how to go beyond monitoring press releases on the subject. The modeling of the innovation field done during the KCP allowed identifying the knowledge needed to develop a low cost product, dividing it into knowledge already existing in the company and the knowledge that had to be sourced externally. It is also being used as a managerial tool, to explain the link between the knowledge being acquired and the global low cost strategy of the firm, in order to render the final goal clearer and improve assimilation and application. In this way, low cost strategies were used as a way to improve RATP's competitive advantage by improving its absorptive capacity.

Conclusion: managerial implications and further research

This paper described how a French public transport operator, RATP, developed its own dynamic capability and those of it industrial ecosystem through the unified and federative guidance of low cost strategies. This approach was based on the simultaneous investigation of two different low cost models [START_REF] Chen | The two models behind low cost products[END_REF].

Using an oriented creativity method named KCP [START_REF] Elmquist | Alternative design strategies to combine environmental and economic sustainability: Lessons from an empirical experiment with an automotive firm[END_REF] and the two different low cost strategies as guidelines, they overcame a core rigidity of the managerial system, thereby facilitating the launch of transversal innovation projects. Secondly, thanks to the unified guidance, knowledge acquisition had been efficiently oriented. This allowed increasing the absorptive capability of the firm and the quality of interaction with ecosystem's stakeholders, better targeting and acquiring external knowledge through collaborative explorations Besides, low cost strategies had been used to deal with the external barriers and core-rigidities at both firm and industrial ecosystem levels through two different and complementary ways of developing low-cost offer for public transport, and thus, reinforce dynamic capabilities at both firm and industrial ecosystem levels. Therefore this paper contributes to empirical knowledge on dynamic capability building.

This study is based on a single case study in a particular organization. To insure generalization is possible it should be repeated in other organizations and ecosystems, which also look at building dynamic capability. Moreover, the innovation projects that resulted from this collaborative research partnership are still ongoing, and accompanying them and their results over time would enrich this research findings. Finally, maintaining dynamic capability over time is also a challenging task that has not yet been thoroughly mastered. Further research should include a longitudinal study of the company's development and maintenance of dynamic capabilities resulting from low cost strategies.

To conclude, our research showed an example of how a low cost approach can be used as unified and federative guidance to build dynamic capabilities, thereby addressing a gap in research on the organizational capability management. It opens few research questions on how other firms could benefit of this specific guidance and what could be alternative unified guidance to build efficiently a sustainable dynamic capability.