Combinatorial Question

Zula110100100

I was wondering the function for getting the number of combinations of 0 1 2, repeatable, but with any combination containing a 02 disallowed.

Up to four places the sequence of answers is 3, 8, 21, 55 that I have counted and verified, It would seem the next few are 144, 377, 987, 2584, I have not verified those for obvious reasons.

The system I worked out to get those numbers is that if, once up to two digits, you name duples as a-h skiping '02' i.e. a='00', b='01',(02 is not allowed) c='10'...,h = '22' and then consider them to be overlapping, so that the second digit of one determines the first digit of the other.

The 8 for two places is obvious as there are 8 duples, that 8 break down to 3(a,c,f) that can only have 2(a,b) that follow, 3(b,d,g) that can have 3 follow(c,d,e) and 2(e,h) that can have 3 follow(f,g,h).

So (3*2)+(3*3)+(2*3) = 6+9+6 = 21
The 21 then breaks down to 8,8,5
(8*2)+(8*3)+(5*3) = 55,
55 breaks down into 21,21,13
(21*2)+(21*3)+(13*3) = 144
144 breaks down into 55,55,34 (The pattern here repeats in that the first two are the answer from before(edit: the answer from two before), and the last one is the two from before added together(13 = 8+5),(34 = 21+13)


But alas, I don't know how to put such a recursive formula into terms that I can supply the number of digits to get the answer without starting at a known point and continuing to the number of digits I want. However, I believe such a formula should exist? One should employ some sort of (n+1) system or something I imagine, but my skills there some short I don't even know where to start.


Finally, to put some background to that, I am figuring the number of possible rhythms in 8 measures of 2/4 going only to 16th notes. So far it would seem the answer is close to maybe 4*10^27. I figure that if 1 billion people wrote 150/minute, it would take almost 14 billion years to accumulate them all.

Also, if you have 9 gallons of water, there are as many rhythms as there are molecules of water. neat stuff

Stephen Tashi

You haven't stated a precise mathematical problem.

Why is the word "repeatable" releavant to a question about combinations? Did you mean "permutations" instead of "combinations"? Or are you talking about combinations that are distinguished both by what digits are in them and also by how many times these digits occur. If that's the case, what dos "0 2" disallowed mean? Does it mean you can't have any 0's and you can't have any 2's ? Or does it mean you can't have exactly one 0 and exactly one 2?

Zula110100100

"02 disallowed" means a number like 1101212021 would be disallowed because it containes a '02'. I haven't stated a mathematical problem because that -is- my question. Perhaps permutations, but I thought that implies starting with a sequence and changing that sequence...

Say the '02' wasn't disallowed then, for example, I am looking for a function like f(n) = 3^n

which for n=2=number of digits=2 digits is 9, namely:
00, 01, 02, 10, 11, 12, 20, 21, 22
However, I include the requirement that no '2' directly follow a '0'.
So the new answer is 8...but what is the function that gives me that answer.


'repeatable' I guess is implied here...I just wanted to be sure you knew 00, 11, 22 are allowable.

So you understand the 02 issue: As I stated before, I am working out the number of possible rhythms in x many beats of 16th note possibilities. I am using a 0 to indicate a rest, a 1 to indicate the beginning of a note, and a 2 to represent the continuation of a note, obviously, a note cannot continue from a rest....I could consider that continuing the rest I guess.. How would that change my final answer?

So by the system used above, a sequence of 0120 is a 16th rest, an 8th note, and a 16th rest, while 1222 is a quarter note, and 1201 is an eigth note, a 16th rest and a 16th note.

Does that make any sense?

Stephen Tashi

The convention you use for notation may change the way the answer is computed, but it shouldn't change the answer!

It makes sense. Pehaps, for the benefit of non-musical-theorists, we should explain that (0,1,1..) and (0,1,2,..). are not the same rhythim snce playing a 1/16 note twice sounds different that playing an 1/8 note, even though these actions have the same total duration. By contrast, if you used a '2' to denote continuing a rest, there wouldn't be an audible distinction between (1,0,2,1..) and (1,0,0,1,...). I have to go to a doctors appointment now, but I'll think about the problem later. Perhaps some other forum member will solve it before I get back.

Stephen Tashi

Try doing a recursion that has more detail. Suppose that for a length of N 1/16 beats, you know the following:

1) The number of distinct rhytims that end in a 1
2) The number of distinct rhythms that end in a 2
3) The number of distinct rhythims that end in 0

