A191755 -id:A191755 - cp's OEIS frontend

A193020 Number of distinct self-shuffles of the word given by the binary representation of n.

1, 1, 2, 1, 3, 4, 3, 1, 4, 9, 8, 6, 6, 6, 4, 1, 5, 16, 18, 18, 13, 16, 18, 8, 10, 18, 13, 9, 10, 8, 5, 1, 6, 25, 32, 40, 27, 40, 54, 30, 19, 40, 32, 27, 37, 36, 32, 10, 15, 40, 37, 36, 24, 27, 27, 12, 20, 30, 19, 12, 15, 10, 6, 1, 7, 36, 50, 75, 48, 77, 120

Offset: 0

John W. Layman, Jul 14 2011

nonn

See Jeffrey Shallit's A191755 for the definition of self-shuffle and a link to a preprint of the paper "Shuffling and Unshuffling".

An examination of the terms of the sequence leads to the following conjectures (in each case with the caveat that k must exceed a certain lower bound): a(2^k-5)=3k-6, a(2^k-4)=k*(k-1)/2, a(2^k-3)=2k-2, a(2^k-2)=k, a(2^k-1)=1, a(2^k)=k+1, a(2^k+1)=k^2, a(2^k+2)=2*(k-1)^2, a(2^k+3)=k*(k-1)^2/2. To illustrate, consider a(2^k+1); we get, for k=1, 2, 3, ..., a(3)=1, a(5)=4, a(9)=9, a(17)=16, a(33)=25, a(65)=36, a(129)=49, a(257)=64,..., leading to the conjecture that a(2^k+1)=k^2. The other conjectures were arrived at in the same manner.

			The binary representation of n=9 is 1001, which has the nine distinct self-shuffles 1'0'0'1001'1, 1'0'0'101'01, 1'0'0'1'1001, 1'0'10'001'1, 1'0'10'01'01, 1'0'10'1'001, 1'10'0'001'1, 1'10'0'01'01, 1'10'0'1'001 (although 1' is identical to 1, and similarly for 0' and 0, the apostrophes indicate one way in which the digits may be assigned to the two copies of the word 1001 and 1'0'0'1' before self-shuffling).  Thus a(9)=9.

Alois P. Heinz, Table of n, a(n) for n = 0..2048

Cf. A191755, A192296.

A330941 a(n) is the greatest value whose binary representation can be obtained by interleaving (or shuffling) two copies of the binary representation of n.

Original entry on oeis.org

0, 3, 12, 15, 48, 53, 60, 63, 192, 201, 212, 219, 240, 245, 252, 255, 768, 785, 804, 819, 848, 853, 876, 887, 960, 969, 980, 987, 1008, 1013, 1020, 1023, 3072, 3105, 3140, 3171, 3216, 3237, 3276, 3303, 3392, 3401, 3412, 3435, 3504, 3509, 3548, 3567, 3840, 3857

Offset: 0

Rémy Sigrist, Jan 04 2020

The binary representation of all positive terms are square binary words (see A191755).

			The first terms, alongside the binary representations of n and of a(n), are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ----------
   0     0       0           0
   1     3       1          11
   2    12      10        1100
   3    15      11        1111
   4    48     100      110000
   5    53     101      110101
   6    60     110      111100
   7    63     111      111111
   8   192    1000    11000000
   9   201    1001    11001001
  10   212    1010    11010100
  11   219    1011    11011011
  12   240    1100    11110000

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Rémy Sigrist, Logarithmic scatterplot of the first difference of the first 2^13 terms
Rémy Sigrist, PARI program for A330941
Index entries for sequences related to binary expansion of n

See A330940 for the minimum variant.

Cf. A002001, A024036, A191755, A193020.

PARI
```
See Links section.
```

a(2^k) = 3*4^k = A002001(k+1) for any k >= 0.
a(2^k-1) = 4^k-1 = A024036(k) for any k >= 0.
a(n) >= A330940(n).

A279200 Number of square permutations of 2n things.

Original entry on oeis.org

1, 2, 20, 504, 21032, 1293418

Offset: 0

