A381127 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-SpellUnder dealing is used, then the resulting cards will be dealt in increasing order.

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

Offset: 1

Author

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

Keywords

• nonn
• word
• tabl

Comments

In Down-SpellUnder dealing, we deal the first card, then spell the positive integers starting from O-N-E, moving a card from the top of the deck underneath the deck for each letter in the English spelling of the number, followed by dealing or "putting down" the top card. So we start by dealing the first card, then putting 3 cards under because O-N-E has three letters, then we deal the next card. Then we put 3 cards under because T-W-O has three letters, then we deal a card. Then we put 5 cards under for T-H-R-E-E, and so on. This dealing sequence is highly irregular because it depends on English spelling. The dealing pattern starts: DUUUDUUUDUUUUUD, where each "U" corresponds to putting a card “under” and each "D" corresponds to dealing a card “down”.

This card dealing can be thought of as a generalized version of the Josephus problem. In this version of the Josephus problem, we start by executing the first person, then spell the positive integers in increasing order, each time skipping past 1 person for each letter and executing the next person. The card in row n and column k is x if and only if in the corresponding Josephus problem with n people, the person numbered x is the k-th person eliminated.

Equivalently, each row of the corresponding Josephus triangle A381114 is an inverse permutation of the corresponding row of this triangle. The first column contains only ones, since person number 1 always dies first in the corresponding Josephus problem. The index of the largest number in row n is A381129(n), corresponding to the index of the freed person in the corresponding Josephus problem. The number of card moves that we need to take if we start with n cards is A381128(n).

Examples

			Triangle begins:
 1;
 1, 2;
 1, 3, 2;
 1, 2, 4, 3;
 1, 3, 5, 4, 2;
 1, 6, 4, 3, 2, 5;
 1, 5, 3, 6, 2, 4, 7;
 1, 3, 4, 5, 2, 7, 6, 8;
  ...
For n = 4, suppose there are four cards arranged in the order 1,2,4,3. Card 1 is dealt, and then three cards go under the deck because O-N-E has three letters. Now, the deck is ordered 2,4,3. Card 2 is dealt, and three cards go under because T-W-O has three letters. Now, the leftover deck is ordered 3,4. Card 3 is dealt, and five cards go under because T-H-R-E-E has five letters. Then card 4 is dealt. The dealt cards are in numerical order. Thus, the fourth row of the triangle is 1, 2, 4, 3.
		

Crossrefs

Cf. A005589, A006257, A225381, A321298, A378635, A380201, A380202, A380204, A380246, A380247, A380248, A381114, A381128, A381129.

Programs

Python

from num2words import num2words as n2w
def f(n): return sum(1 for c in n2w(n).replace(" and", "") if c.isalpha())
def row(n):
    c, i, J, out = 1, 0, list(range(1, n+1)), []
    while len(J) > 1:
        q = J.pop(i)
        out.append(q)
        i = (i + f(c))%len(J)
        c = c+1
    out.append(J[0])
    return [out.index(j)+1 for j in list(range(1, n+1))]
print([e for n in range(1, 15) for e in row(n)]) # Michael S. Branicky, Feb 16 2025