A384770 Triangle T(n,k) read by rows, where row n is a permutation of the numbers 1 through n, such that if a deck of n cards is prepared in this order, and under-under-under-down dealing is used, then the resulting cards will be dealt in increasing order.

1, 2, 1, 1, 3, 2, 2, 4, 3, 1, 5, 4, 2, 1, 3, 3, 2, 4, 1, 6, 5, 2, 7, 6, 1, 4, 3, 5, 5, 4, 6, 1, 3, 8, 7, 2, 9, 8, 3, 1, 6, 5, 7, 2, 4, 8, 3, 5, 1, 10, 9, 4, 2, 7, 6, 3, 8, 7, 1, 9, 4, 6, 2, 11, 10, 5, 12, 11, 6, 1, 4, 9, 8, 2, 10, 5, 7, 3, 6, 8, 4, 1, 13, 12, 7, 2, 5, 10, 9, 3, 11

Offset

1,2

Comments

Under-under-under-down dealing is a dealing pattern where the top three cards are placed at the bottom of the deck, and then the next card is dealt. This pattern repeats until all of the cards have been dealt.

This card dealing can equivalently be seen as a variation on the Josephus problem where every 4th person is eliminated. T(n,k) is the number of eliminations in the Josephus problem that occur before the k-th person is eliminated. Equivalently, each row of T is the inverse permutation of the corresponding row of the Josephus triangle A384772, i.e. A384772(n,T(n,k)) = k.

The total number of moves for row n is 4n.

The first column is A384774(n), the order of elimination of the first person in the Josephus problem.

The index of the largest number in row n is A088333(n), corresponding to the index of the freed person in the corresponding Josephus problem.

T(n,4j) = j, for 4j <= n.

Links

Table of n, a(n) for n=1..91.

Eric Huang, Tanya Khovanova, Timur Kilybayev, Ryan Li, Brandon Ni, Leone Seidel, Samarth Sharma, Nathan Sheffield, Vivek Varanasi, Alice Yin, Boya Yun, and William Zelevinsky, Card Dealing Math, arXiv:2509.11395 [math.NT], 2025. See p. 17.

Formula

T(n, 4) = 1 for n >= 4

T(n, k) = T(n-1, k-4 mod n) + 1 if k !== 4 (mod n).

Example

Consider a deck of four cards arranged in the order 2,4,3,1. If we put the top 3 cards under and deal the next card, we will deal card number 1. Now the deck is ordered 2,4,3. If we place 3 cards under and deal the next one, we will deal card number 2, and be left with cards 4,3. Again placing 3 cards under and dealing the next, we will deal card number 3, leaving card number 4 to be dealt last. The dealt cards are in order. Thus, the fourth row of the triangle is 2,4,3,1.
The triangle begins as follows:
 1
 2, 1;
 1, 3, 2;
 2, 4, 3, 1;
 5, 4, 2, 1, 3;
 3, 2, 4, 1, 6, 5;
 2, 7, 6, 1, 4, 3, 5;
 5, 4, 6, 1, 3, 8, 7, 2;
 9, 8, 3, 1, 6, 5, 7, 2, 4

Prog

(Python)
def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 1:
        i = (i + 3)%len(J)
        out.append(J.pop(i))
    out += [J[0]]
    return [out.index(j)+1 for j in list(range(1, n+1))]
print([e for n in range(1, 14) for e in row(n)])

Crossrefs

Cf. A378635, A321298, A006257, A225381, A008586, A384772, A088333, A384774.

Sequence in context: A348217 A290981 A380201 * A161065 A161104 A110248

Adjacent sequences: A384767 A384768 A384769 * A384771 A384772 A384773

Keyword

nonn,tabl

Author

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Jun 09 2025

Status

approved