Number of permutative

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Number of permutative

G H J

Reveal topic tags

combinatorics unsolved

L

G H BBookmark kLocked kLocked NReply

Source: When solving a problem

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

186 posts

#1 h Dec 14, 2005, 6:22 PM • 2 Y

Y by Adventure10, Mango247

Find out the number of permutations of $n$ first positive integer such that they contain no block $(i,i + 1)$ or $(i + 1,i)$ for all $i$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

629 posts

maxal

#2 h Jan 29, 2006, 10:38 AM • 1 Y

Y by Adventure10

By inclusion-exclusion it is
$n! + \sum_{k=1}^n (-1)^k \sum_{t=1}^k {k-1\choose t-1}{n-k\choose t} 2^t (n-k)!$
See also sequence A002464 for recurrent formula and other references.

This post has been edited 1 time. Last edited by maxal, Aug 9, 2013, 1:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

485 posts

#3 h Jan 30, 2006, 3:25 AM • 2 Y

Y by Adventure10, Mango247

maxal wrote:

By inclusion-exclusion it is
$n! + \sum_{k=1}^n (-1)^k \sum_{t=1}^k {k-1\choose t-1}{n-k\choose t} 2^t (n-k)!$
.

Could you explain me how you got it???

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

629 posts

maxal

#4 h Jan 30, 2006, 4:27 AM • 2 Y

Y by Adventure10, Mango247

k stands for the number of pairs (i,i+1) that are adjacent in the permutation, such pairs form chains (e.g., if i,i+1 are adjacent and i+1,i+2 are adjacent then i,i+1,i+2 is a chain in the permutation), and t stands for the number of such chains. Summands are the number of permutations with k adjacent pairs forming t chains. In particular,
${k-1\choose t-1}$ is the number of distributions of k adacent pairs among t chains such that each chain contains at least one pair;
${n-k\choose t}$ is the number of ways to select t chains of total length k+t out of elements $1,2,\dots,n$ ;
$2^t$ is the number of ways to orient the chains in the permutation (e.g., a chain i,i+1,i+2 can appear in the permutation as i,i+1,i+2 or as i+2,i+1,i);
$(n-k)!$ is the number of permutations of n-k-t elements not included into the chains and t chains (chains here can be viewed as single elements, hence, it's simply the number of permutations of n-k-t+t=n-k elements).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

485 posts

#5 h Jan 30, 2006, 11:07 AM • 2 Y

Y by Adventure10, Mango247

As I understand now: $(^{k-1}_{t-1})$ is number of oisitive intergral roots of the Diophant equation: $x_1+x_2+...+x_t=k$ .
Is it right??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

59 posts

#6 h Jan 30, 2006, 12:02 PM • 2 Y

Y by Adventure10, Mango247

it's the way to divide k pairs into t chain.I use alsi this way to solve this pro:
http://www.mathlinks.ro/Forum/viewtopic.php?t=4110

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

629 posts

maxal

#7 h Jan 30, 2006, 12:10 PM • 2 Y

Y by Adventure10, Mango247

keira_khtn wrote:

As I understand now: $(^{k-1}_{t-1})$ is number of oisitive intergral roots of the Diophant equation: $x_1+x_2+...+x_t=k$ .
Is it right??

That's correct.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2785 posts

#8 h Jun 7, 2020, 7:25 PM • 3 Y

Y by fidgetboss_4000, RadiantCheddar, IAmTheHazard

bruh $\text{[math]}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

416 posts

#9 h Jun 7, 2020, 8:43 PM • 2 Y

Y by fidgetboss_4000, IAmTheHazard

wish id seen this like 2 days ago

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a