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

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.

Links

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

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)

Example

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.

Sequence in context: A082074 A132283 A378682 * A307081 A256440 A088370

Adjacent sequences: A378670 A378672 A378673 * A378676 A378677 A378678

Keyword

nonn,tabl,new

Author

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

Status

approved