Reusable Specification Components for Model-Driven Development∗

Description

Reusable Specification Components for Model-Driven Development∗ Kathryn Anne Weiss, Elwin C. Ong, and Nancy G. Leveson Massachusetts Institute of Technology Abstract: Modern, complex control systems for a specific application domain often display com- mon system design architectures with similar subsystem functionality and interactions, making them suitable for representation by a reusable specification architecture. For example, every space- craft requires attitude determination and control, power, thermal, communications, and propulsion subsystems.

• spacecraft
• rwa
• specification
• model
• models
• control
• development
• software
• system
• design

Sujets

• Lundqvist
• Global
• Climate
• Storey
• Viguier
• Zimmerman
• Larsen
• European Space Agency
• System

Informations

• Publié par: istyo
• Nombre de lectures: 22
• Langue: English

Extrait

Lecture 8 MATH1904

Multinomial Coefficients

The number of ordered arrangements ofn objects, in which there arekobjects of 1 type 1,kobjects of type 2,. . ., andk 2 m objects of typemand where +k+∙ ∙ ∙ k 1 2 +k m =n, is   n n! =. , k , k!k!k. . . ! k 1 2 . . . , k m 1 2 m This number is called amultinomial coefficient.

The Multinomial theorem

n (x+ 1 x+∙ ∙ ∙+x m ) = 2

  X n k k 1 2 k m x x . . . x . 1 2 m k , k , . . . , k 1 2 m k+k+∙∙∙+k m =n 1 2

Amultinomialis an expression of the form + x 1 x+∙ ∙ ∙+x m . 2

1

Examples

•The number of ways to arrange 5a’s, 3 b’s and 4c’s is   12 12! = 5,3,3! 4!4 5!

•The number of ways to place 15 labelled balls in 5 boxes with 3 balls to each box is   15 15! = 5 3,3,3,3,3 (3!)

2 3 4 •The coefficient ofx x xin 1 2 3 9 (x+x+x) is 1 2 3   9 9! = 2,3,3! 4!4 2!

2

Binomial identities

m   X m m 2 = k k=0

 m    X m 0 k (−1) =  k 1 k=0

  m = 0, n

m6= 0 m= 0

ifn > m

  m = 1 0

    m m = k m−k

3

(1)

(2)

(3)

(4)

(5)

    m m m−1 = k k k−1

      n m n n−k = m k k m−k

•Pascal’s Triangle

      m+ 1m m = + k k k−1

•The Vandermonde identity

n      X w+m w m = n k n−k k=0

4

(6)

(7)

Introduction to the WZ method

Suppose we wish to prove an identity of the P formf(n, k) =g(n), wheref(n, k) is k constructed from binomial coefficients. For example,   X n n = 2. k k

A method for doing this has been discovered by Herb Wilf and Doron Zeilberger first published in 1990 and now explained in detail in their delightful book A=Bk.seiwhtaMkrPoteokˇv

The method is very versatile but it is best carried out with a computer. It is available for Mathematica and for Maple.

5

Here is the WZ method, taken from the bookA=B:

1. Divide through by the right hand side to change the identity to X F(n, k) = 1, k whereF(n, k) =f(n, k)/g(n).

2. Find a functionR(n, k) with the amazing property that forG(n, k) =R(n, k)F(n, k) we have F(n+ 1, k)−F(n, k) =G(n, k+ 1)−G(n, k).

3. Sum the equation over all values ofkand observe that the right hand side is a “telescoping sum” which telescopes to 0. This means that X X F(n+ 1, k) =F(n, k). k k P 4. From the previous step we see thatF(n, k) k does not depend onnis, it is a constant.. That

5. Verify that the constant is 1 by checking that P F(0, k) = 1. k

6

  P n n The identity= 2 k k

  n n We haveF(n, k) =/2 and it turns out k k thatR(n, k) = . 2(k−n−1)

ThenG(n, k) =R(n, k)F(n, k) simplifies to   n −n−1 −we can check directly that2 and k−1 F(n+ 1, k)−F(n, k) =G(n, k+ 1)−G(n, k).

That is     n+ 1n −n−1−n 2−2 = k k     n n −n−1−n−1 −2 + 2 k k−1

Notice now that     0 1 ,ifk= 0 F(0, k=) =  k 0,otherwise P and thereforeF(0, k) = 1. k

7

Example identities

    −1 X n x x+n k (−1) = k k+x n k

    k n x x+n In this caseF(n, k) = (−1) k k+x n k(k+x) andR(n, k.) = (n+1)(k−n−1)

     X n x n+x = k k+r n+r k

     n x n+x In this caseF(n, k) =/and k k+r n+r k(k+r) R(n, k.) = (n+x+1)(k−n−1)

8