degree of f=2^k

The post below has been deleted. Click to close.

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

Sayan

2130 posts

Sayan

#1 h May 13, 2012, 11:54 PM • 2 Y

Y by mathbuzz, Adventure10

Let $S = \{1,2,3,\ldots,n\}$ . Consider a function $f\colon S\to S$ . A subset $D$ of $S$ is said to be invariant if for all $x\in D$ we have $f(x)\in D$ . The empty set and $S$ are also considered as invariant subsets. By $\deg (f)$ we define the number of invariant subsets $D$ of $S$ for the function $f$ .

i) Show that there exists a function $f\colon S\to S$ such that $\deg (f)=2$ .

ii) Show that for every $1\leq k\leq n$ there exists a function $f\colon S\to S$ such that $\deg (f)=2^{k}$ .

This post has been edited 3 times. Last edited by Sayan, May 16, 2012, 7:18 AM

Z K Y

The post below has been deleted. Click to close.

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

iarnab_kundu

866 posts

iarnab_kundu

#2 h May 14, 2012, 5:24 AM • 3 Y

Y by mathbuzz, Adventure10, and 1 other user

pls post it in combinatorics; I wrote it fully but someone erased everything

writing again :

lets take f to be a permutation. consider a permutation where

(n-t+2,...,n) are fixed points. and consider the biggest of the remaining elements; assign the biggest i.e (n-t+1) to f(1) ; and the smallest to f(2), second smallest to f(3)(if it is possible ) and so on

this works (easy to prove)

for example the required permutation of (1,2,..,5) with degree 2^3 is (3,1,2,4,5)

Z K Y

The post below has been deleted. Click to close.

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

mavropnevma

15142 posts

mavropnevma

#3 h May 14, 2012, 9:48 AM • 6 Y

Y by Abhinandan18, opptoinfinity, math_and_me, Adventure10, Mango247, PRMOisTheHardestExam

As a first observation, one must allow $\emptyset$ to be (vacuously) considered as an invariant subset, for any $f$ (otherwise point ii) would fail for $k=n$ ).

Now, the idea from above can be written more simply, with the permutation $f_k = (1)(2)\cdots(k-1)(k,k+1,\ldots,n)$ , written as a product of cycles, having $\deg(f) = 2^{k}$ for all $1\leq k \leq n$ .

Z K Y

The post below has been deleted. Click to close.

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

iarnab_kundu

866 posts

iarnab_kundu

#4 h May 14, 2012, 11:15 AM • 2 Y

Y by Adventure10, Mango247

In the actual paper it was mentioned that the empty set and the set {1,...,n} are ''invariant'' subset. So I request Sayan to edit it.

Z K Y

The post below has been deleted. Click to close.

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

mathbuzz

803 posts

mathbuzz

#5 h May 15, 2012, 4:57 AM • 4 Y

Y by ISI4, agirlhasnoname, Adventure10, Mango247

well, for part (1) , we may take a cycle permutation.i.e. take f(1)=2 , f(2)=3 ,...,f(n-1)=n,f(n)=1.this clearly satisfies deg.(f)=2

Z K Y

The post below has been deleted. Click to close.

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

Irfan

389 posts

Irfan

#6 h Apr 20, 2016, 1:33 AM • 2 Y

Y by Adventure10, Mango247

Can we simply not use f(1)=1 f(2)=4.... argument for (1) ?

Z K Y

The post below has been deleted. Click to close.

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

JackXD

151 posts

JackXD

#7 h May 9, 2017, 12:59 PM • 2 Y

Y by Adventure10, Mango247

ignore this post

This post has been edited 1 time. Last edited by JackXD, May 9, 2017, 1:00 PM
Reason: faulty post in another forum

Z K Y

The post below has been deleted. Click to close.

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

stranger_02

337 posts

stranger_02

#9 h Jun 18, 2020, 3:24 PM • 2 Y

Y by Madhavi, PRMOisTheHardestExam

Sayan wrote:

Let $S = \{1,2,3,\ldots,n\}$ . Consider a function $f\colon S\to S$ . A subset $D$ of $S$ is said to be invariant if for all $x\in D$ we have $f(x)\in D$ . The empty set and $S$ are also considered as invariant subsets. By $\deg (f)$ we define the number of invariant subsets $D$ of $S$ for the function $f$ .

i) Show that there exists a function $f\colon S\to S$ such that $\deg (f)=2$ .

ii) Show that for every $1\leq k\leq n$ there exists a function $f\colon S\to S$ such that $\deg (f)=2^{k}$ .

For the second part, we can simply consider a function defined piecewise as
$f(x)=x$ when $x\leq{k}$
$f(x)=1$ $($ or any number in this range $)$ , otherwise

Therefore, we see that $f(x)$ has exactly $2^k$ subsets..

Q.E.D $\square$

This post has been edited 1 time. Last edited by stranger_02, Jun 18, 2020, 3:25 PM
Reason: Latex

Z K Y

The post below has been deleted. Click to close.

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

Titttu

7 posts

Titttu

#10 h Jun 27, 2020, 2:28 PM

