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,3

Links

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

Wikipedia, Transposition.

Formula

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

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

Example

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).

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 *)

Prog

(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

Crossrefs

Cf. A000120, A001477, A024316, A070939.

Sequence in context: A361079 A302439 A331855 * A227532 A152534 A136018

Adjacent sequences: A178241 A178242 A178243 * A178245 A178246 A178247

Keyword

nonn,base,easy,look

Author

Juri-Stepan Gerasimov, May 23 2010

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

Status

approved