Edik
Lv 5
Edik asked in Science & MathematicsMathematics · 1 decade ago

Two questions on partial orderings?

I have the following succession of numbers:

1-3-1-2-5-1-1-3-1-2-1

My list involves 11 places, but only 4 distinct integers. I’m interested in the successions of these numbers. 1 can be followed by 1, 2 or 3, but not 5. 2 can be followed by 1 and 5, but not 3. 3 and 5 are only ever followed by 1. These are “partial orderings,” correct?

(--> means "can be followed by")

1 --> 2

1 --> 3

2 --> 1

2 --> 5

3 --> 1

5 --> 1

I could construct another succession of 11 numbers following these same rules. Such as:

1 2 5 1 1 3 1 1 2 1 3

QUESTION #1: If I wanted to figure out how many possible ways there are of ordering the numbers 1,2,3,5 in 11 places (4^11, correct?) such that the previously stated partial orderings are maintained, how would I go about doing that?

QUESTION #2: Do you have any recommendations on easy (layman’s terms, please) readings on partial orderings? (other than Wikipedia…)

2 Answers

Relevance
  • 1 decade ago
    Best Answer

    What you have is not a partial ordering, but a grammar,

    which is a set of rules for generating "sentences" in a "language".

    Writing this in BNF it would be:

    let "e" = the empty string.

    S will be a sentence in the language this grammar generates.

    ::= means "is defined as" and | means "or".

    1,2,3,5 represent themselves.

    Other letters are things which are themselves defined by the grammar.

    (O is a 1, possibly followed by what can follow a 1,

    W is a 2, possibly followed by what can follow a 2,

    etc.)

    S ::= e | O | W | H | F

    O ::= 1 | 1 O | 1 W | 1 H .... ( 1 -> {1, 2, 3} )

    W :: = 2 | 2 O | 2 F .... ( 2 > {1, 5} )

    H :: = 3 | 3 O .... ( 3 > (1} )

    F ::= 5 | 5 O .... ( 5 > {1} )

    Well, don't worry if that doesn't make any sense.

    Just know that this is not a partial ordering, and you have

    a bunch of "OK" sequences of 1,2,3,5's and lots more which are

    not "OK".

    Not having any idea how to count these, I wrote a program to generate them.

    Here are the results:

    Len: 3 -- 16

    Len: 4 -- 34

    Len: 5 -- 73

    Len: 6 -- 157

    Len: 7 -- 337

    Len: 8 -- 724

    Len: 9 -- 1555

    Len: 10 -- 3340

    Len: 11 -- 7174

    Each additional character multiplies the number for the previous length by about 2.18, reflecting an average of about 2.18 possible extensions in each position.

    That's well below 4^n, which would be

    64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304

    and falling farther and farther behind, since counts are only doubling

    versus possibilities quadrupling each time.

    To count them you'd have a recursive function:

    Let c(x, n) be number of strings starting with x of length n.

    and C(n) be total strings of length n.

    Then C(n) = c(1, (n-1)) + c(2, (n-1)) + c(3, (n-1)) + c(5, (n-1))

    Where

    c(1, n) = c(1, n-1) + c(2, n-1) + c(3, n-1)

    c(2, n) = c(1, n-1) + c(2, n-1)

    c(3, n) = c(1, n-1)

    c(5, n) = c(1, n-1)

    and if n = 1, c(x, n) = 1

    (or something like that)

    So you could simplify it some:

    C(n) = 4 * c(1, n-1) + 2 * c(2, n-1) + c(3, n-1)

    Here are the ones of length 4: (a = 1, b = 2, c = 3, e = 5)

    eaaa eaab eaac eaba eabe eaca

    caaa caab caac caba cabe caca

    aaaa aaab aaac aaba aabe aaca

    abaa abab abac abea

    acaa acab acac

    baaa baab baac baba babe baca

    beaa beab beac

  • adora
    Lv 4
    3 years ago

    grow to be no longer conscious. no longer shocked, many stable human beings save on with those paths. i could think of an exceedingly being concerned soul who had greater to spare would not complication approximately who grow to be administering the charity, as long by using fact the help went to the needy. Heck, even outlaw biker gangs do charity paintings... the only themes I even have with charity paintings is while the human beings administering are making use of the ought to line their very own wallet, or while the donating definitely everyone seems to be basically involved interior the tax receipt. i think the excuses of the giver are not as significant as long as people who choose help get it.

Still have questions? Get your answers by asking now.