For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. Combinatorics is a ...

learn more… | top users | synonyms (4)

0
votes
1answer
57 views

probability equiprobable space?

For the problem below are we going to use the equiprobable space. Which is In particular, if S contains n points then the probability of each point is 1/n . For an event A, P(A) = number of elements ...
0
votes
3answers
62 views

choosing 5 numbers out of 20 - smallest is bigger than '5'

What is the probability to choose $5$ numbers between $ 1,2..,20$ so the smallest number of them is bigger than $5$? My answer: we have $5\frac{1}{20}$ for the 5 #. we have $\frac{20-5}{20}$ ...
3
votes
2answers
65 views

How many way can we obtain $0$?

You are walking in road and you have only two directions,forward and back.Your $n$th step has length $n$. How many way can you return your starting point after $n$ steps ? It is equivalent to say ...
0
votes
0answers
63 views

Estimation for sum over binomial coefficients

I am trying to show that a certain procedure for resource allocation is approximately efficient. For this I need to show that $$ \lim_{n\rightarrow \infty} \left(\frac{1}{e}\right)^n\sum_{c=2}^n ...
2
votes
1answer
48 views

How many increasing maps from $\mathbb N_n^*$ to $\mathbb N_p^*$ do exist?

Let $\mathbb N_n^*=\{1,2,3,,...,n\}$ be the set of integers greater than zero. How many increasing maps from $\mathbb N_n^*$ to $\mathbb N_p^*$ do exist ? It is not mentioned that $p\ge n$, So i ...
0
votes
2answers
43 views

How many combinations of ten options?

If we have ten different options and we can have combinations of none, one, two and so on up to all ten of the options, how many possible combinations could we have?
1
vote
0answers
58 views

Local Lemma on lower bounding R(k,k)

We aim to prove that if $k \ge 3$ and $e2^{1-\binom{k}{2}}\binom{n}{k-2} \le 1$ then $R(k,k) >n$ Now I understand that we colour the edges of $K_n$ red and black with probability 1/2. For each ...
1
vote
2answers
448 views

Number of ways to distribute indistinguishable balls into distinguishable boxes of given size

I need to find a formula for the total number of ways to distribute $N$ indistinguishable balls into $k$ distinguishable boxes of size $S\leq N$ (the cases with empty boxes are allowed). So I mean ...
-1
votes
2answers
242 views

Balls and bins problem - expected number of balls needed to throw [closed]

Suppose we have n boxes and we start randomly and independently throwing balls into the boxes. (a) For a given box, what is the expected number of balls we need to throw before one of the balls lands ...
0
votes
2answers
58 views

Placing black and white balls in a row, s.t. no pair of black balls is lying side by side

In how many ways can we dispose $m$ white and $n$ black balls such that there is no pair of black balls lying side by side ? If $n>m+1$ it is not possible, if not; I place the black balls, ...
0
votes
1answer
33 views

Calculate the number of secant lines and intersections

Given a circle $k$, and a finite number of points $n$ on the circle, where every 2 points are connected with a secant line such that no point in circle exists where 3 secant lines intersect. Calculate ...
1
vote
1answer
36 views

intersection of lines and planes ?

if 6 lines are drawn in a plane , what is the maximum number of parts in which plane is divided by them ? If there are 'k' lines drawn in the plane then plane is divided into how many maximum parts ? ...
0
votes
0answers
29 views

2nd Question in introductory probability

There are the same number of red and blue people at a party. And decided to meet up the next day. 1/5 of the red people and 1/3 of all the people were missing. Calculate the probability that a ...
0
votes
1answer
38 views

Beginner question in probability

i'm a beginner in statistics and probability and i need help with a given problem please. We are given a guy who has a machine and a button, the outcames when he presses the button are: a)Music ...
1
vote
1answer
80 views

How many ways are there to arrange 1's and 0's with no two 1's in a row? [duplicate]

Given n spaces, how many ways are there to fill up the spaces with 1's and 0's such that no two 1's are together. For example, let's say n = 3 (_ _ _). There are 5 ways to fill up the spaces such ...
0
votes
1answer
47 views

How many numbers with seven digits are possible with restrictions?

a) How many numbers with seven digits are possible if exactly one digit occurs exactly four times and all other digits are distinct? b) How many numbers with seven digits are possible if exactly two ...
1
vote
0answers
21 views

Probability of cross-free path

I don't know how to name such problem, but basically we have an infinite two dimensional grid with mouse (point, machine, whatever) that moves up, down, left or right. Every move has same probability ...
1
vote
0answers
63 views

