Fdtxjr

Antler Helmet: Can it work?

Strange behaviour of Check

Problem when applying foreach loop

Does a C shift expression have unsigned type? Why would Splint warn about a right-shift?

What is the electric potential inside a point charge?

How are presidential pardons supposed to be used?

When is phishing education going too far?

How do you clear the ApexPages.getMessages() collection in a test?

Is above average number of years spent on PhD considered a red flag in future academia or industry positions?

Array/tabular for long multiplication

Can the prologue be the backstory of your main character?

What would be Julian Assange's expected punishment, on the current English criminal law?

Fishing simulator

What LEGO pieces have "real-world" functionality?

Why is "Captain Marvel" translated as male in Portugal?

New Order #5: where Fibonacci and Beatty meet at Wythoff

Estimated State payment too big --> money back; + 2018 Tax Reform

Blender game recording at the wrong time

How do I automatically answer y in bash script?

Determine whether f is a function, an injection, a surjection

Can a zero nonce be safely used with AES-GCM if the key is random and never used again?

Writing Thesis: Copying from published papers

Is there folklore associating late breastfeeding with low intelligence and/or gullibility?

Passing functions in C++

Number of ways in which we can select non-intersecting couples from $n$ elements

0

$begingroup$

While i was doing an Olympiad problem, i managed to reduce it to this one with a bijection, but now i don't know what to do:

Suppose we have $n$ objects ordered in a line. In how many ways I can select a subset of non-intersecting couples composed by consecutive elements?

For example in the sequence $12345$ the answer is $7$:

$12\ 23 \ 34 \ 45 \ 12,34 \ 12,45 \ 23,45 $

There is also a generalization that may be helpful:

Suppose we have $n$ objects ordered in a line. In how many ways I can select a subset $A$ (with $|A|leq k$ where k is a given integer) of non-intersecting $j$-ples composed by consecutive elements?

I would be happy even if you help me just with the first one. Thank you :)

combinatorics

share|cite|improve this question

edited Mar 25 at 19:11

Eureka

asked Mar 25 at 19:01

EurekaEureka

876114

$endgroup$

add a comment | 

0

$begingroup$

While i was doing an Olympiad problem, i managed to reduce it to this one with a bijection, but now i don't know what to do:

Suppose we have $n$ objects ordered in a line. In how many ways I can select a subset of non-intersecting couples composed by consecutive elements?

For example in the sequence $12345$ the answer is $7$:

$12\ 23 \ 34 \ 45 \ 12,34 \ 12,45 \ 23,45 $

There is also a generalization that may be helpful:

Suppose we have $n$ objects ordered in a line. In how many ways I can select a subset $A$ (with $|A|leq k$ where k is a given integer) of non-intersecting $j$-ples composed by consecutive elements?

I would be happy even if you help me just with the first one. Thank you :)

combinatorics

share|cite|improve this question

edited Mar 25 at 19:11

Eureka

asked Mar 25 at 19:01

EurekaEureka

876114

$endgroup$

add a comment | 

$begingroup$

While i was doing an Olympiad problem, i managed to reduce it to this one with a bijection, but now i don't know what to do:

Suppose we have $n$ objects ordered in a line. In how many ways I can select a subset of non-intersecting couples composed by consecutive elements?

For example in the sequence $12345$ the answer is $7$:

$12\ 23 \ 34 \ 45 \ 12,34 \ 12,45 \ 23,45 $

There is also a generalization that may be helpful:

Suppose we have $n$ objects ordered in a line. In how many ways I can select a subset $A$ (with $|A|leq k$ where k is a given integer) of non-intersecting $j$-ples composed by consecutive elements?

I would be happy even if you help me just with the first one. Thank you :)

combinatorics

share|cite|improve this question

edited Mar 25 at 19:11

Eureka

asked Mar 25 at 19:01

EurekaEureka

876114

$endgroup$

share|cite|improve this question

edited Mar 25 at 19:11

Eureka

asked Mar 25 at 19:01

EurekaEureka

876114

share|cite|improve this question

edited Mar 25 at 19:11

Eureka

asked Mar 25 at 19:01

EurekaEureka

876114

