A067281 Number of permutations of {1,2,3,...,n} where the elements of n are considered indistinguishable if they differ by a power of 2 (for example 3, 12 and 24 are all considered equivalent).

1, 1, 1, 3, 4, 20, 60, 420, 840, 7560, 37800, 415800, 1663200, 21621600, 151351200, 2270268000, 7264857600, 123502579200, 1111523212800, 21118941043200, 140792940288000, 2956651746048000, 32523169206528000, 748032891750144000, 4488197350500864000

Offset: 0

Author

Brian Rothbach (rothbach(AT)math.berkeley.edu), Feb 23 2002

Keywords

• easy
• nonn

Comments

Alternatively, one can think of these sequences as permutation of {1,2,...,n} where the term n corresponds to the appropriate ideal in Z[1/2]. This description gives an obvious generalization to Z[1/n] or other localizations of Z.

The conjecture a(2n+1)=(2n+1)a(2n) is obviously true from the definition of the sequence and the fact that 2n+1 is the smallest element of its equivalence class. - Brian Rothbach (rothbach(AT)Math.Berkeley.EDU), Sep 15 2004

a(2n+1) = (2n+1)*a(2n). However, a(n+1)/a(n) is non-integral for n = {3, 15, 19...}.

Examples

			a(6) = 20 since {1,2,3,4,5,6} becomes {1,1,3,1,5,3} which has 60 permutations.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..490 (terms n=1..250 from Sean A. Irvine)
• Sean A. Irvine, Java program (github)

Crossrefs

Cf. A000265.

Extensions

More terms from Vladeta Jovovic, Mar 09 2002

a(0)=1 prepended by Alois P. Heinz, Dec 11 2023