cp's OEIS Frontend

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

%I A386639 #11 Aug 06 2025 22:42:01
%S A386639 1,2,1,3,1,2,2,1,4,3,3,1,4,5,2,4,1,6,3,2,5,5,1,3,4,2,6,7,3,1,7,5,2,6,
%T A386639 8,4,7,1,8,6,2,9,4,5,3,9,1,8,5,2,4,7,6,3,10,5,1,6,4,2,10,11,7,3,8,9,7,
%U A386639 1,4,9,2,11,10,8,3,6,5,12,4,1,13,11,2,10,6,7,3,5,12,9,8,10,1,7,6,2,12,8,5,3,14
%N A386639 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 the AP dealing is used, then the resulting cards will be dealt in increasing order.
%C A386639 The AP dealing is a dealing pattern where x cards are placed at the bottom of the deck, and then the next card is dealt. The number of cards x placed at the bottom changes with every dealt card according to the arithmetic progression 1, 2, 3, and so on. This pattern repeats until all of the cards have been dealt.
%C A386639 This card dealing can equivalently be seen as a variation on the Josephus problem, where one person is skipped, then the next person is eliminated, then two people are skipped and one person is eliminated, then three people are skipped, and so on. T(n,k) is the order of elimination of the k-th person in the Josephus problem. Equivalently, each row of T is the inverse permutation of the corresponding row of the Josephus triangle A386641, i.e., A386641(n,T(n,k)) = k.
%C A386639 The total number of moves for row n is A000096.
%C A386639 The first column is A386643(n), the order of elimination of the first person in the Josephus problem.
%C A386639 The index of the largest number in row n is A291317(n), corresponding to the index of the freed person in the corresponding Josephus problem.
%F A386639 T(n,A000096(k)) = k, for A000096(k) <= n.
%e A386639 Consider a deck of four cards arranged in the order 2,1,4,3. We put one card under and deal the next card, which is card number 1. Now the deck is ordered 4,3,2. We place 2 cards under and deal the next one, which is card number 2. Now the deck is 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,1,4,3.
%e A386639 The triangle begins as follows:
%e A386639   1;
%e A386639   2, 1;
%e A386639   3, 1, 2;
%e A386639   2, 1, 4, 3;
%e A386639   3, 1, 4, 5, 2;
%e A386639   4, 1, 6, 3, 2, 5;
%e A386639   5, 1, 3, 4, 2, 6, 7;
%e A386639   3, 1, 7, 5, 2, 6, 8, 4;
%e A386639   7, 1, 8, 6, 2, 9, 4, 5, 3;
%Y A386639 Cf. A000096, A291317, A386641, A386643.
%Y A386639 Cf. A378635 (classical elimination process).
%K A386639 nonn,tabl
%O A386639 1,2
%A A386639 _Tanya Khovanova_, _Nathan Sheffield_, and the MIT PRIMES STEP junior group, Jul 27 2025