cp's OEIS Frontend

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

%I A381050 #29 May 15 2025 21:24:35
%S A381050 1,1,2,1,3,2,1,4,2,3,1,4,2,3,5,1,5,2,3,6,4,1,7,2,3,6,4,5,1,6,2,3,7,4,
%T A381050 5,8,1,7,2,3,9,4,5,8,6,1,10,2,3,8,4,5,9,6,7,1,8,2,3,9,4,5,11,6,7,10,1,
%U A381050 9,2,3,12,4,5,10,6,7,11,8,1,12,2,3,10,4,5,11,6,7,13,8,9
%N A381050 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-under-down dealing is used, then the resulting cards will be dealt in increasing order.
%C A381050 Down-under-down dealing is a dealing pattern where the top card is dealt, the second card is placed at the bottom of the deck, then the third card is dealt. This pattern repeats until all of the cards have been dealt.
%C A381050 This card dealing is related to a variation on the Josephus problem, where the first person is eliminated, the second person is skipped, and the third person is eliminated. 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 A383076 is an inverse permutation of the corresponding row of this triangle.
%C A381050 The total number of moves for row n is A032766(n) = floor(3n/2).
%C A381050 The index of the largest number in row n is A381051(n), corresponding to the index of the freed person in the corresponding Josephus problem.
%F A381050 T(n,3j) = 2j, for 3j <= n. T(n,3j+1) = 2j+1, for 3j+1 <= n.
%e A381050 Consider a deck of four cards arranged in the order 1,4,2,3. In round 1, card 1 is dealt, card 4 goes under, card 2 is dealt. Now the deck is ordered 3,4. In round 2, card 3 is dealt, card 4 goes under, then card 4 is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 1,4,2,3.
%e A381050 Table begins:
%e A381050   1;
%e A381050   1, 2;
%e A381050   1, 3, 2;
%e A381050   1, 4, 2, 3;
%e A381050   1, 4, 2, 3, 5;
%e A381050   1, 5, 2, 3, 6, 4;
%e A381050   1, 7, 2, 3, 6, 4, 5;
%e A381050   1, 6, 2, 3, 7, 4, 5, 8;
%t A381050 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"]];If[ds["Length"]>1,res["SetPart",i++,ds["Pop"]];]];res["SetPart",n,ds["Pop"]];Flatten[PositionIndex[res["Elements"]]/@Range[n]]];
%t A381050 Array[row, 13, 1] // Flatten (* _Shenghui Yang_, May 11 2025 *)
%o A381050 (Python)
%o A381050 def row(n):
%o A381050     i, J, out = 0, list(range(1, n+1)), []
%o A381050     while len(J) > 1:
%o A381050         i = i%len(J)
%o A381050         out.append(J.pop(i))
%o A381050         i = (i + 1)%len(J)
%o A381050         #i = i%len(J)
%o A381050         if len(J) > 1:
%o A381050             out.append(J.pop(i))
%o A381050     out += [J[0]]
%o A381050     return [out.index(j)+1 for j in list(range(1, n+1))]
%o A381050 print([e for n in range(1, 14) for e in row(n)]) # _Michael S. Branicky_, Apr 28 2025
%Y A381050 Cf. A006257, A032766, A225381, A321298, A378635, A381050, A381051, A383076, A378674.
%K A381050 nonn,tabl
%O A381050 1,3
%A A381050 _Tanya Khovanova_, _Nathan Sheffield_, and the MIT PRIMES STEP junior group, Apr 14 2025