Y by

I can give a hint sumation of binomial coffecient wii helpful.. breka as required in 2,3,4,...n parts the total set and for every break u get the required 2^k

Z K Y

The post below has been deleted. Click to close.

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

Titttu

7 posts

Titttu

#11 h Jun 27, 2020, 3:11 PM

Y by

I can give a hint sumation of binomial coffecient wii helpful.. breka as required in 2,3,4,...n parts the total set and for every break u get the required 2^k
I gave one example which help you .
Let, k=3 then break S in 3 parts.
The break is going to happen like this=
f(x)=x+1 and f(b) =a ( where a is the first element of the partion and b is the last element of the partion . and for rest of the elemnets of the element it will tak care by the f(x) =x+1 )
Now if we choose one partition we can do it by 3c1 ways , we can choose 2 partition by 3c2 ways and 3 partition(which is total set for this case) 3c3 ways . And we can choose no partition in 3co ways ( which is empty set) .
The sum of all the cases is 2^3 .And you can do it 4 partition(u get 2^4) and so on ..upto n partition (after some partition u have to consider 1 element as partition & always shuffle the partition like that inside the partition there is no kind of subset which can satisfy our requirements .

Sorry guys I can't use the latex format .

Z K Y

The post below has been deleted. Click to close.

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

ftheftics

651 posts

ftheftics

#12 h May 20, 2021, 1:01 PM • 1 Y

Y by Gerninza

It will enough to show a construction of a function to prove the existence.

For a fixed positive integer $k \in [1,n]$ consider the function

$f(x) = \begin{cases} x + 1 & \text{for} , 1\le x\le n-k-1 \\ 1 & \text{for} , x\ge n-k \end{cases}$
Now consider $A =\{ 1 ,2,\cdots , n-k \}$ and $B =\{n-k+1,\cdots ,n\}$

Now Any subset $D$ of $S$ with $D= A \cup R$ (Where $R$ is subset of $B$ ) is invariant Under $f$ .

Since there is $2^k$ subsets of $B$ thus , There can have $2^k$ subset $D$ of $S$ for which $D$ is invariant under $f$ .

By definition $\deg (f) =2^k$

Now for part (i) just take $k=1$

This post has been edited 1 time. Last edited by ftheftics, May 20, 2021, 1:07 PM

Z K Y

The post below has been deleted. Click to close.

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

allofme

2 posts

allofme

#13 h May 26, 2021, 10:50 AM

Y by

@ftheftics the subsets you have considered as AUR where R is subset of B, all of them essentially consist A and some additional elements. So we get 2^k subsets all containing at least A. But apart from this there is phi which does not include anything making the deg(f)=2^k+1. Kindly enlighten me on this aspect.

Z K Y

The post below has been deleted. Click to close.

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

idkwhatthisis

44 posts

idkwhatthisis

#14 h May 27, 2021, 8:23 AM

Y by

I believe induction should work, for $\deg(f) = 2$ just take a cycle, and to get to a permutation with $\deg(f) = 2^m$ from $n$ to $n+1$ just take $f(n+1) = n+1$ and a permutation $g$ of $\{1,\ldots,n\}$ such that $\deg(g) = 2^{m-1}$ and we should be done.

EDIT: I just realised that by fixing $k-1$ points and applying the same construction in (i) to the remaining numbers then everything is cool

This post has been edited 2 times. Last edited by idkwhatthisis, May 28, 2021, 11:51 AM

Z K Y

The post below has been deleted. Click to close.

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

green_leaf

225 posts

green_leaf

#15 h May 27, 2021, 3:06 PM

Y by

For each function $f$ , consider a directed graph where vertices are numbers in $S$ and there is an edge $A \to B$ iff $f(A) = B$ .
i) This is equivalent to showing there is a function such that there are no directed cycles of length $k < n$ . This can simply be achieved by taking $f(i) = i+1 ~~~ \forall 1 \leq i \leq n-1$ and $f(n) = 1$ .

ii) Choose a function that splits $S$ into $k$ disjoint directed cycles. The number of invariant subsets are equivalent to the subsets of the set whose elements are the $k$ cycles, since the sets of cycles can be combined to form new sets which are still valid invariant sets. But the number of subsets of an set with $k$ elements is simply $2^k$ (including the empty set).

This post has been edited 1 time. Last edited by green_leaf, May 27, 2021, 3:07 PM

Z K Y

The post below has been deleted. Click to close.

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

quasar_lord

157 posts

quasar_lord

#17 h Mar 8, 2025, 1:27 PM

Y by

soln

Z K Y

The post below has been deleted. Click to close.

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

Gejabsk

7 posts

Gejabsk

#18 h Tuesday at 5:57 PM

Y by

If we're mapping one subset of k elements to itself and dearranging the rest, but S in invariant too , so total would be 2^k + 1
for deg(f) = 2^k , the invariants excluding S must be 2^k -1 , which doesn't seem possible ...

This post has been edited 1 time. Last edited by Gejabsk, Tuesday at 6:00 PM
Reason: .

Z K Y