Different patterns in Sn modulo 2, is it A001405?
Ivica Kolar
telpro at kvid.hr
Thu Dec 20 11:37:07 CET 2007
Thank you all for your kind answers!
You got me thinking ;)
"The combinations function is one of the most fundamental in
combinatorics, and while S_n is equally fundamental, looking
at numbers modulo 2 is a fairly specialized operation. (Franklin )"
Sorry, I was not clear enough. My "point of view" is modulo i, not just modulo 2.
Please, let me defend (and I hope, explain) my modulo i point of view:
1. Index of permutation, [0..n!-1]
Let Ix be integer index of a permutation from Sn, Ix element of [0..n!-1].
We can get rid of base 10 integers expressing them in Factorial Number System, FNS.
That is modulo i number system, i element of [2..n], base i!.
Let R be index of a permutation expressed in FNS.
2. Permutation Generator, PG
Lets define PG as transformation of R to permutation, P.
I'm aware of two family of PG's which converts R to P using modulo i arithmetic (+,-), i element of [2..n].
3. Permutation
P obtained above can be viewed as own index expressed in base n number system.
So, Ix and R and P are all the same thing, what differs is only used number system.
That allows me to view the whole Sn as modulo i thing,
with i being fixed, i.e. n, or i varying from 2 to n...
Now back to the subject:
Lets define n! as "number of different patterns in the set of all permutations Sn taken modulo n".
Generalized question now becomes:
What is the number of different patterns in the set of all permutations Sn taken modulo i, i element of [2..n]?
Sequences:
SEQ CONSTRUCTION (FIXED i)
i n= 1 2 3 4 5 6 7 8 OEIS
-----------------------------------------------
2 1,2,3, 6, 10, 20, 35, 70,.. A001405
3 1,2,6,12, 30, 90, 210, 560,.. A022916
4 1,2,6,24, 60,180, 630, 2520,.. A022917
5 1,2,6,24,120,360,1260, 5040,.. -------
6 1,2,6,24,120,720,2520,10080,.. -------
7 1,2,6,24,120,720,5040,20160,.. -------
..
-----------------------------------------------
limes A000142 n!
Solutions:
----------
i=2 A001405 Central binomial coefficients: C(n,floor(n/2)).
i=3 A022916 Multinomial coefficient n!/([n/3]![(n+1)/3]![(n+2)/3]!)
i=4 A022917 Multinomial coefficient n!/ ([n/4]!, [(n+1)/4]!, [(n+2)/4]!, [(n+3)/4]!)
...
Thank you again,
--ivica
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20071220/e7419844/attachment-0001.htm>
More information about the SeqFan
mailing list