# 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

- MathMan TGLv 71 decade agoBest 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

- adoraLv 43 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.