Math Is Fun Forum

mnovaes

Member

Registered: 2006-12-14

Posts: 1

A problem in Combinatorics

Hello!

I have this problem in combinatorics which I need to solve, but I don't know where to look for information on it. Maybe someone here has seen something similar and can direct me to the right place?

The problem is the following. Suppose you are given n1 copies of the number "1", n2 copies of the number "2" and n3 copies of the number "3". You then arrange them in a sequence of length n1+n2+n3. Then you scan the sequence and write down the transitions that you encounter.

For example, if you write 1123312 the transitions are (11)(12)(23)(33)(31)(12)

Now comes the question. Suppose I want to fix the number of transitions, i.e. I require that the transition (jk) appears a number m(jk) of times. Question is: How many different sequences can I write with the same m(jk), given n1, n2 and n3.

Of course the numbers must satisfy some conditions, such as the sum of all m(jk) equals n1+n2+n3-1 and m(12)<2min(n1,n2).

For a simple example, for n1=n2=n3=1 with m(11)=m(22)=m(33)=m(13)=0 and m(12)=m(23)=1 there are two possibilities, 123 - 321

I would really appreciate some help!
Thanks!

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: A problem in Combinatorics

Interesting problem.  I don't have the time to work on it now, but here is my suggestion:

The number of groupings will basically set that many elements in place.  Take the number of groupings and find out how many different places these groupings can go (remember each grouping is identical).

Then once you have this number, you now independently select the other groups, which are allowed to vary without restrictions.  So you multiply this number by the number of groupings.

But I believe it's easier said than done.  I'll have more time to work on it a bit later tonight.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

F.A.P

Member

Registered: 2006-12-18

Posts: 1

Re: A problem in Combinatorics

Hello!
For a simple example, for n1=n2=n3=1 with m(11)=m(22)=m(33)=m(13)=0 and m(12)=m(23)=1 there are two possibilities, 123 - 321

Given the above conditions there is only one possibility 123 with transitions (12)(23).

Last edited by F.A.P (2006-12-19 08:27:04)