cp's OEIS Frontend

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

%I A383847 #8 May 23 2025 16:06:14
%S A383847 1,1,2,1,2,3,1,2,4,3,1,2,5,3,4,1,2,5,3,4,6,1,2,6,3,4,7,5,1,2,8,3,4,7,
%T A383847 5,6,1,2,7,3,4,8,5,6,9,1,2,8,3,4,10,5,6,9,7,1,2,11,3,4,9,5,6,10,7,8,1,
%U A383847 2,9,3,4,10,5,6,12,7,8,11,1,2,10,3,4,13,5,6,11,7,8,12,9
%N A383847 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-down-under dealing is used, then the resulting cards will be dealt in increasing order.
%C A383847 Down-down-under dealing is a dealing pattern where the top two cards are dealt, then the third card is placed at the bottom of the deck. This pattern repeats until all of the cards have been dealt.
%C A383847 This card dealing is related to a variation on the Josephus problem, where the first two people are eliminated, and the third person is skipped. 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 A383845 is an inverse permutation of the corresponding row of this triangle.
%C A383847 The total number of moves for row n is A001651(n) = floor((3*n-1)/2).
%C A383847 The index of the largest number in row n is A383846(n), corresponding to the index of the freed person in the corresponding Josephus problem.
%F A383847 T(n,3j+1) = 2j+1, for 3j+1 <= n. T(n,3j+2) = 2j+2, for 3j+2 <= n.
%e A383847 Consider a deck of four cards arranged in the order 1,2,4,3. In round 1, card 1 is dealt, card 2 is dealt, and card 4 goes under. Now the deck is ordered 3,4. In round 2, card 3 is dealt, then card 4 is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 1,2,4,3.
%e A383847 The table begins:
%e A383847   1;
%e A383847   1, 2;
%e A383847   1, 2, 3;
%e A383847   1, 2, 4, 3;
%e A383847   1, 2, 5, 3, 4;
%e A383847   1, 2, 5, 3, 4, 6;
%e A383847   1, 2, 6, 3, 4, 7, 5;
%e A383847   1, 2, 8, 3, 4, 7, 5, 6;
%o A383847 (Python)
%o A383847 def row(n):
%o A383847     i, J, out = 0, list(range(1, n+1)), []
%o A383847     while len(J) > 1:
%o A383847         out.append(J.pop(i))
%o A383847         i = i%len(J)
%o A383847         if len(J) > 1:
%o A383847             out.append(J.pop(i))
%o A383847         i = (i + 1)%len(J)
%o A383847     out += [J[0]]
%o A383847     return [out.index(j)+1 for j in list(range(1, n+1))]
%o A383847 print([e for n in range(1, 14) for e in row(n)])
%Y A383847 Cf. A006257, A001651, A225381, A321298, A378635, A383845, A383846, A381050, A382528.
%K A383847 nonn,tabl
%O A383847 1,3
%A A383847 _Tanya Khovanova_, _Nathan Sheffield_, and the MIT PRIMES STEP junior group, May 12 2025