cp's OEIS Frontend

A378635 Triangle T(n,k) read by rows, where row n is a permutation of numbers 1 through n, such that if the deck of n cards is prepared in this order, and under-down dealing is used, then the resulting cards are put down in increasing order.

%I A378635 #12 Dec 12 2024 15:21:32
%S A378635 1,2,1,2,1,3,4,1,3,2,3,1,5,2,4,5,1,4,2,6,3,4,1,6,2,5,3,7,8,1,5,2,7,3,
%T A378635 6,4,5,1,9,2,6,3,8,4,7,8,1,6,2,10,3,7,4,9,5,6,1,9,2,7,3,11,4,8,5,10,
%U A378635 11,1,7,2,10,3,8,4,12,5,9,6,7,1,12,2,8,3,11,4,9,5,13,6,10,11,1,8,2,13,3,9,4
%N A378635 Triangle T(n,k) read by rows, where row n is a permutation of numbers 1 through n, such that if the deck of n cards is prepared in this order, and under-down dealing is used, then the resulting cards are put down in increasing order.
%C A378635 Under-down dealing is a dealing pattern where the top card is put on the bottom of the deck, and the next card is dealt. Then, this pattern repeats until all cards are dealt.
%C A378635 This card dealing is related to the Josephus problem. The card in row n and column k is x if and only if in the Josephus problem with n people, the person number x is the k-th person eliminated. Equivalently, each row of Josephus triangle A321298 is an inverse permutation of the corresponding row of this triangle.
%C A378635 The total number of moves for row n is 2n.
%C A378635 The first column is A225381, the order of elimination of the first person in the Josephus problem.
%C A378635 The index of the largest number in row n is A006257(n), corresponding to the index of the freed person in the Josephus problem.
%C A378635 T(n,2j) = j, for 2j <= n.
%F A378635 T(1,1) = 1, for n > 1, T(n,1) = T(n-1,n-1) + 1 and T(n,2) = 1. For n > 1 and k > 2, T(n,k) = T(n-1,k-2) + 1.
%e A378635 Suppose there are four cards arranged in order 4,1,3,2. Card 4 goes under, and card 1 is dealt. Now the deck is ordered 3,2,4. Card 3 goes under, and card 2 is dealt. Now the leftover deck is ordered 4,3. Card 4 goes under, and card 3 is dealt. Then card 4 goes under, and card 4 is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 4,1,3,2.
%e A378635 Triangle begins:
%e A378635   1;
%e A378635   2, 1;
%e A378635   2, 1, 3;
%e A378635   4, 1, 3, 2;
%e A378635   3, 1, 5, 2, 4;
%e A378635   5, 1, 4, 2, 6, 3;
%e A378635   4, 1, 6, 2, 5, 3, 7;
%e A378635   8, 1, 5, 2, 7, 3, 6, 4;
%e A378635   5, 1, 9, 2, 6, 3, 8, 4, 7;
%Y A378635 Cf. A005843, A006257, A225381, A321298.
%K A378635 nonn,tabl
%O A378635 1,2
%A A378635 _Tanya Khovanova_ and the MIT PRIMES STEP junior group, Dec 02 2024