# Tagged Questions

Permutations, combinations, bijective proofs, generating functions

2answers
57 views

### Binomial probability with summation

Show that $$\sum_{k=0}^{m} \frac{m!(n-k)!}{n!(m-k)!} = \frac{n+1}{n-m+1}$$ Attempt: It becomes: $$\sum_{k=0}^{m } \frac{\binom{m}{k}}{\binom{n}{k}}$$ Telescoping, pairing, binomial theorem don't ...
2answers
45 views

### $a_{k+1}-a_k = a_2 - a_1$,$\sum \limits_{k=1}^{n}{a_k}$=?

I need to find an explicit formula for the sum $\sum \limits_{k=1}^{n}{a_k}$ where $(a_k)_{k∈ℕ}∈ℚ^ℕ$ with $a_{k+1}-a_k = a_2 - a_1$ for all k∈ℕ I would love to start with by collecting the values of ...
1answer
140 views

### No of labeled trees with n nodes such that certain pairs of labels are not adjacent.

Moderator Note: This is a current contest question on codechef.com. What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for \$i ...
2answers
59 views

### Permutations of a queue of interlaced boys and girls.

Suppose $5$ boys and $4$ girls are to be arranged in a queue such that between any two boys there is at least one girl. Find the number of such arrangements possible. What i think is $5$ boys ...
4answers
145 views

### Find a ternary $4\times 39$ matrix satisfying the conditions below

Can you find a matrix $A_{4\times39}$ with elements from $\{-1,0,1\}$ so that No column is all zero. All columns are different. No column is $-1$ times another column. Each row consists of $13$ of ...
1answer
42 views

### total number of different mixes

Patient Age Avg Visits / Year <1 year 7.5 1-4 years 3.0 5-14 years 1.8 15-24 years 1.7 25-44 years 2.6 45-64 years ...
0answers
140 views

### Possible Playable Chords on a Guitar

Fingerstyle Guitar Chord Diversity Check Considering a $20$-fret $6$-string acoustic guitar and supposing that the fretting range (inclusive of the fingered notes) for an average hand is $4$ frets in ...
1answer
33 views

### how often does a value appear in a combination

Say I have a set of numbers 1,2,3,4,5,6,7,8,9,10 and I say 10 C 4 I know that equals 210. But lets say I want to know how often 3 appears in those combinations how do I determine that?
2answers
154 views

### Choosing a linear map $(\mathbb{Z}/2\mathbb{Z})^n \rightarrow \mathbb{Z}/2\mathbb{Z}$ which is nonzero on half of a sequence of vectors

Let $v_1,\ldots,v_m \in (\mathbb{Z}/2\mathbb{Z})^n$ be nonzero vectors. Is it always possible to choose a linear map $f : (\mathbb{Z}/2\mathbb{Z})^n \rightarrow \mathbb{Z}/2\mathbb{Z}$ such that $f$ ...
0answers
211 views
+500

### Conjecture regarding trapping rational numbers in some special intervals

Conjecture: Let $b\in\mathbb{N}_{\geq3}$ and $\{x_i\}$ be a collection of $b−2$ rational numbers greater than $1$. Does there always exist a natural number $a$ such that for all $i$ there exists some ...
6answers
60 views

### How to prove a limit with a recurrence?

$s_1 = 1$ and $s_{n+1} = \dfrac{s_n + 1}{3}$ for $n \in \Bbb N$. How do you find $\displaystyle \lim_{x\to \infty} s_n$? Then how do you prove that the value is the limit using the definition of the ...
1answer
52 views

### Counting 0-1 matrices up to symmetry

I'm interested in counting the number of n×n 0-1 matrices with a given number of 1s up to rotation and reflection. What is the best way to do this if n is not too small? For example, consider ...
1answer
35 views

### Proof of bipartite graphs with $k$ edges

