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

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.

Links

Table of n, a(n) for n=1..99.

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.

Example

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.

Sequence in context: A330953 A360308 A325702 * A304746 A304748 A323903

Adjacent sequences: A378632 A378633 A378634 * A378636 A378637 A378638

Keyword

nonn,tabl

Author

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

Status

approved