OFFSET
1,2
COMMENTS
Under-down-down dealing is a dealing pattern where the top card is placed at the bottom of the deck, then the next two cards are dealt. This pattern repeats until all of the cards have been dealt.
This card dealing is related to a variation on the Josephus problem, where one person is skipped, and the next two are eliminated. 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 ??? is an inverse permutation of the corresponding row of this triangle.
The total number of moves for row n is A007494(n) = ceiling(3n/2).
The first column is A381048, the order of elimination of the first person in the Josephus problem.
The index of the largest number in row n is A337191(n), corresponding to the index of the freed person in the corresponding Josephus problem.
LINKS
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,k) = T(n-2,k-3) + 2. T(1,1) = 1. For the first 3 columns, we have T(n,1) = T(n-2,n-2) + 2, T(n,2) = 1, and T(n,3) = 2.
It follows that T(n,3k+2) = 2k+1, T(n,3k) = 2k.
EXAMPLE
Consider a deck of four cards arranged in the order 3,1,2,4. Card 3 goes under, then card 1 is dealt, then card 2 is dealt, then card 4 goes under, then cards 3 and 4 are dealt. Thus, the fourth row of the triangle is 3,1,2,4.
Table begins:
1;
2, 1;
3, 1, 2;
3, 1, 2, 4;
4, 1, 2, 5, 3;
6, 1, 2, 5, 3, 4;
5, 1, 2, 6, 3, 4, 7;
6, 1, 2, 8, 3, 4, 7, 5;
PROG
(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 DDU(n):
return [0] + [(i)%2 for i in range(n)]
def DUD(n):
return DDU(n+1)[1:]
def UDD(n):
return DUD(n+1)[1:]
seq = []
for i in range(1, 10):
seq += T(i, UDD(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 + 1)%len(J)
out.append(J.pop(i))
i = i%len(J)
if len(J) > 1:
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)]) # Michael S. Branicky, Apr 28 2025
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Apr 12 2025
STATUS
approved