cp's OEIS Frontend

A378674 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 down-under dealing is used, then the resulting cards are put down in increasing order.

%I A378674 #23 May 16 2025 14:33:09
%S A378674 1,1,2,1,3,2,1,3,2,4,1,5,2,4,3,1,4,2,6,3,5,1,6,2,5,3,7,4,1,5,2,7,3,6,
%T A378674 4,8,1,9,2,6,3,8,4,7,5,1,6,2,10,3,7,4,9,5,8,1,9,2,7,3,11,4,8,5,10,6,1,
%U A378674 7,2,10,3,8,4,12,5,9,6,11,1,12,2,8,3,11,4,9,5,13,6,10,7,1,8,2,13,3
%N A378674 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 down-under dealing is used, then the resulting cards are put down in increasing order.
%C A378674 Down-under dealing is a dealing pattern where the top card is dealt then the next card is put on the bottom of the deck. Then, this pattern repeats until all cards are dealt.
%C A378674 This card dealing is related to a variation of the Josephus problem, where the first person is eliminated and the second person is skipped. The card in row n and column k is x if and only if in the Josephus problem variation with n people, the person number x is the k-th person eliminated. Equivalently, each row of the Josephus triangle A378682 related to this variation is an inverse permutation of the corresponding row of this triangle.
%C A378674 The total number of moves for row n is 2n-1.
%C A378674 The first column is the order of elimination of the first person in the corresponding variation of the Josephus problem and consists of all ones.
%C A378674 The index of the largest number in row n is A152423(n), corresponding to the index of the freed person in this variation of the Josephus problem.
%C A378674 T(n,2j-1) = j, for 2j-1 <= n.
%C A378674 Sequence A378635 represents a similar triangle for under-down dealing.
%F A378674 T(1,1) = 1, for n > 1, T(n,1) = 1 and T(n,2) = T(n-1,n-1) + 1. For n > 1 and k > 2, T(n,k) = T(n-1,k-2) + 1.
%F A378674 From _Pontus von Brömssen_, Dec 11 2024: (Start)
%F A378674 T(n,k) = A378635(n-1,k-1) + 1 for 2 <= k <= n.
%F A378674 T(n,k) = A378635(n,(k mod n) + 1).
%F A378674 (End)
%e A378674 Suppose there are four cards arranged in order 1,3,2,4. Card 1 is dealt, and card 3 goes under, then card 2 is dealt, and card 4 goes under. Now, the leftover deck is ordered 3,4. Card 3 is dealt, and card 4 goes under. Now, the leftover deck is card 4, which is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 1,3,2,4.
%e A378674 Triangle begins:
%e A378674   1;
%e A378674   1, 2;
%e A378674   1, 3, 2;
%e A378674   1, 3, 2, 4;
%e A378674   1, 5, 2, 4, 3;
%e A378674   1, 4, 2, 6, 3, 5;
%e A378674   1, 6, 2, 5, 3, 7, 4;
%e A378674   1, 5, 2, 7, 3, 6, 4, 8;
%e A378674   1, 9, 2, 6, 3, 8, 4, 7, 5;
%t A378674 row[n_] := Module[{ds, res, k, i = 1, len}, ds = CreateDataStructure["Queue", Range[n]]; res = CreateDataStructure["FixedArray", n]; While[(ds["Length"] >= 2), res["SetPart", i++, ds["Pop"]]; ds["Push", ds["Pop"]];]; res["SetPart", n, ds["Pop"]]; Flatten[PositionIndex[res["Elements"]] /@ Range[n]]]; Array[row, 14, 1] // Flatten (* _Shenghui Yang_, May 16 2025 *)
%Y A378674 Cf. A006257, A152423, A225381, A321298, A378635, A378682, A381050.
%K A378674 nonn,tabl
%O A378674 1,3
%A A378674 _Tanya Khovanova_ and the MIT PRIMES STEP junior group, Dec 03 2024