In how many ways can you form the same categories of rhythm by adding one 1/16 beat to these patterns?

For example, to get a rhythim that ends in 2, you can add a 2 to those rhythms of type 1) and 2), but not to the rhythms of type 3).

Zula110100100

I think that leads you to the same place as my letter system above, to get category 1, you can add a 1 to 1-3, for category 2, you can add a 2 to 1 or 2, and for 3 you add a 0 to 1-3, but then you have to keep track of the way that 8 break down into 3 of 1, 2 of 2 and 3 of 3. The problem I am having is that the 8 doesn't break down the same as it is built, so at each step, you have to figure out how many end up in each category, which is not the same as the number you can make by adding a digit, i.e. category 2 has three possible that follow, but it one from category 2 and one from category 1 that make up the components of category 2 in the second round.

That is quite pointlessly wordy, I apologize for that. What I mean I guess is that when you add the digit to the end, you change the category that each number goes too, I am not sure how to prove how that breaks down...

Stephen Tashi

Is your complaint that you want a non-recursive formula? There may not be one, but you should write the recursion out symbolically to see if there is a pattern.

c[i,n] = number of sequences of length n in category i
T[n] = c[1,n] + c[2,n] + c[3,n] = total number of sequences of length n

c[1,n+1] = c[1,n] + c[2,n] + c[3,n] = T[n]
c[2,n+1] = c[1,n] + c[2,n]
c[3,n+1 ] = c[1,n] + c[2,n] + c[3,n] = T[n]
T[n+1] = 3 c[1,n] + 3 c[2,n] + 2 c[3,n] = 3T[n] - c[3,n] = 3T[n] - T[n-1]

So the recurrence relation is T[n+1] - 3T[n] + T[n-1] = 0

If that looks correct, we can proceed to learn about "Linear homogeneous recurrence relations with constant coefficients" in the article http://en.wikipedia.org/wiki/Recurrence_relation. I worked with such things years ago, so I'll need a review.

Stephen Tashi

If we are considering the first 1/16 th to be the first note of melody, it wouldn't make sense to start with '2', which would imply there was a note preceeding it..

With that convention,

C[1,1] = 1
C[1,2] = 0
C[1,3] = 1
T[1] = 2

C[2,1] = 2
C[2,2] = 1
C[2,3] = 2
T[2] = 5

C[3,1] =5
C[3,2] =3
C[3,3] = 5
T[3] = 13

C[4,1] = 13
C[4,2] = 8
C[4,3] = 13
T[4] = 34

Zula110100100

Very good point, I believe at that time I was thinking of how to get an approximation with the possibilities for one beat be able to just use T[4]^(number of beats)

But with this improved method that is a much better way to look at it.

