Combinatorics problem

Consider a 4 4 -dimensional array R R . Any element of the array can be represented by R a b c d R_{abcd} where a , b , c , d a,b,c,d are any four (not necessarily distinct) integers from the set { 1 , 2 , 3 N } \{1,2,3…N\} .

Given that,

i) R a b c d = R a b d c R_{abcd}=-R_{abdc}

ii) R a b c d = R b a c d R_{abcd}=-R_{bacd}

iii) R a b c d = R c d a b R_{abcd}=R_{cdab}

iv) R a b c d + R a d b c + R a c d b = 0 R_{abcd}+R_{adbc}+R_{acdb}=0

When N = 15 N=15 , how many elements of R R are independent?


The answer is 4200.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Arpon Paul
Dec 12, 2016

Using condition (i), R a b c c = R a b c c R a b c c = 0 R_{abcc}=-R_{abcc} \implies R_{abcc}=0 So, for independent elements, the last two indices should be different. Again, from condition (i), we have, for example, R 1234 = R 1243 R_{1234}=-R_{1243} If we know the value of R 1234 R_{1234} , we know the value of R 1243 R_{1243} straight away. Only one of them is independent.

Considering condition (i) only, we can conclude, for every combination (obviously distinct numbers) of the last two indices, we have one independent element.

And there are N ( N 1 ) 2 ! \frac{N(N-1)}{2!} number of such combinations.

Now considering condition (ii), R a a c d = 0 R_{aacd}=0 , so R a a c d R_{aacd} is not independent. Again, for every combination (obviously distinct integers) of the first two indices, we have one independent element.

And there are N ( N 1 ) 2 ! \frac{N(N-1)}{2!} number of such combinations.

So, considering condition (i) and (ii), there are N ( N 1 ) 2 ! N ( N 1 ) 2 ! \frac{N(N-1)}{2!}\cdot\frac{N(N-1)}{2!} independent elements.

Now, let's consider condition (iii). According to condition (iii), if we interchange the first couple of indices with the last couple of indices, the element remains the same.

But if ( a , b ) = ( c , d ) (a,b)=(c,d) , for example, R 1212 = R 1212 R_{1212}=R_{1212} , this is an identity.

There are N C 2 = N ( N 1 ) 2 ! {}^NC_2=\frac{N(N-1)}{2!} such identities.

Otherwise, for each independent element, there is a corresponding dependent element. So considering condition (i), (ii) and (iii), there are

1 2 ( N ( N 1 ) 2 ! N ( N 1 ) 2 ! N ( N 1 ) 2 ! ) + N ( N 1 ) 2 ! = 1 2 N ( N 1 ) 2 ! ( N ( N 1 ) 2 ! + 1 ) \frac{1}{2}\left(\frac{N(N-1)}{2!}\cdot\frac{N(N-1)}{2!}-\frac{N(N-1)}{2!}\right)+\frac{N(N-1)}{2!}=\frac{1}{2}\cdot\frac{N(N-1)}{2!}\left(\frac{N(N-1)}{2!}+1\right)

independent elements.

Now, consider condition (iv). We have to count the number of independent equations that condition (iv) provides.

If a = b a=b , we have,

R a a c d + R a d a c + R a c d a = 0 R_{aacd}+R_{adac}+R_{acda}=0

R a d a c = R a c d a \implies R_{adac}=-R_{acda} ... (v) [ R a a c d = 0 R_{aacd}=0 according to condition (ii)]

Equation (v) can also be derived using condition (i) and (iii). Thus, when a = b a=b , condition (iv) does not provide any new independent equation. Same can be shown for a = c a=c , a = d a=d , b = c b=c , b = d b=d and c = d c=d .

Again,

R a b c d + R a d b c + R a c d b = 0 R_{abcd}+R_{adbc}+R_{acdb}=0

R b a c d + R b c a d + R d b a c = 0 \implies-R_{bacd}+R_{bcad}+R_{dbac}=0 [Using condition (ii) and (iii)]

R b a c d R b c d a R b d a c = 0 \implies-R_{bacd}-R_{bcda}-R_{bdac}=0 [Using condition (i) and (ii)]

R b a c d + R b c d a + R b d a c = 0 \implies R_{bacd}+R_{bcda}+R_{bdac}=0 ... (vi)

So if equation (v) is satisfied (also condition (i), (ii) and (iii) ), equation (vi) is automatically satisfied.

In the same way, it can be shown that the following equations are also satisfied:

R c a b d + R c d a b + R c b d a = 0 R_{cabd}+R_{cdab}+R_{cbda}=0

& R d a b c + R d c a b + R d b c a = 0 R_{dabc}+R_{dcab}+R_{dbca}=0

So, for ( a , b , c , d ) = ( 1 , 2 , 3 , 4 ) , ( 1 , 2 , 4 , 3 ) , ( 1 , 3 , 2 , 4 ) . . . (a,b,c,d) = (1,2,3,4) , (1, 2, 4, 3) , (1, 3, 2, 4) ... any permutation of ( 1 , 2 , 3 , 4 ) (1,2,3,4) , we have only one independent equation from condition (iv).

Thus, for each combination of four distinct integers, we have only one independent equation. So we get N C 4 {}^NC_4 independent equations.

So considering all the conditions, we have 1 2 N ( N 1 ) 2 ! ( N ( N 1 ) 2 ! + 1 ) N C 4 = N 2 ( N 2 1 ) 12 \frac{1}{2}\cdot\frac{N(N-1)}{2!}\left(\frac{N(N-1)}{2!}+1\right)-{}^NC_4=\frac{N^2(N^2-1)}{12} independent elements.

Ah, I initially had a question about the "N-dimensional" part, and I see you've updated the problem.

The overall presentation of the solution could be improved by providing clear signposts to the readers. For example, saying "Case 1: At least 2 values are the same, Case 2: all values are distinct" would show the reader how you're treating it.

Calvin Lin Staff - 4 years, 6 months ago

Agreed with Calvin here - I managed to read this but with great difficulty. Organizing with headers would help a lot.

Jason Dyer Staff - 4 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...