N. J. A. Sloane, Dec 15 2016

			The 20 square permutations of order 4 are 1234, 1243, 1423, 1324, 1342, 4132, 3124, 3142, 3412, 4312, 2134, 2143, 2413, 4213, 2314, 2431, 4231, 3241, 3421, 4321.

Samuele Giraudo, S. Vialette, Unshuffling Permutations, arXiv preprint arXiv:1601.05962 [cs.DS], 2016.

Cf. A191755 (square binary words).

A330940 a(n) is the least value whose binary representation can be obtained by interleaving (or shuffling) two copies of the binary representation of n.

Original entry on oeis.org

0, 3, 10, 15, 36, 43, 54, 63, 136, 147, 170, 175, 204, 219, 238, 255, 528, 547, 586, 591, 660, 683, 694, 703, 792, 819, 858, 879, 924, 955, 990, 1023, 2080, 2115, 2186, 2191, 2340, 2347, 2358, 2367, 2600, 2643, 2730, 2735, 2764, 2779, 2798, 2815, 3120, 3171

Offset: 0

Rémy Sigrist, Jan 04 2020

The binary representation of all positive terms are square binary words (see A191755).

			The first terms, alongside the binary representation of n and of a(n), are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0       0          0
   1     3       1         11
   2    10      10       1010
   3    15      11       1111
   4    36     100     100100
   5    43     101     101011
   6    54     110     110110
   7    63     111     111111
   8   136    1000   10001000
   9   147    1001   10010011
  10   170    1010   10101010
  11   175    1011   10101111

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Rémy Sigrist, Logarithmic scatterplot of the first difference of the first 2^13 terms
Rémy Sigrist, PARI program for A330940
Index entries for sequences related to binary expansion of n

See A330941 for the maximum variant.

Cf. A007582, A024036, A191755, A193020.

PARI
```
See Links section.
```

a(2^k) = 2^k*(1+2^(k+1)) = A007582(k+1) for any k >= 0.
a(2^k-1) = 4^k-1 = A024036(k) for any k >= 0.
a(n) <= A330941(n).

A361398 An infiltration of two words, say x and y, is a shuffle of x and y optionally followed by replacements of pairs of consecutive equal symbols, say two d's, one of which comes from x and the other from y, by a single d (that cannot be part of another replacement); a(n) is the number of distinct infiltrations of the word given by the binary representation of n with itself.

Original entry on oeis.org

1, 2, 5, 3, 9, 12, 9, 4, 14, 28, 30, 21, 19, 21, 14, 5, 20, 53, 68, 60, 55, 74, 68, 32, 34, 60, 55, 36, 34, 32, 20, 6, 27, 89, 126, 134, 120, 181, 196, 108, 88, 181, 183, 136, 151, 164, 126, 45, 55, 134, 151, 129, 107, 136, 120, 54, 69, 108, 88, 54, 55, 45, 27

Offset: 0

Rémy Sigrist, Mar 10 2023

Leading zeros in binary expansions are ignored.

See A191755 for the definition of a shuffle.

			For n = 2:
- the binary expansion of 2 is "10",
- we have essentially the following infiltrations:
         x        10   10    1 0   10     1 0
         y        10   1 0    10     10    1 0
                  --   ---   ---   ----   ----
    infiltration  10   100   110   1010   1100
- so a(2) = 5.

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Rémy Sigrist, PARI program
Wikipedia, Infiltration product.
Index entries for sequences related to binary expansion of n

Cf. A000096, A191755, A193020.

PARI
```
See Links section.
```

a(n) >= A193020(n).
a(2^k - 1) = k + 1 for any k >= 0.
a(2^k) = A000096(k + 1) for any k >= 0.

A192296 Number of ternary words of length 2n obtained by self-shuffling.

Original entry on oeis.org

1, 3, 15, 93, 621, 4425, 32703, 248901, 1934007, 15285771, 122437215, 991731999, 8107830597

Offset: 0

John W. Layman, Jun 27 2011

