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.

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, 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, 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

Offset: 1

Author

Tanya Khovanova and the MIT PRIMES STEP junior group, Dec 03 2024

Keywords

• nonn
• tabl

Comments

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.

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.

The total number of moves for row n is 2n-1.

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.

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.

T(n,2j-1) = j, for 2j-1 <= n.

Sequence A378635 represents a similar triangle for under-down dealing.

Examples

			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.
Triangle begins:
  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, 4, 8;
  1, 9, 2, 6, 3, 8, 4, 7, 5;
		

Crossrefs

Cf. A006257, A152423, A225381, A321298, A378635, A378682, A381050.

Programs

Mathematica

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 *)

Formula

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.

From Pontus von Brömssen, Dec 11 2024: (Start)

T(n,k) = A378635(n-1,k-1) + 1 for 2 <= k <= n.

T(n,k) = A378635(n,(k mod n) + 1).

(End)