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)

2
votes
3answers
132 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
64 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
45 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
12 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
27 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
57 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
123 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
20 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
40 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
49 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
22 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
131 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
35 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
84 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
46 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
76 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
41 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
36 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 ...
0
votes
1answer
58 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
75 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
27 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
20 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
30 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
57 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
57 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 ...
0
votes
1answer
19 views

Bound the Number of Acute-angled Triangles

I encounter the following problem with solution. But I do not quite understand the argument for 5, 10 points and eventually 100 points. Can someone elucidate the details? Problem In a plane there ...
1
vote
3answers
45 views

P white balls, Q black balls, N boxes

First of all sorry if this has been asked before, I could find "similiar" questions which seem to be harder but not quite this specific question. You are given P white balls and Q black balls, how ...
0
votes
1answer
19 views

How many functions defined on $n$ points are possible if each functional value is either $0$ or $1$?

How many functions defined on $n$ points are possible if each functional value is either $0$ or $1$? This is from the text A First Course on Probability by Sheldon Ross. The solution he ...
0
votes
0answers
20 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...