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.

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

Offset: 1

Author

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

Keywords

• nonn
• tabl

Comments

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.

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.

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

The first column is A225381, the order of elimination of the first person in the Josephus problem.

The index of the largest number in row n is A006257(n), corresponding to the index of the freed person in the Josephus problem.

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

Examples

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

Crossrefs

Cf. A005843, A006257, A225381, A321298.

Formula

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.