Prove that the minimum of row sums of a nonnegative symmetric matrix is preserved

Let $A$ be an $n\times n$ adjacency (nonnegative, irreducible and symmetric) matrix with zeros on the diagonal. Denote $i$-th row sum of $A^k$ as $r^{(k)}_i$, where $k\geq1$. I want to prove that if ...
0
votes
7answers
172 views

$\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$

Show that $\,\displaystyle\sum_{i=1}^{n} \binom{i}{2}=\binom{n+1}{3}$. I'm thinking right now (though not getting anywhere with it) that I want to expand out the summation portion to ...
2
votes
3answers
54 views

Discrete Math Pascal's Triangle and n choose k

A juggling club has 5 male members and 4 female members. a) I know the answer to this: "How many nonempty sets of juggling club members can be chosen to perform in a show" is Answer: 2^9 - 1. ...
0
votes
1answer
33 views

Strictly increasing maps

For $p\ge n$, how many strictly increasing maps from $N^*_n$ to $N^*_p$ do exist, where $N^*_n = \{1, 2, \dots, n\}$ is the set of the first $n$ integers greater than 0 ? My answer: uncountable many. ...
0
votes
0answers
45 views

Moment generating function with binomial coefficients

I am trying to calculate a moment generating function, and I have obtained the following result: \begin{equation} ...
1
vote
0answers
90 views

An extension of a game with two dice

This question is an extension of a previous question already correctly answered: A game with two dice. In that question, we had two dice: the first one, when rolled, determined the number of times ...
1
vote
1answer
25 views

What are the number of circular arrangements possible?

Suppose we have $4$ identical red beads and $3$ identical blue beads. In how many ways can we form a necklace out of these? I am a little confused here. Suppose we fix a red bead and treat the ...
2
votes
1answer
61 views

Finding $\lim\limits_{n\rightarrow \infty}\sum\limits_{r=1}^{n}\frac{1}{T_r}$ given $\sum\limits_{r=1}^{n}T_r=\frac{n(n+1)(n+2)(n+3)}{8}$

If $\displaystyle\sum_{r=1}^{n}T_r=\frac{n(n+1)(n+2)(n+3)}{8}$, then how can we find $\displaystyle\lim_{n\rightarrow \infty}\sum_{r=1}^{n}\frac{1}{T_r}$?
0
votes
1answer
102 views

Combinatorics, find all 10 length arrays of positive integers whose sum is equal to 100

At the beginning, I was trying to solve (apparently) another problem but it led me to this one. ...
3
votes
3answers
144 views

solve the puzzle how many liars?

Each boy in a group of $20$ boys either always tells thuth or always tells a lie. These boys are sitting around a table. Each boy says that his neighbours are liars. Prove that at least $7$ out of ...
7
votes
2answers
170 views

Cousin of the Vandermonde binomial identity

The Vandermonde binomial identity can be expressed as \begin{align*} \sum_{i+j=r} \binom{m}{i} \binom{n}{j} = \binom{m+n}{r} && r \leq m +n. \end{align*} While working on an algebra problem, I ...
3
votes
2answers
469 views

Proof of $\sin^2(x) + \cos^2(x)=1$ using series

I have to prove the following identity $\sin^2 (x) + \cos^2(x)=1$. I can easily prove this, but this exercise is given in the section introducing the series expansions for $\sin(x)$ and $\cos(x)$ and ...
1
vote
1answer
31 views

Probability of subgroup

We have a class of 100 students and we want to form 4 subgroups of 40,30,20 and 10 students each one. What's the number of different ways to form these subgroups: So given that we have a ...
0
votes
2answers
180 views

Programmatically getting list of combinations

EDIT: This question is in a grey area between between SO and here. The source code isn't quite necessary, but I would at lease have a clue as to figure it out. Also, I've clarified and simplified my ...
0
votes
1answer
29 views

Combinations of marbles

Let's say I have 10 marbles, with a known distribution. Just as an example, I have the following, but I'm trying to find a general solution. Red- 5 Blue- 2 Green- 3 I draw 5 without replacement ...
2
votes
2answers
36 views

A question regarding recurrences

I have often come across the fact that if we have a recurrence relation of the form $$f(n)=a_1f(n-1)+a_2f(n-2)+\dots+a_kf(n-k)$$ then $f(n)=b_1r_1^n+b_2r_2^n+\dots+b_kr_k^n$, where $r_1,r_2,\dots,r_k$ ...
5
votes
2answers
112 views

Counting number of bijections satisfying given inequality