This does indeed seem to be correct(Even with the change, it just changes the starting values right?: T[n+1] - 3T[n] + T[n-1] = 0

But that's a lot to look at, thanks for the link(and correction)

Stephen Tashi

Another thing we should do is define the "actual" answer to be A[n] = T[n]-1 unless you want to count the squence consisting of only rests as a rhythm.

By decrementing the indexes, the recurrence can be written as

[itex] T[n] - 3T[n-1] + T[n-2] = 0 [/itex]

According to the Wikipedia link, this gives the "characteristic equation"

[itex] t^n - 3t^{n-1} + t^{n-2} = 0 [/itex]

Whose roots are 0 and the two roots of

[itex] t^2 - 3t + 1 = 0 [/itex]

I don't think the zero roots enter into the solution, so as I interpret the article, the solution is

[itex] T[n] = k_1 r_1^n + k_2 r_2^n [/itex]

with [itex] r_1 = \frac{3 + \sqrt{ 5}}{2}, [/itex] [itex] r_2 = \frac{3 - \sqrt{5}} {2} [/itex]
and [itex] k_1, k_2 [/itex] some constants that are to be determined. It will be interesting to see if we can find contants that make [itex] T[n] [/itex] always turn out to be an integer.

Of course, I might not be interpreting the article correctly. Can anyone comment on that?

awkward

I think you are on the right path. Another approach is to derive the generating function for the number of arrangements, which turns out to be
[tex]f(x) = \frac{1}{x^2 - 3x +1}[/tex]
which has an obvious relationship to the characteristic equation.

Stephen Tashi

Thank you for the confirmation.

Now ( wishing I had a symbolic algebra program handy) I shall attempt a manual solution. See if I get this much correct.

Let [itex] s = \sqrt{5} [/itex]
So
[itex] r_1 = (3 + s)/2 [/itex]
[itex] r_1^2 = (14 + 6s)/4 = (7+3s)/2 [/itex]
[itex] r_2 = (3 - s)/2 [/itex]
[itex] r_2^2 = (14 - 6s)/4 = (7 - 3s)/2 [/itex]

eq 1: [itex] T[1] = k_1 r_1 + k_2 r_2 = k_1 (3+s)/2 + k_2 (3-s)/2 = 2 [/itex]
eq 2: [itex] T[2] = k_1 r_1^2 + k_2 r_2^2 = k_1(7+3s)/2 + k_2 (7 -3s)/2 = 5 [/itex]

eq 1A: [itex] k_1 + k_2 \frac{(3-s)(2)}{(2)(3+s)} = 2(2/ (3+s)) = 4/(3+s) [/itex]
eq 2A: [itex] k_1 + k_2 \frac{ (7 - 3s)(2)}{(2)(7 + 3s)} = 5(2/(7+3s)) = 10/(7+s)[/itex]

eq 1B: [itex] k_1 + k_2 \frac{3-s}{3+s} = 4/(3+s) [/itex]
eq 2B: [itex] k_1 + k_2 \frac{7-3s}{7+3s} = 10/(7+3s) [/itex]

eq 3: [itex] k_2 [ \frac{3-s}{3+s} - \frac{7-3s}{7+3s}] = \frac{4}{3+s} - \frac{10}{7+3s} [/itex]

eq 3A: [itex] k_2 [ \frac{ (3-s)(7+3s) - (7-3s)(3+s)}{(3+s)(7+3s)} ] = \frac{ 4(7+3s) - 10(3+s)}{(3+s)(7+3s)} [/itex]

eq 3B: [itex] k_2 [ (3-s)(7+3s) - (7-3s)(3+s) ] = 4(7+3s) - 10(3+s) [/itex]

eq 3C: [itex] k_2 [ (21 +2s - 3s^2) - (21 - 2s - 3s^2) ] = 28 + 12s - 30 - 10s [/itex]

eq 3D: [itex] k_2 [ 4s ] = -2 + 2s [/itex]

eq 3E: [itex] k_2 = (-2 + 2s)/(4s) = (-2s + 2s^2)/ (4s^2) [/itex]

eq 4E: [itex] k_2 = \frac{ - 2 \sqrt{5} + 10}{20} = \frac{5 - \sqrt{5}}{10} [/itex]

devinedj

This looks right. Gives $k_1 = \frac{5+sqrt{5}}{10}$.

With $T_n = k_1 r_1^n + k_2 r_2^n$ we find that $T_n = \{2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, ...\}$

See Wolfram

Zula110100100

Right on guys, thanks a lot for the help. So the n here is not equal to beats(in 2/4) but rather is equal to 16th notes, so n = 64 would be 8 measures of 2/4? If so, wolfram gives 4.07*10^26 , which is pretty close(ish) to my initial approximation of 4*10^27. A final question is this is still counting the all rest pattern right?

Stephen Tashi

Yes, T[n] counts the pattern of all rests.

devinedj

And yes, n represents the number of 16th notes so n=64 is 8 measures of 2:4 time.

Zula110100100

Very interesting result... So that is also the most general equation for this sort of thing? As that can be used as n=128th notes or 256th notes, then just you number of n per beat goes up, but for instance n=12 would work for 1 measure of 6/8 going to 16ths? 2 beats, 6 divisions per beat.