cp's OEIS Frontend

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.

%I A384770 #18 Aug 18 2025 22:07:28
%S A384770 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,
%T A384770 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,
%U A384770 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
%N 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.
%C A384770 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.
%C A384770 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.
%C A384770 The total number of moves for row n is 4n.
%C A384770 The first column is A384774(n), the order of elimination of the first person in the Josephus problem.
%C A384770 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.
%C A384770 T(n,4j) = j, for 4j <= n.
%F A384770 T(n, 4) = 1 for n >= 4
%F A384770 T(n, k) = T(n-1, k-4 mod n) + 1 if k !== 4 (mod n).
%e A384770 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.
%e A384770 The triangle begins as follows:
%e A384770  1
%e A384770  2, 1;
%e A384770  1, 3, 2;
%e A384770  2, 4, 3, 1;
%e A384770  5, 4, 2, 1, 3;
%e A384770  3, 2, 4, 1, 6, 5;
%e A384770  2, 7, 6, 1, 4, 3, 5;
%e A384770  5, 4, 6, 1, 3, 8, 7, 2;
%e A384770  9, 8, 3, 1, 6, 5, 7, 2, 4
%o A384770 (Python)
%o A384770 def row(n):
%o A384770     i, J, out = 0, list(range(1, n+1)), []
%o A384770     while len(J) > 1:
%o A384770         i = (i + 3)%len(J)
%o A384770         out.append(J.pop(i))
%o A384770     out += [J[0]]
%o A384770     return [out.index(j)+1 for j in list(range(1, n+1))]
%o A384770 print([e for n in range(1, 14) for e in row(n)])
%Y A384770 Cf. A378635, A321298, A006257, A225381, A008586, A384772, A088333, A384774.
%K A384770 nonn,tabl,changed
%O A384770 1,2
%A A384770 _Tanya Khovanova_, _Nathan Sheffield_, and the MIT PRIMES STEP junior group, Jun 09 2025