## Counting even permutations with repetitions

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

### Counting even permutations with repetitions

I was working on a homework problem, and I was stuck on the last part of the result I needed which is as follows. Given a seven digit number [imath]d_1 d_2 d_3 d_4 d_5 d_6 d_7[/imath]from 0000000 to 9999999, and the function [imath]\sigma(d_i)[/imath] which counts the number of digits to the left of [imath]d_i[/imath] which are strictly greater than [imath]d_i[/imath], then define [imath]N(x)=\sum_{i=1}^7 \sigma(d_i)[/imath] I want to count the subset of these seven digit numbers where [imath]N(x) \equiv 0\ mod\ 2[/imath]. I'm guessing it's somewhere around 5 million since I know the set of permutations of even parity has the same cardinality of the odd parity permutations, however I'm not sure how to deal with permutation actions on the digits that stabilize the numbers. I don't necessarily require the exact number to support my argument, however I would need a good lower bound. So far I've tried some tinkering to see if I could come up with a recursive scheme based on the number of digits, however I'm a bit lost making the leap from two to three digits. As always please provide moderate direction as I would much prefer to enjoy the epiphany if possible, and my instructor will sleep better knowing I did most of the heavy lifting myself.

Thanks as always for the help.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

### Re: Counting even permutations with repetitions

So, I brute forced this with a script and came up with 5005000 and the homework is due this afternoon so I'm going with that. I'm still going to work on this solution though since I could use the practice with counting.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

Patashu
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

### Re: Counting even permutations with repetitions

This might be useful for your extrapolation. If you continually remove one digit from the maximum number size, you get the following pattern of 0 mod 2s and 1 mod 2s:

5005000 4995000
500500 499500
50500 49500
5050 4950
550 450
55 45

jp26
Posts: 7
Joined: Thu Dec 24, 2009 8:15 pm UTC

### Re: Counting even permutations with repetitions

Does it help you to break the set of numbers into ones which are palindromic and those which are not?

Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

### Re: Counting even permutations with repetitions

Ok so talking with my instructor afterwards turned some some interesting information. Firstly, my solution although arrived at differently was the solution he had in mind. Secondly, he didn't have a counting argument he had just written a script to brute force the calculation as I did. This left me with some open question however, so I'd like to state the problem in full. The homework has all been handed, so no harm in something more spoiler intensive responses.

Given a seven digit phone number, a common error at the switchboard would be to transpose two adjacent elements thereby connecting to the wrong person. Come up with a scheme detect such errors, and route them to a "this number is not in service" message. A friend described this as a "self-hashing number" although I'm not sophisticated enough on the computer science end of things to understand what he meant.

The question's I'm left pondering are if the scheme I came up with is maximal? I suspect it is, based on some fuzzy understanding of coset leaders and their relationship to the Hamming distance. Also, I devised my scheme based on the set of even permutations being a subgroup, and the set of stabilizers being a subgroup, so I can view my scheme as all the even permutations of a string and all the odd permutations of a string that stabilize the string, however I'm not sure how/if all those structural pieces can be exploited to tackle these problems.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

jp26
Posts: 7
Joined: Thu Dec 24, 2009 8:15 pm UTC

### Re: Counting even permutations with repetitions

My solution was just based on the fact that for 7 digit phone numbers there are 21 different pairs of digits, an odd number.
Thus the total reversal of any phone number will have the opposite parity for your concept of positive differences. ([imath]n>m[/imath] or [imath]n-m > 0[/imath]). We can then pair up every number with its total reversal and half of those will give most elements of your subset.

We are left with just those phone numbers which are palindromic; there are [imath]10^4[/imath] of them, and they happen to have an even number of positive differences, so all are in your subset. An easy calculation from there gives $\frac{(10^7-10^4)}{2} + 10^4 = 5005000$ as required. A similar idea can be made to work for other length phone numbers, of course.