See A191755 for the number of binary words of length 2n obtained by self-shuffling and also for an explanation of "self-shuffling" and a reference.

			a(2) = 15 because {0,0,0,0}, {0,0,1,1}, {0,0,2,2}, {0,1,0,1}, {0,2,0,2}, {1,0,1,0}, {1,1,0,0}, {1,1,1,1}, {1,1,2,2}, {1,2,1,2}, {2,0,2,0}, {2,1,2,1}, {2,2,0,0}, {2,2,1,1}, {2,2,2,2} (and no other ternary words of length 4) are generated by self-shuffling.

N. Rampersad and J. Shallit, Shuffling and unshuffling, preprint, arXiv:1106.5767 [cs.FL], 2011.

Cf. A191755.

from itertools import product, combinations
def a(n):
  if n<=1: return 3**n
  range2n, set2n = list(range(2*n)), set(range(2*n))
  allset, ssw = set(), [0 for i in range(2*n)]
  for w in product("012", repeat=n-1):
    w = "0" + "".join(w)
    if w.count("1") > w.count("2"): continue
    for s in combinations(range2n, n):
      nots = sorted(set2n-set(s))
      for i, c in enumerate(w): ssw[s[i]] = ssw[nots[i]] = c
      allset.add("".join(ssw))
  num2g1 = sum(w.count("1") < w.count("2") for w in allset)
  return 3*(len(allset) + num2g1)
print([a(n) for n in range(8)]) # Michael S. Branicky, Jan 03 2021

a(8)-a(9) from Alois P. Heinz, Sep 26 2011

a(10)-a(12) from Bert Dobbelaere, Oct 02 2018

A358892 Numbers obtained by self-shuffling the binary expansion of nonnegative numbers.

Original entry on oeis.org

0, 3, 10, 12, 15, 36, 40, 43, 45, 48, 51, 53, 54, 58, 60, 63, 136, 144, 147, 149, 153, 160, 163, 165, 169, 170, 172, 175, 178, 180, 183, 187, 192, 195, 197, 201, 202, 204, 207, 210, 212, 215, 216, 219, 221, 228, 232, 235, 237, 238, 240, 243, 245, 246, 250, 252

Offset: 1

Rémy Sigrist, Dec 05 2022

This sequence lists the distinct values in A358893, in ascending order.
For any n > 0, there are A191755(n)/2 terms with binary length 2*n.
All terms are evil (A001969) and have an even number of binary digits (A053754).

			The binary expansion of 204 is "11001100" and can be obtained by self-shuffling the binary expansion of 10 ("1010") or 12 ("1100"), so 204 is a term.

Rémy Sigrist, PARI program
Index entries for sequences related to binary expansion of n

Cf. A001969, A053754, A191755, A358893.

PARI
```
See Links section.
```

A331850 Largest cardinality of a set obtained by self-shuffling a binary word of length n.

Original entry on oeis.org

1, 2, 4, 9, 18, 54, 120, 324, 900, 2406, 6400, 19600, 50176, 148042, 442325, 1373070, 3954113

Offset: 1

Jeffrey Shallit, Jan 29 2020

The self-shuffle of a length-n word w is the set of all length-2n words that can be obtained by interleaving w with itself, as in the shuffle of a deck of cards (but not a perfect shuffle).

			For n = 3 one can obtain {010010, 001010, 010100, 001100} by self-shuffling 010, so a(3) = 4.

Cf. A191755.

# uses a() in A191755; a(n)[2] generates the lex. least argmax
print([a(n)[1] for n in range(1, 9)]) # Michael S. Branicky, Sep 28 2021

For n = 1..17 the values a(n) are achieved by the lexicographically least strings given below:
: 0
: 01
: 010
: 0110
: 00110
: 011001
: 0110001
: 01100110
: 011000110
: 0110001110
: 01110001110
: 011100001110
: 0111000001110
: 01100011110001
: 011000011110001
: 0111000011110001
: 01110000011110001

a(11)-a(13) from Giovanni Resta, Jan 29 2020
a(14)-a(15) from Giovanni Resta, Jan 30 2020
a(16)-a(17) from Bert Dobbelaere, Feb 08 2020

A360412 Number of binary words of length 2n with an even number of 1's which are not shuffle squares.

Original entry on oeis.org

