A178244 Number of distinct permutations of binary digits (0's and 1's) in n.

1, 1, 2, 1, 3, 3, 3, 1, 4, 6, 6, 4, 6, 4, 4, 1, 5, 10, 10, 10, 10, 10, 10, 5, 10, 10, 10, 5, 10, 5, 5, 1, 6, 15, 15, 20, 15, 20, 20, 15, 15, 20, 20, 15, 20, 15, 15, 6, 15, 20, 20, 15, 20, 15, 15, 6, 20, 15, 15, 6, 15, 6, 6, 1, 7, 21, 21, 35, 21, 35, 35, 35, 21, 35, 35, 35, 35, 35, 35, 21

Offset: 0

Author

Juri-Stepan Gerasimov, May 23 2010

Keywords

• nonn
• base
• easy
• look

Examples

			a(0) = 1 because the only permutation is 0 (or 0 written in base 2),
a(1) = 1 because the only permutation is 1 (or 1 written in base 2),
a(3) = 2 because there are two distinct permutations of the binary digits in 2 = 10_2: {01, 10} (identity permutation and transposition tau_12).
a(12) = 6, because the binary digits of 12 = 1100_2 have 6 distinct permutations {0011, 0101, 0110, 1001, 1010, 1100}, of which only 0101, 0110, 1001, 1010 are transpositions (= permutations changing exactly 2 elements).
		

Links

• Robert Israel, Table of n, a(n) for n = 0..10000
• Wikipedia, Transposition.

Crossrefs

Cf. A000120, A001477, A024316, A070939.

Programs

Maple

f:= proc(n) local L;
  L:= convert(n,base,2);
  binomial(nops(L),convert(L,`+`))
end proc:
map(f, [$0..100]); # Robert Israel, Oct 25 2023

Mathematica

A178244[n_]:=Binomial[BitLength[n],DigitCount[n,2,1]];Array[A178244,100,0] (* Paolo Xausa, Nov 03 2023 *)

PARI

A178244(n)=binomial(exponent(n*2+1),hammingweight(n));
apply(A178244, [0..99]) \\ M. F. Hasler, Feb 23 2023

Python

from math import comb
def A178244(n): return comb(n.bit_length(),n.bit_count()) # Chai Wah Wu, Mar 13 2023

Formula

a(n) = binomial((A000120(n) + A023416(n)), A000120(n)).

a(n) = binomial(A070939(n), A000120(n)). - Paolo Xausa, Nov 03 2023

Extensions

Corrected (a 3 in the first group removed) by R. J. Mathar, May 28 2010

Definition corrected by M. F. Hasler, Feb 23 2023