Let $b_k(n)$ be the number of bipartite graphs (without multiple edges) with $k$ edges on the vertex set $[n]$. Show that: \sum_{n\geq 0}\sum_{k\geq 0}b_k(n)q^k\frac{x^n}{n!}=\sqrt{\sum_{n\geq ...
3answers
121 views

### Evaluate a sum with binomial coefficients

$$\text{Find} \ \ \sum_{k=0}^{n} (-1)^k k \binom{n}{k}^2$$ I expanded the binomial coefficients within the sum and got $$\binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \dots + \binom{n}{n}^2$$ ...
1answer
71 views

### 65-card deck consisting of 13 ranks and 5 suits

** I FIGURED OUT 15 out of 16 cases. I don't understand the last case of RUNT. Anyone helps? I recently went to a math event and one person presented a weird card deck, consisting of 13 ranks and 5 ...
0answers
25 views

### Probability question using PIE

Five people check identical suitcases before boarding an airplane. At the baggage claim, each person takes one of the five suitcases at random. What is the probability that every person ends up with ...
6answers
48 views

### calculate the number of possible number of words

If one word can be at most 63 characters long. It can be combination of : letters from a to z numbers from 0 to 9 hyphen - but only if not in the first or the last character of the word I'm trying ...
2answers
33 views

### Combinatorics/Probability - Multiple Groups Example Problem

Joe, an avid and properly licensed sportsman, is in his hunting blind when he locates 20 Canada geese, 25 Mallard ducks, 40 Bald Eagles, 10 Whopping Cranes, and 5 Flamingos. Joe randomly selects ...
2answers
119 views

### Derivative of Schur function

In his answer to http://mathoverflow.net/questions/129854, R. Stanley says that the partial derivative (over the relevant x[i]) of the Schur function of a partition lambda of n equals the sum the ...
1answer
17 views

### Prove that $h_r(x_1,\dots,x_n)=\sum^n_{k=1}x^{n-1+r}_k\prod_{i\neq k}(x_k-x_i)^{-1}$

How do I show that $$h_r(x_1,\dots,x_n)=\sum^n_{k=1}x^{n-1+r}_k\prod_{i\neq k}(x_k-x_i)^{-1}$$ Can anyone just give me like a hint or "headstart"? Thanks!
1answer
41 views

### Growth rate of formula

I have formula: $\frac{(m+n)!}{m!n!}$ I am wondering what is growth rate of it. Can I say that it grows exponentially with m and n? Or maybe this is different growth rate? Greetings, Rnd
0answers
25 views

### Sets of numbers satisfying a simple additive property

There are four sets of size $N$ in the integers, say $A_1,A_2,A_3,A_4$. And for at least $\epsilon N^3$ of the tuples $(a_1,a_2,a_3,a_4) \in A_1 \times A_2 \times A_3 \times A_4$ it is true that \$a_1 ...
3answers
65 views

### Factorial Equality Problem

I'm stuck on this problem, any help would be appreciated. Find all $n \in \mathbb{Z}$ which satisfy the following equation: $${12 \choose n} = \binom{12}{n-2}$$ I have tried to put each of them ...
1answer
44 views

### binary circle - difficult question

I ran into this question and I'm not really sure how to start. we are looking at 100 0/1's that are written arround a circle. for a binary sequence $w$, we'll define $n_{w}$ as the number of times ...
1answer
66 views

### Probability to complete a sequence with two attempts

Imagine a slot machine with $N$ reels. I want to calculate the probability $P$ that a player hits a certain sequence $A$, if the player has given the possibility to spin again (and only once again), ...
0answers
57 views

### Ball and holder problem [duplicate]

I am trying to solve this but having a tough time deriving the formula. There are $X$ ball and $Y$ holders $Y \leq X$. Out of the $X$ balls, $N$ are red and $X-N$ are blue. What is the probability ...
1answer
50 views

### Ferrers Diagram Partitions

Using Ferrer's diagram, prove that the number of partitions of n in which each part is 1 or 2 is equal to the number of partitions of n+3 which has exactly two distinct parts. Any help please, all I ...
2answers
52 views

### Solution gives wrong answer to probability problem

Great Northern Airlines flies small planes in northern Canada and Alaska. Their largest plane can seat 16 passengers seated in 8 rows of 2. On a certain flight flown on this plane, they have 12 ...
1answer
28 views

### Combinatorial Techniques: Putting two and two together

This is a $3$-part question. I got the first two parts, but could not get the third part (which uses the first two parts): Pick sequence of $8$ coins from sack of $40$ coins, containing $10$ pennies, ...
0answers
106 views

### (3n,n)-Turán graph [closed]

I'm working on a problem regarding (kn,n)-Turán graphs. The (2n,n)-Turán graph, also known as the cocktail party graph, has a closed formula for its number of spanning trees. I want to know if there ...
2answers
179 views

### A card game with no decisions

A friend showed me a mindless card game he plays, in which the initial state of the deck completely determines whether he wins or loses. The game is played as follows: Shuffle a standard $52$ card ...
2answers
38 views

### Probability/Combinatorics Problem - Old Maid Cards

A special deck of Old Maid cards consist of 25 pairs and a single old maid card. All 51 cards evenly between you and two other players – 17 cards for each player. (a) how many different ...
0answers
42 views

### Calculating a probability

Given $m\cdot e$ balls, $b$ of which are black (suppose the rest are white balls). Randomly put the balls into $m$ baskets, with $e$ balls in each basket. What is the probability of the event that ...
2answers
53 views

### A probability question: a building and an elevator.

Suppose that 7 people waiting for an elevator in a building with 14 flours. Q: What is the probability that every person get out in different flour? My attempt: There is \$14 \cdot 13 \cdot 12 \cdot ...
0answers
66 views

### A combinatorial problem.

Let be $(X, \mathbb{A}, \mu)$ a measure space, a partition of $X$ is a disjoint family $\xi=\{P_1,\ldots,P_k \}$ of measurable sets such tath $\bigcup P_i=X\pmod0).$ If \$\xi=\{P_1,\ldots,P_k ...
1answer
58 views

### Distributing objects in boxes

In how many way can we distribute: 7 objects in 3 boxes; provided that: 1) objects are distinct, boxes are distinct and boxes may be empty; 2) objects are distinct, boxes are distinct and boxes may ...
3answers
107 views