Given two sets $$A=\{a_{1},a_{2},\cdots,a_{m}\},B=\{b_{1},b_{2},\cdots,b_{m}\}$$ where $$a_{i}<b_{i}<a_{i+1}<b_{i+1},i=1,2,\cdots,m-1$$ and the function $$g(a,b)=\begin{cases} 1&a>b\\ ...
2
votes
2answers
57 views

Prove:that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014

Show that in any set of 1009 positive integers exits two numbers $a_i$ and $a_j$ such that $a_i-a_j$ or $a_i+a_j$ is divisible by 2014 without remainder ($i\not=j$). I think the "pigeonholes" here ...
3
votes
3answers
472 views

Prove: Number of Derangement is odd if and only if number of items is even .

let $D_n$ be a number of Derangement of n items . prove that $D_n$ is odd if and only if n is even . i was trying to use induction on the $!n=(n-1)(!(n-1)+!(n-2))$ recurrence relation but i cant ...
0
votes
2answers
43 views

Permutations and Combinations with conditions

Please I'm having difficulties solving this question: In how many ways A, B, C, D, E, F, G, H can be arranged such that A, B, and C always come before F, G and H?
1
vote
3answers
86 views

How can I find the coefficient of a term in this generating function by using the “old” method?

I'm trying to verify my answer to this problem by going back and solving the same problem using methods I've used before learning about generating functions, but I'm not quite sure how to do it in ...
2
votes
2answers
168 views

Winning a restricted game of Nim?

Given the following piles, find the Grundy number of the initial position and make the first move in a winning strategy given that no more than two sticks may be removed from a pile at any time. Pile ...
5
votes
1answer
55 views

Generating Functions Interpretation - Expanding around other points?

Generating functions are incredibly useful for solving all kinds of combinatorial problems. Whenever they are used, though, the generating function is always expanded around $x=0$ to obtain the ...
1
vote
1answer
76 views

ambidextrous mathematician. combinations problem

Please help me solve this problem. At first it seemed to be easy, but I got stuck. An ambidextrous mathematician with a very short attention span keeps two video game credit cards, one in each of ...
0
votes
2answers
44 views

Sharing the same card

Suppose I choose 5 numbers from 1 to 12 randomly, and my friend does so as well. What is the probability that we share $n$ numbers? I know that the denominator will be $12 \choose 5$$12 \choose 5$ but ...
0
votes
1answer
37 views

Combinatorial analysis problem

Case 1 Have $90 + x\text{ elements,}\quad x < 15$ How many combinations of $60$ elements are possible? (order doesn't count) Case 2 $$50 + x\text{ elements,}\quad x < 15$$ How many ...
6
votes
2answers
633 views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
2
votes
2answers
76 views

Finding the Generating Function for $\sum_{n_1 +n_2 + \ldots + n_k = n} n_1 n_2 \cdot \ldots \cdot n_k$

I'm studying problem 2.6 (p. 65) in Herbert Wilf's generatingfunctionology (released by the author for free online). This problem actually has a solution already written in the back of the book (p. ...
2
votes
1answer
85 views

Question on Proof that the Fibonacci Word is Sturmian

I am currently reading a text where it is proved that the infinite Fibonacci Word $u$ defined as the limit of the sequence $$ u_n = \varphi^n(0) $$ where the morphism is given by $\varphi(0) = 01, ...
1
vote
1answer
73 views

Determining Grundy Numbers for an inverted takeaway game

Given the following game, I need to determine a winning strategy and find the set of positions in the kernel. I figure the best way to do so would be with Grundy numbers. Rules: The game consists ...
1
vote
0answers
63 views

Prove that there exists a subset with sum >=1 such that the remaining integer sum reduces by 1

let $ n \in \mathbb{N} $ and $ \frac{1}{w_1},\ldots, \frac{1}{w_n} $ for some (not necessarily distinct) $ w_1,\ldots,w_n \in \mathbb{N} $ and $ w_1,\ldots,w_n \ge 2 $ be given. Assume that $ ...
1
vote
1answer
196 views

combinatorics questions from studying

Hi all I need some assistance How many 5-digit briefcase combinations contain 1.Two pairs of distinct digits and 1 other distinct digit. (e.g 12215) I wasn't sure on which approach was correct. 10 ...
0
votes
1answer
24 views

Number of positive $n$ s.t. $5|n^4 + 5n^2 + 9$

Find the total number of positive integers $n$ not more than $2013$ such that $n^4 + 5n^2 + 9$ is divisible by $5$. This problem was taken from Singapore Math Olympiad 2013, Open Section, First round. ...