cp's OEIS Frontend

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.

%I A381622 #10 Apr 05 2025 23:25:07
%S A381622 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,
%T A381622 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,
%U A381622 5,11,2,8,6,3,12,10,4,7,9,1,8,10,2,6,12,3,9,7,4,13,11,5
%N 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.
%C A381622 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.
%C A381622 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.
%C A381622 The total number of moves for row n is 3n-2.
%C A381622 The first column consists of all ones: it is the order of elimination of the first person in the Josephus problem.
%C A381622 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.
%C A381622 T(n,3j-2) = j, for 3j-2 <= n.
%F A381622 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.
%e A381622 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.
%e A381622 Table begins:
%e A381622 1;
%e A381622 1, 2;
%e A381622 1, 2, 3;
%e A381622 1, 3, 4, 2;
%e A381622 1, 5, 3, 2, 4;
%e A381622 1, 3, 5, 2, 6, 4;
%e A381622 1, 7, 5, 2, 4, 6, 3;
%e A381622 1, 7, 4, 2, 8, 6, 3, 5;
%o A381622 (Python)
%o A381622 def T(n, A):
%o A381622     return invPerm(J(n,A))
%o A381622 def J(n,A):
%o A381622     l=[]
%o A381622     for i in range(n):
%o A381622         l.append(i+1)
%o A381622     index = 0
%o A381622     P=[]
%o A381622     for i in range(n):
%o A381622         index+=A[i]
%o A381622         index=index%len(l)
%o A381622         P.append(l[index])
%o A381622         l.pop(index)
%o A381622     return P
%o A381622 def invPerm(p):
%o A381622     inv = []
%o A381622     for i in range(len(p)):
%o A381622         inv.append(None)
%o A381622     for i in range(len(p)):
%o A381622         inv[p[i]-1]=i+1
%o A381622     return inv
%o A381622 def DUU(n):
%o A381622     return [0] + [2 for i in range(n)]
%o A381622 seq = []
%o A381622 for i in range(1,20):
%o A381622     seq += T(i, DUU(i))
%o A381622 print(", ".join([str(v) for v in seq]))
%o A381622 (Python)
%o A381622 def row(n):
%o A381622     i, J, out = 0, list(range(1, n+1)), []
%o A381622     while len(J) > 1:
%o A381622         i = i%len(J)
%o A381622         out.append(J.pop(i))
%o A381622         i = (i + 2)%len(J)
%o A381622     out += [J[0]]
%o A381622     return [out.index(j)+1 for j in list(range(1, n+1))]
%o A381622 print([e for n in range(1, 14) for e in row(n)]) # _Michael S. Branicky_, Mar 27 2025
%Y A381622 Cf. A006257, A016777, A054995, A225381, A321298, A378635, A381623.
%K A381622 nonn,tabl
%O A381622 1,3
%A A381622 _Tanya Khovanova_, _Nathan Sheffield_, and the MIT PRIMES STEP junior group, Mar 22 2025