asked Mar 25 at 19:01

EurekaEureka

876114

asked Mar 25 at 19:01

EurekaEureka

876114

1 Answer
1

active

oldest

votes

2

$begingroup$

Do you allow the empty subset? If so, the answer is $F_n+1$, the $(n+1)^st$ Fibonacci number. If not, then subtract one from this.

You can prove this by induction. If $a_n$ is the number of ways to select the couples (allowing the empty selection), then $a_n=a_n-1+ a_n-2$, which follows by considering whether or not the rightmost object, $n$, is in one of the chosen couples.

share|cite|improve this answer

answered Mar 25 at 20:39

Mike EarnestMike Earnest

27.9k22152

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Stunning work :)
  $endgroup$
  – Eureka
  Mar 25 at 20:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The comment about the empty subset is the subtle bit here. :) $F_5 = 7$ is not a Fibonacci number, after all. And if one tries to write the recursion using $b_n$ which doesn't include the empty subset, one gets $b_n = b_n-1 + (b_n-2 colorred+ 1)$ which is of course a shifted Fibonacci but may be less obvious.
  $endgroup$
  – antkam
  Mar 26 at 14:20
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3162192%2fnumber-of-ways-in-which-we-can-select-non-intersecting-couples-from-n-elements%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

Do you allow the empty subset? If so, the answer is $F_n+1$, the $(n+1)^st$ Fibonacci number. If not, then subtract one from this.

You can prove this by induction. If $a_n$ is the number of ways to select the couples (allowing the empty selection), then $a_n=a_n-1+ a_n-2$, which follows by considering whether or not the rightmost object, $n$, is in one of the chosen couples.

share|cite|improve this answer

answered Mar 25 at 20:39

Mike EarnestMike Earnest

27.9k22152

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Stunning work :)
  $endgroup$
  – Eureka
  Mar 25 at 20:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The comment about the empty subset is the subtle bit here. :) $F_5 = 7$ is not a Fibonacci number, after all. And if one tries to write the recursion using $b_n$ which doesn't include the empty subset, one gets $b_n = b_n-1 + (b_n-2 colorred+ 1)$ which is of course a shifted Fibonacci but may be less obvious.
  $endgroup$
  – antkam
  Mar 26 at 14:20
  

  
  
  
  

add a comment | 

2

$begingroup$

Do you allow the empty subset? If so, the answer is $F_n+1$, the $(n+1)^st$ Fibonacci number. If not, then subtract one from this.

You can prove this by induction. If $a_n$ is the number of ways to select the couples (allowing the empty selection), then $a_n=a_n-1+ a_n-2$, which follows by considering whether or not the rightmost object, $n$, is in one of the chosen couples.

share|cite|improve this answer

answered Mar 25 at 20:39

Mike EarnestMike Earnest

27.9k22152

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Stunning work :)
  $endgroup$
  – Eureka
  Mar 25 at 20:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The comment about the empty subset is the subtle bit here. :) $F_5 = 7$ is not a Fibonacci number, after all. And if one tries to write the recursion using $b_n$ which doesn't include the empty subset, one gets $b_n = b_n-1 + (b_n-2 colorred+ 1)$ which is of course a shifted Fibonacci but may be less obvious.
  $endgroup$
  – antkam
  Mar 26 at 14:20
  

  
  
  
  

add a comment | 

$begingroup$

Do you allow the empty subset? If so, the answer is $F_n+1$, the $(n+1)^st$ Fibonacci number. If not, then subtract one from this.

You can prove this by induction. If $a_n$ is the number of ways to select the couples (allowing the empty selection), then $a_n=a_n-1+ a_n-2$, which follows by considering whether or not the rightmost object, $n$, is in one of the chosen couples.

share|cite|improve this answer

answered Mar 25 at 20:39

Mike EarnestMike Earnest

27.9k22152

$endgroup$

share|cite|improve this answer

answered Mar 25 at 20:39

Mike EarnestMike Earnest

27.9k22152

answered Mar 25 at 20:39

Mike EarnestMike Earnest

27.9k22152

answered Mar 25 at 20:39

Mike EarnestMike Earnest

27.9k22152