cp's OEIS Frontend

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

%I A380195 #18 May 10 2025 11:27:52
%S A380195 1,1,2,2,3,1,4,2,1,3,2,4,1,5,3,6,4,1,3,5,2,6,3,1,7,5,2,4,3,5,1,7,4,2,
%T A380195 8,6,9,7,1,4,6,2,8,5,3,6,4,1,10,8,2,5,7,3,9,4,10,1,7,5,2,11,9,3,6,8,7,
%U A380195 9,1,5,11,2,8,6,3,12,10,4,11,5,1,8,10,2,6,12,3,9,7,4,13
%N A380195 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 under-under-down dealing is used, then the resulting cards will be dealt in increasing order.
%C A380195 Under-under-down dealing is a dealing pattern where the top card is placed at the bottom of the deck, then the next card is also placed at the bottom of the deck, and then the next card is dealt. This pattern repeats until all of the cards have been dealt.
%C A380195 This card dealing is related to a variation on the Josephus problem, where two people are 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 A381667 is an inverse permutation of the corresponding row of this triangle.
%C A380195 The total number of moves for row n is 3n.
%C A380195 The first column is A381591, the order of elimination of the first person in the Josephus problem.
%C A380195 The index of the largest number in row n is A054995(n), corresponding to the index of the freed person in the corresponding Josephus problem.
%C A380195 T(n,3j) = j, for 3j <= n.
%F A380195 T(n, 3 mod n) = 1
%F A380195 T(n, k) = T(n-1, k-3 mod n) + 1 if k != 3 mod n, where "a mod b" denotes the representative of the a's modular equivalence class in {0, ..., b-1}.
%e A380195 Consider a deck of four cards arranged in the order 4,2,1,3. Card 4 goes under, card 2 goes under, and card 1 is dealt. Now the deck is ordered 3,4,2. Card 3 goes under, card 4 goes under, and card 2 is dealt. Now the leftover deck is ordered 3,4. Card 3 goes under, card 4 goes under, and card 3 is dealt. Then card 4 is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 4,2,1,3.
%e A380195 Table begins:
%e A380195   1 ;
%e A380195   1, 2;
%e A380195   2, 3, 1;
%e A380195   4, 2, 1, 3;
%e A380195   2, 4, 1, 5, 3;
%e A380195   6, 4, 1, 3, 5, 2;
%e A380195   6, 3, 1, 7, 5, 2, 4;
%e A380195   3, 5, 1, 7, 4, 2, 8, 6;
%e A380195   9, 7, 1, 4, 6, 2, 8, 5, 3;
%o A380195 (Python)
%o A380195 def UUD(n):
%o A380195     return invPerm(UUDES(n))
%o A380195 def UUDES(n):
%o A380195     l=[]
%o A380195     for i in range(n):
%o A380195         l.append(i+1)
%o A380195     index = 0
%o A380195     P=[]
%o A380195     for i in range(n):
%o A380195         index+=2
%o A380195         index=index%len(l)
%o A380195         P.append(l[index])
%o A380195         l.pop(index)
%o A380195     return P
%o A380195 def invPerm(p):
%o A380195     inv = []
%o A380195     for i in range(len(p)):
%o A380195         inv.append(None)
%o A380195     for i in range(len(p)):
%o A380195         inv[p[i]-1]=i+1
%o A380195     return inv
%o A380195 sequence = []
%o A380195 for i in range(1,20):
%o A380195     sequence += [str(v) for v in UUD(i)]
%o A380195 print(", ".join(sequence))
%o A380195 (Python)
%o A380195 def row(n):
%o A380195     i, J, out = 0, list(range(1, n+1)), []
%o A380195     while len(J) > 0:
%o A380195         i = (i + 2)%len(J)
%o A380195         out.append(J.pop(i))
%o A380195     return [out.index(j)+1 for j in list(range(1, n+1))]
%o A380195 print([e for n in range(1, 14) for e in row(n)]) # _Michael S. Branicky_, Mar 27 2025
%Y A380195 Cf. A006257, A054995, A225381, A321298, A378635, A380195, A008585, A381591 A381667.
%K A380195 nonn,tabl
%O A380195 1,3
%A A380195 _Tanya Khovanova_ and the MIT PRIMES STEP junior group, Jan 15 2025