|
%I #42 Nov 03 2023 17:01:01
%S 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,
%T 5,5,1,6,15,15,20,15,20,20,15,15,20,20,15,20,15,15,6,15,20,20,15,20,
%U 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
%N Number of distinct permutations of binary digits (0's and 1's) in n.
%H Robert Israel, <a href="/A178244/b178244.txt">Table of n, a(n) for n = 0..10000</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Transposition (mathematics)">Transposition</a>.
%F a(n) = binomial((A000120(n) + A023416(n)), A000120(n)).
%F a(n) = binomial(A070939(n), A000120(n)). - _Paolo Xausa_, Nov 03 2023
%e a(0) = 1 because the only permutation is 0 (or 0 written in base 2),
%e a(1) = 1 because the only permutation is 1 (or 1 written in base 2),
%e 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).
%e 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).
%p f:= proc(n) local L;
%p L:= convert(n,base,2);
%p binomial(nops(L),convert(L,`+`))
%p end proc:
%p map(f, [$0..100]); # _Robert Israel_, Oct 25 2023
%t A178244[n_]:=Binomial[BitLength[n],DigitCount[n,2,1]];Array[A178244,100,0] (* _Paolo Xausa_, Nov 03 2023 *)
%o (PARI) A178244(n)=binomial(exponent(n*2+1),hammingweight(n));
%o apply(A178244, [0..99]) \\ _M. F. Hasler_, Feb 23 2023
%o (Python)
%o from math import comb
%o def A178244(n): return comb(n.bit_length(),n.bit_count()) # _Chai Wah Wu_, Mar 13 2023
%Y Cf. A000120, A001477, A024316, A070939.
%K nonn,base,easy,look
%O 0,3
%A _Juri-Stepan Gerasimov_, May 23 2010
%E Corrected (a 3 in the first group removed) by _R. J. Mathar_, May 28 2010
%E Definition corrected by _M. F. Hasler_, Feb 23 2023
|
