Counting even permutations with repetitions

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Counting even permutations with repetitions

Postby Cleverbeans » Wed Jul 21, 2010 4:20 am UTC

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. :D
"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

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

Re: Counting even permutations with repetitions

Postby Cleverbeans » Wed Jul 21, 2010 12:50 pm UTC

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

User avatar
Patashu
Answerful Bignitude
Posts: 378
Joined: Mon Mar 12, 2007 8:54 am UTC
Contact:

Re: Counting even permutations with repetitions

Postby Patashu » Wed Jul 21, 2010 12:58 pm UTC

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

Postby jp26 » Wed Jul 21, 2010 1:53 pm UTC

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

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

Re: Counting even permutations with repetitions

Postby Cleverbeans » Fri Jul 23, 2010 2:31 pm UTC

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

Postby jp26 » Fri Jul 23, 2010 3:28 pm UTC

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 [math]\frac{(10^7-10^4)}{2} + 10^4 = 5005000[/math] as required. A similar idea can be made to work for other length phone numbers, of course.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests