A378674 -id:A378674 - 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.

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, 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, 9, 2, 3, 12, 4, 5, 10, 6, 7, 11, 8, 1, 12, 2, 3, 10, 4, 5, 11, 6, 7, 13, 8, 9

Offset: 1

Tanya Khovanova, Nathan Sheffield, and the MIT PRIMES STEP junior group, Apr 14 2025

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.
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.
The total number of moves for row n is A032766(n) = floor(3n/2).
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.

			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.
Table begins:
  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, 5, 8;

Cf. A006257, A032766, A225381, A321298, A378635, A381050, A381051, A383076, A378674.

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]]];
Array[row, 13, 1] // Flatten (* Shenghui Yang, May 11 2025 *)

def row(n):
    i, J, out = 0, list(range(1, n+1)), []
    while len(J) > 1:
        i = i%len(J)
        out.append(J.pop(i))
        i = (i + 1)%len(J)
        #i = i%len(J)
        if len(J) > 1:
            out.append(J.pop(i))
    out += [J[0]]
    return [out.index(j)+1 for j in list(range(1, n+1))]
print([e for n in range(1, 14) for e in row(n)]) # Michael S. Branicky, Apr 28 2025

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

A378682 Triangle T(n,k) read by rows: where T(n,k) is the number of the k-th eliminated person in the variation of the Josephus elimination process for n people, where the first person is eliminated, and after that, every second person is eliminated.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 1, 3, 2, 4, 1, 3, 5, 4, 2, 1, 3, 5, 2, 6, 4, 1, 3, 5, 7, 4, 2, 6, 1, 3, 5, 7, 2, 6, 4, 8, 1, 3, 5, 7, 9, 4, 8, 6, 2, 1, 3, 5, 7, 9, 2, 6, 10, 8, 4, 1, 3, 5, 7, 9, 11, 4, 8, 2, 10, 6, 1, 3, 5, 7, 9, 11, 2, 6, 10, 4, 12, 8, 1, 3, 5, 7, 9, 11, 13, 4, 8, 12, 6, 2, 10, 1, 3, 5, 7, 9, 11, 13, 2, 6, 10, 14, 8, 4, 12

Offset: 1

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

The n-th row has n elements.

In this variation of the Josephus elimination process, the numbers 1 through n are arranged in a circle. A pointer starts at position 1. With each turn, the number at the pointer is eliminated, and the pointer skips the next number. This repeats until no numbers remain. This sequence represents the triangle J(n, k), where n is the number of people in the circle, and J(n, k) is the elimination order of the k-th number in the circle.

			Consider 5 people in a circle. During the first round around the circle, people numbered 1, 3, and 5 are eliminated in this order. The next person, numbered 2, is skipped, and 4 is eliminated. Person 2 is eliminated last. Thus, the fifth row of the triangle is 1, 3, 5, 4, 2.
Triangle begins;
  1;
  1, 2;
  1, 3, 2;
  1, 3, 2, 4;
  1, 3, 5, 4, 2;
  1, 3, 5, 2, 6, 4;
  1, 3, 5, 7, 4, 2, 6;
  1, 3, 5, 7, 2, 6, 4, 8;
  1, 3, 5, 7, 9, 4, 8, 6, 2;

Cf. A006257, A225381, A321298, A378635, A378674.

T(n,1) = 1 and T(n,k) = A321298(n-1,k-1) + 1, for n,k > 1.

T(n,k) = (A321298(n,k)-2 mod n) + 1. - Pontus von Brömssen, Dec 11 2024

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula