This tag is for basic 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. ...

learn more… | top users | synonyms (4)

1
vote
2answers
63 views

How find the what is the minimum number of operations required that the sums of any number of numbers in the list can never be $2014$

Question: Initially we have a list of numbers $1,2,3,\cdots,2013$.an operation is defined that taking two numbers $a, b$ out from the list, but add $a+b$ into it instead, what is the minimum ...
4
votes
1answer
61 views

How prove this can choose two postive integer numbers $a_{m},a_{k},$such $\frac{a_{m}+a_{k}}{3a_{p}}\notin N^{+},$

If $a_{1},a_{2},\cdots,a_{n}(a_{i}\neq a_{j}),n\ge 3$ are positive integers,show that: we can always choose two positive integers among them, $a_{m},a_{k},m,k\in\{1,2,\cdots,n\}$.such that ...
2
votes
1answer
56 views

Algebraic Combinatorics

Let $K_{r,s}$ denote the complete bipartite graph, defined on $r + s$ vertices $\{v_1,v_2,...,v_r,w_1,...,w_s\}$, with an edge between $v_i$ and $w_j$ for $1 ≤ i ≤ r$ and $1 ≤ j ≤ s$. By ...
1
vote
0answers
25 views

Coxeter length of a cycle in $S_n$

Is there a formula for the Coxeter length of a cycle in $S_n$? For example, if the cycle is $(ij)$ then the length is $2(j-i)-1$.
2
votes
3answers
128 views

Minimum number of combinations

I have a group of 10 players and I want to form two groups with them.Each group must have atleast one member.In how many ways can I do it?
0
votes
0answers
23 views

Is there an upper limit to the number of times a value can occur in a superset?

Given a set of numbers S=(-5,6,9,3,2,-2,), is there an upper limit to the number of times a particular value (say 4) can occur in the sums of all the combinations of these numbers? For example: in ...
4
votes
1answer
63 views

2D Rubik's cube?

There is a $3\times3$ matrix filled by numbers 1~9 that might look like this $$\begin{bmatrix}3 & 8 & 2 \\ 4 & 1 & 6 \\ 7 & 5 & 9\end{bmatrix}$$ All its rows and columns can ...
0
votes
1answer
26 views

Suppose we toss a coin 5 times and define Y as number of runs of heads. How do you find expectation and variance?

Range would be {0,1,2,3,4,5} Is there an easy way to find expectation rather than writing out all the possible outcomes?
0
votes
2answers
44 views

What subject in mathematics investigates the type of problems that constitute the LSAT “logic games” (example given)?

For my own curiosity, I read part of an LSAT study guide yesterday. The "logic games" section comprised questions like, An advertising executive must schedule the advertising during a particular ...
0
votes
2answers
46 views

How find this $\max{|A|}$ if $A=\{S_{i}|S_{i}\equiv 1\pmod 2\}$

let $(a_{1},a_{2},\cdots,a_{2014})$ be a permutation of $(1,2,3,\cdots,2014)$,and define $$S_{k}=a_{1}+a_{2}+\cdots+a_{k},k=1,2,3,\cdots,2014$$ Find the $\max{|A|}$, where ...
0
votes
0answers
11 views

# of counts of an element - Combinatorial Proof of Inclusion-Exclusion Principle (IEP) [Ross P31]

Let $A_{1},\ A_{2}$, , $A_{n}$ be $n$ sets. Then $|A_{1}\cup A_{2}\cup ... \cup A_{n}|= \sum_{i}|A_{i}|-\sum_{i<j}|A_{i}\cap A_{j}|+ +(-1)^{n-1}|A_{1}\cap A_{2}\cap\ \cap A_{n}|. $ Proof. ...
1
vote
0answers
26 views

Finite sum identity involving Stirling numbers

I was given the following identities (note: $s_{n,k},S_{n,k}$ are the Stirling numbers of first and second kind respectively): (1) $s_{n+1,k+1}=\sum_{i=k}^{n}\binom{i}{k}s_{n,i}$ (2) ...
1
vote
1answer
37 views

Counting triangles in triangular graphs

A triangular graph $T_n$ is the line graph of the complete graph $K_n$ (see for example here). Can you derive a formula for the number of triangles in the triangular graph $T_n$? If not, can you at ...
3
votes
1answer
56 views

number of spanning trees in this graph

This is a homework help, it ask us to find the number of spanning trees in this graph. I can use "matrix tree theorem" to solve it, but that means I need to compute the determinant of a $ 15\times ...
-4
votes
1answer
121 views

Approximating $\pi$ using expected values [closed]

We approximate $\pi$ by choosing random points in a square and seeing what fraction fall in the inscribed circle. If we choose $k$ random points, the expectation $E[X]$ of the number $X$ of points in ...
1
vote
0answers
19 views

Rearanging people so that no one is in the same spot

I am not sure how to approach this problem: "n people are seated in numbered chairs 1 to n. Let the number of ways the people can be reseated so that no one is in the same chair as before be N. Show ...
0
votes
2answers
38 views

Combinatorics-Generating function

5 pirates find 3000 gold coins. In how many ways they can distribute them, if the captain gets at least 500 and not more then 2000 coins. the rest get at least 150 but not more then 1000 coins.(each ...
0
votes
1answer
18 views

Number of ways of arranging 7 coloured blocks in patterns

The question goes: Given you have 7 differently coloured blocks (red, orange, yellow, green, blue, indigo, violet), how many different arrangements are there such that the blue and green are not ...
1
vote
1answer
20 views

Placing between n and n+2 different books into n different boxes

The homework question asks: There are n (for integers $n>1$) different boxes, each of which can hold up to $n+2$ books. Find the probability that: a) No box is empty when $n$ different ...
0
votes
1answer
28 views

Number of configurations in a constrained nested loops and configuration back from serial

Consider 4 counters looping the digits 0, 1, 2 to form the various "configurations", like in : ...
0
votes
0answers
19 views

closed form of a specific crazy summation?

How can I find the closed form of $f_2 + f_4 + ...+ f_{2m}$ where $\sum\limits_{m=1}^\infty f_{2m} = u_{2m-2}- u_{2m} $ where $u_{2m} = \binom{2m}{m} 2^{-(2m)}$ and $u_{2m-2} = \binom{2m-2}{m-1} ...
0
votes
1answer
47 views

Approximation of $\frac{1}{2^{N}} \binom{N}{\frac{1}{2}(N + s)} $ for big N

I have the following function that I have to approximate for big N and I really have no clue what to do - I hope that anyone can help me out: $$P_N(s) = \begin{cases} \frac{1}{2^{N}} ...
0
votes
0answers
21 views

Find Sum of series

Find Sum of series - $$ C^n_k + C^n_{k+t} + C^n_{k+2t} + C^n_{k+3t} + ... C^n_{k+qt} $$ Here $$ k+q\cdot t \le n $$ $$ q\ge 0 $$ $$ k \le n $$
4
votes
3answers
127 views

Help with this combinatorial proof $\sum\limits_{k=1}^nk^2(k-1){n\choose k}^2 = n^2(n-1){2n-3\choose n-2}$ considering $n\ge2$

$\displaystyle\sum\limits_{k=1}^nk^2(k-1){n\choose k}^2 = n^2(n-1) {2n-3\choose n-2}$ considering $n\ge2$ Can somebody help with this combinatorial proof? I'm struggling a lot. Thanks. EDIT: Ok. ...
1
vote
0answers
30 views

Simple problem in probability

You have 100 lightbulbs. Every lightbulb is either functioning or not. You test 20 of them, and all of the 20 are functioning. What is the probability that 10 of the 100 lightbulbs do not function? ...
1
vote
0answers
32 views

Special case coefficient sum in multinomial equation

I need to find the sum of coefficients of $x^{c}$ in the general equation $(1+x)^{a_1}(1+x^2)^{a_2}...(1+x^m)^{a_m}$, where $c$ is a multiple of $m+1$. For example in $(1+x)^2(1+x^2)$ the ...
3
votes
2answers
82 views

Deriving a (tricky, I think?) recurrence relation

I'm having trouble trying to derive a recurrence relation for a problem I'm looking at. "Let $h_n$ be the number of ways of packing a bag with $n$ fruits (either apples, oranges, bananas, or pears), ...
1
vote
0answers
42 views

Arranging Peoples In A Row

Why when we need to put 2 people together we calculate them as one unit and not two? They have 2 ways to sit one near the other, but why we reduce just 1 from the overall number of peoples?
0
votes
1answer
45 views

Summation of product of combinations

my question is, can the following series be solved $$ \sum_{i,j}^{} {a\choose i} {b \choose j} $$ where, (i+j) mod 3 =0 or i+j is multiple of 3 I need a generalized solution, i.e variables i,j,k... ...
0
votes
2answers
67 views

Grasshopper in a tropical forest

There is a Grasshopper in a tropical forest. The grasshopper can jump only vertically and horizontally, and the length of the jump is always equal to x centimeters. A Grassshopper has found herself at ...
0
votes
1answer
39 views

Differences Exponential and Ordinary Generating Functions

I am trying to understand conceptually the differences between ordinary generating functions (OGF$=1+x+x^2+\ldots$ ) and exponential generating functions (EGF$=1+x+\frac{x^2}{2!}+\ldots$ ) when it ...
4
votes
0answers
76 views

How to prove this indentity $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-…-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$ [duplicate]

I don't know how to prove this identity: $\binom{100}{0}^2-\binom{100}{1}^2+\binom{100}{2}^2-\binom{100}{3}^2+...-\binom{100}{99}^2+\binom{100}{100}^2=\binom{100}{50}$
1
vote
2answers
35 views

How many ways are there to pick 18 letters from 12 A's and 12 B's?

How many ways are there to pick 12 letters from 12 A's and 12 B's? How many ways are there to pick 18 letters from 12 A's and 12 B's?
2
votes
1answer
40 views

How do you handle this kind of probability?

What is the probability of selecting a singular matrix from $\Bbb{R}^{3\times 3}$? I calculated it to be zero based on their being approximately $9$ degrees of freedom to choose entries of $A$ such ...
1
vote
1answer
55 views

How find this number of permutation such $|a_{k}-k|\ge\dfrac{n-1}{2}$

let $n$ is give postive integer,Find the number of the $(a_{1},a_{2},\cdots,a_{n})$ be a permutation of $(1,2,3,\cdots,n)$.such $$|a_{k}-k|\ge\dfrac{n-1}{2}$$for any $k=1,2,\cdots,n$ This is ...
1
vote
1answer
39 views

How to prove a set must have a specific number of elements?

Trying to understand sets but having a hard time. Could someone help me through this one? Let A be a set of six positive integers each of which is less than 13. Show that there must be two distinct ...
2
votes
1answer
34 views

counting vector pairs with a given hamming distance

Let $\mathbb{F}_2$ denote the binary field. For integer $t\geq 0$, define $W_t = \{(x,y)\in \mathbb{F}_2^n\times \mathbb{F}_2^n: d_H(x,y)=t\}$, where $d_H(\cdot,\cdot)$ denotes the Hamming distance. ...
0
votes
2answers
23 views

Minimum of Maximum of Addition of two vectors/arrays

Suppose you have two arrays and you want to compute the maximum of the addition of the two arrays. Now you move the second array one field to the right. Now you can compute the maximum again of the ...
4
votes
1answer
74 views

Proving a combinatorial identity “directly”

This is a homework problem. In the first part of the problem, I managed to use a combinatorial problem to prove the following identity: $\Sigma_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} = 2n+1$ But ...
1
vote
1answer
28 views

Number [n,k]-linear codes with one fixed vector

I need to find the number of $[n,k]$-linear binary codes with one fixed codeword x (non zero) in it. So I guess, I need to count the number of $k$-dimensional ...
1
vote
2answers
26 views

$K$ events that are $(K-1)$-wise Independent but not Mutually/Fully Independent

I had the following question: Construct a probability space $(\Omega,P)$ and $k$ events, each with probability $\frac12$, that are $(k-1)$-wise, but not fully independent. Make the sample space as ...
0
votes
0answers
19 views

finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
0
votes
1answer
26 views

Inclusion Exclusion Principle Question

A merchant have 3 kinds of coins in his pocket: r of copper, s of aluminum and t of gold. He randomly take out 3 coins from his pocket. how much combinations there are in which he will pull 3 coins ...
1
vote
0answers
56 views

Number of paths in a grid

A common puzzle problem is to count the number of paths that start from the bottom-left-hand corner of a grid and end at the top-right hand corner, with the restriction that you can only move upwards ...
1
vote
1answer
26 views

Partitioning N people into N/2 sized groups across N - 1 days

Problem Statement: Given a list of $N$ people. On the 1st day, divide them into $N/2$ groups of two people each. On the 2nd day, divide them into groups of two again... Do this every day, until day ...
1
vote
0answers
14 views

Generalized permutahedron and random polytopes

The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
0
votes
1answer
54 views

Number of seating arrangements in 5 cars

An exercise from Introductory Combinatorics by Richard A.Brualdi: A roller coaster has five cars, each containing four seats, two in front and two in back. There are 20 people ready for a ride. ...
0
votes
1answer
14 views

number of elements in unsortet case

I have a group M with Mn different elements. How many unique combinations can I make out of this in an n digit system when order is no importance. For example if M = {1 2} & n = 3 ...
0
votes
2answers
45 views

Two sequences $a$ and $b$ for which $\Delta a_n = \Delta b _n$

Find two different sequences $a$ and $b$ for which $\Delta a_n = \Delta b_n$ for all of $n$. This is my first time doing recurrence relations, so if anyone could provide some thorough and clear ...
0
votes
0answers
25 views

Combinatorics of relations

Let A = {1,2,3}. Find the total number of relations on A that are both symmetric and transitive. I know that there are 64 symmetric relations, but how can I find out of those how many are transitive ...