### How can one show $100!=100 \cdot 99!$ by combinatorial arguments

How does one show $100!=100\cdot 99!$ by using combinatorial arguments?
0answers
32 views

### Different Perspectives of Multinomial Theorem & Partitions

There are 2 important interpretations of the multinomial theorem and coefficients. 1: Determining the number of ordered strings that can be formed using a set of letters. For example, with 1 m, 4 ...
1answer
53 views

### What is the probability that, given the smallest of 50 random integers(>0), it will be the smallest of 50 other random integers (one being itself)?

More generally, if an array of random integers (size N), and another array of random integers (size M), "overlap" by R numbers (have them in common): What is the chance that the smallest of one is the ...
2answers
37 views

### Probability of selecting correct answer in 15 out of 25 exercises with 0.25 chance

There are 25 exercises, each one consists of answers: a, b, c, d and only one answer is correct. My question is what is the probability of selecting correct answer in 15 out of 25 exercises. My idea: ...
2answers
39 views

### How many different 2-regular graphs are there with 5 vertices?

How many different 2-regular (simple) graphs are there with 5 vertices? I just asked a very similar question, and I actually already understand the answer of this question. I think there are ...
0answers
34 views

### Is there a two name Wikipedia pangram? [closed]

Benjamin Franklin Goodrich and François-Xavier Wurth-Paquet are people in Wikipedia with the letters A-O and N-X. Is there a pair of names in Wikipedia that has all the letters A-Z? I use ...
0answers
35 views

### which kind of data related to permutation group and SSYT [closed]

if do not have these books, then just focus on which data related to permutation group and SSYT page 309 in enumerative combinatorics book volume 2 (old edition) prepare to apply this chapter, which ...
1answer
22 views

### Partitioning of subsets

This is a previous exam question. Let $S$ be a subset of $\{10,11,...,99\}$ containing 10 elements. Show that there will exist two disjoint subsets $A$ and $B$ of $S$ such that sum of the elements of ...
0answers
225 views

### Counting number of spanning trees in $(3n,n)$-turan graph [closed]

Moderator Note: This is a current contest question on codechef.com. I'm working on a problem regarding $(kn,n)$-Turán graphs. The $(2n,n)$-Turán graph, also known as the cocktail party graph, has ...
3answers
50 views

### About ascending numbers

I have that a positive integer d is said to be ascending if in its decimal representation: $$d=d_md_{m-1}\cdots d_2d_1$$ we have $$0<d_m\leq d_{m-1}\leq \cdots \leq d_2\leq d_1.$$ How can I find ...
1answer
187 views

### What can we say about the size of $HK\cap KH$ when $HK\neq KH$?

If $G$ is a finite group, and $H$, $K$ are proper subgroups of $G$, then it is not necessary that $HK=KH$. But, these two subsets have same size. The question I would like to ask, then, is If ...
2answers
85 views

### How does this “combinatorial proof” work?

For any non-integer $n$, $$(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k$$ Let $y_1,\dots,y_n$ be variables and, for any subset $S$ of $\{1,\dots,n\}$, let $y^S$ denote the product of the $y_i$'s for each ...
1answer
67 views

### Conditional probability Bayes Theorem

I am trying to solve this problem but I am not sure how to obtain the formula given below. Any help would be appreciated. A boy is selected at random from among the children belonging to families ...
1answer
30 views

### $\frac{1}{4^n}\binom{1/2}{n} \stackrel{?}{=} \frac{1}{1+2n}\binom{n+1/2}{2n}$ - An identity for fractional binomial coefficients

In trying to write an answer to this question: calculate the roots of $z = 1 + z^{1/2}$ using Lagrange expansion I have come across the identity  \frac{1}{4^n}\binom{1/2}{n} = ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 95, "mathjax_display_tex": 9, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9200353026390076, "perplexity_flag": "middle"}