A381622 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 down-under-under dealing is used, then the resulting cards will be dealt in increasing order.

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

Offset: 1

Author

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Mar 22 2025

Keywords

• nonn
• tabl

Comments

Down-under-under dealing is a dealing pattern where the top card is dealt; then the next two cards are placed at the bottom of the deck. This pattern repeats until all of the cards have been dealt.

This card dealing is related to a variation on the Josephus problem, where the first person is eliminated, then two people are skipped, and then the process is repeated. The card in row n and column k is x if and only if in the corresponding Josephus problem with n people, the person number x is the k-th person eliminated. Equivalently, each row of Josephus triangle A381623(n) is an inverse permutation of the corresponding row of this triangle.

The total number of moves for row n is 3n-2.

The first column consists of all ones: it is the order of elimination of the first person in the Josephus problem.

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

T(n,3j-2) = j, for 3j-2 <= n.

Examples

			Consider a deck of four cards arranged in the order 1,3,4,2. Card 1 is dealt. Then cards 3 and 4 go under, and card 2 is dealt. Now the deck is ordered 3,4. Cards 3 and 4 go under, and card 3 is dealt. Then card 4 is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 1,3,4,2.
Table begins:
1;
1, 2;
1, 2, 3;
1, 3, 4, 2;
1, 5, 3, 2, 4;
1, 3, 5, 2, 6, 4;
1, 7, 5, 2, 4, 6, 3;
1, 7, 4, 2, 8, 6, 3, 5;
		

Crossrefs

Cf. A006257, A016777, A054995, A225381, A321298, A378635, A381623.

Programs

Python

def T(n, A):
    return invPerm(J(n,A))
def J(n,A):
    l=[]
    for i in range(n):
        l.append(i+1)
    index = 0
    P=[]
    for i in range(n):
        index+=A[i]
        index=index%len(l)
        P.append(l[index])
        l.pop(index)
    return P
def invPerm(p):
    inv = []
    for i in range(len(p)):
        inv.append(None)
    for i in range(len(p)):
        inv[p[i]-1]=i+1
    return inv
def DUU(n):
    return [0] + [2 for i in range(n)]
seq = []
for i in range(1,20):
    seq += T(i, DUU(i))
print(", ".join([str(v) for v in seq]))

Python

def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 1:
        i = i%len(J)
        out.append(J.pop(i))
        i = (i + 2)%len(J)
    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)]) # Michael S. Branicky, Mar 27 2025

Formula

For any n, we have T(n,1) = 1. T(2,2) = 2. For n > 2, T(n,2) = T(n-1,n-2) + 1 and T(n,3) = T(n-1,n-1) + 1. For n > 3 and k > 3, T(n,k) = T(n-1,k-3) + 1.