0, 0, 2, 10, 46, 192, 780, 3090, 12136, 47100, 181820, 697856, 2667642, 10157814, 38563342, 146002012, 551483230, 2078722874, 7821121318, 29378487188

Offset: 0

Bartlomiej Pawlik, Feb 07 2023

A shuffle square is a word obtained by self-shuffling, e.g., the French word "tuteurer" is a shuffle square as it can be obtained by self-shuffling the word "tuer".

Words with an odd number of 1's obviously are not shuffle squares.

			a(3)=10, since the binary words of length 6 with an even number of 1's which are not shuffle squares are 000110, 010001, 011000, 011101, 011110, 100001, 100010, 100111, 101110 and 111001.

Cf. A191755.

a(n) = 2^(2n-1) - A191755(n), since the number of binary words of length 2n with an even number of 1's is 2^(2n-1).

A384705 Number of binary shuffle squares of length 2n with prefix 0, that can be obtained from a unique binary word of length n.

Original entry on oeis.org

1, 3, 11, 38, 135, 475, 1681, 5875, 20641, 71956, 250448, 869332, 3015496, 10440429

Offset: 1

Bartlomiej Pawlik, Jun 07 2025

A shuffle square is a word obtained by self-shuffle (i.e. by mixing two copies of the same word, keeping the order of letters from each copy). For example, the shuffle square "tuteurer" can be obtained by self-shuffling the word "tuer" (tu-t-e-u-r-er). The word 0011 is a shuffle square, while 0110 is not.

			a(4) = 38 since there are exactly 41 binary shuffle squares of length 8 starting with 0, however three of them can be obtained from more than one binary word:
00100100 can be obtained from 0010 (e.g., 001-001-0-0) and from 0100 (e.g., 0-0-100-100);
00101011 from 0011 (001-0-1-011) and from 0101 (0-0-10-101-1);
00110011 from 0011 (e.g., 0011-0011) and form 0101 (e.g., 0-0-1-1-0-0-1-1).

D. Datko and Bartlomiej Pawlik, Roots of Binary Shuffle Squares, Symmetry 17/2: 305 (2025).

Cf. A191755 (number of all binary shuffle squares with length 2n).

from collections import Counter
from itertools import combinations, combinations_with_replacement as cwr
from sympy.utilities.iterables import multiset_permutations as mp
def self_shuffles(w):
    sswset, n = set(), len(w)
    set2n, ssw = set(range(2*n)), [0 for i in range(2*n)]
    for s in combinations(list(range(2*n)), n):
        nots = sorted(set2n-set(s))
        for i, c in enumerate(w): ssw[s[i]] = ssw[nots[i]] = c
        sswset.add("".join(ssw))
    return sswset
def a(n):
    if n == 0: return 1
    u = 0
    for w in cwr("10", n-1):          # "base" or "sorted" roots
        c = Counter()
        for pw in mp(w):              # iterate over permutations of these
            pw = "0" + "".join(pw)    # enforce prefix 0
            sspw = self_shuffles(pw)  # build self_shuffles from these roots
            c.update(sspw)
        u += sum(1 for x in c if c[x] == 1)  # count results w/unique roots
    return u
print([a(n) for n in range(1, 10)]) # Michael S. Branicky, Jun 17 2025

a(10)-a(12) corrected by Michael S. Branicky, Jun 15 2025
a(13) from Michael S. Branicky, Jun 17 2025
a(14) from Sean A. Irvine, Jun 24 2025

cp's OEIS Frontend

A193020 Number of distinct self-shuffles of the word given by the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A330941 a(n) is the greatest value whose binary representation can be obtained by interleaving (or shuffling) two copies of the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A279200 Number of square permutations of 2n things.

Views

Author

Keywords

Examples

Links

Crossrefs

A330940 a(n) is the least value whose binary representation can be obtained by interleaving (or shuffling) two copies of the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A192296 Number of ternary words of length 2n obtained by self-shuffling.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A358892 Numbers obtained by self-shuffling the binary expansion of nonnegative numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A331850 Largest cardinality of a set obtained by self-shuffling a binary word of length n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

Extensions